A Heuristic Algorithm for Survivable Mapping in IP-Over-WDM Networks

L. Ruan and C. Liu (USA)


Network survivability, survivable mapping, IP-over-WDM


Survivability is an important issue in IP-over-WDM net works. IP layer failure recovery is possible only if the IP topology is mapped onto the WDM topology in a surviv able way, i.e., the failure of any single fiber will not dis connect the IP topology. This problem has been proven NP-hard in [1]. And an integer linear programming (ILP) formulation that solves this problem is provided in [2]. We present a polynomial time heuristic algorithm for the sur vivable mapping problem named Map-and-Fix. The key idea of Map-and-Fix is to first compute a mapping that is likely to be survivable or close to survivable; if the mapping is not survivable, then it is transformed to a survivable map ping by rerouting some of the IP links. Simulation studies showed that Map-and-Fix runs much faster than ILP and can find survivable mappings for most of the test cases. In addition, the obtained mappings are close to optimal.

Important Links:

Go Back