Computer Systems Organization
We introduce a new version of the widely studied survivable mapping problem in IP-over-WDM networks. The new problem allows augmenting the given logical topology and is described as follows: given a physical topology and a logical topology, compute a survivable logical topology that contains the given logical topology such that the minimal survivable mapping cost for the result logical topology is minimized. The problem is significant for two reasons: 1) If there does not exist a survivable mapping for the given logical topology, we can add logical links to the given logical topology to make it survivable; 2) Even if a survivable mapping for the given logical topology can be found, it is still possible to reduce the minimal survivable mapping cost by adding logical links selectively. We first prove the existence of a solution to the problem, then provide a straightforward Integer Linear Program (ILP) formulation for the problem. Moreover, we present a theoretical result that leads to a simple NP-hardness proof of the problem and an improved ILP formulation. Simulation results demonstrate the significance of both the new survivable mapping problem and the theoretical result.