標題: A Lagrangean relaxation based near-optimal algorithm for advance lightpath reservation in WDM networks
作者: Lee, Steven S. W.
Chen, Alice
Yuang, Maria C.
資訊工程學系
Department of Computer Science
關鍵字: Advance lightpath reservation;Call admission control;Routing and wavelength assignment;Lagrangean relaxation
公開日期: 1-二月-2010
摘要: 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.
URI: http://dx.doi.org/10.1007/s11107-009-0215-9
http://hdl.handle.net/11536/5910
ISSN: 1387-974X
DOI: 10.1007/s11107-009-0215-9
期刊: PHOTONIC NETWORK COMMUNICATIONS
Volume: 19
Issue: 1
起始頁: 103
結束頁: 109
顯示於類別:期刊論文


文件中的檔案:

  1. 000273480400011.pdf