Optimisation des réseaux de télécommunications : Réseaux multiniveaux, Tolérance aux pannes et Surveillance du trafic

This thesis is devoted to optimization problems arising in telecommunication networks. We tackle these problems from two main points of view. On the one hand we study their complexity and approximability properties. On the second hand, we propose heuristic methods, approximation algorithms or even exact algorithms that we compare with mixed integer linear programming formulations on specific instances.<br /><br />We are interested in backbone networks as well as access networks. In the first chapter, we briefly present access networks and IP/WDM multilayer backbone networks using the MPLS architecture. These networks are composed of a physical layer on which is routed a virtual layer. In turn, the users' requests are routed on the virtual layer. We also present multilayer network survivability issues motivating two of the questions we have studied.<br /><br />The second chapter is dedicated to the design of virtual networks. First we propose a mixed integer linear programming formulation with network survivability constraints. Then we study a sub-problem, the grooming problem. Our objective is to minimize the number of virtual links, needed to route a given set of requests when the physical layer is a directed path. <br /><br />The third chapter deals with Shared Risk Resource Groups (SRRG) induced by stacking up network layers in multilayer networks. Thanks to the colored graphs model, we study connexity and failure vulnerability of these networks.<br /><br />The positioning of traffic measurement points in the access network of an internet service provider is the subject of the fourth chapter. Monitoring the traffic has numerous applications, such as failure detection and assessment of network performances. We consider passive as well as active measurementsLes problèmes étudiés dans cette thèse sont motivés par des questions issues de l'optimisation des réseaux de télécommunication. Nous avons abordé ces problèmes sous deux angles principaux. D'une part nous avons étudié leurs propriétés de complexité et d'inapproximabilité. D'autre part nous avons dans certains cas proposé des algorithmes exacts ou d'approximation ou encore des méthodes heuristiques que nous avons pu comparer à des formulations en programmes linéaires mixtes sur des instances particulières.<br /><br />Nous nous intéressons aussi bien aux réseaux de coeur qu'aux réseaux d'accès. Dans le premier chapitre, nous présentons brièvement les réseaux d'accès ainsi que les réseaux multiniveaux de type IP/WDM et l'architecture MPLS que nous considérons pour les réseaux de coeur. Ces réseaux sont composés d'un niveau physique sur lequel est routé un niveau virtuel. A leur tour les requêtes des utilisateurs sont routées sur le niveau virtuel. Nous abordons également la tolérance aux pannes dans les réseaux multiniveaux qui motive deux problèmes que nous avons étudiés.<br /><br />Le second chapitre est consacré à la conception de réseaux virtuels. Dans un premier temps nous modélisons un problème prenant en compte la tolérance aux pannes, puis nous en étudions un sous-problème, le groupage. Notre objectif est de minimiser le nombre de liens virtuels, ou tubes, à installer pour router un ensemble de requêtes quelconque lorsque le niveau physique est un chemin orienté.<br /><br />Le troisième chapitre traite des groupes de risque (SRRG) induits par l'empilement de niveaux au sein d'un réseau multiniveaux. Grâce à une modélisation par des graphes colorés, nous étudions la connexité et la vulnérabilité aux pannes de ces réseaux.<br /><br />L'objet du quatrième chapitre est le problème du placement d'instruments de mesure du trafic dans le réseau d'accès d'un opérateur. Nous considérons aussi bien les mesures passives qu'actives. La surveillance du trafic possède de nombreuses applications, en particulier la détection de pannes et l'évaluation des performances d'un réseau