Locating Congested Segments on the Internet by Clustering the Delay Performance of Multiple Paths

A practical method of locating congested segments on the Internet by periodic end-to-end packet delay measurements along multiple paths is presented. This method is a network tomographic approach based on a clustering technique that effectively tackles the correlation among delay variations. Since the Internet is still highly prone to performance deterioration due to transient delays, locating the segments responsible is vital to ensure that Internet service providers can mitigate or prevent such performance deterioration. Our concern is how to detect and locate such segments promptly in a large network. The proposed method was implemented and evaluated through a real-world experiment by actively measuring packet delays from multiple origins to multiple destinations over the Japanese commercial Internet, and was shown to have considerable potential to precisely locate congested segments.