A Lagrangean relaxation-based approach for routing and wavelength assignment in multigranularity optical WDM networks

Steven S W Lee*, Maria C. Yuang, Po-Lung Tien, Shih Hsun Lin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


Optical wavelength-division multiplexed (WDM) networks often include optical cross-connects with multigranularity switching capability, such as switching on a single lambda, a waveband, or an entire fiber basis. In addition, it has been shown that routing and wavelength assignment (RWA) in an arbitrary mesh WDM network is an NP-complete problem. In this paper, we propose an efficient approximation approach, called Lagrangean relaxation with heuristics (LRH), aimed to resolve RWA in multigranularity WDM networks particularly with lambda and fiber switches. The task is first formulated as a combinatorial optimization problem in which the bottleneck link utilization is to be minimized. The LRH approach performs constraint relaxation and derives a lower-bound solution index according to a set of Lagrangean multipliers generated through subgradient-based iterations. In parallel, using the generated Lagrangean multipliers, the LRH approach employs a new heuristic algorithm to arrive at a near-optimal upper-bound solution. With lower and upper bounds, we conduct a performance study on LRH with respect to accuracy and convergence speed under different parameter settings. We further draw comparisons between LRH and an existing practical approach via experiments over randomly generated and several well-known large sized networks. Numerical results demonstrate that LRH outperforms the existing approach in both accuracy and computational time complexity, particularly for larger sized networks.

Original languageEnglish
Pages (from-to)1741-1751
Number of pages11
JournalIEEE Journal on Selected Areas in Communications
Issue number9
StatePublished - Nov 2004


  • Combinatorial optimization problem
  • Lagrangean relaxation
  • Multigranularity switching capabilities
  • Routing and wavelength assignment (RWA)
  • Wavelength-division multiplexing (WDM)


Dive into the research topics of 'A Lagrangean relaxation-based approach for routing and wavelength assignment in multigranularity optical WDM networks'. Together they form a unique fingerprint.

Cite this