Etude de reseaux complexes et de leurs proprietes pour l’optimisation de modèles de routage

Internet, qui à l’origine était un réseau militaire et universitaire interconnectant quelques dizaines d’acteurs, est devenu le plus grand système distribué de communication au monde. Actuellement, le cœur du réseau Internet est composé d’environ 48 000 systèmes autonomes (ou AS, Autonomous System) [Bat]. Ces AS sont des entités administratives autonomes. Ce sont par exemple des fournisseurs d’accès Internet, des universités ou encore des réseaux d’acteurs privés ou gouvernementaux. Ces deux dernières décennies ont vu s’accroître l’usage des services et le développement de nouvelles technologies utilisant le réseau Internet pour communiquer. Des millions de terminaux sont maintenant connectés en permanence, des usages de plus en plus nombreux se développent, nous rendant dépendants du bon fonctionnement du réseau.

Cette évolution rapide d’Internet et de ses usages impose de nombreuses contraintes aux opérateurs réseaux afin de garantir le bon fonctionnement du réseau. L’augmentation du nombre d’AS, l’explosion des communications haut débit à partir de lignes fixes et mobiles, l’accès aux fournisseurs de contenu et les réseaux en nuage sont quelques exemples de ces nouveaux usages.

Une des fonctions essentielles d’Internet est d’assurer le routage distribué des données entre une source et une ou plusieurs destinations. Chaque nœud de la topologie exécute une fonction de routage qui, pour chaque destination atteignable, calcule un chemin sans boucle pour transmettre les données vers cette destination. Le système de routage d’Internet est assuré par le protocole de routage frontière [RLH06] (ou BGP, Border Gateway Protocol).  L’architecture de routage d’Internet et plus particulièrement BGP, montre ses limites en termes d’ingénierie de trafic et du nombre de systèmes autonomes pouvant être supportés. L’algorithme à vecteur de chemin sur lequel repose BGP est à l’origine du problème de passage à l’échelle du protocole :
— le nombre d’entrées stockées dans les tables de routage pour assurer un routage des plus courts chemins sans boucle est linéaire en le nombre d’AS ;
— de nombreux messages doivent être échangés afin de converger, c’est-à-dire jusqu’à ce que l’ensemble des routeurs ait une vue cohérente de la topologie.

Afin de pallier à ces limitations, ces deux dernières décennies ont vu émerger deux catégories d’études. Une première catégorie vise à améliorer le fonctionnement de BGP afin d’assurer la pérennité de l’architecture actuelle. La seconde porte sur la conception de nouveaux schémas de routage en vue du remplacement de BGP. Un schéma de routage est un algorithme permettant de calculer une table de routage afin d’acheminer des données entre deux nœuds du réseau. Certains schémas de routage ont été développés afin de prendre en compte certaines spécificités de la topologie d’Internet [NRS12, LABJ01, PKBV09, Gla13]. Les performances de ces nouveaux schémas doivent ensuite être évaluées et comparées à celles du protocole de référence dans Internet, BGP.

Dans cette thèse, mes travaux portent sur deux aspects distincts mais complémentaires pour l’étude des réseaux et de leurs protocoles de routage : l’étude de l’hyperbolicité dans les grands graphes d’une part, et la simulation de modèles de routage dans les grands réseaux d’autre part.

De nombreuses propriétés structurelles (distribution des degrés, clustering coefficient, structure arborescente, etc) sont étudiées depuis plusieurs années dans les grands graphes modélisant les réseaux sociaux, les réseaux biologiques, les réseaux de citations ou Internet. Ces études permettent de mieux comprendre la structure de ces réseaux, de les modéliser et de proposer de nouveaux algorithmes de routage pour Internet. Plus particulièrement, certaines études récentes [AD14, Dra13] se sont intéressées à différents paramètres mesurant la structure arborescente présente dans les réseaux complexes. Dans ce contexte, une propriété particulièrement étudiée est celle de l’hyperbolicité selon Gromov [Gro87]. Une définition de l’hyperbolicité, nommée condition des quatre points, définit un graphe G= (V, E) comme δ-hyperbolique si pour tout quadruplet a, b, c, d ∈ V , les deux plus grandes des sommes S1 = d(a, b) + d(c, d), S2 = d(a, c) + d(b, d), et S3 = d(a, d) + d(b, c) diffèrent d’au plus 2δ. L’hyperbolicité de G désigne la valeur du plus petit δ vérifiant cette définition.

L’hyperbolicité d’un graphe exprime comment son espace métrique se rapproche de celui d’un arbre. La propriété d’hyperbolicité d’un graphe s’est révélée être d’une grande importance pour le routage dans les réseaux. Dans [KPK+10], les auteurs fournissent un cadre géométrique pour l’étude de la structure de réseaux complexes et mettent en lumière la géométrie hyperbolique sous-jacente de ces réseaux. Ils montrent que les réseaux à géométrie hyperbolique sont robustes et permettent une navigabilité optimale. Par exemple, il est possible de plonger avec précision la topologie de l’Internet dans un espace hyperbolique [BPK10]. Il a été montré qu’un algorithme de routage glouton utilisant les coordonnées des sommets et les distances entre sommets dans cet espace métrique a un faible étirement par rapport aux plus courts chemins [PKBV09]. Pour rappel, l’étirement d’un chemin est dit multiplicatif si il mesure le rapport entre la longueur du chemin calculée par l’algorithme de routage sur celle du plus court chemin. On dira qu’il est additif dans le cas de la différence entre les longueurs de ces deux chemins. Plus généralement, l’efficacité des algorithmes de routage dépend de la nature hyperbolique de l’espace métrique d’une topologie donnée [CDE+12]. La notion d’hyperbolicité a aussi été utilisée pour exprimer la latence de l’Internet comme une métrique arborescence [RMK+09], comprendre et améliorer la fiabilité et la sécurité des réseaux [NS11, JL04] ou encore mesurer la distance géodésique entre des arbres phylogénétiques pour leur classification [CH12, DHK+11].