A RECURSIVE VARIANCE-REDUCTION ALGORITHM FOR ESTIMATING COMMUNICATION-NETWORK RELIABILITY

In evaluating the capacity of a communication network architecture to resist possible faults of some of its components, several reliability metrics are used, This paper considers the K-terminal unreliability me asure. The exact evaluation of this parameter is, in general, very cos tly since it is in the NP-hard family. An alternative to exact evaluat ion is to estimate it using Monte Carlo simulation, For highly reliabl e networks, the crude Monte Carlo technique is prohibitively expensive ; thus variance reduction techniques must be used, We propose a recurs ive variance-reduction Monte-Carlo scheme (RVR-MC) specifically design ed for this problem. RVR-MC is recursive, changing the original proble m into the unreliability evaluation problem for smaller networks, When all resulting systems are either up or down independently of componen ts state the process terminates. Simulation results are given for a we ll-known test topology. The speedups obtained by RVR-MC with respect t o crude Monte Carlo are calculated for various values of component unr eliability. These results are compared to previously published results for five other methods (bounds, sequential construction, dagger sampl ing,failure sets, and merge process) showing the value of RVR-MC.