Algorithmique et optimisation dans les réseaux de télécommunications

The general contexts of my research activity are the connection oriented networks, either WDM (wavelength division multiplexing) optical network, or MPLS (Multi-protocol label switching), or wireless backhaul networks using microwave links. In such networks, I am interested in routing data flows, in aggregating low rate traffic streams into higher speed one, in updating the routing after traffic or topological modifications, and in ensuring the traffic continuity under single or multiple failures scenarios. To address these issues, I use a variety of tools from algorithmics, graph theory and combinatorial optimization. All results presented in this document are the result of collaborative work with members of the project-team MASCOTTE, colleagues from other universities (in France and abroad), and colleagues from France Telecom, Alcatel-Lucent and 3Roam. The introduction summarizes our work on routing, traffic grooming, fault tolerance and reconfiguration. It also summarizes more recent work on minimizing the number of labels in MPLS networks, the design of wireless backhaul networks, as well as the disjoint routing of particular set of requests. Then, I present in more details our work on traffic grooming in Chapter 3, on of shared risk resource groups in Chapter 4, and on the reconfiguration of routing in Chapter 5. Finally, Chapter 6 concludes this manuscript with perspectives for future researches.Le contexte général de mes travaux se situe dans les réseaux orientés connexions, que ce soit des réseaux optiques à multiplexage en longueur d'onde (WDM), des réseaux MPLS (multi-protocol label switching), ou encore des réseaux à faisceaux hertziens (wireless backhaul networks). Dans ces réseaux, je m'intéresse à router les flux d'information, à agréger des flux d'information bas débits dans des flux de plus hauts débits, à faire évoluer le routage en cas de variations dans la quantité de trafic à transporter ou dans la topologie du réseau, et à assurer la continuité du trafic en cas de panne simple ou multiple. Pour aborder ces questions, j'utilise des outils variés de l'algorithmique, de la théorie des graphes et de l'optimisation combinatoire. L'ensemble des résultats présentés dans ce document est le fruit de travaux collaboratifs avec les membres de l'équipe-projet MASCOTTE, des collègues d'autres universités, française ou étrangères, et des collègues de France Télécom, Alcatel-Lucent et 3Roam. L'introduction de ce manuscrit résume nos travaux sur le routage, le groupage de trafic, la tolérance aux pannes et la reconfiguration, ainsi que des travaux plus récents sur la minimisation du nombre d'étiquettes dans les réseaux MPLS, le dimensionnement de réseaux de collecte IP sans fil, et sur le routage disjoints d'ensembles particuliers de requêtes. Ensuite, je détaille nos travaux sur le groupage de trafic au travers d'un état de l'art dans le chapitre 3, nos contributions sur la notion de groupes de ressources partageant un risque dans le chapitre 4, et sur la reconfiguration de routages dans le chapitre 5. Le chapitre 6 conclut ce manuscrit en présentant avec quelques directions de recherches