Bounded relative error in estimating transient measures of highly dependable non-Markovian systems

ABSTRACT

This article deals with fast simulation techniques for estimating transient measures in highly dependable systems. The systems we consider of components with generally distributed lifetimes and repair times, with complex interaction among components. As is well known, standard simulation of highly dependable systems is very inefficient, and importance-sampling is widely used to improve efficiency. We present two new techniques, one of which is based on the uniformization approach to simulation, and the other is a natural extension of the uniformization approach which we call exponential transformation. We show that under certain assumptions, these techniques have the bounded relative error property, i.e., the relative error of the simulation estimate remains bounded as components become more and more reliable, unlike standard simulation in which it tends to infinity. This implies that only a fixed number of observations are required to achieve a given relative error, no matter how rare the failure events are.

REFERENCES

• 1: BARLOW, R. E. AN F. PROSCUAN, 1981. Stattst*cal Theory of Rellablhty and Lz{k Testing. Holt, Reinhart and Winston, Silver Spring, Md.
• 2: BROWN, M. 1990. Error bounds for exponential approximations of geometric convolutions. Ann. Prob. 18, 3, 1388 1402.
• 3: CARRASCO, J.A. 1991a. Failure distance-based simulation of repairable fault-tolerant systems. In Modelling Techniqltes and Tools for Computer Performance Evaluation, North Holland, Amsterdam, 337-351.
• 4: CARRASCO, J.A. 1991b. Efficient transient simulation of failure/repair Markovian models. In Proceedings of the lOth Symposium on Reliable and Dzstrd~uted Computing. IEEE Press, New York, 152-161.
• 5: DUGAN, J. B. TRIVEDI, K. S., SMOTHERMAN, M. K, AND GEIST, R.M. 1986. The hybrid automated reliability predictor. J. Gu~d. Contr. Dynam. 9, 3, 319-331.
• 6: Bennett L. Fox , Peter W. Glynn, Discrete-time conversion for simulating finite-horizon Markov processes, SIAM Journal on Applied Mathematics, v.50 n.5, p.1457-1473, Oct. 1990 [doi>10.1137/0150085]
• 7: FRATER, M. R., LENNON, T. M., AND ANDERSON, B. D.O. 1991. Optimally efficient estimation of the statistics of rare events in queueing networks. IEEE Trans. Autom. Contr. 36, 12, 1395-1405.
• 8: GE~ST, R. M. AND SMOTHERMAN, M.K. 1989. Ultrahigh reliability estimates through simulation. In Proceedings of the Annual Reliability and Maintainability Symposium. IEEE Press, New York, 350 355.
• 9: GEIST, R. M. AND TR~VEDI, K. S. 1983. Ultra-high reliability prediction for fault-tolerant computer systems. IEEE Trans. Comput. 32, 1118 1127.
• 10: GERTSBAKH, I.B. 1984. Asymptotic methods in reliability theory: A review, Adv. Appl. Prob. 16, 147-~175.
• 11: GLYNN, P.W. 1989. A GSMP formalism for discrete event systems. Proc. IEEE 77, 1, 14 23
• 12: GLYNN, P.W. 1992. Importance sampling for Markov chains: Asymptotics for the variance. Tech. Rep., Dept. of Operations Research, Stanford Univ., Stanford, Calif.
• 13: 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]
• 14: Peter W. Glynn , Philip Heidelberger , Victor F. Nicola , Perwez Shahabuddin, Efficient estimation of the mean time between failures in non-regenerative dependability models, Proceedings of the 25th conference on Winter simulation, p.311-316, December 12-15, 1993, Los Angeles, California, United States [doi>10.1145/256563.256657]
• 15: 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
• 16: 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]
• 17: GROSS, D. AND MILLER, D. R. 1984. The randomization technique as a modeling tool and solution procedure for transient Markov processes. Oper. Res. 32, 2, 343-361.
• 18: HAMMERSLEY, J. M. AND HANDSCOMB, D.C. 1964. Monte Carlo Methods. Methuen, London.
• 19: HEIDELBERGER, P. 1993. Fast simulation of rare events in queueing and reliability models. IBM Res. Rep. RC 19028, IBM, Yorktown Heights, New York. To appear in Models and Techniques for Performance Evaluation of Computer and Communications Systems, Lecture Notes in Computer Science, Springer-Verlag.
• 20: Philip Heidelberger , Victor F. Nicola , Perwez Shahabuddin, Simultaneous and efficient simulation of highly dependable systems with different underlying distributions, Proceedings of the 24th conference on Winter simulation, p.458-465, December 13-16, 1992, Arlington, Virginia, United States [doi>10.1145/167293.167402]
• 21: JENSEN, A. 1953. Markov chains as an md in the study of Markov processes. Skand. Aktuarletidskr. 36, 87-91.
• 22: JUNEJA, S. AND SHAHABUDDIN, P. 1992. Fast simulation of Markovian reliability/availability models with general repair policies In Proceedings of the 22nd International Symposium on Fault-Tolerant Computing. IEEE Computer Society Press, Los Alamitos. Calif., 150-159.
• 23: KEILSON, J. 1979. Markov Chain Models--Rarzty and Exponentlality. Springer-Verlag, New York.
• 24: LEW~S, E. E. AND BOHM. F. 1984. Monte Carlo simulation of Markov unreliability models. Nuclear Eng. Des. 77, 49 62.
• 25: LEWIS, P. A. W. AND SHEDLER, G.S. 1979. Simulation of nonhomogeneous Poisson processes by thinning. Naval Res. Logzst. Q. 26, 3,403-413.
• 26: MOORSEL, A. P. A., VAN HAVERKORT, B. R. AND NIEMEGEERS, I. G. 1991. Fault injection simulation: A variance reduction technique For systems with raro ov~nts. In Deper2clable Computing for Crztical Applwations 2. Springer-Verlag, New York. 115-134
• 27: Marvin K. Nakayama, Asymptotics of likelihood ratio derivative estimators in simulations of highly reliable Markovian systems, Management Science, v.41 n.3, p.524-554, March 1995 [doi>10.1287/mnsc.41.3.524]
• 28: Marvin K. Nakayama, A characterization of the simple failure-biasing method for simulations of highly reliable Markovian Systems, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.4 n.1, p.52-88, Jan. 1994 [doi>10.1145/174619.174621]
• 29: NAKAYAMA, M. K. 1993b. General conditions for bounded relative error in simulations of highly reliable Markovian systems. IBM Res. Rep. RC 18993, IBM, Yorktown Heights, N.Y.
• 30: NICOLA, V. F., HEIDELBERGER, P., AND SHAHABUDDIN, P. 1992a. Uniformization and exponential transformation: Techniques for fast simulation of highly dependable non-Markovian systems. In Proceedzngs of the 22nd Internatwnal Symposium on Fault-Tolerant Coraputu~g. IEEE Computer Society Press, Los Alamitos, Cahf. 130-139.
• 31: NICOLA, V. F., NAKAYAMA, M., HEIDELBERGER, P., AND GOYAL, A. 1990. Fast simulation of dependability models with general failure, repair and maintenance processes. In Proceedings of the 20th International Symposium on Fault-Tolerant Computing. IEEE Computer Society Press, Los Alamitos, Calif. 491 498.
• 32: NICOLA, V. F., SHAHABUDDIN, P., AND HEIDELBERGER, P. 1993. Techniques for fast simulation of highly dependable systems. In Proceedings of the 2nd Internatzonal Workshop on Performability Modelhng of Computer and Communwatwns Systems. IFIP WG 7 3
• 33: NICOLA, V. F., SHAHABUDDIN, P., HEIDELBERGER, P., AND GLYNN, P.W. 1992b. Fast simulation of steady-state availability in non-Markovian highly dependable systems. In Proceedings of the 23rd International Symposnlm on Fault-Tolerant Computing. IEEE Computer Society Press, Los Alamitos, Calif. 38-47
• 34: PAREKa, S. AND WALRAND, J. 1989. A qmck simulation method for excessive backlogs in networks of queues. IEEE Trans. Aurora. Contr. 34, 1, 54-56.
• 35: SADOWSKY, J. S. 1991. Large deviations and efficient simulation of excessive backlogs m a GI/G/m queue IEEE Trans. Automat. Contr 36, 1383-1394.
• 36: Perwez Shahabuddin , Marvin K. Nakayama, Estimation of reliability and its derivatives for large time horizons in Markovian systems, Proceedings of the 25th conference on Winter simulation, p.422-429, December 12-15, 1993, Los Angeles, California, United States [doi>10.1145/256563.256679]
• 37: Perwez Shahabuddin , Peter W. Glynn, Simulation and analysis of highly reliable systems, 1990
• 38: Perwez Shahabuddin, Fast transient simulation of Markovian models of highly dependable systems, Proceedings of the 16th IFIP Working Group 7.3 international symposium on Computer performance modeling measurement and evaluation, p.267-286, May 1994, Rome, Italy
• 39: 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]
• 40: SHAHABUDDIN, P., AND NAKAYAMA, M K. 1994. Fast simulation for estimating transient measures m highly reliable Markovian systems IBM Res. Rep. IBM, Yorktown Heights, Yorktown Heights, N.Y.
• 41: J George Shanthikumar, Uniformization and hybrid simulation/analytic models of renewal processes, Operations Research, v.34 n.4, p.573-580, July-Aug. 1986 [doi>10.1287/opre.34.4.573]
• 42: STIFFLER, J., BRYANT, L., AND GUCCIONE, L.J. 1979. CARE III Phase 1. NASA Contractor Rep. 1-1572, Raytheon Corp., Sudbury, Mass
• 43: VAN DIJK, N.M. 1990. On a simple proof of uniformlzation for continuous and discrete-state continuous-time Markov chains. Adv. Appl. Prob. 22, 749-750.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Reliability, Theory

Keywords:
highly-dependable systems, importance sampling, non-Markovian systems, transient measures, uniformization-based simulation, variance reduction