Au cours de la dernière décennie, le trafic dans les réseaux a connu une croissance explosive en double environ tous les trente trois mois. Les sources à l'origine de cette croissance proviennent de nombreuses applications à grande vitesse qui impliquent la transmission de données dans des groupes de multicast. Pour réaliser la multicast optique, les routeurs optiques peuvent avoir des répartiteurs de lumière spéciaux pour diviser des signaux lumineux et des convertisseurs de longueur d'onde pour modifier les longueurs d'onde où c'est nécessaire. Cependant, la division réduit l'énergie du signal qui nécessite alors une amplification ou une régénération qui nécessitent du matériel coûteux. Les convertisseurs de longueurs d'onde aussi ne sont pas suffisamment matures pour être largement déployés dans les technologies optiques actuelles. Par conséquent, dans les réseaux tout-optique, les unités de transformation des routeurs sont souvent hétérogènes et les algorithmes de routage doivent en tenir compte tout en parvenant à des solutions de compromis coût-performances qui satisfassent les exigences de bande passante et les contraintes optiques.Dans cette thèse, nous étudions les problème de routage multicast tout-optique (AOMR) dans les réseaux tout-optique hétérogènes. L'hétérogénéité provient principalement de l'absence / présence de séparateurs de lumière et de convertisseurs de longueur d'onde et de la répartition inégale des longueurs d'onde dans les liens du réseau. En général, les problèmes de AOMR sont NP-difficiles. L'objectif de la thèse est d'analyser et de formuler les problèmes sous différentes contraintes optiques, pour rechercher des solutions optimales ou proposer des heuristiques efficaces. Les deux contextes possibles, la demande unique ou multiple de multicast, sont examinés. Toutes les propositions présentées dans la thèse sont validées par des simulations approfondies. Les principales contributions peuvent être résumées comme il suit.1) Nous identifions les structures des routes optimales pour les problèmes de l'AOMR dans les réseaux WDM hétérogènes. Comme indiqué dans la thèse, les solutions optimales ne sont plus basées sur des arbres de lumière classiques, mais sur une structure arborescente plus générale appelée hiérarchie. Certaines formes de hiérarchie pour la multicast WDM sont des parcours optiques, des hiérarchies optiques, des hiérarchies-araignée optiques ou encore des ensembles de ces routes optiques. Les algorithmes exacts et les heuristiques proposés dans la thèse sont principalement basés sur les hiérarchies.2) Dans le cas du problème de multicast avec une seule demande dans des réseaux partiellement équipés de diviseurs de lumière, nous proposons une heuristique efficace dont les résultats font le compromis entre la consommation de longueur d'onde, le coût total, et le délai de bout-en-bout.3) Dans le même cas mais dans des réseaux non équipés de diviseurs de lumière, nous prouvons la NP-difficulté, exprimons les problèmes au moyen d'un programme linéaire (ILP) pour trouver les solutions exactes et proposons plusieurs heuristiques pour calculer de bonnes solutions.4) Pour le cas de demandes multicast multiples, nous nous concentrons sur les modèles de trafic statiques dans des réseaux partiellement équipés de diviseurs mais sans convertisseurs de longueur d'onde. Tout d'abord nous proposons une formulation ILP sur la base de hiérarchies optiques afin de rechercher la solution optimale. Ensuite, utilisant un modèle de graphe en couches, nous développons plusieurs heuristiques adaptatives pour calculer des hiérarchies optiques de solutions approximatives. Ces algorithmes adaptatifs surpassent les techniques de routage existants pour minimiser la probabilité de blocage.Dans l'ensemble, la thèse souligne que les solutions optimales pour les problèmes de l'AOMR considérés correspondent à des hiérarchies, que ce soit pour une seule demande ou des demandes multiples. / Over the past decade, network traffic levels experienced an explosive growth at about double amount in approximately every thirty months. The sources accounting for this growth come from numerous high-speed applications (e.g., video-on-demand, high-definition television) which involve the data transmission in multicast groups. To realize optical multicasting, optical routers should have light splitters to split light signals and wavelength converters to change the wavelengths wherever needed. However, the splitting reduces the energy of the output signal which in turn requires the costly power amplification or regeneration. Wavelength converters are also immature to be deployed widely in current optical technologies. Consequently, in all-optical networks, routers are often heterogeneous in their processing units, which challenges the routing. Therefore, it is crucial to design efficient multicast routing strategies at the backbone optical networks, in order to achieve cost-performance tradeoff solutions while satisfying the ever-increasing bandwidth demands and optical constraints.In this thesis, we investigate the all-optical multicast routing (AOMR) problems in heterogeneous optical networks. The heterogeneity mainly comes from the absence/presence of light splitters and wavelength converters and the uneven distribution of wavelengths in the network links. In general, AOMR problems are often NP-hard. The objective of the thesis is to analyze and formulate the problems, to search for the optimal solutions, and to propose efficient heuristics to solve the problems under different optical constraints. Both possible contexts, i.e., single-multicast request and multiple-multicast requests, are examined. All the reported results in the thesis are supported by extensive and careful simulations. The major contributions can be summarized as follows.1) We identify the optimal route structures for AOMR problems under heterogeneous mesh WDM networks. As shown in the thesis, the optimal solutions are no longer based on conventional light-trees, but a more general tree-like structure called hierarchy. Some forms of hierarchy realized for WDM multicasting are light-trails, light-hierarchies, light-spider hierarchies and a set of these light-structures. The exact and heuristic algorithms proposed in the thesis are mainly based on hierarchy. 2) For single-multicast with sparse-splitting case, we propose an efficient heuristic algorithm to produce a good tradeoff solution among wavelength consumption, channel total cost and end-to-end delay.3) For single-multicast with non-splitting case, we prove the NP-hardness, identify the optimal solution as a set of light-spider hierarchies, formulate the problems by means of Integer Linear Program (ILP) formulations to find the exact solution, and propose several cost-effective heuristic algorithms to compute the approximate solutions. 4) For the case with multiple-multicast requests, we focus on static traffic patterns under sparse-splitting without wavelength conversion case. First, an ILP formulation based on light-hierarchies is proposed to search for the optimal solution. By applying the layered graph model, we then develop several adaptive heuristic algorithms to compute light-hierarchies for approximate solutions. These adaptive algorithms outperform the existing fixed routing ones in minimizing the blocking probability. Overall, the thesis points out that the optimal solutions for heterogeneously constrained AOMR problems correspond to hierarchies, regardless of request multiplicity consideration.

