New event-driven sampling techniques for network reliability estimation

Exactly computing network reliability measures is an NP-hard problem. Therefore, Monte Carlo simulation has been frequently used by network designers to obtain accurate estimates. This paper focuses on simulation estimation of network reliability. Using a heap data structure, efficient implementation of a previous approach, dagger sampling, is proposed. Two new techniques, geometric sampling and block sampling, 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 test relative performance, computational experiments are carried out on various types of networks using the new procedures.