Importance Sampling to Evaluate Real-time System Reliability: A Case Study

Abstract

Real-time distributed computers are often used in life- critical applications. However, the complexity of such systems calls for extensive simulation studies to validate their performance and reliability before a design can be accepted and a prototype constructed. A simulator testbed has been built to model a variety of such systems quickly from a few basic building blocks. Life-critical applications require reliability levels so high that brute-force simula tion to validate these levels would take weeks of computer time. In this paper, we present studies we have conducted into the use of importance sampling in simulating real- time systems. This paper presents a interesting case- study of the use of importance sampling in an increas ingly important branch of computer engineering. Impor tance sampling may not work for all cases and over all parameter ranges. In this paper, we are interested in finding out whether (and how well) this scheme works for the case of distributed real-time systems and also the range of failure bias values for which it works well. Specifically, we look at the implementation of two heuris tics called 'forcing' and failure biasing' in the testbed. This was validated by comparing the reliability estimates with that of normal (very long) simulation. The effect of the failure bias on the dynamics of the scheme is also investigated to provide readers with some guidance on choosing appropriate bias values.

Keywords

Importance sampling rare-event simulation real-time systems embedded systems reliability evaluation

Get full access to this article

View all access options for this article.

References

Allalouf, M. , Chang, J. , Durairaj, G. , Lakamraju, V.R. , Unsal, O.S. , Koren, I. and Krishna, C.M. "RAPIDS: A Simulator Testbed for Fault-Tolerant Real-Time Systems." Proc. of HPC'98, Grand Challenges in Computer Simulation, pp 191-196, Boston, April 1998.

Allalouf, M. , Chang, J. , Durairaj, G. , Haines, J. , Lakamraju, V.R. , Toutireddy, K. , Unsal, O.S. , Yu, K. , Koren, I. and Krishna, C.M. "The RAPIDS Simulator: A Testbed for Evaluating Scheduling. Allocation, and Fault-Recovery in Distributed Real-Time Systems ." Dependable Network Computing. D. Avresky (Editor), pp 413-431, Kluwer Academic Publishers, MA, 2000.

Andradottir, S. , Heyman, D. and Ott, T. "On the Choice of Alternative Measures in Importance Sampling with Markov Chains." Operations Research Vol. 43, No. 3, pp 509-519, 1995.

Berg, M. and Koren, I. "On Switching Policies for Modular Fault-Tolerant Computing Systems ." IEEE Trans. Computers. Vol. C-36, pp 1052-1062, Sept 1987.

Boyd, M. and Bavuso, S. "Simulation Modeling for Long Duration Spacecraft Control Systems." 1993 Proc. Annual Reliability and Maintainability Symposium, pp 106-113, 1993.

Carrasco, J. "Failure distance based simulation of repairable fault-tolerant systems ." Proc. of 5th International Conf. on Modeling Techniques and Tools for Computer Performance Evaluation , pp 337-351, 1991.

Carrasco, J. "Efficient Transient Simulation of Failure/Repair Markovian Models ." Proc. of 10th Symposium on Reliable and Distributed Computing, IEEE Computer Society Press, pp 152-161, 1991.

L'Ecuyer, P. "Efficiency Improvement and Variance Reduction ." Proc. of the 1994 Winter Simulation Conf, pp 122-132, 1994.

Geist, A. , Beguelin, A. , Dongarra, J. , Jiang, W. , Manchek, R. , Sunderam, V. PVM: Parallel Virtual Machine. MIT Press, 1994.

10.

Glynn, P. and Iglehart, D. "Importance Sampling for Stochastic Simulations ." Management Science. Vol. 35, No. 11, pp 1367-1393, 1989.

11.

Goyal, A. and Lavenberg, S.S. "Modeling and analysis of computer system availability." IBM J. Res. Develop. Vol. 31, pp 651-664, 1987.

12.

Goyal, A. , Heidelberger, P. , Shahabuddin, P. "Measure Specific Dynamic Importance Sampling for Availability Simulations ." 1987 Winter Simulation Conference Proceedings , IEEE Press, 1987.

13.

Goyal, A. , Shahabuddin, P. Heidelberger , P. , Nicola, V.F. and Glynn, P.W. "A Unified Framework for Simulating Markovian Models of Highly Dependable Systems." IEEE Transactions on Computers. Vol. 41, No. 1, pp 36-51, 1992.

14.

Hammersley, J.M. and Handscomb , D.C. Monte Carlo Methods . Meuthen, London, 1964.

15.

Heidelberger, P. "Fast Simulation of Rare Events in Queueing and Reliability Models." ACM Transactions on Modeling and Computer Simulation. Vol. 5, No. 1, 1995.

16.

Jain, R. FDDI Handbook. Addison-Wesley, 1994.

17.

Krishna, C.M. and Shin, K.G. "Performance Measures for Multiprocessor Controllers." Performance '83. pp 229-250, May 1983 .

18.

Krishna, C.M. and Shin, K.G. Real-Time Systems. McGraw-Hill , 1997.

19.

Lamport, L. "Time, Clocks, and the Ordering of Events in a Distributed System." Communications of the ACM. Vol. 21, No. 7, 1978.

20.

Lewis, E.E. and Bohm, F. "Monte Carlo simulation of Markov unreliability models." Nuclear Engineering and Design. Vol. 77, pp 49-62, 1984.

21.

Nakayama, M. "A Characterization of the simple failure biasing method for simulations of highly reliable Markovian Systems." ACM Trans. Model. Comput. Simul. Vol. 4, No. 1, pp 52-88, 1994.

22.

Puterman, M.L. Markov Decision Processes. John Wiley & Sons Inc., 1994.

23.

Ross, S.M. Applied Probability Models with Optimization Applications. San Francisco: Holden-Day, 1970.

24.

Ross, S.M. Simulation. Academic Press, 1997.

25.

Shahabuddin, P. , Nicola, V. , Heidelberger, P. , Goyal , A. and Glynn, P. "Variance Reduction in Mean Time to Failure Simulations." 1988 Winter Simulation Conference Proceedings, IEEE Press, 1988.

26.

Shahabuddin, P. "Simulation and Analysis of Highly Reliable Systems," PhD Thesis, Department of Operations Research, Stanford University, Palo Alto, California, 1990.

27.

Shahabuddin, P. and Nakayama, M. "Estimation of Reliability and Its Derivatives for Large Time Horizons in Markovian Systems." 1993 Winter Simulation Conference Proceedings, IEEE Press , pp 491-499, 1993.

28.

Shahabuddin, P. "Simulation of Highly Reliable Markovian Systems ." Management Science. Vol. 40, pp 333-352, 1994.

29.

Stallings, W. Handbook of Computer-Communications Standards . Howard W. Sams & Co., 1988.

30.

Steinman, J.S. "Breathing Time Warp. " Proceedings of the 1993 Workshop on Parallel and Distributed Simulation, 1993.

31.

Toutireddy, K.K. "A Testbed for Fault Tolerant Real-Time Systems." MS Thesis, University of Massachusetts, Amherst, 1996.

32.

Yu, K. "RAMP and the Dynamic Recovery and Reconfiguration of a Distributed Real-Time System," PhD Thesis, University of Massachusetts , Amherst, 1996.

33.

Yu, K. and Koren, I. "Reliability Enhancement of Real-Time Multiprocessor Systems through Dynamic Reconfiguration." In Fault-Tolerant Parallel and Distributed Systems, D. Pradhan and D. Avresky (Editors), pp 161-168, IEEE Computer Society Press, Los Alamitos, CA, 1995.