archives

A New Survivable Mapping Problem in IP-over-WDM Networks


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Liu, Chang and Ruan, Lu (2005) A New Survivable Mapping Problem in IP-over-WDM Networks. Technical Report, Computer Science, Iowa State University.

Full text available as:Adobe PDF

Abstract

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.

Subjects:Computer Systems Organization: COMPUTER-COMMUNICATION NETWORKS
ID code:00000390
Deposited by:Chang Liu on 02 November 2005



Contact site administrator at: ssg@cs.iastate.edu