Algorithmique et optimisation de réseaux de communications optiques

This thesis deals with optical communication networks, especially free space optical networks and optical fiber networks.First we address the design of free space optical networks using the Optical Transpose Interconnection System (OTIS) architecture defined in [MMHE93]. We give a model of these networks with H(p,q,d) digraphs which we characterize. We take a specific interest in isomorphisms between these digraphs and well known digraphs (de Bruijn, Kautz and other alphabet graphs). We develop a family of alphabet digraphs which includes a large number of digraphs isomorphic to the de Bruijn and use it to obtain an optimal design of the de Bruijn with OTIS, in terms of minimizing the number of lenses. Then, we study a family of networks modeled by directed hypergraphs and called stack-Kautz, for which we provide routing algorithms and control protocols.In a second part we address the problem of WDM network survivability using protection. This problem consists in using precomputed and dedicated resources in order to ensure traffic continuity if a bundle of fibers breaks down. We describe numerous strategies for protecting the instance and the network. We go more deeply into subnetwork protection where protection resources are shared by sets of request describing a specific subnetwork (circuit). We give an optimal solution to this problem when the network is a cycle and the requests realize the All-to-All pattern.Dans cette thèse, nous nous intéressons aux réseaux de communications optiques avec d'une part des réseaux en espace libre optique et d'autre part des réseaux à fibres optiques.Dans un premier temps, nous étudions l'implantation en espace libre optique de réseaux de communications à l'aide de l'architecture OTIS (Optical Transpose Interconnection System), proposé dans [MMHE93]. Nous proposons une modélisation de ces réseaux par les graphes H(p,q,d) que nous cherchons ensuite à caractériser. Nous étudions en particulier les isomorphismes entre ces graphes et des graphes connus (de Bruijn, Kautz et autres graphes à alphabet). Nous développons une famille de graphes à alphabet contenant de nombreux graphes isomorphes au de Bruijn, que nous utilisons pour obtenir une implantation optimale, au sens de la minimisation du nombre de lentilles, du de Bruijn avec OTIS. Nous étudions aussi une famille de réseaux modélisés par des hypergraphes orientés, appelées stack-Kautz, pour laquelle nous donnons un algorithme de routage et des protocoles de contrôles.Dans un deuxième temps, nous nous intéressons au problème de la sécurisation par protection dans les réseaux WDM, qui consiste à utiliser des ressources prédéterminées et dédiées pour assurer la continuité du trafic lors de la rupture d'un faisceau de fibres dans le réseau. Nous décrivons de nombreuses stratégies de protection de l'instance et du réseau. Nous étudions plus particulièrement la protection par sous-réseaux qui consiste au partage de ressources de protection par un ensemble de requêtes formant un sous-réseau particulier (circuit). Nous donnons une solution optimale au problème de la protection par sous-réseaux dans le cas où le réseau est un cycle et les requêtes représentent un échange total