Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-01663508
Contributor : Gerardo Rubino <>
Submitted on : Thursday, December 14, 2017 - 6:30:35 AM
Last modification on : Saturday, July 11, 2020 - 3:16:24 AM

File

Networks2017-new.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

697

Files downloads

279