Traceroute is the most popular tool to discover the path between two machines in the internet. Uses range from the diagnosis of network problems to the assemblage of internet maps. It works under the assumption that just one single path exists between a pair of end-hosts, at any given time. However, most commercial routers have load balancing capabilities. If network administrators turn this feature on, then a stream of packets from a source to a destination can follow different paths. Under load balancing, traceroute suffers from two deficiencies. First, it measures inaccurate paths, inferring a number of false links and measurement artifacts. Second, it is unable to detect all the available paths. For traceroute users, the consequences are serious. Network operators diagnose wrong paths, while researchers assemble and work on buggy internet maps.
This thesis presents a new traceroute implementation, called Paris traceroute, which solves classic traceroute's problems under load balancing. By maintaining a constant flow identifier (defined as the 5-tuple: source and destination addresses and ports, and protocol), it measures accurate paths, therefore avoiding a majority of measurement artifacts caused by load balancing. In addition, its adaptive probing algorithm reports complete paths under load balancing, while classic traceroute sends too few probes to have even a moderate indication of the presence of load balancing.
We use Paris traceroute to characterize the extent of the deployment of load balancing in today's internet. Our measurement study from hundreds of source machines to thousands of destinations reveals that 50% of the source-destination pairs traverse a per-flow load balancer. A large number of core networks take advantage of load balancing capabilities. As a result, the multipath routes that we observe generally span a few hops in a single network, and consist in parallel physical links between pairs of routers. Furthermore, those parallel paths generally offer similar properties (e.g. almost identical delays). These findings dramatically contrast with the traditional model of an internet path, and should prompt researchers to take load balancing into account in their future work.
Defence : 10/18/2010 - 11h - Site Jussieu 25-26/105 Jury members : Jean-Jacques PANSIOT, Professeur, Université de Strasbourg (Rapporteur)
Olivier BONAVENTURE, Professeur, Université catholique de Louvain (Rapporteur)
Matthieu LATAPY, Chercheur CNRS, UPMC Sorbonne Universités
Martin MAY, Chercheur, Thomson Labs
Abdelhamid MELLOUK, Professeur, Université Paris-Est Créteil
Serge FDIDA, Professeur, UPMC Sorbonne Universités
Timur FRIEDMAN, Maître de Conférences, UPMC Sorbonne Universités
Renata TEIXEIRA, Chercheuse CNRS, UPMC Sorbonne Universités
B. Augustin, T. Friedman, R. Teixeira : “Multipath Tracing with Paris traceroute”, E2EMON 2007 - 5th IEEE/IFIP Workshop on End-to-End Monitoring Techniques and Services, Munich, Germany, pp. 1-8, (IEEE) (2007)
J. Augé, B. Augustin, M.‑O. Buob, X. Cuvellier, T. Friedman, M. Latapy, C. Magnien, B. Orgogozo, I. Ribeiro, R. Teixeira, D. Veitch, F. Viger : “Logiciel Paris Traceroute”, (2007)
B. Augustin, X. Cuvellier, B. Orgogozo, F. Viger, T. Friedman, M. Latapy, C. Magnien, R. Teixeira : “Avoiding traceroute anomalies with Paris traceroute”, IMC 2006 - 6th ACM Internet Measurement Conference, Rio de Janeiro, Brazil, pp. 153-158, (ACM) (2006)