Locating congested segments over the Internet by clustering the delay performance of multiple paths

Delay variation-based detection and location of congestion in a large network is considered. Since the Internet is still highly prone to performance deterioration due to transient large delays, locating a part of the network (segments) responsible is vital to ensure that Internet Service Providers can mitigate or prevent such performance deterioration. In the proposed method, the end-to-end packet delays from multiple origins to multiple destinations are actively and continuously measured. By analyzing those data on delay variation along each monitored path, congestion is detected by finding a delay performance deterioration worse than a predefined criteria and a congested segment responsible could be inferred by finding a set of paths among which delay variations are strongly correlated. This is a network tomographic approach based on a clustering technique that effectively tackles the correlation among packet delay variation along individual paths. The proposed method was evaluated through a real-world long-term experiment on the Japan’s commercial Internet, and was shown to have considerable potential to promptly locate congested segments through various analyses on the experimental results.