Fast simulation of rare events in queueing and reliability models

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

• 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.

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