Direction de recherche : Matthieu LATAPY

Co-encadrement : CRESPELLE Christophe

Une approche pour l'estimation fiable des propriétés de la topologie de l'Internet

Les grands réseaux sont partout dans la science, la société, et la vie quotidienne : dans les transports (ligne aériennes, routes) ; dans les communications (internet, web, échanges de fichiers ou de courriers) ; dans la vie sociale (collaborations, amitié, échanges économiques) ; dans les sciences du vivant (interactions entre protéines et gènes, dépendances entre espèces) ; dans l'analyse des langages (synonymie, cooccurrences de mots) ; etc. Par exemple, l'internet est un ensemble de routeurs avec des liens entre eux ; le web est un ensemble de pages web avec des hyperliens entre elles ; les réseaux sociaux sont en général des ensembles de personnes liées par des relations sociales comme l'amitié ou la collaboration professionnelle ; les réseaux de synonymie sont des ensembles de mots reliés s'ils sont synonymes ; etc.
Dans tous ces contextes, modéliser les objets sous-jacents comme des graphes (ensemble de noeuds et de liens entre eux), appelés graphes de terrain ou complex networks en anglais, s'est montré extrêmement fructueux : cette approche joue un rôle central dans leur modélisation et en simulation ; elle rend possible l'étude de la diffusion d'information, rumeurs et virus ; elle donne également des informations précieuses sur la robustesse des réseaux considérés ; etc.
Dans la plupart des cas, toutefois, les graphes de terrain ne sont connus qu'au travers d'une opération de mesure qui en donne une vision partielle et biaisée. L'approche actuelle, faute de mieux, consiste en l'obtention d'échantillons aussi grands que possible puis en l'hypothèse que ces échantillons sont représentatifs. La validité de cette hypothèse est loin d'être claire, et il a été montré qu'elle est fausse dans certains cas.
L'objectif de ce projet est de développer une approche radicalement différente, consistant en la conception et l'implémentation de mesures ciblant certaines propriétés ; il ne s'agit plus de collecter de grands échantillons, mais de faire des mesures permettant d'estimer précisément et rigoureusement une propriété ciblée. On peut ainsi imaginer des méthodes de mesure différentes pour les différentes propriétés d'un même graphe de terrain. Outre l'obtention de cette information, qui serait un progrès essentiel en soi, on tentera de capturer ces propriétés dans des modèles de génération de graphes.
Ce changement de façon d'envisager la mesure et la modélisation des graphes de terrain a un potentiel très fort pour le domaine : il permettrait d'obtenir des graphes artificiels, construits par les modèles, plus réalistes que n'importe quel échantillon collecté. Enjeux
L'objectif de ce projet est d'asseoir les études de graphes de terrain sur une connaissance fiable de leurs propriétés, d'un point de vue à la fois pratique et fondamental. Il est par conséquent très important pour le domaine. Il a le potentiel de rendre toutes les études de graphes de terrain bien plus rigoureuses, et donc plus pertinentes. Il vise à élever significativement les standards scientifiques du domaine, et ses résultats seront utilisables dans une variété de contextes très large.
Le projet vise un autre impact fondamental: changer de façon radicale la façon dont les experts des graphes de terrain voient leurs objets d'étude. Alors que la tendance actuelle est aux mesures massives (l'exhaustivité étant en général hors d'atteinte), ce projet propose de considérer les graphes de terrain comme des objets noirs, mais dans lesquels nous pouvons envoyer des sondes de diverses sortes afin d'obtenir de l'information sur leurs propriétés (et non un échantillon).
Ce projet se veut donc très important pour le domaine, et devrait avoir un impact très fort sur celui-ci : il vise à changer la façon dont on travaille sur les graphes de terrain, à la fois d'un point de vue théorique et pratique.
Il devrait également avoir un impact fort sur les infrastructures de mesure, comme notre approche de la mesure changera probablement. Les infrastructures actuellement conçues et déployées seront certainement d'une importance centrale pour mener les mesures nécessitées par le projet. De même, les ensembles de données massifs collectés aideront à mener le projet. Celui-ci doit donc être vu comme complémentaire des approches actuelles, en un premier temps, et aura une influence forte sur la conception et le déploiement des futures infrastructures de mesure.
Au delà du champ des études de graphes de terrain, il doit être clair qu'avoir, pour la première fois, une information fiable sur les propriétés des graphes de terrain, ainsi que des modèles adaptés, aura un impact sur la plupart des applications impliquant des graphes de terrain. En particulier, tous les travaux utilisant des simulations devraient en bénéficier fortement, car les résultats de simulation reflèteront bien mieux la réalité.

Publications 2010-2017

• 2017
  • M. Latapy, E. Rotenberg, Ch. Crespelle, F. Tarissan : “Rigorous Measurement of the Internet Degree Distribution”, Complex Systems, vol. 26 (1), (Complex Systems Publications, Inc.) (2017)
• 2015
  • E. Rotenberg : “Une approche pour l’estimation fiable des propriétés de la topologie de l’Internet”, soutenance de thèse, soutenance 08/01/2015, direction de recherche Latapy, Matthieu, co-encadrement : Crespelle, Christophe (2015)
• 2014
  • F. Tarissan, E. Rotenberg, M. Latapy, Ch. Crespelle : “UDP PING: a dedicated tool for improving measurements of the Internet topology”, MASCOTS'14 : IEEE 22^nd International Symposium on Modeling Analysis and Simulation of Computer and Telecomunication Systems, Paris, France, pp. 506-509 (2014)
  • M. Latapy, E. Rotenberg, Ch. Crespelle, F. Tarissan : “Measuring the degree distribution of routers in the core internet”, Proceedings of the 13^th IFIP International Conference on Networking, Trondheim, Norway, pp. 1-9, (IEEE) (2014)
  • E. Rotenberg, Ch. Crespelle, M. Latapy : “Measuring routing tables in the internet”, Proceedings of NetSciCom 2014, Toronto, Canada, pp. 795-800 (2014)
• 2010
  • Ch. Crespelle, M. Latapy, E. Rotenberg : “Rigorous Measurement of IP-Level Neighborhood of Internet Core Routers”, Second International Workshop on Network Scienece for Communication Networks (NetSciCom 2010), San Diego, CA, United States, pp. 499-504 (2010)