Survivable Routing of Mesh Topologies in IP-over-WDM Networks by Recursive Graph Contraction
Authors:
- 29 May 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 25 (5) , 922-933
Abstract
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
This publication has 12 references indexed in Scilit:
- Characterization of Failures in an Operational IP Backbone NetworkIEEE/ACM Transactions on Networking, 2008
- Survivable routing in IP-over-WDM networks: An efficient and scalable local search algorithmOptical Switching and Networking, 2005
- On survivable routing of mesh topologies in IP-over-WDM networks2005
- Survivable mapping algorithm by ring trimming (SMART) for large IP-over-WDM networks2004
- Efficient routing and wavelength assignment for reconfigurable WDM networks with wavelength converters2004
- Increasing the robustness of IP backbones in the absence of optical level protection2004
- Design of a survivable WDM photonic network2002
- Survivable embedding of logical topologies in WDM ring networksInformation Sciences, 2002
- IP restoration vs. WDM protection: is there an optimal choice?IEEE Network, 2000
- Design protection for WDM optical networksIEEE Journal on Selected Areas in Communications, 1998