Network reliability estimation

Computing the reliability of a network is a #P-complete problem, therefore estimation by means of simulation often becomes a favourable choice. In modern communication networks, link failure probabilities are usually small and hence network failures become rare events. This poses a challenge to estimate the network reliability. In this thesis we present different techniques for network reliability estimation. There are two main sampling techniques in reliability estimation: combinatorial and permutational sampling. Combinatorial sampling has the advantage of speed but has poor performance in rare event simulations. Permutational sampling gives good simulation performance but at a higher computational cost. We combine the two techniques and propose a hybrid sampling scheme called Tree Cut and Merge. By employing simple bounding together with clever conditional sampling, the TCM scheme achieves over 10(superscript 7) times speed up in certain classes of heterogeneous networks. The Crude Monte Carlo (combinatorial) component in the Tree Cut and Merge scheme may cause problems in some situations. In bad cases, the slow convergence problem re-appears. To address the problem, we modifed the scheme by introducing the Importance Sampling technique. The new Tree Cut and Merge with Importance Sampling scheme maintained the speed advantage of the Tree Cut and Merge and minimizes, at the same time, the potential problems caused by the Crude Monte Carlo component. Associated with the Importance Sampling technique, a new technique called the Cross-Entropy method has been developed in the late 90's to find the optimal Importance Sampling parameters. By employing the Cross-Entropy technique, we propose a new scheme called the Merge Process with Cross-Entropy. The new scheme improves the Merge Process in nearly all classes of network; in contrast, Tree Cut and Merge with Importance Sampling scheme sees the greatest improvement in heterogeneous networks. Besides estimating the reliability of a single network, this thesis also investigates a closely related problem: estimating the difference in reliability of two very similar networks. The problem is closely linked to the applications in the areas of network optimization, network evolution, reconfiguration and recovery, for example. The fact that the probabilities of rare events are hard to estimate makes estimating their difference even more difficult. Coupled and differential sampling techniques are proposed and applied to various schemes in this thesis. They prove to be superior to the conventional independent "estimate and subtract" method. Interestingly, these concepts also lead to new ideas regarding the estimation of the reliability of networks that are similar to networks with polynomially computable reliability.Thesis (Ph.D.)--School of Mathematical Sciences, 2005