Measure specific dynamic importance sampling for availability simulations

ABSTRACT

This paper considers the application of importance sampling to simulations of highly available systems. By regenerative process theory, steady state performance measures of a Markov chain take the form of a ratio. Analysis of a simple three state Birth and Death process shows that the optimal (zero variance) importance sampling distributions for the numerator and denominator of this ratio are quite different and are both dynamic in that they do not correspond directly to time homogeneous Markov chains. Analysis of this three state example suggests heuristics for choosing effective importance sampling distributions for more complex models of highly available systems. These heuristics are applied to a large model of computer system availability. The example shows that additional variance reduction over that previously reported can be obtained by simulating the numerator and denominator independently with different dynamic importance sampling distributions.

REFERENCES

• 1: Conway, A.E. and Goyal, A, (1987). Monte Carlo Simulation of Computer System Availability/Reliability Models. Proceedings of the Seventeenth Symposium on Fault-Tolerant Computing. Pittsburgh, Pennsylvania, 230-235.
• 2: Crane, M.A. and lgtehart, D.L. (1975). Simulating Stable Stochastic Systems, III: Regenerative Processes and Discrete Event Simulations. Operations Research 23, 33-45.
• 3: Geist, R.M. and Trivedi, K.S. (1983). Ultra-High Reliability Prediction for Fault-Tolerant Computer Systems. 1EEE Transactions on Computers C-32, 1118-1127.
• 4: Hammersley, J.M. and Handscomb, D.C. (1964). Monte Carlo Methods. Methuen, London.
• 5: Hordijk, A., Iglehart, D.L. and Schassberger, R. (1976). Discrete Time Methods for Simulating Continuous Time Markov Chains. Adv. AppL Prob. 8, 772-788.
• 6: Karlin, S. and Taylor, H.M. (1975). A First Course in Stochastic Processes, Second Edition. Academic Press, New York.
• 7: Lewis, E.E. and Bohm, F. (1984). Monte Carlo Simulation of Markov Unreliability Models. Nuclear Engineering and Design 77, 49-62.
• 8: Meketon, M.S and Heidelberger, P. (1982). A Renewal Theoretic Approach to Bias Reduction in Regenerative Simulations. Management Science 24, 173-181.
• 9: Siegmund, D. (1976), Importance Sampling in the Monte Carlo Study of Sequential Tests. The Annals of Statistics 4, 673-684.
• 10: Walrand, J. (I987). Quick Simulation of Rare Events in Queueing Networks. Proceedings of the Second International Workshop on Applied Mathematics and Perf o finance/Reliability Models of Computer/Communication Systems. G. Iazeolla, P.J. Courtois and O.J. Boxma (eds). North Holland Publishing Company, Amsterdam, 275-286.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  G. Mathematics of Computing

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Measurement, Performance, Theory