SRLG-Diverse Routing with the Star Property

Jean-Claude Bermond 1 David Coudert 1 Gianlorenzo D'Angelo 2 Fatima Zahra Moataz 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 : The notion of Shared Risk Link Groups (SRLG) has been introduced to capture survivability issues where some links of a network fail simultaneously. In this context, the diverse routing problem is to find a set of pairwise SRLG-disjoint paths between a given pair of end nodes of the network. This problem has been proved NP-complete in general and some polynomial instances have been characterized. In this paper, we investigate the diverse routing problem in networks where the SRLGs are localized and satisfy the star property. This property states that a link may be subject to several SRLGs, but all links subject to a given SRLG are incident to a common node. We first provide counterexamples to the polynomial time algorithm proposed in the literature for computing a pair of SRLG-disjoint paths in networks with SRLGs satisfying the star property, and then prove that this problem is in fact NP-complete. Then, we devise polynomial time algorithms for practically relevant subcases, in particular when the number of SRLGs is constant, the maximum degree of the vertices is at most 4, and when the network is a directed acyclic graph. Finally we consider the problem of finding the maximum number of SRLG-disjoint paths in networks with SRLGs satisfying the star property. We prove that such problem is NP-hard and hard to approximate. Then, we provide exact and approximation algorithms for relevant subcases.
Type de document :
Communication dans un congrès
Design of Reliable Communication Networks, DRCN, Mar 2013, Budapest, Hungary. 2013
Liste complète des métadonnées


https://hal.inria.fr/hal-00794638
Contributeur : Fatima Zahra Moataz <>
Soumis le : mardi 26 février 2013 - 11:48:47
Dernière modification le : lundi 5 octobre 2015 - 16:57:51
Document(s) archivé(s) le : dimanche 2 avril 2017 - 05:21:39

Fichier

SRLG-Divrse_Routing_with_the_S...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00794638, version 1

Collections

Citation

Jean-Claude Bermond, David Coudert, Gianlorenzo D'Angelo, Fatima Zahra Moataz. SRLG-Diverse Routing with the Star Property. Design of Reliable Communication Networks, DRCN, Mar 2013, Budapest, Hungary. 2013. <hal-00794638>

Partager

Métriques

Consultations de
la notice

348

Téléchargements du document

152