On the design of Multifiber WDM Networks

A. Ferreira 1 Stéphane Pérennes A.W. Richa Hervé Rivano N. Stier
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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$.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00072343
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 8:28:34 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Sunday, April 4, 2010 - 11:04:44 PM

Identifiers

  • HAL Id : inria-00072343, version 1

Collections

Citation

A. Ferreira, Stéphane Pérennes, A.W. Richa, Hervé Rivano, N. Stier. On the design of Multifiber WDM Networks. RR-4244, INRIA. 2001. ⟨inria-00072343⟩

Share

Metrics

Record views

358

Files downloads

123