Conception de réseaux dynamiques tolérants aux pannes

Le déploiement des réseaux de télécommunication assure l’interconnexion des utilisateurs où qu’ils soient dans le monde. Ce développement a lieu au travers de plusieurs types de réseaux. Les réseaux satellites permettent de relayer les communications partout dans le monde mais leur coût est élevé. Les réseaux WiFi type GSM (Groupe Spécial Mobile) sont utilisés dans les pays occidentaux dans lesquels l’utilisation des téléphones mobiles s’est banalisée et dans les pays en voie de développement car le coût des infrastructures est faible et que ces réseaux sont facile et rapide à installer. Les réseaux optiques sont utilisés dans les zones ayant un fort trafic ou pour assurer les liaisons intercontinentales, elles permettent entre autre une liaison plus rapide que par satellite. J’ai débuté ma thèse dans un contexte d’essor de ces réseaux de télécommunication suite à un ralentissement aux alentours de 2002. Les sommes engagées dans le développement de ces réseaux sont très importantes (elles se comptent en centaines de milliards d’euros rien qu’en Europe) et sont en forte croissante. Ainsi, il est crucial de construire des réseaux adaptés.

Les réseaux que j’ai cités précédemment -réseaux embarqués pour les satellites, réseaux d’antennes captant les signaux des satellites, réseaux WiFi et réseaux optiquesont chacun leurs propres spécificités techniques, mais un grand nombre de problématiques fondamentales sont transverses, comme le dimensionnement, la tolérance aux pannes, la nécessité de pouvoir s’adapter à un environnement ou à une demande dynamique et la minimisation des ressources nécessaires à une qualité de services suffisante. La maîtrise de ces différentes problématiques est essentielle à tout opérateur qui souhaite être compétitif et la maîtrise de l’une d’elles n’est utile que conjointement à la maîtrise des autres problématiques.

Au cours de ma thèse, je me suis intéressé à ces problématiques en utilisant plusieurs approches, notamment de nature combinatoire et algorithmique. Mon objectif a été d’étudier différentes étapes du cycle de vie d’un réseau, de sa conception à son exploitation quotidienne. Cela me permet de mettre en évidence les points communs entre les différents problèmes, d’utiliser des techniques variées pour les résoudre et d’apporter une expertise originale. Les approches que j’utilise dans chacun des chapitres sont pour la plupart génériques et peuvent être adaptées à d’autres problèmes. Ceci dit, afin de les illustrer, je les applique à un type donné de problème et de réseau .

Les problématiques que j’ai dégagées, concernant le cycle de vie d’un réseau, m’ont permis de mettre en œuvre des techniques variées dont certaines sont transverses. Dans cette section, je décris leurs utilités.

Graphes d’expansion et structure des graphes. Le rôle des réseaux étant d’interconnecter des utilisateurs entre eux, ceux-ci doivent avoir de bonnes propriétés de connectivité. Dans les cas où la topologie du réseau peut être choisie, l’utilisation de graphes d’expansion (des graphes dont tout ensemble de moins de la moitié des sommets a un nombre de voisins proportionnel à sa taille) comme modèle peut s’avérer intéressante, tout comme celle de graphes ayant une bonne robustesse si le besoin en connectivité est moindre. Des techniques de décomposition de graphes peuvent également être utiles pour mettre en exergue de petites structures interdites et ainsi obtenir des garanties d’optimalité pour les réseaux conçus ; la q-quasi partition (une répartition des sommets en ensembles connexes de taille à peu près q et tels que peu de sommets soient dans plusieurs ensembles) en est un exemple. D’autres types de décompositions sont utilisés pour la conception de réseaux, telle la vertex separation (une énumération des sommets telle que tous segments initiaux aient peu de voisins, un paramètre équivalent à la pathwidth) qui a été introduite pour la conception de circuits. Enfin, l’utilisation de méthodes probabilistes permet d’obtenir des garanties théoriques sur l’existence de « bons » réseaux.

Problèmes de coloration de graphes, méthode probabiliste et programmation linéaire. Le problème de dimensionnement de lien est complémentaire au problème de choix de la structure. Il s’agit d’assurer que les capacités du réseau permettent de satisfaire les demandes prévues. Il s’agit donc de garantir la répartition de ressources disponibles entre différentes requêtes (ce sont typiquement des problèmes de routage et/ou d’ordonnancement) de telle sorte qu’une ressource ne soit pas simultanément utilisée par plusieurs requêtes. De tels problèmes sont facilement modélisables par des problèmes de coloration de graphes. Les couleurs représentent alors les ressources, les sommets du graphe représentent les requêtes et une arête représente une interaction entre deux requêtes. Les problèmes de coloration que j’étudie sont la coloration pondérée k-impropre, la coloration proportionnelle, la coloration fractionnaire -une relaxation de la coloration normale- et le directed star colouring. Le problème est alors de trouver le nombre de couleurs minimum pour colorier les graphes d’une classe de graphes bien précise. Lors du dimensionnement des réseaux, l’important est l’existence de solution, il est donc pertinent d’utiliser des techniques probabilistes telle que le Lemme Local de Lovász, duquel il existe une version déterministe. Une approche complémentaire pour résoudre des problèmes d’allocation de ressources est l’usage de programmes linéaires. Quand un problème est trop complexe pour être modélisé de manière suffisamment simple pour pouvoir le résoudre de manière théorique, l’utilisation de programmes linéaires permet, à l’aide de simulateurs et d’un solveur, d’obtenir des résultats empiriques sur le comportement du réseau que l’on conçoit. Au cours de ma thèse, j’ai conçu des programmes linéaires pour des problèmes de routage et de protection. Les objectifs à considérer sont variés, il est nécessaire de prendre en compte le profit réalisé ainsi que la qualité du service offert aux clients. J’ai utilisé la technique dite de génération de colonnes afin de pouvoir résoudre des problèmes de grande taille.

Décomposition de graphes et algorithmes d’approximation. Lors de la conception d’un réseau, le temps de calcul n’est pas un facteur limitant. Cependant, lors de son exploitation, des algorithmes d’optimisation efficaces sont indispensables afin de pouvoir faire face aux évolutions dynamiques des demandes et des caractéristiques. Dans des cas où le problème peut être modélisé par un graphe de petite pathwidth ou treewidth (deux types de description de séparateurs de petite tailles), il est parfois possible de calculer la solution optimale. Sinon cela prend trop de temps car les problèmes sous-jacents sont souvent NP-durs. Ainsi, il est nécessaire de développer des algorithmes d’approximation et si possible distribués pour faciliter l’exploitation des réseaux. Les problèmes de coloration se prêtent souvent bien à la conception de tels algorithmes. Si les programmes linéaires sont suffisamment vite résolus, ils peuvent également être utilisés lors du routage. Une autre solution pour exploiter un réseau dont les caractéristiques ou les demandes évoluent dynamiquement est de se baser sur une solution courante et de la faire évoluer. Ce problème a été modélisé par un paramètre appelé process number. Il se trouve que ce paramètre est étroitement lié à la pathwidth, l’étude de ce paramètre est donc intéressante tant d’un point de vue pratique que théorique.