Génération des topologies des réseaux pour la modélisation et la simulation
des interdépendances

 Introduction

La forte croissance de l’Internet et les difficultés liées au manque de technique et de données pour la production d’une cartographie précise de l’Internet ont poussé à réfléchir à des techniques appropriées de représentation topologique du réseau. En effet, cette croissance explosive cause un certain nombre de problèmes liés au routage, à l’administration, à la réservation des ressources et au risque des pannes et attaques de grande ampleur. Le développement des outils appropriés pour faire face à ces problèmes nécessite des simulations et des modèles réalistes de la structure du réseau pour évaluer les solutions proposées. Les interconnexions des différentes infrastructures impliquées dans la cadre des études sur les interdépendances renforcent les difficultés liées à la mise à disposition des topologies qui représentent, de manière réaliste l’ensemble de ces infrastructures. Or, pour effectuer des études de modélisation et de simulation, les chercheurs ont, le plus souvent besoin de la topologie du réseau étudié. La topologie du réseau désigne la définition de l’architecture, c’est à dire de la disposition et de la hiérarchie de l’ensemble des composants du réseau et les liaisons entre ces différents composants. Selon l’objectif, cette topologie peut représenter différents niveaux des réseaux. Pour les réseaux de télécommunications, cette topologie peut représenter les interconnexions des systèmes autonomes, on parle alors de topologies de niveau AS ou les interconnexions des routeurs à l’intérieur d’un système autonome. Elle peut aussi concerner les réseaux d’accès ou les réseaux de cœur. Pour les réseaux électriques, il est possible de représenter uniquement les interconnexions entre les différents réseaux, celles d’un réseau particulier, les réseaux de distribution ou les réseaux de transport. Cette représentation topologique peut être faite à l’aide des graphes où les nœuds du graphe représentent les composants et les arrêtes représentent les liaisons entre ces composants. Actuellement, de nombreux travaux de recherche sont basés sur des topologies représentées par les graphes réguliers (topologie maillée, en anneau, en étoile, en arbre), les réseaux bien connus comme ARPANet [48] ou des topologies générées 65 Génération des topologies des réseaux pour la modélisation et la simulation des interdépendances aléatoirement. La principale limite de ces méthodes est que les topologies générées aléatoirement et les graphes réguliers sont, le plus souvent, très loin des réseaux qu’on souhaite étudier. Les topologies représentant les réseaux bien connus ne conviennent que pour des études particulières comme l’évaluation des performances de nouveaux protocoles, elles sont souvent trop anciennes, donc inadaptées à l’étude des interdépendances des infrastructures actuelles. Par exemple, les topologies des réseaux électriques fréquemment utilisées pour des tests, comme celle du réseau électrique IEEE de 14 nœuds1 datent des années 60. Or les résultats des simulations varient fortement en fonction des environnements, notamment les topologies utilisées. Donc, pour obtenir des résultats pertinents avec des expérimentations basées sur des modèles et des simulations, il est indispensable de disposer, en nombre suffisant, des topologies qui représentent fidèlement les réseaux étudiés. Par ailleurs, pour les simulations des interdépendances, la topologie utilisée doit représenter une multitude de réseaux interconnectés à des points précis suivant des accords ou des nécessités techniques. Les simulations des propagations des pannes dans les réseaux nécessitent une caractérisation de l’ensemble des événements qui conduisent à ces pannes : leur origine, leur évolution et leurs conséquences. Il est donc nécessaire de représenter l’ensemble des entités qui influent sur les propagations de ces pannes et d’utiliser des topologies qui représentent aussi bien les interconnexions au sein d’un réseau particulier que celles entre les différents opérateurs. Puisqu’il existe une différence fonctionnelle importante entre les interconnexions au sein d’un même réseau et celles entre différents réseaux liées, notamment aux accords, ces topologies doivent offrir des moyens pour identifier ces différentes interconnexions. Pour l’étude des interdépendances et les propagations des défaillances entre les infrastructures, les réseaux impliqués sont de grande taille et ont des topologies complexes. La nécessité, pour les chercheurs de disposer de topologies en nombre suffisant pour leur simulation ont contribué à l’émergence du besoin de développer des techniques de génération automatique des topologies. Dans ce chapitre, nous présentons une technique de génération des topologies pour la modélisation et la simulation des interdépendances. La technique proposée consiste à appliquer les règles de déploiement des réseaux pour produire une topologie proche des infrastructures existantes. Ces règles sont différentes suivant les domaines, par exemple, les paramètres fondamentaux pour déployer un réseau de télécommunications diffèrent de ceux du réseau électrique. Nous prenons donc en compte ces spécificités, mais définissons un algorithme qui peut être adapté à ces spécificités. Notre algorithme utilise des paramètres d’entrée simples et réalistes couramment pris en compte pour la conception et le dimensionnement des réseaux et génère des graphes représentant des topologies qui offrent des possibilités pour identifier les interconnexions, donc les interdépendances. Ces paramètres peuvent être des résultats des mesures ou des enquêtes ou encore générés aléatoirement. La technique proposée et les résultats de l’évaluation de la qualité des topologies générées sont décrites dans les sections suivantes. Une partie du travail présenté dans ce chapitre a été publié [50] au 4th International Workshop on Critical Information Infrastructures Security (CRITIS’092 ) en octobre 2009.

