A Lagrangean relaxation based near-optimal algorithm for advance lightpath reservation in WDM networks

S. S W Lee, Alice Chen, Maria C. Yuang

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


Advance lightpath reservation is a new research topic for connecting high-speed computer servers in lambda grid applications and for dynamic lightpath provisioning in the future optical internet. In such networks, users make call requests in advance to reserve network resources for communications. The challenge of the problem comes from how to jointly determine call admission control, lightpath routing, and wavelength assignment. In this paper, we propose an efficient Lagrangean relaxation (LGR) approach to resolve advance lightpath reservation for multi-wavelength optical networks. The task is first formulated as a combinatorial optimization problem in which the revenue from accepting call requests is to be maximized. The LGR approach performs constraint relaxation and derives an upper-bound solution index according to a set of Lagrangean multipliers generated through subgradient-based iterations. In parallel, using the generated Lagrangean multipliers, the LGR approach employs a new heuristic algorithm to arrive at a near-optimal solution. By upper bounds, we assess the performance of LGR with respect to solution accuracy. We further draw comparisons between LGR and three heuristic algorithms-Greedy, First Come First Serve, and Deadline First, via experiments over the widely-used NSFNET network. Numerical results demonstrate that LGR outperforms the other three heuristic approaches in gaining more revenue by receiving more call requests.

Original languageEnglish
Pages (from-to)103-109
Number of pages7
JournalPhotonic Network Communications
Issue number1
StatePublished - 1 Feb 2010


  • Advance lightpath reservation
  • Call admission control
  • Lagrangean relaxation
  • Routing and wavelength assignment

Fingerprint Dive into the research topics of 'A Lagrangean relaxation based near-optimal algorithm for advance lightpath reservation in WDM networks'. Together they form a unique fingerprint.

Cite this