DONNET Benoit

ongoing PhD project
Team : NPA
https://inl.info.ucl.ac.be/donnet.html

Supervision : Serge FDIDA

Co-supervision : FRIEDMAN Timur, BAYNAT Bruno

Algorithmes pour la Découverte de Topologie à Grande Echelle

Ces dernières années ont vu un intérêt croissant dans la découverte, à grande échelle, de la topologie d'internet au niveau des interfaces IP. Une nouvelle génération de systèmes de mesure fortement distribués est actuellement en train d'être déployée. Malheureusement, avant cette thèse, la communauté de la recherche ne s'est pas attardée sur la question de savoir comment effectuer ces mesures de manière efficace. Dans cette thèse, nous proposons plusieurs contributions pour permettre aux mesures de passer à l'échelle. D'abord, nous montrons que les méthodes classiques de découverte de topologie (i.e., skitter) sont inefficaces car elles sondent de manière répétée les mêmes interfaces. De telles méthodes peuvent poser problème lors du passage à l'échelle car le trafic généré pourrait aisément ressembler à une attaque de déni de service distribué. Nous mesurons deux types de redondance dans l'envoi de sondes (intra- et inter-moniteur) et montrons qu'ils sont tous deux élevés. Dans un deuxième temps, comme il n'est pas inhabituel pour un moniteur de traceroute d'opérer en isolation, nous proposons et évaluons des stratégies pour réduire la redondance à l'intérieur d'un seul moniteur. L'idée clé de ces stratégies est de commencer à sonder loin du moniteur et de fonctionner en arrière. Nos résultats montrent que nos algorithmes peuvent diminuer la redondance au prix d'une légère réduction dans la découverte de noeuds et de liens. Ensuite, nous proposons et évaluons Doubletree, un algorithme coopératif qui réduit simultanément les deux types de redondance sur les routeurs et les systèmes finaux. Les idées clés sont (i) exploiter les structures en arbres des routes vers et depuis un seul point afin de décider quand arrêter d'envoyer des sondes, (ii) commencer à sonder quelque part au milieu du chemin. Nos résultats montrent que Doubletree peut réduire les deux types de charge sur le réseau de manière drastique tout en permettant de découvrir presque le même ensemble de noeuds et de liens. En plus, nous fournissons et évaluons une implémentation de Doubletree dans un outil appelé traceroute@home. Quatrièmement, nous fournissons plusieurs améliorations à Doubletree afin de réduire le coût de communication, la charge sur les destinations et augmenter la couverture. Enfin, nous proposons une généralisation des filtres de Bloom, les retouched Bloom filters, qui permet des faux négatifs en plus des faux positifs ainsi qu'un moyen d'obtenir un compromis entre les deux. Nous montrons aussi comment diminuer le taux d'erreur global, en l'exprimant comme une combinaison entre les taux de faux positifs et de faux négatifs.

Defence : 09/22/2006

Jury members :

Pierre Sens, Université Pierre & Marie Curie (France)
Serge Fdida, Université Pierre & Marie Curie (France)
Timur Friedman, Université Pierre & Marie Curie (France)
Olivier Bonaventure, Université Catholique de Louvain (Belgique) [Rapporteur]
Guy Leduc, Université de Liège (Belgique) [Rapporteur]
Mark Crovella, Boston University (USA)
Philippe Owezarski, LAAS (France)
kc claffy, University of California at San Diego/CAIDA (USA)

Departure date : 09/23/2006

2005-2013 Publications