A HEURISTIC ALGORITHM FOR SURVIVABLE MAPPING IN IP-OVER-WDM NETWORKS

摘要

Survivability is an important issue in IP-over-WDM networks. 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 disconnect 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 mapping 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.