HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

GMPLS Routing Strategies based on the Design of Hypergraph Layouts

Jean-Claude Bermond 1 David Coudert 1, * Joanna Moulierac 1 Stéphane Pérennes 1 Ignasi Sau Valls 1, 2 Fernando Solano Donado 3
* Corresponding author
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - 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 hyperedges 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 C log n hardness for directed networks and non-existence of PTAS for undirected networks, where C is a a positive constant and n is the number of nodes of the network. 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 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 of [BCM+09b] for a single source.
Complete list of metadata

Contributor : David Coudert Connect in order to contact the contributor
Submitted on : Wednesday, February 11, 2009 - 3:19:36 PM
Last modification on : Friday, February 4, 2022 - 3:20:09 AM
Long-term archiving on: : Friday, October 12, 2012 - 11:40:36 AM


Files produced by the author(s)


  • HAL Id : inria-00360576, version 1



Jean-Claude Bermond, David Coudert, Joanna Moulierac, Stéphane Pérennes, Ignasi Sau Valls, et al.. GMPLS Routing Strategies based on the Design of Hypergraph Layouts. [Research Report] RR-6842, INRIA. 2009. ⟨inria-00360576⟩



Record views


Files downloads