DROP COST AND WAVELENGTH OPTIMAL TWO-PERIOD GROOMING WITH RATIO 4∗

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
Abstract : We study grooming for two-period optical networks, a variation of the traffic grooming problem for WDM ring networks introduced by Colbourn, Quattrocchi, and Syrotiuk. In the two-period grooming problem, during the first period of time there is all-to-all uniform traffic among $n$ nodes, each request using $1/C$ of the bandwidth; and during the second period, there is all-to-all uniform traffic only among a subset $V$ of $v$ nodes, each request now being allowed to use $1/C'$ of the bandwidth, where $C' < C$. We determine the minimum drop cost (minimum number of ADMs) for any $n,v$ and $C=4$ and $C' \in \{1,2,3\}$. To do this, we use tools of graph decompositions. Indeed the two-period grooming problem corresponds to minimizing the total number of vertices in a partition of the edges of the complete graph $K_n$ into subgraphs, where each subgraph has at most $C$ edges and where furthermore it contains at most $C'$ edges of the complete graph on $v$ specified vertices. Subject to the condition that the two-period grooming has the least drop cost, the minimum number of wavelengths required is also determined in each case.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2010, 24 (2), pp.400-419
Domaine :

https://hal.inria.fr/inria-00505516
Contributeur : Jean-Claude Bermond <>
Soumis le : vendredi 23 juillet 2010 - 22:26:25
Dernière modification le : lundi 24 janvier 2011 - 21:12:47
Document(s) archivé(s) le : lundi 25 octobre 2010 - 12:04:21

Fichier

SIAM74419.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

• HAL Id : inria-00505516, version 1

Citation

Jean-Claude Bermond, Charles J. Colbourn, Lucia Gionfriddo, Gaetano Quattrocchi, Ignasi Sau. DROP COST AND WAVELENGTH OPTIMAL TWO-PERIOD GROOMING WITH RATIO 4∗. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2010, 24 (2), pp.400-419. <inria-00505516>

Consultations de
la notice

233

Téléchargements du document