Bottleneck discovery in large-scale networks based on the expected value of per-hop delay

To relieve congestion in a large-scale network, it is crucial to identify the links, which contribute most to the congestion and then take action to relieve it. This paper presents an algorithm for detecting bottlenecks in a congested large-scale packet-switched network. The strongest bottleneck candidate for a congested session is not necessarily the session link with highest percent utilization or the link with the lowest capacity, but rather the session link with the highest expected value of delay - provided that this link´s expected value of delay is significantly greater than the average delay for all links in the session. The approach is based on estimating the per-link expected value of delay (transmission plus queuing) and turning this expected value to a per-link weight. Based on this per-link weight and information collected from an end-to-end QoS monitoring mechanism, the algorithm points to the bottleneck hop where congestion likely occurred. To alleviate congestion, the following actions may be taken: redirect traffic, increase the bottleneck link bandwidth (if possible), implement aggressive traffic shaping, and/ or throttle low priority calls/sessions using the congested link.