Fast simulation of rare events in queueing and reliability models

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast simulation of rare events in queueing and reliability models

Full text

Pdf (3.33 MB)

Source

ACM Transactions on Modeling and Computer Simulation (TOMACS) archive
Volume 5 , Issue 1 (January 1995) table of contents

Pages: 43 - 85

Year of Publication: 1995

ISSN:1049-3301

Author

Philip Heidelberger

IBM T. J. Watson Research Center, Hawthorne, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 25, Downloads (12 Months): 191, Citation Count: 81

Additional Information:

abstract references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/203091.203094 What is a DOI?

ABSTRACT

This paper surveys efficient techniques for estimating, via simulation, the probabilities of certain rare events in queueing and reliability models. The rare events of interest are long waiting times or buffer overflows in queueing systems, and system failure events in reliability models of highly dependable computing systems. The general approach to speeding up such simulations is to accelerate the occurrence of the rare events by using importance sampling. In importance sampling, the system is simulated using a new set of input probability distributions, and unbiased estimates are recovered by multiplying the simulation output by a likelihood ratio. Our focus is on describing asymptotically optimal importance sampling techniques. Using asymptotically optimal importance sampling, the number of samples required to get accurate estimates grows slowly compared to the rate at which the probability of the rare event approaches zero. In practice, this means that run lengths can be reduced by many orders of magnitude, compared to standard simulation. In certain cases, asymptotically optimal importance sampling results in estimates having bounded relative error. With bounded relative error, only a fixed number of samples are required to get accurate estimates, no matter how rare the event of interest is. The queueing systems studied include simple queues (e.g., GI/GI/1), Jackson networks, discrete time queues with multiple autocorrelated arrival processes that arise in the analysis of Asynchronous Transfer Mode communications switches, and tree structured networks of such switches. Both Markovian and non-Markovian reliability models are treated.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	AL-QAQ, W. A, DEVETSIKIOTIS, M, AND TOWNSEND, J.K. 1993. Importance sampling methodolog/es for simulation of communication systems with adaptwe equalizers and time-varying channels. IEEE J. Selected Areas Commun 11,317-327.
	2	V. Anantharam, How large delays build up in a GI/G/1 quqe, Queueing Systems: Theory and Applications, v.5 n.4, p.345-368, November 1989 [doi>10.1007/BF01225324]
	3	ANANTHARAM, V, HEIDELBERGER, r., AND TSOUCAS, P. 1990. Analysis of rare events m continuous time Markov chains via time reversal and fluid approximation. Rep. RC 16280, IBM, Yorktown Heights, New York.
	4	ARSHAM, H., FUERVERGER, A., MCLEJSH, D. L., KREIMER, J., AND RUBINSTE~N, R. Y. 1989. Sensitivity analysis and the "what iff problem in simulation analysis. Math. Comput. Model. 12, 193-219
	5	ASMUSSEN, S. 1993. Busy period analysis, rare events and transient behawour m fluid models. To appear in J. Appl. Math. Stochasttc Anal.
	6	ASMUSSEN, S. 1990. Exponential famihes and regression in the Monte Carlo study of queues and random walks. Ann. Statzst. 18, 1851-1867.
	7	ASMUSSEN, S.1989.Risk theory in a Markowan enwronment. Scand. Actuarial J, 69 100
	8	ASMUSS~N, S.1987.Apphed Probabzhty and Queues. Wiley, New York
	9	ASMUSSEN, S. 1985.Conjugate processes and the s~mulation of ruin problems. Stochasttc Process Appl. 20, 213-229.
	10	ASMUSSEN, S 1982. Conditioned limit theorems relating a random walk to its associate. Adv. Appl. Probab. 14, 143-170.
	11	ASMUSSEN, S., AND RUBINSTEIN, R. Y 1994. Complexity properties of steady-state rare events simulation in queueing models. Preprint.
	12	ASMUSSEN, S., AND RUBINSTEIN, R.Y. 1992. The efficiency and heavy traffic properties of the score function method in sensitivity analysis of queueing models. Adv. Appl. Probab. 24, 172-201.
	13	ASMUSSEN, S., RUBINSTEIN, e. Y., AND WANG, C.L. 1992. Efficient regenerative rare events simulation via the likelihood ratio method. Preprint.
	14	BARLOW, R. E., AND PROSCHAN, F. 1981. Statistical Theory of Reliability and Life Testing. Holt, Reinhart and Winston, New York.
	15	Leo Breiman, Probability, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
	16	BROWN, M. 1990. Error bounds for exponential approximations of geometric convolutions. A. Probab. 18, 1388-1402.
	17	BUCKLEW, J. 1990. Large Deviation Techniques in Decision, S~mulation and Estimation. Wiley, New York.
	18	BUCKLEW, J. A., NEY, P., AND SADOWSKY, J. S. 1990. Monte Carlo simulation and large deviations theory for uniformly recurrent Markov chains. J. Appl. Probab. 27, 44-99.
	19	CARRASCO, J.A. 1991a. Failure distance-based simulation of repairable fault-tolerant systems. In Proceedings of the 5th Internatlonal Conference on Modeling Techniques and Tools for Computer Performance Evaluation, 337-351.
	20	CARRASCO, J.A. 1991b. Efficient transient simulation of failure/repair Markovian models. In Procee&ngs of the lOth Symposium on Reliable and Distributed Computing. (Pisa, Italy) IEEE Computer Society Press, 152-161.
	21	CHANt, C.S. 1994. Stability, queue length and delay of deterministic and stochastic queueing networks. IEEE Trans. Autom. Control 39, 913-931.
	22	CHANG, C.S. 1992. Stability, queue length and delay, Part II: Stochastic queueing networks. In Proceedings of the IEEE CDC'92 Conference. (Tucson, Ariz.). IEEE Computer Society Press, 1005-1010.
	23	Cheng-Shang Chang , Philip Heidelberger , Sandeep Juneja , Perwez Shahabuddin, Effective bandwidth and fast simulation of ATM intree networks, Performance Evaluation, v.20 n.1-3, p.45-65, May 1994
	24	CHANG, C. S., HEIDELBERGER, P., JUNEJA, S., AND SHAHABUDDIN, P. 1993. The application of effective bandwidth to fast simulation of communication networks. Rep. RC 18877, IBM, Yorktown Heights, New York.
	25	CHANG, C. S., HEIDELBERGER, P., AND SHAHABUDDIN, P. 1993. Fast simulation of packet loss rates in a shared buffer communications switch. Rep. RC 19250, IBM, Yorktown Heights, New York.
	26	Hong Chen , Avi Mandelbaum, Discrete flow networks: bottleneck analysis and fluid approximations, Mathematics of Operations Research, v.16 n.2, p.408-446, May 1991 [doi>10.1287/moor.16.2.408]
	27	~INLAR, E. 1975. Introduction to Stochastic Processes. Prentice Hall, Englewood Cliffs, NJ.
	28	COGBURN, e. 1975. A uniform theory for sums of Markov chain transition probabilities. Ann. Probab. 3, 191-214.
	29	COTTRELL, M., FORT, J. C., AND MALGOUYRES, G. 1983. Large deviations and rare events in the study of stochastic algorithms. IEEE Trans. Autom. Control. AC-28, 907-920.
	30	CRANE, M. A., AND IGLEHART, D.L. 1975. Simulating stable stochastic systems III: regenerative processes and discrete event simulation. Oper. Res. 23, 33-45.
	31	CSISZ~R, I., COVER, T. M., AND CHOI, B.-S. 1987. Conditional limit theorems under Markov conditioning. IEEE Trans. Inf. Theor. 33, 788-801.
	32	DEVETSIKIOTIS, M., AL-QAQ, W. A., FREEBERSYSER, J. A., AND TOWNSEND, J.K. 1993. Stochastic gradient techniques for the efficient simulation of high-speed networks using importance sampling. In Proceedings ofIEEE Globecom '93. IEEE Computer Society Press, 751-756.
	33	Michael Devetsikiotis , J. Keith Townsend, Statistical optimization of dynamic importance sampling parameters for efficient simulation of communication networks, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.293-305, June 1993 [doi>10.1109/90.234852]
	34	DEVETSIK~OTIS, M., AND TOWNSEND, J.K. 1992a. On the efficient simulation of large communication networks using importance sampling. In Proceedings of IEEE Globecom '92. IEEE Computer Society Press, 1455-1459.
	35	DEVETSiKIOTiS, M. AND TOWNSEND, J.K. 1992b A dynamic importance sampling methodology for the efficient estimation of rare event probabilities in regenerative simulations of queueing systems. In Proceedings of the IEEE ICC '92 Conference. IEEE Computer Society Press, 1290 1297.
	36	DE VECIAN^, G., COURCOUBETIS, C., ANn WALmkND, J. 1994. Decoupling bandwidths for networks: A decomposition approach to resource management for networks In IEEE Infocom Proceedzngs '94, 466 473
	37	DuPuJs, P. AND ELLIS, R.S. 1993. The large deviation principle for a general class of queueing systems, I. Rep. LCDS 93-10, Division of Applied Mathematics, Brown University, Providence, R.I.
	38	DuPuIs, P, ISHII, H., AND SONER, H.M. 1990. A viscosity solution approach to the asymptotic analyms of queueing systems. Ann. Probab. 18, 226-255
	39	ELLIS, R.S. 1984. Large deviations for a general class of random vectors Ann. Probab. 12, 1-12
	40	FELLER, W. 1971. An Introductmn to ProbabzI~ty Theory and ~ts Appllcatzons, vol. 2. J. Wiley, New York
	41	FRATER, M.R. 1993. Fast simulation of buffer overflows in equally loaded networks. Australzan Telecornmun. Res 27, 1, 13-18
	42	FRATER, M. R., AND ANDERSON, B. n. O 1994. Fast simulation of buffer overflows in tandem networks of GI/GI/1 queues. Ann. Oper Res. 49, 207-220.
	43	FRATER, M. R., AND ANDERSON, B. n.O. 1989. Fast estimation of the statistics of excessive backlogs in tandem networks of queues. Austrahan Telecommun Res. 23, 49 55.
	44	FRATER, M. R., BIT~mAD, R. R, KENNEDY, R. A, AND ANDERSON, B. D.O. 1989. Rare events and reverse time models. In Proceedlngs of the 28th Conference on Deczswn and Control. IEEE Press, 1180 1183.
	45	FRATER, M R., LENON, T M., AND ANDERSON, B D.O. 1991. Optimally efficient estimation of the statistics of rare events in queuelng networks. IEEE Trans Aurora. Control 36, 1395-1405.
	46	FRATER, M. R., WALRAND, J., AND ANDERSON, B. D.O. 1990. Optimally efficient simulation of buffer overflows in queues with deterministic service times via importance sampling Austrahan Telecommun. Res. 24, 1-8.
	47	R. D. Fresnedo, Quick simulation of rare events in networks, Proceedings of the 21st conference on Winter simulation, p.514-523, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76805]
	48	G;iRTNER, J. 1977. On large deviations from invariant measure Theory Probab. Appl. 22, 24 39.
	49	GEIST, R. M. AND SMOTHERMAN, M. K 1989. Ultrahigh reliability estimates through simulation In Proceedings of the Annual Reliabihty and Maintaznablh(y Symposium. IEEE Press, 350-355.
	50	vGERTSBAKH, I. B. 1984. Asymptotic methods in reliability theory: A review. Adv. Appl Probab. 16, 147 175.
	51	R. J. Gibbens , P. J. Hunt, Effective bandwidths for the multi-type UAS channel, Queueing Systems: Theory and Applications, v.9 n.1-2, p.17-28, Oct. 1991 [doi>10.1007/BF01158790]
	52	GLASSERMAN, P. 1993 Stochastic monotonicity and conditional Monte Carlo for likelihood ratios. Adv. Appl Probab. 25, 103 115.
	53	GLASSERMAN, P. AND KOU, S.G. 1993. Overflow probabilities in Jackson networks. In Proceed- ~ngs of the 32nd Conference on Deczszon and Control. IEEE Press, 3178-3182.
	54	GLASSERMAN, P. AND KOU, S. G 1995. Analysis of an importance sampling estimator for tandem queues. Preprint.
	55	GLYNN, P.W. 1992. Importance samphng for Markov chains: asymptotics for the variance. Tech. Rep., Department of Operations Research, Stanford University. To appear in Stochastzc Models
	56	GLYNN, P.W. 1989. A GSMP formalism for discrete event systems. In Proc. IEEE 77, 14 23.
	57	Peter W. Glynn , Philip Heidelberger, Experiments with initial transient deletion for parallel, replicated steady-state simulations, Management Science, v.38 n.3, p.400-418, March 1992 [doi>10.1287/mnsc.38.3.400]
	58	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]
	59	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]
	60	Peter W. Glynn , Ward Whitt, The asymptotic efficiency of simulation estimators, Operations Research, v.40 n.3, p.505-520, May–June 1992 [doi>10.1287/opre.40.3.505]
	61	GOYAL, A., CARTER, W. C., DE SOUZA E SILVA, E., LAVENBERG~ S. S., AND TRIVEDI, K. S. 1986. The system availability estimator. In Proceedings of the Sixteenth International Symposium on Fault-Tolerant Computing. IEEE Computer Society Press, 84-89.
	62	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
	63	Ambuj Goyal , Philip Heidelberger , Perwez Shahabuddin, Measure specific dynamic importance sampling for availability simulations, Proceedings of the 19th conference on Winter simulation, p.351-357, December 14-16, 1987, Atlanta, Georgia, United States [doi>10.1145/318371.318607]
	64	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]
	65	GUgRIN, R., AHMADI, H., AND NAGHSHINEH, M. 1991. Equivalent capacity and its application to bandwidth allocation in high-speed networks. IEEE J. Select. Areas Commun 9,968-981.
	66	ItALTON, J.H. 1970. A retrospective and prospective survey of the Monte Carlo method. SIAM Rev. 12, 1 60.
	67	HAMMERSLEY, J. M., AND HANDSCOMB, D.C. 1964. Monte Carlo Methods. Methuen, London.
	68	Philip Heidelberger, Discrete event simulations and parallel processing: statistical properties, SIAM Journal on Scientific and Statistical Computing, v.9 n.6, p.1114-1132, November 1988 [doi>10.1137/0909077]
	69	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]
	70	Philip Heidelberger , Perwez Shahabuddin , Victor F. Nicola, Bounded relative error in estimating transient measures of highly dependable non-Markovian systems, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.4 n.2, p.137-164, April 1994 [doi>10.1145/175007.175008]
	71	P. Heidelberger , R. Simha, Fast simulation of a voice-data multiplexer, Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies (Vol. 1)-Volume, p.361, April 02-06, 1995
	72	HEIDELBERGER, P., AND TSOUCAS, P. 1991. Reverse time simulation of rare events. IBM Tech. Disclosures Bull. 34, 3, 163-165.
	73	HuI, J.Y. 1988. Resource allocation for broadband networks. IEEE J. Selected Areas Commun. 6, 9, 1598-1608.
	74	IGLEHART, D.L. 1972. Extreme values in the GI/G/1 queue. Ann. Math. Statist. 43, 627-635.
	75	JENSEN, A. 1953. Markov chains as an aid in the study of Markov processes. Skand. Aktuarietidskr, 36, 87-91.
	76	JUNEJA, S. 1993. Efficzent Rare Event Stmulation of Stochasttc Systems. Ph.D. Thesis, Department of Operations Research, Stanford University, Palo Alto, California.
	77	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, 150-159.
	78	Malvin H. Kalos , Paula A. Whitlock, Monte Carlo methods. Vol. 1: basics, Wiley-Interscience, New York, NY, 1986
	79	KEILSON, J. 1979. Markov Chain Models--Rarity and Exponentiality. Springer Verlag, New York.
	80	F. P. Kelly, Effective bandwidths at multi-class queues, Queueing Systems: Theory and Applications, v.9 n.1-2, p.5-16, Oct. 1991 [doi>10.1007/BF01158789]
	81	KELLY, F.P. 1979. Reverstbility and Stochastic Networks. Wiley, New York.
	82	G. Kesidis , J. Walrand, Quick simulation of ATM buffers with on-off multiclass Markov fluid sources, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.3 n.3, p.269-276, July 1993 [doi>10.1145/174153.174162]
	83	KOVALENKO, I.N. 1994. Rare events in queueing systems--a survey. Queuemg Syst. 16, 1-49.
	84	LEHTONEN, T., AND NYRHINEN, H. 1992a. Simulating level-crossing probabilities by importance samphng. Adv. Appl Probab 24, 858 874.
	85	LEHTONEN, T., AND NYRHINEN, H 1992b. On asymptotically efficient simulation of ruin probabilities in a Markovlan environment Scand. Actuarial or., 60-75
	86	LEWIS, E. E , AND BOHM, F 1984 Monte Carlo simulation of Markov unreliability models. Nuclear Eng. Des'. 77, 49-62.
	87	LEWIS, P. A. W., AND SHEDLER, G.S. 1979. Simulation of nonhomogeneous Poisson processes by thinning. Naval Res. Logistics Q. 26, 403 413
	88	NAKAYAMA, M.K. 1991. Szmulatmn of Highly Reliable Markovtan and Non-Markowan Systems Ph.D. Thesis, Department of Operations Research, Stanford University, Palo Alto, California.
	89	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]
	90	NAKaYAMA, M.K. 1993 General conditions for bounded relative error in simulations of highly reliable Markovian systems. Rep. RC 18993. IBM, Yorktown Heights, New York.
	91	NAKAYAMA, M.K. 1991. Asymptotics for hkehhood ratio derivative estimators m simulations of highly reliable Markovian systems. Rep. RC 17357, IBM, Yorktown Heights, New York.
	92	NAKAYAMA, M K., GOd, L, A., AND GLYNN, P.W. 1994. Likelihood ratio sensitivity analysis for Markovlan models of highly dependable systems. Oper. Res. 42, 1, 137-157.
	93	N~COL, D M., AND PALUMBO, D.L. 1995. Reliability analysis of complex models using SURE bounds. Tech. Rep. 93-14, ICASE NASA Langley Research Center. IEEE Trans. Rehab. 44, 1, 46-53.
	94	NICOLA, V. F., HEIDELBERGER, P., AXD SHAHABUDDIN, P. 1992. Umformlzatlon and exponential transformation: techniques for fast simulation of highly dependable non-Markovian systems. In Proceedings of the 22nd International Symposium on Fault-Tolerant Computing. IEEE Computer Socmty Press, 130 139.
	95	Victor F. Nicola , Marvin K. Nakayama , Philip Heidelberger , Ambuj Goyal, Fast Simulation of Highly Dependable Systems with General Failure and Repair Processes, IEEE Transactions on Computers, v.42 n.12, p.1440-1452, December 1993 [doi>10.1109/12.260634]
	96	NIEOLA, V. F., NAKAYAMA, M K., HEIDELBERGER, P., AND GOY^L, A 1990. Fast simulation of dependability models with general failure, repair and maintenance processes. In Proceedings of the 20th International Sympostum on Fault-Tolerant Computing. IEEE Computer Society Press, 491-498.
	97	NICOLA, V. F., SHAHABUDmN, P, .~D HEtDELBERGER, P. 1993 Techniques for fast simulation of highly dependable systems. In Proceedings of the 2nd International Workshop on Performabtllty Modelling of Computer and Communtcatton Systems.
	98	NICOLA, V. F., SHAHABUDDIN, P., HEIDELBERGER, P., AND GLYNN, P.W. 1993. Fast simulation of steady-state availability in non-Markovian highly dependable systems. In Proceedtngs of the 23rd International Symposium on Fault-Tolerant Computing IEEE Computer Society Press, 38 47.
	99	OPAL II, W. D., AND SANDERS, W. H. 1994. Importance sampling simulation in UltraSAN. Simulation 62, 2, 98-111.
	100	PAREKH, S., AND WALRAND, J. 1989. A quick simulatmn method for excessive backlogs m networks of queues. IEEE Trans Autom. Control 34, 54 56.
	101	R. Rubinstein, How to optimize discrete-event systems from a single sample path by the score function method, Annals of Operations Research, v.27 n.1-4, p.175-212, Dec. 1990 [doi>10.1007/BF02055195]
	102	SADOWSKY, J.S. 1993. On the optimality and stability of exponential twisting in Monte Carlo estimation. IEEE Trans Inf. Theor. 39, 119-128.
	103	SADOWSKY, J. S 1991. Large deviations and efficient simulation of excessive backlogs m a GI/G/m queue IEEE Trans. Aurora. Control 36, 1383-1394.
	104	SADOWSKY, J. S., AND BUCKLEW, J A. 1990. On large deviations theory and asymptotically efficient Monte Carlo estimation. IEEE Trans Inf. Theor 36, 579-588.
	105	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]
	106	Perwez Shahabuddin, Fast transient simulation of Markovian models of highly dependable systems, Performance Evaluation, v.20 n.1-3, p.267-286, May 1994
	107	Perwez Shahabuddin, Fast simulation of packet loss rates in communication networks with priorities, Proceedings of the 26th conference on Winter simulation, p.274-281, December 11-14, 1994, Orlando, Florida, United States
	108	Perwez Shahabuddin , Peter W. Glynn, Simulation and analysis of highly reliable systems, 1990
	109	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]
	110	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]
	111	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]
	112	SHWARTZ, A., AND WEISS, A. 1993. Induced rare events: analysis via time reversal and large deviations. Adv. Appl. Probab. 25, 667-689.
	113	SIEGMUND, D. 1976. Importance sampling in the Monte Carlo study of sequential tests. Ann. Statistics 4, 673-684.
	114	SMITH, W.L. 1955. Regenerative stochastic processes. Proc. Roy. Soc. Ser. A. 232: 6-31.
	115	Stephen G. Strickland, Optimal importance sampling for quick simulation of highly reliable Markovian systems, Proceedings of the 25th conference on Winter simulation, p.437-444, December 12-15, 1993, Los Angeles, California, United States [doi>10.1145/256563.256683]
	116	TSOUCAS, P. 1992. Rare events in series of queues. J. Appl. Probab. 29, 168-175.
	117	WEISS, A. 1986. A new technique for analyzing large traffic systems. Adv. Appl. Probab. 18, 506-532.
	118	WHITT, W. 1993. Tail probability with statistical multiplexing and effective bandwidths in multi-class queues. Telecommun. Syst. 2, 71-107.
	119	WHITT, W.1980. Continuity of generalized semi-Markov processes. Math. Oper. Res. 5, 494-501.

