Reliability of Connections in Multilayer Networks under Shared Risk Groups and Costs Constraints

David Coudert 1 Florian Huc 1 Fabrice Peix 1 Marie-Emilie Voge 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
Abstract : The notion of Shared Risk Resource Groups (SRRG) has been introduced to capture survivability issues when a set of resources may fail simultaneously. Applied to Wavelength Division Multiplexing Network (WDM), it expresses that some links and nodes may fail simultaneously. The reliability of a connection therefore depends on the number of SRRGs through which it is routed. Consequently, this number has to be minimized. This problem has been proved NP-complete and hard to approximate in general, even when routing a single request. Some heuristics using shortest paths have already been designed, however the cost (the usual routing cost, not in term of SRRG) was not part of the objective. In this paper we study the problem of minimizing a linear combination of the average number of SRRG per paths and the cost of the routing. The main result of our work is a column generation formulation that allows to solve efficiently the problem of maximizing the reliability of a set of connection requests in MPLS/WDM mesh networks with SRRGs while keeping the cost of the routing low.
Type de document :
Communication dans un congrès
IEEE International Conference on Communications (ICC '08), May 2008, Beijing, China. IEEE, pp.5170 - 5174, 2008, <10.1109/ICC.2008.971>
Liste complète des métadonnées

https://hal.inria.fr/inria-00429150
Contributeur : David Coudert <>
Soumis le : mardi 2 novembre 2010 - 13:52:23
Dernière modification le : mardi 2 novembre 2010 - 19:49:05
Document(s) archivé(s) le : jeudi 3 février 2011 - 02:33:30

Fichier

04534007.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

INRIA | I3S | UNICE

Citation

David Coudert, Florian Huc, Fabrice Peix, Marie-Emilie Voge. Reliability of Connections in Multilayer Networks under Shared Risk Groups and Costs Constraints. IEEE International Conference on Communications (ICC '08), May 2008, Beijing, China. IEEE, pp.5170 - 5174, 2008, <10.1109/ICC.2008.971>. <inria-00429150>

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de
la notice

161

Téléchargements du document

116

Contact


archive-ouverte@inria.fr