État de l’art de la génération de topologies des réseaux de télécommunications pour des études des interdépendances

La génération automatique de topologie des réseaux a mobilisé de nombreux chercheurs et plusieurs travaux ont été faits pour fournir des outils de génération dont les plus connus sont les techniques de génération aléatoire. A titre d’exemple, on peut citer les travaux de Waxman [144] qui avait développé l’un des modèles les plus populaires. Sa technique consiste à générer des graphes probabilistes en considérant la distance euclidienne entre les nœuds. Par la suite, les auteurs de [29, 52, 149, 148] ont introduit la notion de hiérarchie observée sur Internet à l’aide des logiciels GT-ITM3 et Inet4 démontrant ainsi les limites du modèle de Waxman [144] pour représenter le réseau Internet, notamment sa structure hiérarchique. Le développement de ces modèles était essentiellement fondé sur des observations qui ont montré que les topologies des réseaux étaient loin d’être arbitraire et présentaient des structures hiérarchiques évidentes. L’approche de ces outils prônait aussi la prise en compte les principes de conception et de déploiement de réseaux par les générateurs de topologies. Ces outils ont été très vite suivis par l’apparition des logiciels comme BRITE5 [99] et PLRG [15] qui, en plus de la génération des graphes hiérarchiques offrent des possibilités de produire des graphes dits sans-échelle (scale free) dont la distribution des degrés suit une loi de puissance. Les auteurs de [95] introduisent un modèle hybride combinant des techniques de génération aléatoires des topologies et des techniques fondées sur la distribution des degrés. Ils proposent l’utilisation des techniques aléatoires pour générer les graphes représentant les interconnexions intra-AS et la technique dont la distribution des degrés suit une loi de puissance pour générer les graphes inter-AS. Pour rappel, l’architecture Internet est constituée de différents AS hiérarchiques. Les AS de niveau 1 (Tier-1 AS) sont des réseaux IP qui participent à l’Internet uniquement par le biais d’interconnexions non payantes, également connu sous le nom de peering gratuit. Ce sont les réseaux qui peuvent atteindre tous les autres réseaux sur Internet sans avoir à payer pour des services d’un réseau de transit. Ils se situent au plus haut niveau de la hiérarchie (Top level AS). Il existe aussi des AS de niveaux 2 (Tier-2 AS) et 3 (Tier-3 AS). Les AS de niveau 2 sont des réseaux qui peuvent établir des liens de peering gratuit avec d’autres réseaux de même niveau et sont des clients des AS de niveau 1. Les AS de niveau 3 sont, en général sans lien de peering, ils sont des simples clients des AS de niveau 2. Dans [28], les auteurs étudient la structure hiérarchique de l’Internet pour identifier les différentes parties du réseau qui peuvent être correctement représentées par les techniques de génération de topologie fondées sur la distribution des degrés et sur la structure hiérarchique de l’Internet. D’après leurs résultats, à l’exception des interconnexions entre les AS de niveau 1 (Tier-1 AS), la distribution des degrés des interconnexions entre les différents systèmes autonomes suivent une loi de puissance. Ils déduisent une technique hybride de génération permettant d’obtenir des graphes conformes à cette distribution de degrés et à la structure hiérarchique. Dans le même ordre d’idée, les auteurs de [81] proposent MAMT (Multi-ASes and Multi-Tiers) pour la génération des graphes représentant à la fois plusieurs systèmes autonomes 3http://www.isi.edu/nsnam/ns/ns-topogen.html#gt-itm 4http://www.isi.edu/nsnam/ns/ns-topogen.html#inet 5http://www.cs.bu.edu/faculty/matta/Research/BRITE/ 67 de différents niveaux (Tier-1, Tier-2 et Tier-3) à partir d’une technique fondée sur la structure hiérarchique du réseau Internet. Pour améliorer la qualité des topologies générées par les techniques fondées sur la structure hiérarchique, ATETEs (Adapting Traffic Evolution Topology gEnerators) [84] propose d’utiliser, en plus de la structure hiérarchique et de la distribution des degrés, la distribution du trafic pour générer des topologies sur la base de l’évolution du réseau. L’approche d’évolution du réseau utilisée est fondée sur l’ajout des liens et des nœuds au graphe initial de manière à réduire la charge des parties les plus congestionnées du réseau. Une autre approche fréquemment utilisée pour la génération des topologies est celle qui consiste à générer des graphes à partir des données collectées par des moniteurs placés sur certains points du réseau Internet. Les travaux des auteurs de [145] considèrent, sur la base des données collectées en 1998, que la distribution des degrés de connectivité des liens inter-AS suivent une loi de puissance. Ils proposent une technique fondée sur cette distribution. Ces travaux ont servi de base à de nombreuses techniques de génération des topologies. Cependant, des travaux comme ceux de [109] ont démontré, par la suite que les résultats fournis par cette technique sont trop approximatifs et présentent des limites pour l’étude de la propagation des pannes à cause de la topologie incomplète du réseau qu’elle produit et l’impossibilité d’obtenir des graphes de niveau routeur nécessaires pour la modélisation des propagations des pannes. Dans [93], les auteurs proposent de combiner les données collectées à partir des réseaux existants, de la théorie des graphes et des contraintes techniques et économiques liées au déploiement des réseaux pour générer des topologies de niveau routeur. Les contraintes techniques et économiques utilisées comprennent le nombre maximum de ports d’un routeur, donc son degré de connectivité et le coût des liaisons entre les différents sites. Avec leurs résultats, les auteurs démontrent que les réseaux fortement connectés ne sont pas forcément efficaces en terme de bande passante et de coût. Les auteurs de [49] utilisent une technique de rétro-ingénierie (reverse-engineering) pour générer des topologies représentant des réseaux à l’échelle d’un pays à partir des données sur des réseaux de plus petite taille (à l’échelle régionale par exemple). Pour prendre en compte les contraintes techniques et de coût de déploiement des réseaux, les auteurs combinent la technique de rétro-ingénierie aux contraintes liées au coût de déploiement et à la performance, notamment la limite des routeurs et des liens en terme de bande passante. Avec leurs résultats, les auteurs démontrent que même avec une même distribution de degrés, les topologies peuvent avoir une différence importante en terme de structure lorsque la technique de génération prend en compte les contraintes d’ingénierie.