Diameter constrained network reliability :exact evaluation by factorization and bounds

Abstract

Consider a network where the links are subject to random, independent failures. The diameter constrained network reliability parameter R(G,K,D) measures the probability that the set K of terminals of the network are linked by operational paths of length less or equal to D. This parameter generalizes the classical network reliability, allowing to reflect performance objectives that restrict the maximum length of a path in the network. This is the case, for example, when the transmissions between every two terminal nodes in the subset K are required to experience a maximum delay D.T (where T is the delay experienced at a single node or link); then the probability that after random failures of the communication links, the surviving network meets the maximum delay requirement is the diameter constrained reliability R(G,K,D). This paper defines the diameter constrained network reliability, and gives a formulation in terms of events corresponding to the operation of the (length constrained) paths of the network. Based on this formulation, the exact value of the diameter constrained reliability is derived, for the special case where K=\{s,t\} and the upper bound D of the path length is 2. For other values of K and D an exact evaluation algorithm based on a factorization approach is proposed. As this algorithm has exponential worst case complexity, upper and lower bounds for K=\{s,t\} are developed, which in some cases may be used instead of the exact value