Factorization and Exact Evaluation of the Source-Terminal Diameter-Constrained Reliability

Abstract : In classical network reliability, the system under study is a network with perfect nodes and imperfect links that fail randomly and In classical network reliability, the system under study is a network with perfect nodes and imperfect links that fail randomly and independently.. The probability that a given subset K of terminal nodes belongs to the same connected component is called classical or K-Terminal reliability. Although (and because) the classical reliability computation belongs to the class of N P-Hard problems, the literature offers many methods for this purpose, given the importance of the models. This article deals with diameter-constrained reliability, where terminal nodes are further required to be connected by d hops or fewer (d is a given strictly positive parameter of the metric called its diameter). This metric was defined in 2001, inspired by delay-sensitive applications in telecommunications. Factorization theory is fundamental for the classical network reliability evaluation, and today it is a mature area. However, its extension to the diameter-constrained context requires at least the recognition of irrelevant links, which is an open problem. In this paper, irrelevant links are efficiently determined in the most used case, where |K| = 2, thus providing a first step towards a Factorization theory in diameter-constrained reliability. We also analyze the metric in series-parallel and composition graphs. The article closes with a Factoring algorithm and a discussion of trends for future work.
Type de document :
Article dans une revue
Networks, Wiley, 2017, Special Issue on Design of Resilient Communication Networks, 70 (4), pp.283-291. 〈10.1002/net.21780〉
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01663508
Contributeur : Gerardo Rubino <>
Soumis le : jeudi 14 décembre 2017 - 06:30:35
Dernière modification le : mercredi 16 mai 2018 - 11:24:13

Fichier

Networks2017-new.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Eduardo Canale, Pablo Romero, Gerardo Rubino. Factorization and Exact Evaluation of the Source-Terminal Diameter-Constrained Reliability. Networks, Wiley, 2017, Special Issue on Design of Resilient Communication Networks, 70 (4), pp.283-291. 〈10.1002/net.21780〉. 〈hal-01663508〉

Partager

Métriques

Consultations de la notice

310

Téléchargements de fichiers

36