Network reliability estimation using the tree cut and merge algorithm with importance sampling
Date
2003
Authors
Hui, K.
Bean, N.
Kraetzl, M.
Kroese, D.
Editors
MacGregor, M.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
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
Statement of Responsibility
Hui, K.-P. ; Bean, N.G. ; Kraetzl, M. ; Kroese, D.
Conference Name
International Workshop on the Design of Reliable Communication Networks (4th : 2003 : Banff, Alberta, Canada)
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.