CITED BY 81

	Peter Buchholz, A new approach combining simulation and randomization for the analysis of large continuous time Markov chains, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.2, p.194-222, April 1998
	Paul Glasserman , Philip Heidelberger , Perwez Shahabuddin , Tim Zajic, Splitting for rare event simulation: analysis of simple cases, Proceedings of the 28th conference on Winter simulation, p.302-308, December 08-11, 1996, Coronado, California, United States
	Perwez Shahabuddin, Rare event simulation in stochastic models, Proceedings of the 27th conference on Winter simulation, p.178-185, December 03-06, 1995, Arlington, Virginia, United States
	Ernest H. Page , David M. Nicol , Osman Balci , Richard M. Fujimoto , Paul A. Fishwick , Pierre L'Ecuyer , Roger Smith, Strategic directions in simulation research (panel), Proceedings of the 31st conference on Winter simulation: Simulation---a bridge to the future, p.1509-1520, December 05-08, 1999, Phoenix, Arizona, United States
	Sandeep Juneja , Perwez Shahabuddin, Simulating heavy tailed processes using delayed hazard rate twisting, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.12 n.2, p.94-118, April 2002
	Nam Kyoo Boots , Perwez Shahabuddin, Statistical tools for simulation design and analysis: simulating ruin probabilities in insurance risk processes with subexponential claims, Proceedings of the 33nd conference on Winter simulation, December 09-12, 2001, Arlington, Virginia
	Jinwoo Choe , Ness B. Shroff, A central-limit-theorem-based approach for analyzing queue behavior in high-speed networks, IEEE/ACM Transactions on Networking (TON), v.6 n.5, p.659-671, Oct. 1998
	Michel Mandjes , Ad Ridder, A large deviations analysis of the transient of a queue with many Markov fluid inputs: approximations and fast simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.12 n.1, p.1-26, January 2002
	Sandeep Juneja , Perwez Shahabuddin , Anurag Chandra, Simulating heavy tailed processes using delayed hazard rate twisting, Proceedings of the 31st conference on Winter simulation: Simulation---a bridge to the future, p.420-427, December 05-08, 1999, Phoenix, Arizona, United States
	Pierre L'Ecuyer , Yanick Champoux, Estimating small cell-loss ratios in ATM switches via importance sampling, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.11 n.1, p.76-105, Jan. 2001
	Cheng-Shang Chang , Philip Heidelberger , Perwez Shahabuddin, Fast simulation of packet loss rates in a shared buffer communications switch, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.5 n.4, p.306-325, Oct. 1995
	Indira Kuruganti , Stephen G. Strickland, Importance sampling for Markov chains: computing variance and determining optimal measures, Proceedings of the 28th conference on Winter simulation, p.273-280, December 08-11, 1996, Coronado, California, United States
	Zsolt Haraszti , J. Keith Townsend, Rare event simulation of delay in packet switching networks using DPR-based splitting, Proceedings of the 31st conference on Winter simulation: Simulation---a bridge to the future, p.402-410, December 05-08, 1999, Phoenix, Arizona, United States
	Matthias Falkner , Michael Devetsikiotis , Ioannis Lambadaris, Fast simulation of networks of queues with effective and decoupling bandwidths, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.9 n.1, p.45-58, Jan. 1999
	Pierre L'Ecuyer , Yanick Champoux, Importance sampling for large ATM-type queueing networks, Proceedings of the 28th conference on Winter simulation, p.309-316, December 08-11, 1996, Coronado, California, United States
	Dirk P. Kroese , Victor F. Nicola, Efficient simulation of a tandem Jackson network, Proceedings of the 31st conference on Winter simulation: Simulation---a bridge to the future, p.411-419, December 05-08, 1999, Phoenix, Arizona, United States
	Pieter-Tjerk de Boer , Victor F. Nicola , Reuven Y. Rubinstein, Techniques for simulating difficutl queueing problems: adaptive importance sampling simulation of queueing networks, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
	Nam Kyoo Boots , Perwez Shahabuddin, Simulating GI/GI/1 queues and insurance risk processes with subexponential distributions, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
	Dirk P. Kroese , Victor F. Nicola, Efficient simulation of a tandem Jackson network, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.12 n.2, p.119-141, April 2002
	Marvin K. Nakayama, Output analysis: analysis of simulation output, Proceedings of the 35th conference on Winter simulation: driving innovation, December 07-10, 2003, New Orleans, Louisiana
	R. S. Randhawa , S. Juneja, Combining importance sampling and temporal difference control variates to simulate Markov Chains, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.14 n.1, p.1-30, January 2004
	Zsolt Haraszti , J. Keith Townsend, The theory of direct probability redistribution and its application to rare event simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.9 n.2, p.105-140, April 1999
	Christian Kelling, A framework for rare event simulation of stochastic Petri nets using “RESTART”, Proceedings of the 28th conference on Winter simulation, p.317-324, December 08-11, 1996, Coronado, California, United States
	Nam Kyoo Boots , Perwez Shahabuddin, Simulating tail probabilities in GI/GI/1 queues and insurance risk processes with subexponential distributions (extended abstract), ACM SIGMETRICS Performance Evaluation Review, v.29 n.3, December 2001
	Marvin K. Nakayama, Output analysis: simulation output analysis, Proceedings of the 34th conference on Winter simulation: exploring new frontiers, December 08-11, 2002, San Diego, California
	Ramya Dhamodaran , Bruce C. Shultes, Queueing network simulation analysis: efficient analysis of rare events association with individual buffers in a tandem Jackson network, Proceedings of the 35th conference on Winter simulation: driving innovation, December 07-10, 2003, New Orleans, Louisiana
	Ioannis Ch. Paschalidis , Spyridon Vassilaras, Importance sampling for the estimation of buffer overflow probabilities via trace-driven simulations, IEEE/ACM Transactions on Networking (TON), v.12 n.5, p.907-919, October 2004
	Tito Homem-de-Mello , Reuven Y. Rubinstein, Rare event simulation and combinatorial optimization using cross entropy: estimation of rare event probabilities using cross-entropy, Proceedings of the 34th conference on Winter simulation: exploring new frontiers, December 08-11, 2002, San Diego, California
	James M. Calvin , Peter W. Glynn , Marvin K. Nakayama, Steady state simulation analysis: importance sampling using the semi-regenerative method, Proceedings of the 33nd conference on Winter simulation, December 09-12, 2001, Arlington, Virginia
	Ming-hua Hsieh, Adaptive monte carlo methods for rare event simulation: adaptive monte carlo methods for rare event simulations, Proceedings of the 34th conference on Winter simulation: exploring new frontiers, December 08-11, 2002, San Diego, California
	Bruce C. Shultes, Difficult queuing simulation problems: a balanced likelihood ratio approach for analyzing rare events in a tandem Jackson network, Proceedings of the 34th conference on Winter simulation: exploring new frontiers, December 08-11, 2002, San Diego, California
	Lei Wei , Honghui Qi, Extensions: an efficient importance sampling method for rare event simulation in large scale tandem networks, Proceedings of the 34th conference on Winter simulation: exploring new frontiers, December 08-11, 2002, San Diego, California
	Winfried K. Grassmann , Jingxiang Luo, Simulating markov-reward processes with rare events, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.15 n.2, p.138-154, April 2005
	Zhi Huang , Perwez Shahabuddin, New simulation methodology for risk analysis: rare-event, heavy-tailed simulations using hazard function transformations, with applications to value-at-risk, Proceedings of the 35th conference on Winter simulation: driving innovation, December 07-10, 2003, New Orleans, Louisiana
	Sandeep Juneja , Victor Nicola, Efficient simulation of buffer overflow probabilities in jackson networks with feedback, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.15 n.4, p.281-315, October 2005
	Zesheng Chen , Chuanyi Ji, A self-learning worm using importance scanning, Proceedings of the 2005 ACM workshop on Rapid malcode, November 11-11, 2005, Fairfax, VA, USA
	Lachlan L. H. Andrew, Fast simulation of wavelength continuous WDM networks, IEEE/ACM Transactions on Networking (TON), v.12 n.4, p.759-765, August 2004
	P. T. de Boer , D. P. Kroese , R. Y. Rubinstein, Rare event simulation and combinatorial optimization using cross entropy: estimating buffer overflows in three stages using cross-entropy, Proceedings of the 34th conference on Winter simulation: exploring new frontiers, December 08-11, 2002, San Diego, California
	David M. Nicol , William H. Sanders , Kishor S. Trivedi, Model-Based Evaluation: From Dependability to Security, IEEE Transactions on Dependable and Secure Computing, v.1 n.1, p.48-65, January 2004
	Daniel R. Figueiredo , Benyuan Liu , Yang Guo , Jim Kurose , Don Towsley, On the efficiency of fluid simulation of networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.12, p.1974-1994, 24 August 2006
	Gregory K. Chen , David Blaauw , Trevor Mudge , Dennis Sylvester , Nam Sung Kim, Yield-driven near-threshold SRAM design, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	A. B. Dieker , M. Mandjes, Fast simulation of overflow probabilities in a queue with Gaussian input, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.16 n.2, p.119-151, April 2006
	Jose H. Blanchet , Jingchen Liu, Efficient simulation for large deviation probabilities of sums of heavy-tailed increments, Proceedings of the 37th conference on Winter simulation, December 03-06, 2006, Monterey, California
	Hector Cancela , Gerardo Rubino , Bruno Tuffin, New measures of robustness in rare event simulation, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
	Håkan L. S. Younes , Reid G. Simmons, Statistical probabilistic model checking with a focus on time-bounded properties, Information and Computation, v.204 n.9, p.1368-1409, September 2006
	Victor F. Nicola , Tatiana S. Zaburnenko, Efficient simulation of population overflow in parallel queues, Proceedings of the 37th conference on Winter simulation, December 03-06, 2006, Monterey, California
	Pieter-Tjerk De Boer, Analysis of state-independent importance-sampling measures for the two-node tandem queue, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.16 n.3, p.225-250, July 2006
	James M. Calvin , Peter W. Glynn , Marvin K. Nakayama, The semi-regenerative method of simulation output analysis, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.16 n.3, p.280-315, July 2006
	Pierre L'Ecuyer , Valérie Demers , Bruno Tuffin, Rare events, splitting, and quasi-Monte Carlo, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.17 n.2, p.9-es, April 2007
	Marvin K. Nakayama, Output analysis for simulations, Proceedings of the 37th conference on Winter simulation, December 03-06, 2006, Monterey, California
	Pierre L'Ecuyer , Bruno Tuffin, Splitting with weight windows to control the likelihood ratio in importance sampling, Proceedings of the 1st international conference on Performance evaluation methodolgies and tools, October 11-13, 2006, Pisa, Italy
	Pierre L'Ecuyer , Valérie Demers , Bruno Tuffin, Splitting for rare-event simulation, Proceedings of the 37th conference on Winter simulation, December 03-06, 2006, Monterey, California
	Edmundo de S. e Silva , Ana P. C. da Silva , Antonio A. de A. Rocha , Rosa M. M. Leão , Flávio P. Duarte , Fernando J. S. Filho , Guilherme D. G. Jaime , Richard R. Muntz, Modeling, analysis, measurement and experimentation with the Tangram-II integrated environment, Proceedings of the 1st international conference on Performance evaluation methodolgies and tools, October 11-13, 2006, Pisa, Italy
	Victor F. Nicola , Tatiana S. Zaburnenko, Efficient heuristics for the simulation of population overflow in series and parallel queues, Proceedings of the 1st international conference on Performance evaluation methodolgies and tools, October 11-13, 2006, Pisa, Italy
	T. P. I. Ahamed , V. S. Borkar , S. Juneja, Adaptive Importance Sampling Technique for Markov Chains Using Stochastic Approximation, Operations Research, v.54 n.3, p.489-504, May-June 2006
	S. Juneja , R. L. Karandikar , P. Shahabuddin, Asymptotics and fast simulation for tail probabilities of maximum of sums of few random variables, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.17 n.2, p.7-es, April 2007
	Victor F. Nicola , Tatiana S. Zaburnenko, Efficient importance sampling heuristics for the simulation of population overflow in Jackson networks, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
	Werner Sandmann, Importance sampling in Markovian settings, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
	Achal Bassamboo , Sandeep Juneja , Assaf Zeevi, Importance sampling simulation in the presence of heavy tails, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
	Chih-Chieh Hsu , Michael Devetsikiotis, An adaptive approach to fast simulation of traffic groomed optical networks, Proceedings of the 36th conference on Winter simulation, December 05-08, 2004, Washington, D.C.
	Sankalp Singh , James Lyons , David M. Nicol, Fast model-based penetration testing, Proceedings of the 36th conference on Winter simulation, December 05-08, 2004, Washington, D.C.
	Zhi Huang , Perwez Shahabuddin, A unified approach for finite-dimensional, rare-event Monte Carlo simulation, Proceedings of the 36th conference on Winter simulation, December 05-08, 2004, Washington, D.C.
	Poul E. Heegaard , Bjarne E. Helvik , Ragnar Ø. Andreassen, Application of rare event techniques to trace driven simulation, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
	Victor F. Nicola , Tatiana S. Zaburnenko, Efficient importance sampling heuristics for the simulation of population overflow in Jackson networks, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.17 n.2, p.10-es, April 2007
	Ad Ridder , Reuven Rubinstein, Minimum Cross-entropy Methods for Rare-event Simulation, Simulation, v.83 n.11, p.769-784, November 2007
	Chih-Chieh Hsu , Michael Devetsikiotis, An adaptive approach to accelerated evaluation of highly available services, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.18 n.1, p.1-26, December 2007
	Peter Buchholz, A hybrid analysis approach for finite-capacity queues with general inputs and phase type service, Queueing Systems: Theory and Applications, v.35 n.1-4, p.167-183, 2000
	Jianfeng Zhang , James A. Bucklew , Fernando L. Alvarado, Search Strategies For Failure Cascade Paths In Power System Graphs, Probability in the Engineering and Informational Sciences, v.19 n.4, p.507-517, October 2005
	D. P. Kroese , R. Y. Rubinstein, The Transform Likelihood Ratio Method for Rare Event Simulation with Heavy Tails, Queueing Systems: Theory and Applications, v.46 n.3-4, p.317-351, March-April 2004
	Sandeep Juneja , Perwez Shahabuddin, Simulating heavy tailed processes using delayed hazard rate twisting (extended abstract), ACM SIGMETRICS Performance Evaluation Review, v.27 n.3, p.20-22, Dec. 1999
	Marvin K. Nakayama , Perwez Shahabuddin, Quick Simulation Methods For Estimating The Unreliability Of Regenerative Models Of Large, Highly Reliable Systems, Probability in the Engineering and Informational Sciences, v.18 n.3, p.339-368, July 2004
	Nam Kyoo Boots , Michel Mandjes, FAST SIMULATION OF A QUEUE FED BY A SUPERPOSITION OF MANY (HEAVY-TAILED) SOURCES, Probability in the Engineering and Informational Sciences, v.16 n.2, p.205-232, April 2002
	Poul E. Heegaard , Werner Sandmann, Ant-based approach for determining the change of measure in importance sampling, Proceedings of the 39th conference on Winter simulation: 40 years! The best is yet to come, December 09-12, 2007, Washington D.C.
	Edwin Woudt , Pieter-Tjerk De Boer , Jan-Kees Van Ommeren, Improving Adaptive Importance Sampling Simulation of Markovian Queueing Models using Non-parametric Smoothing, Simulation, v.83 n.12, p.811-820, December 2007
	Zesheng Chen , Chuanyi Ji, Optimal worm-scanning method using vulnerable-host distributions, International Journal of Security and Networks, v.2 n.1/2, p.71-80, March 2007
	Michael Short , Michael J. Pont, Assessment of high-integrity embedded automotive control systems using hardware in the loop simulation, Journal of Systems and Software, v.81 n.7, p.1163-1183, July, 2008
	P. Lieshout , M. Mandjes, Importance sampling in rate-sharing networks, Proceedings of the 1st international conference on Simulation tools and techniques for communications, networks and systems & workshops, March 03-07, 2008, Marseille, France
	Pierre L'Ecuyer , Bruno Tuffin, Approximate zero-variance simulation, Proceedings of the 40th Conference on Winter Simulation, December 07-10, 2008, Miami, Florida
	Marvin K. Nakayama, Statistical analysis of simulation output, Proceedings of the 40th Conference on Winter Simulation, December 07-10, 2008, Miami, Florida
	D. I. Miretskiy , W. R. W. Scheinhardt , M. R. H. Mandjes, Simulation of a Jackson tandem network using state-dependent importance sampling, Proceedings of the 3rd International Conference on Performance Evaluation Methodologies and Tools, October 20-24, 2008, Athens, Greece
	Paul Dupuis , Hui Wang, Importance sampling for Jackson networks, Queueing Systems: Theory and Applications, v.62 n.1-2, p.113-157, June 2009

INDEX TERMS

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

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

G. Mathematics of Computing
G.m MISCELLANEOUS
Subjects: Queueing theory**

General Terms:
Performance, Reliability

Keywords:
importance sampling, queueing models, rare event, reliability models, variance reduction

REVIEW

"Taghi J. Mirsepassi : Reviewer"

Heidelberger has written a clear, well-organized paper on estimating rare events. It is highly recommended to those interested in queueing and reliability simulations. In a brief introduction, using some practical cases, the author more...

Collaborative Colleagues:

Philip Heidelberger: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player