A simulation method for network performability estimation using heuristically computed pathsets and cutsets. (1st January 2013)

• Record Type: Journal Article
• Authors: Robledo, Franco; Sartor, Pablo
• Is Part Of: International journal of metaheuristics. Volume 2:Number 4(2013)
• Page Start: 370
• Page End: 391
• Publication Date: 2013-01-01
• Subjects: metaheuristics -- Monte Carlo simulation -- rare events -- networks -- reliability -- performability -- bounded length -- diameter constraints -- pathset -- cutest; Heuristic algorithms -- Periodicals; 006.3105
• Languages: English
• ISSNs: 1755-2176

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.