A splitting algorithm for network reliability estimation

Abstract

Splitting is a variance reduction technique widely used to make efficient estimations of the probability of rare events in the simulation of Markovian models. In this article, splitting is applied to improve a well-known method called the Creation Process (CP), used in network reliability estimation. The resulting proposal, called here Splitting/CP, is particularly appropriate in the case of highly reliable networks; i.e., networks for which failure is a rare event. The article introduces the basis of Splitting/CP and presents a set of computational experiments based on network topologies taken from the literature. The results of these experiments show that Splitting/CP is accurate, efficient, and robust and is therefore a valid alternative to the best known methods used in network reliability estimation.

Keywords:

• Network reliability
• splitting
• simulation
• rare event
• variance reduction