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