GMPLS Label Space Minimization through Hypergraph Layouts

Jean-Claude Bermond 1 David Coudert 1 Joanna Moulierac 1 Stéphane Pérennes 1 Ignasi Sau 2 Fernando Solano Donado 3
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 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : All-Optical Label Switching (AOLS) is a new technology that performs packet forwarding without any optical-electrical-optical 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, called a hypergraph layout, whose hyperarcs are dipaths of the physical graph, called tunnels in GMPLS terminology. We define a cost function for the hypergraph layout, depending on its total length plus its total hop count. 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 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 if the traffic instance is a partial broadcast. On the other hand, we provide approximation algorithms, in particular an O(log n)-approximation for symmetric directed networks. Finally, we focus on the case where the physical network is a directed path, providing a polynomial-time dynamic programming algorithm for a fixed number k of sources running in O(n^{k+2}) time.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2012, 444, pp.3-16. <10.1016/j.tcs.2012.01.033>
Liste complète des métadonnées

https://hal.inria.fr/hal-00706260
Contributeur : David Coudert <>
Soumis le : samedi 9 juin 2012 - 16:10:04
Dernière modification le : mercredi 20 janvier 2016 - 14:58:25
Document(s) archivé(s) le : vendredi 30 novembre 2012 - 13:15:26

Fichier

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

Identifiants

Collections

Citation

Jean-Claude Bermond, David Coudert, Joanna Moulierac, Stéphane Pérennes, Ignasi Sau, et al.. GMPLS Label Space Minimization through Hypergraph Layouts. Theoretical Computer Science, Elsevier, 2012, 444, pp.3-16. <10.1016/j.tcs.2012.01.033>. <hal-00706260>

Partager

Métriques

Consultations de
la notice

399

Téléchargements du document

142