How can we locate congested links in the Internet from end-to-end measurements using active probing mechanisms? As IP multicast is not widely deployed, we want to use only IP unicast probes and avoid relying on tight temporal synchronization between beaconing nodes, which is difficult to achieve between distant sites. Like other problems in network tomography or traffic matrix estimation, this inverse problem is ill-conditioned: the end-of-end measurement outcomes do not allow to uniquely identify the variables representing the status of the IP links. To overcome this critical difficulty, current methods rely on sparsity based heuristics, making the assumption that all IP links have the same prior probability of being congested, and hence looking for the minimal solution of the inverse problem. We find that this assumption is actually not needed: spatial correlations are sufficient to either learn these probabilities, or to identify the variances of the link loss rates. We can then use the learned probabilities or variances as priors to find rapidly the congested links at any time, with an order of magnitude gain in accuracy over existing algorithms. These solutions scale well and are therefore applicable in today's Internet, as shown by the results obtained both by simulation and real implementation using the PlanetLab network over the Internet.
Copyright. All Rights Reserved.