Bounded Monte Carlo estimation of diameter-constrained network reliability

Abstract

The d-diameter-constrained K-reliability (DCR) problem in networks is an extension of the classical problem of computing the K-reliability (CLR) where the subnetwork resulting from the failure of some edges is operational if and only if all nodes in a set of \201Cterminal nodes\201D K have pairwise distances not greater than a certain integer d. Computing the CLR is NP-hard which has motivated the development of simulation schemes, among which a family of Monte Carlo sampling plans that make use of upper and lower bounds to reduce the variance attained after drawing a given number of samples. The DCR is receiving increasing attention in contexts like video-conferencing and peer-to-peer networks; since it is an extension of the CLR it is also NP-hard. This paper presents Monte Carlo sampling plans based on bounds adapted to the DCR. These plans are described in detail focusing on their requirements and limitations. Test cases are presented evidencing how the diameter constraint and the terminal nodes set size affect the efficiency as well as the higher performance improvements attained by the best-performing methods in the context of DCR when compared to CLR.