Optimization problems in WDM optical transport networks with scheduled lightpath demands
Problemes d'optimisation dans les reseaux optiques de transport WDM avec trafic dynamique deterministe
Résumé
Wavelength division multiplexing optical transport networks are expected to provide the capacity required to satisfy the growing demand of telecommunications traffic in a cost-effective way. These networks, based on standards and implementation agreements currently under development by the ITU-T, the IETF and the OIF, are likely to be deployed during the next 5 or 6 years. New optimization problems arise in connection with these networks for several reasons. Firstly, the cost of optical networking equipment is not still well known due mainly to the early stage of development of the relevant technologies. Secondly, the uncertainty of traffic demands, due to the competition in the telecommunications market and to the massive adoption of new data applications, render difficult the accurate dimensioning of networks. Finally, the early stage of development of optical technology results in new functional constraints that must be taken into account during the design and dimensioning of the network. We investigate optimization problems arising in the engineering of an optical transport network. Network engineering concerns the configuration of existing network resources in order to satisfy expected traffic demands. Unlike network planning and traffic engineering, network engineering problems are relevant at time scales ranging from hours to weeks. A these time scales, the dynamic evolution of the traffic load is an important factor that must be taken into account in the configuration of the network. Moreover, the periodicity of the traffic load evolution observed in operational transport networks suggest that the traffic may be modeled deterministically. We propose a dynamic deterministic traffic model called Scheduled Lightpath Demands (SLDs). An SLD is a connection demand represented by a tuple (s, d, n, alpha, omega) where s and d are the source and destination nodes of the demand, n is the number of requested connections and alpha, omega are the set-up and tear-down dates of the requested connections. The model captures the time and space distribution of a set of connection demands and, being deterministic,eases the use of combinatorial optimization techniques to solve network optimization problems. We investigate three network optimization problems involving the SLD traffic model: - We first study the Routing and Wavelength Assignment (RWA) for SLDs problem in a wavelength-switching network. The routing problem is formulated as a combinatorial optimization problem with two possible objective functions. We propose a Branch & Bound (B&B) and a Tabu Search (TS) algorithm that compute, respectively, exact and approximate solutions. Wavelength assignment is formulated as a graph coloring problem. We use an existing greedy algorithm to find approximate solutions. - We then investigate the problem of Diverse Routing and Spare Capacity Assignment (DRSCA) for SLDs in a wavelength-switching network. The problem consists of defining a pair of span-disjoint paths for each SLD so that the number of required working and spare channels is minimal. We propose a channel reuse technique to reduce the required working channels and a backup multiplexing technique to reduce the spare channels required for protection. The problem is formulated as a combinatorial optimization problem. We propose a Simulated Annealing (SA) meta-heuristic algorithm to compute approximate solutions. - Finally, we investigate the problem of Routing and grooming of SLDs (SRG) in a multi-granularity switching network. We consider a network whose nodes have a wavelength cross-connect (WXC) and a waveband cross-connect (BXC). The problem is formulated as a combinatorial optimization problem. We propose a parallel TS meta-heuristic algorithm to compute approximate solutions. We determine the conditions under which a network based on multi-granularity switches is more economical than a wavelength-switching (single-granularity) network.
Les reseaux optiques a multiplexage en longueur d'onde (reseaux WDM) offrent la possibilite de satisfaire economiquement la demande croissante de services de telecommunications. Ces reseaux, bases sur des normes en cours de developpement a l'UIT-T, l'IETF et l'OIF, seront tres probablement deployes dans les 5 ou 6 annees a venir. De nouveaux problemes d'optimisation apparaissent en relation avec ces reseaux pour plusieurs raisons. En premier lieu, les couts pour les equipements optiques sont encore mal connus en raison du caractere recent des technolologies utilisees pour ces reseaux. Deuxiemement, l'incertitude de la demande, liee notamment a la concurrence dans le marche des telecommunications et a l'adoption massive de nouvelles applications informatiques, rendent difficile le dimensionnement des reseaux. Enfin, les nouvelles technologies optiques conduisent a de nouvelles contraintes fonctionnelles qui doivent etre prises en compte dans la conception et le dimensionnement du reseau. Nous etudions les problemes d'optimisation lies a l'ingenierie d'un reseau de transport optique. L'ingenierie de reseaux concerne la configuration des ressources reseau existantes pour satisfaire des demandes de trafic connues. A la difference de la planification des reseaux et de l'ingenierie de trafic, les problemes d'ingenierie de reseaux sont pertinents a des echelles de temps allant de l'heure a la semaine. A cette echelle de temps, l'evolution dynamique de la charge de trafic represente un element important qui doit etre pris en compte dans la configuration du reseau. Par ailleurs, la periodicite de l'evolution de la charge de trafic observee dans des reseaux de transport operationnels suggere que le trafic peut etre modelise de facon deterministe. Nous proposons un modele de trafic dynamique deterministe appele Scheduled Lightpath Demand (SLD). Une SLD est une demande de connexion representee par un quintuplet (s, d, n, alpha, omega) ou s et d representent les noeuds source et destination de la demande, n represente le nombre de connexions requises et alpha et omega les dates d'etablissement (set-up) et de fin (tear-down) des connexions demandees. Le modele decrit la distribution spatiale et temporelle d'un ensemble de connexions et, par son caractere deterministe, facilite l'utilisation de techniques d'optimisation combinatoire pour la resolution de problemes d'optimisation reseau. Nous etudions trois problemes d'optimisation reseau impliquant ce modele de trafic : - le probleme du routage et de l'affectation de longueurs d'onde (RWA) pour des SLDs dans un reseau a commutation de longueurs d'onde. Le probleme du routage est formule sous forme d'un probleme d'optimisation combinatoire avec deux fonctions objectif possibles. Nous proposons une methode par separation et evaluation (Branch & Bound ou B&B, en anglais) et un algorithme de Recherche Tabou (RT) pour le calcul de solutions exactes et approchees, respectivement. Le probleme de l'affectation de longueurs d'onde est formule sous forme d'un probleme de coloration de graphes. Nous utilisons un algorithme glouton existant pour trouver des solutions approchees. - le probleme de protection pour des SLDs dans un reseau a commutation de longueurs d'onde. Le probleme consite a determiner pour chaque demande un couple de chemins disjoints de telle sorte que le nombre de canaux primaires et de protection soit minimal. Nous proposons une technique de reutilisation de canaux pour reduire le nombre de canaux primaires et une technique de multiplexage de protection pour reduire le nombre de canaux dedies a la protection. Le probleme est formule sous forme d'un probleme d'optimisation combinatoire. Nous proposons un algorithme de type recuit simule (RS) pour calculer des solutions approchees. - Finalement, nous etudions le probleme de routage et d'agregation des SLDs (RAS) dans un reseau avec deux niveaux de granularite de commutation. Nous considerons un reseau dont les noeuds disposent d'un commutateur de longueurs d'onde et d'un commutateur de bandes. Le probleme est formule sous forme d'un probleme d'optimisation combinatoire. Nous proposons un algorithme Tabou parallele pour le calcul de solutions approchees. Nous definisons les conditions sous lesquelles un reseau avec deux niveax de granularite de commutation est plus economique qu'un reseau a commutation de longueurs d'onde.