Direction de recherche : Serge FDIDA

Co-encadrement : FRIEDMAN Timur / TEIXEIRA Renata

Traçage de Routes Internet en présence de Répartition de Charge

Traceroute est l'outil le plus couramment utilisé pour découvrir le chemin entre deux machines sur internet. Il permet aussi bien de diagnostiquer des pannes réseau que d'assembler des cartes d'internet. Il opère en partant du principe qu'il n'existe qu'un seul et unique chemin entre deux machines distantes, à tout moment. Cependant, la plupart des routeurs actuels présentent des possibilités de répartition de charge. Si les opérateurs réseau activent cette fonctionnalité, alors un flot de paquets transitant d'une source vers une destination peut suivre différents chemins choisis par le routeur répartissant la charge. En présence de répartition de charge, traceroute présente deux graves défaillances. D'une part, il mesure des chemins inexacts, en inférant de nombreux faux liens et autres artefacts de mesure. D'autre part il est incapable de détecter tous les chemins possibles. Pour les utilisateurs de traceroute, les conséquences sont graves. Les opérateurs réseau diagnostiquent des pannes sur de mauvais chemins, tandis que les chercheurs assemblent et travaillent sur des cartes comportant des erreurs. Cette thèse présente une nouvelle implémentation de traceroute, nommée Paris traceroute, qui résout les problèmes rencontrés par le traceroute classique en présence de répartition de charge. En maintenant constant l'identifiant de flot des sondes qu'il émet (un identifiant de flot est défini par le 5-tuple: adresses et ports source et destination, et protocole), il mesure des chemins exacts, et donc il évite la majorité des artefacts de mesure causés par les répartiteurs de charge. De plus, son algorithme de traçage adaptatif découvre des multichemins complets en présence de répartition de charge, alors que le traceroute classique émet trop peu de sondes pour avoir une indication raisonnable de la présence de répartition de charge. Nous utilisons Paris traceroute pour caractériser l'ampleur du déploiement de la répartition de charge dans l'internet actuel. Nos campagnes de mesures effectuées depuis des centaines de machines sources, vers plusieurs milliers de destinations, révèlent que 50% des paires source-destination traversent un répartiteur de charge par flot. Un grand nombre de réseaux de coeur tirent partie des capacités de répartition des routeurs. En conséquence, les multichemins que nous observons s'étendent généralement sur quelques sauts au sein d'un système autonome donné, et consistent en des liens parallèles entre deux routeurs. De plus, ces chemins parallèles présentent généralement des propriétés similaires, par exemple, des délais pratiquement identiques. Ces résultats contrastent de façon significative avec le modèle traditionnel d'un chemin internet, et devraient inciter les chercheurs à prendre en compte l'existence de la répartition de charge dans leurs travaux futurs.

Publications 2006-2011

• 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”, thèse, soutenance 18/10/2010, direction de recherche Fdida, Serge, co-encadrement : 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)