Traffic Grooming on the Path

Jean-Claude Bermond 1 Laurent Braud 2 David Coudert 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
2 ENS Lyon - École normale supérieure - Lyon
Abstract : In a WDM network, routing a request consists in assigning it a route in the physical network and a wavelength. If each request uses at most 1/C of the bandwidth of the wavelength, we will say that the grooming factor is C . That means that on a given edge of the network we can groom (group) at most C requests on the same wavelength. With this constraint the ob jective can be either to minimize the number of wavelengths (related to the transmission cost) or minimize the number of Add Drop Multiplexer (shortly ADM) used in the network (related to the cost of the nodes). Here we consider the case where the network is a path on N nodes, PN . Thus the routing is unique. For a given grooming factor C minimizing the number of wavelengths is an easy problem, well known and related to the load problem. But minimizing the number of ADM's is NP-complete for a general set of requests and no results are known. Here we show how to model the problem as a graph partition problem and using tools of design theory we completely solve the case where C = 2 and where we have a static uniform all-to-all traffic (requests being all pairs of vertices).
Type de document :
Communication dans un congrès
12th International Colloquium on Structural Information and Communication Complexity (SIROCCO), May 2005, Mont Saint-Michel, France. Springer, pp.34-48, 2005, Lecture Notes in Computer Science. 〈10.1007/11429647_5〉
Liste complète des métadonnées
https://hal.inria.fr/inria-00429172
Contributeur : David Coudert <>
Soumis le : dimanche 1 novembre 2009 - 14:23:57
Dernière modification le : lundi 23 avril 2018 - 10:52:05
Document(s) archivé(s) le : jeudi 17 juin 2010 - 18:54:00

Fichier

BBC-Sirocco05.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

UNICE | INRIA | I3S | ENS-LYON | TDS-MACS | UNIV-COTEDAZUR

Citation

Jean-Claude Bermond, Laurent Braud, David Coudert. Traffic Grooming on the Path. 12th International Colloquium on Structural Information and Communication Complexity (SIROCCO), May 2005, Mont Saint-Michel, France. Springer, pp.34-48, 2005, Lecture Notes in Computer Science. 〈10.1007/11429647_5〉. 〈inria-00429172〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

295

Téléchargements de fichiers

157

Contact


archive-ouverte@inria.fr