Networking Research Laboratory
Director: Simon S. Lam (more publications)
Shared Congestion Detection
The recent proliferation of overlay systems poses a new challenge in detecting shared congestion between two Internet flows. An overlay system typically consists of a large number of end hosts and unicast flows between them. Two such unicast flows may have different sources and destinations, but they still may interfere with each by sharing one or more intermediate links. If the system can tell which flows are sharing a bottleneck link, it can improve overall system performance by changing the overlay topology to avoid such interference.
Prior techniques for inferring shared congestion are adequate for the case where two flows have a common source or a common destination. We discovered a novel technique, named Delay Correlation with Wavelet denoising (DCW), to detect shared congestion between any two Internet paths. Like previous techniques, it is based on the observation that two flows sharing a congested link have high correlation between their one-way delays. However, straightforward correlation measurements may be inaccurate due to a synchronization offset between packet arrivals of different flows at the congested link, as well as random fluctuation in queueing delay and mild congestion on non-shared links. We found that applying a Wavelet denoising method to delay samples of each flow drastically improves the accuracy of shared congestion detection. In particular, we showed that our technique, DCW, tolerates a synchronization offset between flows of up to one second. Given that Internet round-trip delays are generally smaller than a few hundred milliseconds, DCW can be used to detect shared congestion between any two Internet paths with the use of just a simple technique that achieves loose time synchronization between flows in the paths.