Efficient event-driven simulation approaches to analysis of network reliability and performability

Exactly computing network reliability and performability measures are NP-hard problems, precluding their frequent use in design of large networks. Instead, Monte Carlo simulation has been frequently used by network designers to obtain accurate estimates. This paper focuses on simulation estimation of network reliability and performability. First, a literature survey of existing approaches is given. Then, using a heap data structure, efficient implementation of two previous approaches, dagger sampling and Markov model, are proposed. Two new techniques, geometric sampling (GS) and block sampling (BS), are developed to efficiently sample states of a network. These techniques are event-driven rather than time-driven, and are thus efficient for highly reliable networks. To gauge relative performance, computational experiments are carried out on various types of networks using the existing and the new procedures. These networks include up to 400 nodes and both binary and nonbinary structure functions are used.