A practical approach to operating survivable WDM networks

Murari Sridharan, Murti V. Salapaka, Arun K. Somani

Research output: Contribution to journalArticlepeer-review

102 Scopus citations


Several methods have been developed for joint working and spare capacity planning in survivable wavelength-division-multiplexing (WDM) networks. These methods have considered a static traffic demand and optimized the network cost assuming various cost models and survivability paradigms. Our interest primarily lies in network operation under dynamic traffic. We formulate various operational phases in survivable WDM networks as a single integer linear programming (ILP) optimization problem. This common framework avoids service disruption to the existing connections. However, the complexity of the optimization problem makes the formulation applicable only for network provisioning and offline reconfiguration. The direct use of this method for online reconfiguration remains limited to small networks with few tens of wavelengths. Our goal in this paper is to develop an algorithm for fast online reconfiguration. We propose a heuristic algorithm based on LP relaxation technique to solve this problem. Since the ILP variables are relaxed, we provide a way to derive a feasible solution from the relaxed problem. The algorithm consists of two steps. In the first step, the network topology is processed based on the demand set to be provisioned. This preprocessing step is done to ensure that the LP yields a feasible solution. The preprocessing step in our algorithm is based on: a) the assumption that in a network, two routes between any given node pair are sufficient to provide effective fault tolerance and b) an observation on the working of the ILP for such networks. In the second step, using the processed topology as input, we formulate and solve the LP problem. Interestingly, the LP relaxation heuristic yielded a feasible solution to the ILP in all our experiments. We provide insights into why the LP formulation yields a feasible solution to the ILP. We demonstrate the use of our algorithm on practical size backbone networks with hundreds of wavelengths per link. The results indicate that the run time of our heuristic algorithm is fast enough (in order of seconds) to be used for online reconfiguration.

Original languageEnglish (US)
Pages (from-to)34-46
Number of pages13
JournalIEEE Journal on Selected Areas in Communications
Issue number1
StatePublished - Jan 2002

Bibliographical note

Funding Information:
Manuscript received February 22, 2001; revised July 31, 2001. This work was supported in part by the National Science Foundation under Grant ANI 9973102, in part by the Defense Advanced Research Projects Agency (cofunded by the National Security Agency) under Grant N66001-00-1-8949, and in part by the National Science Foundation under Grant ECS 9733802.


  • Heuristic
  • Integer linear programming (ILP)
  • Linear programming (LP) relaxation
  • Optimization
  • Protection
  • Restoration
  • Survivability
  • Wavelength-division multiplexing (WDM)


Dive into the research topics of 'A practical approach to operating survivable WDM networks'. Together they form a unique fingerprint.

Cite this