Conception et optimisation robuste des réseaux de télécommunications

With communication networks getting more and more present in our daily activities, network outages or even significant degradations of the quality of service become less and less tolerable. This calls for a robust design of communication networks anticipating possible failures or shifts in the expected traffic demands. This thesis addresses several robust design and planning problems arising in the telecommunication area. We first address the problem of designing and dimensioning a survivable network topology. We propose a novel network design model integrating all equipment costs and constraints (links, routers and line cards). This model also include operational constraints such as the presence of potential nodes and modular capacities as well as delay constraints. One exact and two heuristic algorithms are proposed to solve this problem. Numerical results show that significant cost-savings can be achieved when equipment costs are taken into account in the early stages of the design process. With the explosive growth of the Internet and the incredible development of network applications, the variation in traffic volumes has become one of the most important problems faced by network operators. Designing a network using a single "busy hour" traffic matrix more and more strains credibility due to the high volatility of traffic patterns. Thus, there is a need to incorporate demand uncertainty into the network routing problems explicitly. We study two robust route optimization problems : (1) the problem of VPN design under the hose model of demand uncertainty and (2) the problem of link weight optimization under demand uncertainty. We establish mathematical models for both problems and propose efficient approximation algorithms based on local-search techniques to solve them. The practical effectiveness of the techniques and methods developed in this thesis is illustrated and validated by a set of numerical tests on realistic data. This work resulted in several software developments in the network planning tool NEST of QoS Design.Les réseaux de communication devenant de plus en plus présents dans nos activités quotidiennes, l'interruption des services fournis par le réseau, ou même une dégradation significative de leurs qualit és, deviennent de moins en moins tolérables. Une conception robuste des réseaux de communication, anticipant les pannes éventuelles d'équipements ou les variations sur la demande en trafic, devient donc de plus en plus nécessaire. Cette thèse traite de plusieurs problèmes de conception et de planification robustes apparaissant dans le domaine des télécommunications. Nous étudions tout d'abord le problème de la conception et du dimensionnement d'une topologie de communication résilience. Nous proposons un nouveau modèle de conception de réseaux intégrant les coûts et les contraintes des différents équipements (liens, routeurs, cartes). Ce modèle prend également en compte de nombreuses contraintes opérationnelles telles que la présence de noeud potentiel et de capacités modulaires, mais aussi des contraintes sur les délais de communication. Un algorithme exact et deux approximations sont proposés pour résoudre ce problème. Les résultats numériques montrent que des économies substantielles peuvent être effectuées en intégrant les coûts d'équipements dans la phase amont du processus de conception. Avec la croissance exponentielle de l'Internet et l'incroyable développement des applications réseaux, les variations sur les volumes de trafic sont devenus un des problèmes majeurs auxquels sont confrontés les opérateurs. Aujourd'hui, concevoir un réseau sur la base d'une unique matrice de trafic "en heure de pointe" est de moins en moins crédible du fait de la forte volatilité des trafics. Il devient ainsi nécessaire d'intégrer explicitement l'incertitude sur la demande en trafic dans les problèmes d'optimisation du routage. Nous étudions deux problèmes d'optimisation robuste du routage : (1) le problème de conception des VPN dans le cadre du modèle hose d'incertitude sur la de mande et (2) le problème d'optimisation des métriques de routage IGP avec incertitude sur la demande. Nous formulons des modèles mathématiques de chacun de ces problèmes et proposons des heuristiques efficaces basées sur des techniques de recherche locale pour les résoudre. L'efficacité pratique des techniques et méthodes développées dans le cadre de cette thèse est démontrée et validée par une batterie de tests sur des données réalistes. Ce travail a d'autre part donné lieu `a plusieurs développements logiciels dans le logiciel de planification de réseaux NEST de QoS Design