- Title: “Towards Efficient and Fault-Tolerant Optical Networks: Complexity and Algorithms”
- When: October 30, 2015 — 14:30
- Where: Inria Sophia Antipolis, salle Euler Violet
- Committee:
- Jean-Claude Bermond, COATI, Inria/I3S-UNS, France
- David Coudert (Supervisor), COATI, Inria/I3S-UNS, France
- Alain Jean-Marie Inria / LIRMM, France
- Arie M.C.A. Koster (Referee), RWTH, Aachen, Germany
- Christian Laforest, ISIMA, LIMOS, Clermont-Ferrand, France
- Hervé Rivano, Inria, CITI Laboratory, INSA Lyon, France
- Yann Vaxès (Referee), LIF – UFR Sciences Luminy, Marseille, France
-
Abstract: We study in this thesis optimization problems with application in optical networks. The problems we consider are related to fault-tolerance and efficient resource allocation and the results we obtain are mainly related to the computational complexity of these problems.
The first part of this thesis is devoted to finding paths and disjoint paths. Finding a path is crucial in all types of networks in order to set up connections and finding disjoint paths is a common approach used to provide some degree of protection against failures in networks. We study these problems under different settings. We first focus on finding paths and vertex or link-disjoint paths in networks with asymmetric nodes, which are nodes with restrictions on their internal connectivity. Afterwards, we consider networks with star Shared Risk Link Groups (SRLGs) which are groups of links that might fail simultaneously due to a localized event. In these networks, we investigate the problem of finding SRLG-disjoint paths.
The second part of this thesis focuses on the problem of Routing and Spectrum Assignment (RSA) in Elastic Optical Networks (EONs). EONs are proposed as the new generation of optical networks and they aim at an efficient and flexible use of the optical resources. RSA is the key problem in EONs and it deals with allocating resources to requests under multiple constraints. We first study the static version of RSA in tree networks. Afterwards, we examine a dynamic version of RSA in which a non-disruptive spectrum defragmentation technique is used.
Finally, we present in the appendix another problem that has been studied during this thesis. It is a graph-theoretic problem referred to as minimum size tree-decomposition and it deals with the decomposition of graphs in a tree-like manner with the objective of minimizing the size of the tree. -
Keywords: Asymmetric nodes, forbidden transitions, shared risk link group, routing and spectrum assignment, tree-decomposition, complexity.
