All-Optical Multicast Routing in Wavelength Routed WDM Networks
Routage multicast tout optique dans les réseaux WDM
Résumé
In this thesis, we studied the all-optical multicast routing (AOMR) problem in wavelength-routed WDM networks. The objective is to find a set of light structures, for instance a light-tree or a light-forest, to distribute the multicast messages to all the desti- nations concurrently while either taking account of both the end-to-end delay and the link stress or minimizing the total cost or the power budget. With respect to the delay and link stress sensitive AOMR, an efficient algorithm based on avoiding multicast incapable branching nodes in light-trees is proposed. This algorithm is shown to be able to improve the end-to-end delay of light-trees and to find a good tradeoff among the end-to-end delay, the link stress and the total cost. Regarding the power-aware AOMR, a new but more accurate and realist power loss model is given for all-optical multicasting. It distinguishes two types of node tapping loss : the one tapped by intermediate optical nodes for network management and the other one tapped by destination nodes for the recovery of multicast messages. Based on this new mo- del, the power optimal design of light-trees is formulated by a mixed-integer programming (MILP). To achieve so, a set of novel linear equations is introduced to replace the nonlinear ones induced by the light splitters. In order to analyze the AOMR heuristic algorithms and assess their performances, light-trees computed using AOMR heuristic algorithms are evaluated mathematically by deriving the cost bounds and the approximation ratios in both unweighted and non-equally weighted WDM mesh networks. Concerning the cost optimal AOMR, a new structure called light-hierarchy is proposed. It is proven that the optimal structure is not the light-tree but the proposed light-hierarchy. The computation of light-hierarchy is modeled as an ILP to search the optimal solu- tion for small instances. A heuristic algorithm using a graph renewal strategy is also proposed for fast AOMR in large scale WDM networks. Simulation results strongly suggest the employment of light-hierarchy for AOMR in WDM networks with sparse splitting.
Dans cette thèse, nous étudions le routage multicast tout optique (AOMR) dans les réseaux WDM. Notre objectif est de trouver un ensemble de structures de diffusion, par exemple un arbre optique ou une forêt optique, pour distribuer des messages multicast vers toutes les destinations en même temps, soit en tenant compte du délai de bout en bout et du stress des liens soit en minimisant le coût total ou le budget en puissance. En ce qui concerne l'AOMR qui tient compte à la fois du délai et du stress des liens, un algorithme efficace évitant les nœuds de branchement ne pouvant pas dupliquer la lumière dans des arbres optiques est proposé. Cet algorithme améliore le délai de bout en bout sur les arbres optiques et trouve un bon compromis entre le délai, le stress des liens et le coût total. En ce qui concerne l'AOMR qui considère la puissance, un nouveau modèle plus précis et plus réaliste de la perte de puissance est introduit lors de la mise en œuvre d'une session multicast. Il distingue deux types de perte de puissance : la partie ponctionnée par les nœuds optiques intermédiaires pour un éventuel monitorage et la partie ponctionnée par les destinations pour la récupération des messages multicast. Basé sur ce nouveau modèle, nous proposons un calcule des arbres optiques optimisant la puissance de l'émetteur réalisé à partir d'une programmation linéaire mixte en nombres d'entiers (MILP). Pour y parvenir, un ensemble d'équations linéaires est introduit pour remplacer les équations non-linéaires induites par les coupleurs optiques. Pour analyser les algorithmes heuristiques de l'AOMR et évaluer leurs performances, nous proposons une analyse mathématique des résultats. Dans notre analyse, nous établis- sons les bornes de coût des routes et les ratios d'approximation des algorithmes dans les réseaux maillés WDM pondérés et non-pondérés. Pour le routage multicast optique de coût minimal, une nouvelle structure appelée hiérarchie optique est proposée. Il est prouvé que la structure optimale n'est pas toujours un arbre optique, mais une hiérarchie optique. Le calcul de la hiérarchie optique est modélisé sous forme d'une ILP. Ce calcul exact permet d'obtenir la solution optimale pour les petites instances. Dans les réseaux WDM à grande échelle, une heuristique efficace utilisant une stratégie de renouvellement du graphe est proposée. Les résultats de simulation justifient l'emploi de la hiérarchie optique pour l'AOMR dans les réseaux WDM avec une capacité clairsemée de duplication.
Loading...