On the Hardness of Equal Shortest Path Routing

Frédéric Giroire 1 Stéphane Pérennes 1 Issam Tahiri 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In telecommunication networks packets are carried from a source s to a destination t on a path that is determined by the underlying routing protocol. Most routing protocols belong to the class of shortest path routing protocols. In such protocols, the network operator assigns a length to each link. A packet going from s to t follows a shortest path according to these lengths. For better protection and efficiency, one wishes to use multiple (shortest) paths between two nodes. Therefore the routing protocol must determine how the traffic from s to t is distributed among the shortest paths. In the protocol called ospf-ecmp (for Open Shortest Path First -Equal Cost Multiple Path) the traffic incoming at every node is uniformly balanced on all outgoing links that are on shortest paths. In that context, the operator task is to determine the "best" link lengths, toward a goal such as maximizing the network throughput for given link capacities. In this work, we show that the problem of maximizing even a single commodity flow for the ospf- ecmp protocol cannot be approximated within any constant factor ratio. Besides this main theorem, we derive some positive results which include polynomial-time approximations and an exponential-time exact algorithm. We also prove that despite their weakness, our approximation and exact algorithms are, in a sense, the best possible.
Type de document :
Communication dans un congrès
International Network Optimization Conference, May 2013, Tenerife, Spain. Elsevier, 41, pp.439-446, 2013, Electronic Notes in Discrete Mathematics. <10.1016/j.endm.2013.05.123>
Liste complète des métadonnées

https://hal.inria.fr/hal-00926348
Contributeur : Frédéric Giroire <>
Soumis le : jeudi 9 janvier 2014 - 14:42:17
Dernière modification le : lundi 5 octobre 2015 - 17:01:35
Document(s) archivé(s) le : jeudi 10 avril 2014 - 15:10:17

Fichier

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

Identifiants

Collections

Citation

Frédéric Giroire, Stéphane Pérennes, Issam Tahiri. On the Hardness of Equal Shortest Path Routing. International Network Optimization Conference, May 2013, Tenerife, Spain. Elsevier, 41, pp.439-446, 2013, Electronic Notes in Discrete Mathematics. <10.1016/j.endm.2013.05.123>. <hal-00926348>

Partager

Métriques

Consultations de
la notice

151

Téléchargements du document

223