Logical topology augmentation for survivable mapping in IP-over-WDM networks

Survivability is an important issue in IP-over-WDM networks. IP layer failure recovery is only possible if the IP topology is mapped onto the WDM topology in a survivable way, i.e., the failure of any single fiber will not disconnect the IP topology. In A. Sen et al. (2002), it has been proven that to find a survivable mapping from a logical to a physical topology is NP-hard. In this paper, a new approach to tackle the inherent hardness of this problem is introduced. The basic idea is to augment the given logical topology using edges that appear in the physical topology such that the intersection of the logical and the physical topologies becomes 2-edge-connected. As a consequence, any shortest path mapping from the result logical topology to the physical topology is survivable. We first prove the correctness of this strategy and give a straightforward integer linear programming (ILP) formulation that minimizes the number of added logical links. Noticing that this graph augmentation problem is NP-hard, we then propose a heuristic algorithm. Simulation results show that this scheme provides a fast and effective alternative solution to the original survivable mapping problem by paying a price of a certain number of extra mapping costs. Meanwhile, another potential benefit is that non-survivable logical topologies can be fixed in this way. On the other hand, the performance of the heuristic augmentation algorithm is promising compared to that of the ILP formulation.