Efficient implementations of heuristics for routing and wavelength assignment
Thiago F. Noronha(tfninf.puc-rio.br)
Abstract: The problem of Routing and Wavelength Assignment in Wavelength Division Multiplexing (WDM) optical networks consists in routing a set of lightpaths and assigning a wavelength to each of them, such that lightpaths whose routes share a common fiber are assigned to different wavelengths. When the objective is to minimize the total number of wavelengths used, this problem is NP-hard. The current state-of-the-art heuristics were proposed in 2007 by Skorin-Kapov. The solutions provided by these heuristics were near-optimal. However, the associated running times reported were high. In this paper, we propose efficient implementations of these heuristics and reevaluate them on a broader set of testbed instances.
Keywords: Algorithm engineering, routing and wavelength assignment, heuristics.
Category 1: Applications -- OR and Management Sciences (Telecommunications )
Category 2: Combinatorial Optimization
Citation: AT&T Labs Technical Report TD-7BBTGY, AT&T Labs Research, Florham Park, NJ 08932 USA, 2008.
Entry Submitted: 01/29/2008
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|