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.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

1 Introduction
1.1 Principaux résultats obtenus
1.2 Réseaux de télécommunication : problématiques et techniques
1.3 Publications
2 Notions de base
2.1 Définitions et notations
2.1.1 Graphes
2.1.2 Caractéristiques des graphes
2.1.3 Quelques familles de graphes
2.2 Introduction sur les réseaux
2.2.1 Fonctionnement général d’un réseau, le modèle OSI, Open Systems Interconnection
2.2.2 Rappels sur le multiflot classique
3 Conception de réseaux tolérants aux pannes
3.1 Concentrateurs, superconcentrateurs et graphes d’expansion
3.2 Réseaux (p,λ,k)
3.3 Résultats antérieurs
3.4 Réseaux tolérant un grand nombre de pannes : contributions
3.4.1 Robustesse des graphes 4-réguliers
3.5 Conclusion et perspectives
4 Conclusion