Supervision : Serge FDIDA

Co-supervision : FRIEDMAN Timur / TEIXEIRA Renata

Tracing Internet Routes under Load Balancing

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.

2006-2011 Publications

• 2011
  • B. Augustin, T. Friedman, R. Teixeira : “Measuring multipath routing in the Internet”, IEEE/ACM Transactions on Networking, vol. 19 (3), pp. 830-840, (IEEE/ACM) (2011)
• 2010
  • B. Augustin : “Traçage de Routes Internet en présence de Répartition de Charge”, thesis, phd defence 10/18/2010, supervision Fdida, Serge, co-supervision : Friedman, Timur / TEIXEIRA Renata (2010)
• 2009
  • D. Veitch, B. Augustin, R. Teixeira, T. Friedman : “Failure Control in Multipath Route Tracing”, IEEE Infocom, Rio de Janeiro, Brazil, pp. 1395-1403, (IEEE) (2009)
• 2008
  • F. Viger, B. Augustin, X. Cuvellier, C. Magnien, M. Latapy, T. Friedman, R. Teixeira : “Detection, understanding, and prevention of traceroute measurement artifacts”, Computer Networks, vol. 52 (5), pp. 998-1018, (Elsevier) (2008)
  • F. Layouni, B. Augustin, T. Friedman, R. Teixeira : “Origine des étoiles dans traceroute”, Colloque Francophone sur l'Ingénierie des Protocoles (CFIP 2008), Les Arcs, France (2008)
• 2007
  • B. Augustin, T. Friedman, R. Teixeira : “Measuring load-balanced paths in the internet”, IMC 2007 - 7^th ACM Internet Measurement Conference, San Diego, CA, United States, pp. 149-160, (ACM) (2007)
  • B. Augustin, T. Friedman, R. Teixeira : “Multipath tracing with Paris traceroute”, E2EMON 2007 - 5^th IEEE/IFIP Workshop on End-to-End Monitoring Techniques and Services, Munich, Germany, pp. 1-8, (IEEE) (2007)
• 2006
  • B. Augustin, X. Cuvellier, B. Orgogozo, F. Viger, T. Friedman, M. Latapy, C. Magnien, R. Teixeira : “Avoiding traceroute anomalies with Paris traceroute”, IMC 2006 - 6^th ACM Internet Measurement Conference, Rio de Janeiro, Brazil, pp. 153-158, (ACM) (2006)