Description
Date depot: 1 janvier 1900
Titre: Route Tracing under Load Balancing
Directeur de thèse:
Serge FDIDA (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
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.
Doctorant.e: Augustin Brice