Monte Carlo estimation of diameter-constrained network reliability conditioned by pathsets and cutsets

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 “terminal nodes” 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 reliability 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 computing it is also NP-hard. This paper extends the mentioned family of Monte Carlo sampling plans from the context of the CLR to that of the DCR. The plans are described in detail focusing on their requirements and limitations. The implications that the diameter constraints have on the topological components employed for computing the bounds (pathsets and cutsets) are discussed. Test cases on sparse and dense topologies are presented to illustrate how the presence of a diameter constraint, its value and the size of the set of terminal nodes affect the performance of the methods. It is also illustrated that the performance improvements achieved over the crude Monte Carlo method tend to be higher in the context of the DCR when compared to the CLR.