Please use this identifier to cite or link to this item:
Scopus Web of ScienceĀ® Altmetric
Type: Conference paper
Title: Network reliability estimation using the tree cut and merge algorithm with importance sampling
Author: Hui, K.
Bean, N.
Kraetzl, M.
Kroese, D.
Citation: Design and management of highly reliable networks and services : fourth International Workshop on the Design of Reliable Communication Networks : proceedings : (DRCN 2003) : October 19-22, 2003, the Banff Centre, Banff, Alberta, Canada / Mike MacGregor (ed.), pp. 254-262
Publisher: The Institute of Electrical and Electronics Engineers Inc
Publisher Place: Canada
Issue Date: 2003
ISBN: 0780381181
Conference Name: International Workshop on the Design of Reliable Communication Networks (4th : 2003 : Banff, Alberta, Canada)
Editor: MacGregor, M.
Statement of
Hui, K.-P. ; Bean, N.G. ; Kraetzl, M. ; Kroese, D.
Abstract: It is well known that the exact calculation of network reliability is a NP-complete problem and that for large networks estimating the reliability using simulation techniques becomes attractive. For highly reliable networks, a Monte Carlo scheme called the Merge Process is one of the best performing algorithms, but with a relatively high computational cost per sample. The authors previously proposed a hybrid Monte Carlo scheme called the Tree Cut and Merge algorithm which can improve simulation performance by over seven orders of magnitude in some heterogeneous networks. In homogeneous networks, however, the performance of the algorithm may degrade. In this paper, we first analyse the Tree Cut and Merge algorithm and explain why it does not perform well in some networks. Then a modification is proposed that subdivides the problem into smaller problems and introduces the Importance Sampling technique to the simulation process. The modified algorithm addresses the slow convergence problem in those hard cases while keeping the performance improvement in heterogeneous networks. Experiments and results are presented with some discussions.
DOI: 10.1109/DRCN.2003.1275364
Appears in Collections:Applied Mathematics publications
Aurora harvest 6
Environment Institute publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.