Diverse Routing with the star property

Jean-Claude Bermond 1 David Coudert 1 Gianlorenzo D'Angelo 1 Fatima Zahra Moataz 1
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
Résumé : La notion de groupe de liens partageant un risque (\emph{Shared Risk Link Group}, (SRLG) a été introduite pour modéliser des problémes de tolérance aux pannes simultanées d'ensembles de liens d'un réseau. Dans ce contexte, le probléme du \emph{routage diversifié} est de trouver un ensemble de chemins SRLG-disjoints entre une paire donnée de n{\oe}uds du réseau. Ce probléme a été prouvé NP-complet en général~\cite{Hu03} et certains cas polynomiaux ont été caractérisés~\cite{CDP+07}. Dans cet article, nous étudions le probléme du routage diversifié dans les réseaux satisfaisants la \emph{propriété d'étoile}~\cite{LW05}. Dans un réseau satisfaisant la propriété d'étoile, un lien peut être affecté par plusieurs SRLGs, mais tous les liens affectés par un même SRLG sont incidents á un même sommet. Nous commençons par donner des contre-exemples á l'algorithme polynomial proposé dans~\cite{LW05} pour le calcul de paires de chemins SRLG-disjoints dans les réseaux satisfaisants la propriété d'étoile. Puis, nous prouvons que ce probléme est en fait NP-difficile au sens fort. Plus généralement, nous montrons que le probléme du routage diversifié dans les réseaux avec la propriété d'étoile est NP-difficile au sens fort, APX-difficile, et W [1]-difficile lorsque le paramétre est le nombre de chemins SRLG-disjoints. Enfin, nous caractérisons de nouvelles instances polynomiales, en particulier lorsque le degré maximum des sommets est 4, ou lorsque le réseau est acyclique.
Type de document :
Rapport
[Research Report] RR-8071, INRIA. 2012


https://hal.inria.fr/hal-00733869
Contributeur : Gianlorenzo D'Angelo <>
Soumis le : mercredi 19 septembre 2012 - 18:57:08
Dernière modification le : samedi 17 septembre 2016 - 01:36:00
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 15:36:42

Fichier

RR-8071.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00733869, version 1

Collections

Citation

Jean-Claude Bermond, David Coudert, Gianlorenzo D'Angelo, Fatima Zahra Moataz. Diverse Routing with the star property. [Research Report] RR-8071, INRIA. 2012. <hal-00733869>

Partager

Métriques

Consultations de
la notice

223

Téléchargements du document

171