Le travail que nous développons dans le cadre de cette thèse s'articule autour des problèmes de recherche de structure de recouvrement de graphes sous contrainte sur le degré des sommets. Comme l'arbre de recouvrement couvre les sommets d'un graphe connexe avec un minimum de liens, il est généralement proposé comme solution à ce type de problèmes. Cependant, pour certaines applications telles que le routage dans les réseaux optiques, les solutions ne sont pas nécessairement des sous-graphes. Nous supposons dans cette thèse que la contrainte sur le degré est due à une capacité limitée instantanée des sommets et que la seule exigence sur le recouvrement est sa connexité. Dans ce cas, la solution peut être différente d'un arbre. Nous reformulons ces problèmes de recouvrement en nous appuyant sur une extension du concept d'arbre appelée hiérarchie de recouvrement. Notre objectif principal est de démontrer son intérêt vis-à-vis de l'arbre en termes de faisabilité et de coût du recouvrement. Nous considérons deux types de contraintes sur le degré : des bornes sur le degré des sommets ou une borne sur le nombre de sommets de branchement et cherchons dans les deux cas un recouvrement de coût minimum. Nous illustrons aussi l'applicabilité des hiérarchies en étudiant un problème prenant davantage en compte la réalité du routage optique. Pour ces différents problèmes NP-difficiles, nous montrons, tant sur le coût des solutions optimales que sur la garantie de performance des solutions approchées, l'intérêt des hiérarchies de recouvrement. Ce constat se voit conforté par des expérimentations sur des graphes aléatoires. / The work conducted in this thesis is focused on the minimum spanning problems in graphs under constraints on the vertex degrees. As the spanning tree covers the vertices of a connected graph with a minimum number of links, it is generally proposed as a solution for this kind of problems. However, for some applications such as the routing in optical networks, the solution is not necessarily a sub-graph. In this thesis, we assume that the degree constraints are due to a limited instantaneous capacity of the vertices and that the only pertinent requirement on the spanning structure is its connectivity. In that case, the solution may be different from a tree. We propose the reformulation of this kind of spanning problems. To find the optimal coverage of the vertices, an extension of the tree concept called hierarchy is proposed. Our main purpose is to show its interest regarding the tree in term of feasibility and costs of the coverage. Thus, we take into account two types of degree constraints: either an upper bound on the degree of vertices and an upper bound on the number of branching vertices. We search a minimum cost spanning hierarchy in both cases. Besides, we also illustrate the applicability of hierarchies by studying a problem that takes more into account the reality of the optical routing. For all those NP-hard problems, we show the interest of the spanning hierarchy for both costs of optimal solutions and performance guarantee of approximate solutions. These results are confirmed by several experimentations on random graphs.