An approach for a reliable estimation of the properties of the internet topology

Cette thèse propose une nouvelle approche pour estimer des propriétés de la topologie d’Internet. Contrairement aux approches historiques, qui se bases sur des données déclaratives très peu fiables, ou sur la lecture de cartes mesurées avec des outils de diagnostic, notre approche consiste à mettre au point des primitives de mesures très fiables, dont le fonctionnement, les hypothèses et les résultats sont bien définis formellement. Notre premier cas d’étude est celui de la distribution de degré de la topologie logique, ou L3. Nous utilisons l’outil traceroute dont nous étudions le fonctionnement, pour en déduire une primitive de mesure. Cette primitive de mesure, qui repose sur l’utilisation d’un ensemble de moniteurs distribué dans le réseau, permet d’obtenir une estimation du nombre de voisins dans la topologie logique, d’un routeur du cœur. Nous utilisons cette primitive vers un échantillon aléatoire de cibles, pour obtenir une estimation de la distribution de degré recherchée et établir les limites de cette approche. Notre deuxième cas d’étude est celui de la distribution de degré de la topologie physique, ou L2-L3. Nous utilisons l’outil UDP Ping, dont nous étudions le fonctionnement, pour en déduire une primitive de mesure. Elle est semblable à l’outil utilisé pour la topologie logique, mais repose sur des hypothèses bien plus clairement établies et vérifiées, et validée par des simulations très détaillées. Nous intégrons également au protocole de mesure, des garanties statistiques sur l’uniformité de l’échantillon de cibles, des routeurs du cœur, que nous mesurons. Nous obtenons une évaluation de la distribution de degré recherchée, d’une très grande fiabilité. Nous complétons ce cas d’étude par un travail complémentaire sur les tables de transmission des routeurs du cœur. Enfin, nous dressons un tableau assez large des perspectives qui s’ouvrent en se basant sur cette approche, par exemple en l’appliquant à d’autres types de réseaux (réseaux sociaux, etc.).This thesis proposes a novel approach to reliably estimate properties of the Internet topology. Unlike historical approaches, based on declarative, hardly reliable data, or on readings from maps measured with diagnostic tools, our approach is to develop very reliable measure primitives, of which the operation, the hypotheses, and the results are well defined. Our first case study is the degree distribution of the logical topology, or L3. We use the traceroute tool, of which we study the operation, to derive a measurement primitive. This measurement primitive, which relies on using a distribution set of monitors over the network, allows us to get an estimation of the number of neighbors in L3 of a target core router. We use this primitive against a random sample of targets and obtain the sought distribution, and establish limits to this method. Our second case study is the degree distribution of the physical topology, or L2-L3. We use the UDP Ping tool, of which we study the operation, to derive a measurement primitive. It is alike the tool we used for the logical topology, but relies on much more clearly established and verified hypotheses, and is validated by very detailed simulations. We also include statistical guarantees of the sampling uniformity of the target core routers to the measurement protocol. We obtain an evaluation of the sought degree distribution, of an unprecedented reliability. We complete this case study by a complimentary study over the forwarding tables of the core routers. Finally, we picture the many perspectives opened by this approach, eg. By applying it to other types of networks (social networks, etc.)