8485 articles  [english version]

inria-00158341, version 2

## Hardness and Approximation of Traffic Grooming

Omid Amini () a1, Stéphane Pérennes () 1, Ignasi Sau 1

N° RR-6236 (2007)

Résumé : Traffic grooming is a central problem in optical networks. It refers to pack low rate signals into higher speed streams, in order to improve bandwidth utilization and reduce network cost. In WDM networks, the most accepted criterion is to minimize the number of electronic terminations, namely the number of SONET Add-Drop Multiplexers (ADMs). In this article we focus on ring and path topologies. On the one hand, we provide the first inapproximability result for \textsc{Traffic Grooming} for fixed values of the grooming factor $g$, answering affirmatively the conjecture of Chow and Lin (\emph{Networks, 44:194-202, 2004}). More precisely, we prove that \textsc{Ring Traffic Grooming} for fixed $g\geq 1$ and \textsc{Path Traffic Grooming} for fixed $g\geq 2$ are \textsc{APX}-complete. That is, they do not accept a PTAS unless $\textsc{P}=\textsc{NP}$. Both results rely on the fact that finding the maximum number of edge-disjoint triangles in a graph (and more generally cycles of length $2g+1$ in a graph of girth $2g+1$) is \textsc{APX}-complete. On the other hand, we provide a polynomial-time approximation algorithm for \textsc{Ring} and \textsc{Path Traffic Grooming}, based on a greedy cover algorithm, with an approximation ratio independent of $g$. Namely, the approximation guarantee is $\mathcal{O}(n^{1/3} \log^2 n)$ for any $g \geq 1$, $n$ being the size of the network. This is useful in practical applications, since in backbone networks the grooming factor is usually greater than the network size. As far as we know, this is the first approximation algorithm with this property. Finally, we improve this approximation ratio under some extra assumptions about the request graph.

• a –  Polytechnique - X
• 1 :  MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
• INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
• Domaine : Informatique/Complexité
Informatique/Algorithme et structure de données
Informatique/Réseaux et télécommunications
• Mots-clés : Approximation Algorithms – Traffic Grooming – Optical Networks – SONET ADM – Apx-hardness – PTAS – Hardness of Approximating
• Référence interne : RR-6236
• Versions disponibles :  v1 (28-06-2007) v2 (29-06-2007) v3 (04-07-2007)

• inria-00158341, version 2
• oai:hal.inria.fr:inria-00158341
• Contributeur :
• Soumis le : Vendredi 29 Juin 2007, 11:44:57
• Dernière modification le : Vendredi 29 Juin 2007, 11:45:41