A characterization of the simple failure-biasing method for simulations of highly reliable Markovian Systems

ABSTRACT

Simple failure biasing is an importance-sampling technique used to reduce the variance of estimates of performance measures and their gradients in simulations of highly reliable Markovian systems. Although simple failure biasing yields bounded relative error for the performance measure estimate when the system is balanced, it may not provide bounded relative error when the system is unbalanced. In this article, we provide a characterization of when the simple failure-biasing method produces estimators of a performance measure and its derivatives with bounded relative error. We derive a necessary and sufficient condition on the structure of the system for when the performance measure can be estimated with bounded relative error when using simple failure biasing. Furthermore, a similar condition for the derivative estimators is established. One interesting aspect of the conditions is that it shows that to obtain bounded relative error, not only the most likely paths to system failure must be examined but also some secondary paths leading to failure as well. We also show by example that the necessary and sufficient conditions for a derivative estimator do not imply those for the performance measure estimator; i.e., it is possible to estimate a derivative more efficiently than the performance measure when using simple failure biasing.

REFERENCES

• 1: CARRASCO, J.A. 1992. Failure distance based simulation of repmrable fault tolerant systems. In Proceedings of the 5th Internattonal Conference on Modelling Techniques and Tools for Computer Performance Evaluation. Elsevier Science Publishers B.V., Amsterdam, 351-365.
• 2: CARP~SCO, J.A. 1991. Efficient transition simulation of failure/repair Markovian models. In Proceedings of the lOth Symposzum on ReltabIe D~stributed Systems. IEEE, New York, 152-161.
• 3: CONWAY, A. E., AND GOYAL~ A. 1987. Monte Carlo simulation of computer system availability/reliability models. In Proceedings of the 17th International Symposium on Fault Tolerant Computtng. 230 235.
• 4: COTTRELL, M., FORT, J. C., AND MALGOUYRES, G 1983. Large deviations and rare events in the study of stochastic algorithms. IEEE Trans. Automat. Contr. AC-28, 907-920.
• 5: Peter W. Glynn, Stochastic approximation for Monte Carlo optimization, Proceedings of the 18th conference on Winter simulation, p.356-365, December 08-10, 1986, Washington, D.C., United States [doi>10.1145/318242.318459]
• 6: P W. Glynn , D. L. Iglehart, Importance sampling for stochastic simulations, Management Science, v.35 n.11, p.1367-1392, Nov. 1989 [doi>10.1287/mnsc.35.11.1367]
• 7: Ambuj Goyal , Stephen S. Lavenberg, Modeling and analysis of computer system availability, IBM Journal of Research and Development, v.31 n.6, p.651-664, Dec. 1987
• 8: Ambuj Goyal , Perwez Shahabuddin , Philip Heidelberger , Victor F. Nicola , Peter W. Glynn, A Unified Framework for Simulating Markovian Models of Highly Dependable Systems, IEEE Transactions on Computers, v.41 n.1, p.36-51, January 1992 [doi>10.1109/12.123381]
• 9: HAMMERSLEY, J. M., AND HANDSCOMB, D.C. 1964. Monte Carlo Methods. Metheun, London.
• 10: JUNEJA, S., AND SHAHABUDDIN, P. 1992. Fast simulation of Markovian reliability/availability models with general repair policies. In Proceedtngs of the 22nd International Symposium on Fault Tolerant Computing.
• 11: LEW~S, E. E., AND BOHM, F. 1984. Monte Carlo simulation of Markov unreliability models. Nuc. Eng. Des. 77, 49 62.
• 12: NAKAYAMA, M.K. 1991. Asymptotics of likelihood ratio derivative estimators in simulations of highly reliable Markovian systems. Revision of Res. Rep. RC 76637, IBM Research Division, T. J. Watson Research Center, Yorktown Heights, N Y
• 13: NAKAYAMA, M. K., GOYAL, A., AND GLYNN, P.W. 1990. Likelihood ratio sensitivity analysis for Markovian models of highly dependable systems. Res. Rep. RC 15400, IBM Research Division, T J. Watson Research Center, Yorktown Heights, N.Y. To appear in Oper. Res.
• 14: PAREKH, S., AND WALRAND, J. 1989 A quick s~mulation method for excessive backlogs in networks of queues IEEE Trans. Automat. Contr. AC-34, 54 66.
• 15: REIMAN, M. I., AND WEISS, A. 1989. Sensitivity analysis for simulations via likelihood ratios. Oper. Res. 37. 830-844.
• 16: R. Y. Rubinstein, Sensitivity analysis and performance extrapolation for computer simulation models, Operations Research, v.37 n.1, p.72-81, Jan.-Feb. 1989 [doi>10.1287/opre.37.1.72]
• 17: Perwez Shahabuddin, Importance sampling for the simulation of highly reliable Markovian systems, Management Science, v.40 n.3, p.333-352, March 1994 [doi>10.1287/mnsc.40.3.333]
• 18: Perwez Shahabuddin , Peter W. Glynn, Simulation and analysis of highly reliable systems, 1990
• 19: SHAHABUDDIN, P., AND NAKAYAMA, M.K. 1992. Fast simulation of transient measures and their derivatives in highly reliable Markowan systems. Working draft.
• 20: Perwez Shahabuddin , Victor F. Nicola , Philip Heidelberger , Ambuj Goyal , Peter W. Glynn, Variance reduction in mean time to failure simulations, Proceedings of the 20th conference on Winter simulation, p.491-499, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318239]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques; Performance attributes

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing; Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Experimentation, Reliability, Theory

Keywords:
balanced failure biasing, gradient estimation, highly reliable systems, importance sampling, likelihood ratios, simple failure biasing