Connexité dans les réseaux de télécommunications
Institution:
NiceDisciplines:
Directors:
Abstract EN:
We study routing and connectivity problems in telecommunication network, using graph theory. In the first part of this thesis, we study static networks, taking particular interest in optical networks. On the one hand, the high bandwidth of optical fibbers enables telecommunication operators to use some part of the resource to guarantee fail proof networks. In this context, we solve a problem of 2-connected network design. On the second hand, we notice that optical links are composed of pairs of opposite unidirectional fibbers. By taking this fact into account, we can model optical networks by symmetric digraphs, and tailor specific routing algorithms. Thus, we study disjoint paths and multiflow problems in symmetric digraphs. In the second part of this thesis, we study dynamic networks, we present a new model, the Evloving Graph that takes into account the time evolution of dynamic networks. On this modes, we propose polynomial routing algorithms optimizing various measures on journeys, among them end-to-end delay, arrival date and hop count. We also study the concept of connectivity in Evolving Graphs, and the problem of computing maximum connected components. Lastly, we overview several dynamic flow problems, and propose a solution to the maximum flow problem in Evolving Graphs.
Abstract FR:
Dans cette thèse, nous étudions des problèmes de routage et de connexite dans les réseaux de télécommunications dans le cadre de la théorie des graphes. En première partie, nous nous intéressons aux réseaux statiques, et plus particulièrement aux réseaux optiques. D’une part, la très grande bande passante offerte par la fibre optique a amené les opérateurs de télécommunication à exploiter une partie des ressources des réseaux optiques pour assurer une continuité du service à l’épreuve des pannes. Dans ce cadre, nous résolvons un problème lié au dimensionnement de réseaux 2-connexes. D’autre part, le fait que les fibres optiques soient des collections de paires de liens opposés permet de modéliser les réseaux optiques par des graphes orientés symétriques. Nous étudions les problèmes de routage et de multiflot en tirant profit des propriétés topologiques des graphes orientés symétriques. En deuxième partie, nous nous intéressons aux réseaux dynamiques. Nous présentons le modèle combinatoire des Graphes Evolutifs qui représente l’évolution temporelle d’un réseau. Sur ce modèle, nous présentons des algorithmes polynomiaux pour résoudre différents problèmes de routage et d’arbres couvrants. En deuxième partie, nous nous intéressons aux réseaux dynamiques. Nous présentons le modèle combinatoire des Graphes Evolutifs qui représente l’évolution temporelle d’un réseau. Sur ce modèle, nous présentons des algorithmes polynomiaux pour résoudre différents problèmes de routage et d’arbres couvrants. En deuxième partie, nous nous intéressons aux réseaux dynamiques. Nous présentons le modèle combinatoire des graphes évolutifs qui représente l’évolution temporelle d’un réseau. Sur ce modèle, nous présentons des algorithmes polynomiaux pour résoudre différents problèmes de routage et d’arbres couvrants. Nous présentons également ce que signifie la notion de connexite pour un réseau dynamique, et nous étudions la complexité du problème du calcul des composantes connexes d’un graphe évolutif. Enfin, nous abordons différents problèmes de flots dynamiques, et nous proposons une résolution du problème du flot maximal dans les graphes évolutifs.