Abstract — Internet paths sharing the same bottleneck can be identified using several shared congestion detection techniques. However, all of these techniques have been designed to detect shared congestion between a pair of paths. To cluster N paths by shared congestion, a straightforward approach of using pairwise tests would require O(N 2) time complexity. In this paper, we present a scalable approach to cluster Internet paths based on DCW (Delay Correlation with Wavelet denoising) which does not require a common end point between paths. We present a function to map each path’s measurement data into a point in a multidimensional space such that points are close to each other if and only if the corresponding paths share congestion. Because points in the space are indexed using a tree-like structure, the computational complexity of clustering N paths can be reduced to O(N log N). The indexing overhead can be further improved by reducing dimensionality of the space through wavelet transform. Computation cost is kept low by reusing for dimensionality reduction the same wavelet coefficients obtained in DCW. Our approach is evaluated by simulations and found to be effective for a large N. The tradeoff between dimensionality and clustering accuracy is shown empirically. I.

The overlay network approach is an emerging technique to satisfy the strict requirements for various real-time multimedia services. However, overlay networks suffer from a shared congestion problem since each unicast flow may interfere with each other in the common underlying links. Most previous techniques to detect shared congestion have limitations when applied as a general solution, since they assume perfect synchronization between probing packets. However, our recent work shows that a technique based on wavelet denoising can overcome the limitations by mitigating the interfering effects such as synchronization offset and the random fluctuations of queueing delay; the proposed technique provides a more robust and accurate detection in the presence of a large amount of synchronization offset In this paper, wavelet denoising is tailored to the characteristics of queueing delay on packet networks. The wavelet denoising based technique is verified through extensive simulations. The efficacy of the proposed approach is demonstrated by the detection accuracy and convergence speed.

Per-flow congestion control helps endpoints fairly and efficiently share network resources. Better utilization of network resources can be achieved, however, if congestion management algorithms can determine when two different flows share a congested link. Such knowledge can be used to implement cooperative congestion control or improve the overlay topology of a P2P system. Previous techniques to detect shared congestion either assume a common source or destination node, drop-tail queueing, or a single point of congestion. We propose in this paper a novel technique, applicable to any pair of paths on the Internet, without such limitations. Our technique employs a signal processing method, wavelet denoising, to separate queueing delay caused by network congestion from various other delay variations. Our wavelet-based technique is evaluated through both simulations and Internet experiments. We show that, when detecting shared congestion of paths with a common endpoint, our technique provides faster convergence and higher accuracy while using fewer packets than previous techniques, and that it also accurately determines when there is no shared congestion. Furthermore, we show that our technique is robust and accurate for paths without a common endpoint or synchronized clocks; more specifically, it can tolerate a synchronization offset of up to one second between two packet flows.