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).

Published in:
IEEE Journal on Selected Areas in Communications, 25, 5, 922 - 933
Other identifiers:

Note: The status of this file is: EPFL only

 Record created 2007-11-15, last modified 2018-03-18

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)