- English
- français
Survivable Routing of Mesh Topologies in IP-over-WDM Networks by Recursive Graph Contraction
Failure restoration at the IP layer in IP-over-WDM networks requires to map the IP topology on the WDM topology in such a way that a failure at the WDM layer leaves the IP topology connected. Such a mapping is called survivable. Finding a survivable mapping is known to be NP-complete, making it impossible in practice to assess the existence or absence of such a mapping for large networks. (i) We first introduce a new concept of piecewise survivability, which makes the problem much easier in practice (although still NP-complete), and allows us to formally prove that a given survivable mapping does or does not exist. (ii) Secondly, we show how to trace the vulnerable areas in the topology, and how to strengthen them to enable a survivable mapping. (iii) Thirdly, we give an efficient and scalable algorithm that finds a survivable mapping. In contrast to the heuristics proposed in the literature to date, our algorithm exhibits a number of provable properties (e.g., it guarantees the piecewise survivability) that are crucial for (i) and (ii).
Keywords: Optical communication ; wavelength division multiplexing ; survivability ; graph theory
Reference
- LCA-ARTICLE-2007-021
- doi:10.1109/JSAC.2007.070606
- View record in Web of Science
Record created on 2007-11-15, modified on 2012-03-21