2026-09-19T10:08:17Zhttps://digital.library.adelaide.edu.au/server/oai/request

oai:digital.library.adelaide.edu.au:2440/379522015-12-07T01:14:17Zcom_2440_14759col_2440_14760

Kraetzl, Miro Bean, Nigel Geoffrey Kroese, Dirk Hui, Kin-Ping School of Mathematical Sciences 2005 http://hdl.handle.net/2440/37952 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. 711781 bytes 131407 bytes application/pdf application/pdf en computer networks, operations research Network reliability estimation Thesis This electronic version is made publicly available by the University of Adelaide in accordance with its open access policy for student theses. Copyright in this thesis remains with the author. This thesis may incorporate third party material which has been used by the author pursuant to Fair Dealing exception. If you are the author of this thesis and do not wish it to be made publicly available or If you are the owner of any included third party copyright material you wish to be removed from this electronic version, please complete the take down form located at: http://www.adelaide.edu.au/legalsopen.access