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. The authors first introduce a new concept of piecewise survivability, which makes the problem much easier in practice (Although still NP-complete), and allows one to formally prove that a given survivable mapping does or does not exist.