Title: A simulation method for network performability estimation using heuristically computed pathsets and cutsets

Authors: Franco Robledo; Pablo Sartor

Addresses: Departamento de Investigación Operativa, Instituto de Computación, Facultad de Ingeniería, Universidad de la República, Julio Herrera y Reissig 565, Montevideo, Uruguay ' Departamento de Investigación Operativa, Instituto de Computación, Facultad de Ingeniería, Universidad de la República, Julio Herrera y Reissig 565, Montevideo, Uruguay

Abstract: Consider a set of terminal nodes K that belong to a network whose nodes are connected by links that fail independently with known probabilities. We introduce a method for estimating a performability measure that depends on the hop distance between terminal nodes. The new measure generalises the diameter-constrained network reliability measure. We propose a Monte Carlo method with significant variance reduction compared to crude Monte Carlo. It is based on using edge sets named d-pathsets and d-cutsets for reducing the variance of the estimator. These edge sets, considered as a priori known in previous literature, heavily affect the attained performance; we hereby introduce and compare a family of heuristics for their selection. Numerical examples are presented, showing the significant efficiency improvements that can be obtained by chaining the edge set selection heuristics to the proposed Monte Carlo sampling plan.

Keywords: metaheuristics; Monte Carlo simulation; rare events; networks; network reliability; performability; bounded length; diameter constraints; path sets; cut sets; sampling planning.

DOI: 10.1504/IJMHEUR.2013.058476

International Journal of Metaheuristics, 2013 Vol.2 No.4, pp.370 - 391

Received: 08 Dec 2012
Accepted: 27 Sep 2013
Published online: 12 Jul 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article