A Lagrangean relaxation approach to routing and wavelength assignment for multi-granularity optical WDM networks

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

*此作品的通信作者

研究成果: Paper同行評審

31 引文 斯高帕斯(Scopus)

摘要

In this paper, we propose an efficient approximation approach, called Lagrangean Relaxation with Heuristics (LRH), aimed to resolve Routing and Wavelength Assignment (RWA) for multi-granularity WDM networks facilitating fiber, waveband, and lambda switching capabilities. 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 delineate the performance of LRH with respect to accuracy and convergence speed under different parameter settings. We further draw comparisons between LRH and a typical Linear Programming (LP) approach via experiments over the widely-used NSFNET and three randomly generated networks. Numerical results demonstrate that LRH outperforms the LP approach in both accuracy and computational time complexity particularly for larger sized networks.

原文English
頁面1936-1942
頁數7
DOIs
出版狀態Published - 11月 2004
事件GLOBECOM'04 - IEEE Global Telecommunications Conference - Dallas, TX, United States
持續時間: 29 11月 20043 12月 2004

Conference

ConferenceGLOBECOM'04 - IEEE Global Telecommunications Conference
國家/地區United States
城市Dallas, TX
期間29/11/043/12/04

指紋

深入研究「A Lagrangean relaxation approach to routing and wavelength assignment for multi-granularity optical WDM networks」主題。共同形成了獨特的指紋。

引用此