Approximations for All-to-all Uniform Traffic Grooming on Unidirectional Ring

Jean-Claude Bermond 1 David Coudert 1 Benjamin Lévêque 2
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 G-SCOP_OC - OC
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
Abstract : Traffic grooming in a WDM network consists of assigning to each request (lightpath) a wavelength with the constraint that a given wavelength can carry at most C requests or equivalently a request uses 1/C of the bandwidth. C is known as the grooming ratio. A request (lightpath) needs two SONET add-drop multiplexers (ADMs) at each end node; using grooming, different requests can share the same ADM. The so called traffic grooming problem consists of minimizing the total number of ADMs to be used (in order to reduce the overall cost of the network). Here we consider the traffic grooming problem in WDM unidirectional rings which has been recently shown to be APX-hard and for which no constant approximations are known. We furthermore suppose an all to all uniform unitary traffic. This problem has been optimally solved for specific values of the grooming ratio, namely C = 2, 3, 4, 5, 6. In this paper we present various simple constructions for the grooming problem providing approximation of the total number of ADMs with a small constant ratio. For that we use the fact that the problem corresponds to a partition of the edges of the complete graph into subgraphs, where each subgraph has at most C edges and where the total number of vertices has to be minimized.
Type de document :
Article dans une revue
Journal of Interconnection Networks, World Scientific Publishing, 2008, 9 (4), pp.471-486. <10.1142/S0219265908002394>
Liste complète des métadonnées


https://hal.inria.fr/inria-00429217
Contributeur : David Coudert <>
Soumis le : dimanche 1 novembre 2009 - 21:46:10
Dernière modification le : mercredi 24 juin 2015 - 13:13:07
Document(s) archivé(s) le : mardi 16 octobre 2012 - 13:05:30

Fichier

BCL-JOIN08.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jean-Claude Bermond, David Coudert, Benjamin Lévêque. Approximations for All-to-all Uniform Traffic Grooming on Unidirectional Ring. Journal of Interconnection Networks, World Scientific Publishing, 2008, 9 (4), pp.471-486. <10.1142/S0219265908002394>. <inria-00429217>

Partager

Métriques

Consultations de
la notice

271

Téléchargements du document

83