Techreport,
On the design of multifiber WDM networks
Research Report, INRIA Research Report 4244, (August 2001)
Abstract
In this paper, we address multifiber optical networks
with Wavelength Division Multiplexing (WDM). Assuming that the
lightpaths use the same wavelength from source to destination, we
extend the definition of the well-known Wavelength Assignment Problem
(WAP), to the case where there are $k$ fibers per link, and $w$
wavelengths per fiber are available. We then develop a new model for
the $(k,w)$-WAP, based on conflict hypergraphs -Conflict hypergraphs
more accurately capture the lightpath interdependencies- ,
generalizing the conflict graphs used for single-fiber networks. By
relating the $(k,w)$-WAP with the hypergraph coloring problem, we
prove that the former is \npc, and present further results with
respect to the complexity of that problem. Finally, we analyze the
practical performances of two methodologies based on hypergraph
coloring, on existing backbone networks in Europe and in the USA. The
first relies on an integer programming formulation and the second
consists of a heuristic based on a randomized algorithm. We consider
the two natural optimization problems that arise from the $(k,w)$-WAP
: the problem of minimizing $k$ given $w$, and that of minimizing $w$
given $k$
