Efficient implementations of heuristics for routing and wavelength assignment

Thiago F. Noronha(tfninf.puc-rio.br)
Mauricio G. C. Resende(mgcrresearch.att.com)
Celso C. Ribeiro(celsoic.uff.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.

Download: [PDF]

Entry Submitted: 01/29/2008
Entry Accepted: 01/30/2008
Entry Last Modified: 01/29/2008

Modify/Update this entry