Wavelength Assignment in Multi-Fiber WDM Networks by Generalized Edge Coloring

Arie M.C.A. Koster (kosterzib.de)

Abstract: In this paper, we study wavelength assignment problems in multi-fiber WDM networks. We focus on the special case that all lightpaths have at most two links. This in particular holds in case the network topology is a star. As the links incident to a specific node in a meshed topology form a star subnetwork, results for stars are also of interest for general meshed topologies.

We show that wavelength assignment with at most two links per lightpath can be modeled as a generalized edge coloring problem. By this relation, we show that for a network with an even number of fibers at all links and at most two links per lightpath, all lightpaths can be assigned a wavelength without conversion. Moreover, we derive a lower bound on the number of lightpaths to be converted for networks with arbitrary numbers of fibers at the links.

A comparison with linear programming lower bounds reveals that the bounds coincide for problems with at most two links per lightpath. For meshed topologies, the cumulative lower bound over all star subnetworks equals the best known solution value for all realistic wavelength assignment instances available, by this proving optimality.

Keywords: Wavelength Assignment, Optical Networks, Graph Theory, Combinatorial Optimization, Integer Programming

Category 1: Applications -- OR and Management Sciences (Telecommunications )

Category 2: Combinatorial Optimization (Graphs and Matroids )

Category 3: Network Optimization

Citation: ZIB Report 05-13, http://www.zib.de/ An extended abstract will be published in the proceedings of the International Network Optimization Conference, INOC 2005, Lissabon, Portugal.

Download: [Compressed Postscript][PDF]

Entry Submitted: 03/17/2005
Entry Accepted: 03/22/2005
Entry Last Modified: 03/17/2005

Modify/Update this entry