Methods of Speeding up of Diameter Constrained Network Reliability Calculation

We consider the problem of reliability calculation of networks with diameter constraint. It is assumed that the network has unreliable communication links and perfectly reliable nodes. The diameter constrained reliability (DCNR) for such network is defined as a probability that every pair of terminals of network is connected by operational paths with a number of included edges less or equal to a given integer. The problem of computing this characteristic is known to be NP-hard, just like the problem of computing the probability of network connectivity. We propose new methods of speeding up of DCNR calculation. These methods are the edge reduction and the edge selection strategy for DCNR computing by the well-known factoring method. Also, we propose the parallel method for DCNR calculation and the method of cumulative updating of lower and upper bounds of DCNR, which allows to decide the feasibility of a network with respect to given threshold without performing exhaustive calculation of reliability. Experiments show an applicability of proposed methods.