Designing Hypergraph Layouts to GMPLS Routing Strategies

Jean-Claude Bermond 1 David Coudert 1 Joanna Moulierac 1 Stéphane Pérennes 1 Fernando Solano Donado 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
Abstract : All-Optical Label Switching (AOLS) is a new technology that performs packet forwarding without any Optical-Electrical-Optical (OEO) conversions. In this paper, we study the problem of routing a set of requests in AOLS networks using GMPLS technology, with the aim of minimizing the number of labels required to ensure the forwarding. We first formalize the problem by associating to each routing strategy a logical hypergraph whose hyperarcs are dipaths of the physical graph, called tunnels in GMPLS terminology. Such a hypergraph is called a hypergraph layout, to which we assign a cost function given by its physical length plus the total number of hops traveled by the traffic. Minimizing the cost of the design of an AOLS network can then be expressed as finding a minimum cost hypergraph layout. We prove hardness results for the problem, namely for general directed networks we prove that it is NP- hard to find a C log n-approximation, where C is a a positive constant and n is the number of nodes of the network. For symmetric directed networks, we prove that the problem is APX-hard. These hardness results hold even is the traffic instance is a partial broadcast. On the other hand, we provide an O(log n)- approximation algorithm to the problem for a general symmetric network. Finally, we focus on the case where the physical network is a path, providing a polynomial-time dynamic programming algorithm for a bounded number of sources, thus extending the algorithm given in [2] for a single source.
Type de document :
Communication dans un congrès
SIROCCO, May 2009, Piran, Slovenia. 2009
Liste complète des métadonnées

https://hal.inria.fr/inria-00428685
Contributeur : Joanna Moulierac <>
Soumis le : jeudi 29 octobre 2009 - 13:48:11
Dernière modification le : lundi 4 décembre 2017 - 15:14:09
Document(s) archivé(s) le : jeudi 17 juin 2010 - 18:40:24

Fichier

BCM_09_camera_ready_13May.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00428685, version 1

Collections

Citation

Jean-Claude Bermond, David Coudert, Joanna Moulierac, Stéphane Pérennes, Fernando Solano Donado. Designing Hypergraph Layouts to GMPLS Routing Strategies. SIROCCO, May 2009, Piran, Slovenia. 2009. 〈inria-00428685〉

Partager

Métriques

Consultations de la notice

318

Téléchargements de fichiers

99