Stage: Mesures et analyse de la cartographie de l’Internet

Proposition de stage de fin d’études Master/Ingénieur orienté recherche

De nouveaux algorithmes sont en cours de conception pour mieux comprendre la structure de l’Internet à travers des mesures. Ce stage consiste à réaliser le déploiement d’un algorithme existant sur la plateforme de mesures PlanetLab Europe, que nous opérons, et d’évaluer son efficacité dans une optique d’améliorations.

Encadrants : Timur FRIEDMAN et Olivier FOURMAUX, maîtres de conférences UPMC Sorbonne Universités (Paris VI) au laboratoire LIP6

Période : 5 à 6 mois entre janvier et septembre 2017

L’Internet consiste en des dizaines de milliers de réseaux indépendants appelés systèmes autonomes, ou AS (autonomous systems). Les chercheurs qui travaillent sur la cartographie d’interconnexions entre ces AS n’en ont qu’une vision partielle. Les plus grands des AS se décomposent en PoP (points of presence), des lieux qui hébergent des routeurs de transit et d’accès. La compréhension de la distribution des routeurs entre PoP à l’intérieur des AS est également partielle. Seul l’opérateur de chaque AS connaît parfaitement la topologie de son réseau.

Les utilisateurs extérieurs, les chercheurs par exemple, n’ont que quelques outils pour les aider à la elaborer la cartographie de l’Internet. Ils peuvent regarder les flux de messages entre routeurs générés par le protocole de routage inter-AS BGP. Ils peuvent également lancer des mesures du type « traceroute » depuis des points d’observation distribués. Ces outils fournissent des données brutes qui ne sont pas suffisantes en elles-mêmes pour déterminer la topologie de l’Internet. Il existe dans la littérature scientifique des algorithmes pour guider l’usage de ces outils et pour interpréter les données résultantes. Ce stage consiste à réaliser le déploiement d’un de ces algorithmes sur la plateforme de mesures PlanetLab Europe (http://planet-lab.eu), que nous opérons, et d’évaluer son efficacité dans une optique d’améliorations.

Les étapes du stage sont :

• le choix, en concertation avec les encadrants, de l’algorithme à implémenter (voir en bas deux exemples de papiers scientifiques qui proposent des algorithmes)
• l’implémentation de l’algorithme en utilisant ou éventuellement étendant des capacités de mesure existantes sur PlanetLab Europe
• la comparaison des mesures obtenus avec les résultats publiés dans la littérature scientifique
• la réflexion autour des améliorations à apporter éventuellement à l’algorithme ou l’utilisation éventuelle d’autres algorithmes à sa place

Compétences :

• aptitude/intérêt à faire de la recherche
• capacité à programmer

Candidature : Merci de bien vouloir nous envoyer par e-mail :

• un CV
• une lettre de motivation
• une ou deux personnes référentes

Timur Friedman <timur.friedman@lip6.fr <timur.friedman@lip6.fr>>, Olivier Fourmaux <olivier.fourmaux@lip6.fr <olivier.fourmaux@lip6.fr>> Laboratoire LIP6-CNRS UPMC Sorbonne Universités (Paris VI) 4 place Jussieu, 75005 Paris

N’hésitez pas à nous contacter pour d’avantage de détails.

Exemples d’algorithmes dans la littérature scientifique :

Dima Feldman and Yuval Shavitt. "Automatic Large Scale Generation of Internet PoP Level Maps". In Proceedings of IEEE GLOBECOM 2008, New Orleans, LA, USA.

Brice Augustin, Balachander Krishnamurthy, and Walter Willinger. "IXPs: mapped?". In Proceedings of the ACM SIGCOMM Internet Measurement Conference (IMC) 2009, New York, NY, USA.