The DOI matches its Crossref record; 31 of the 31 references it cites were found in a registry or an index.
Fast simulation of rare events in queueing and reliability models
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
An introduction to probability theory and its applications
(1958) · Journal of the Franklin Institute · doi:10.1016/0016-0032(58)90688-4 · Cited by 29,269
Hammersley, J. M., & Handscomb, D. C. (1964) · Springer eBooks · doi:10.1007/978-94-009-5819-7 · Cited by 4,054
Statistical Theory of Reliability and Life Testing-Probability Models
Smith, D. R., Barlow, R. E., & Proschan, F. (1977) · Technometrics · doi:10.2307/1268641 · Cited by 3,666
Applied Probability and Queues
Dave, U. (1987) · Journal of the Operational Research Society · doi:10.1057/jors.1987.184 · Cited by 2,704
Introduction to Stochastic Processes
(2014) · Stochastic Numerical Methods · doi:10.1002/9783527683147.ch6 · Cited by 2,383
Reversibility and Stochastic Networks
Cohen, J. E., & Kelly, F. P. (1981) · Technometrics · doi:10.1080/00401706.1981.10486278 · Cited by 2,212
Kalos, M. H., & Whitlock, P. A. (1986) · Wiley eBooks · doi:10.1002/9783527617395 · Cited by 1,546
Equivalent capacity and its application to bandwidth allocation in high-speed networks
Guerin, R., Ahmadi, H., & Naghshineh, M. (1991) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.103545 · Cited by 1,311
Simulation of nonhomogeneous poisson processes by thinning
Lewis, P. A. W., & Shedler, G. S. (1979) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800260304 · Cited by 846
Markov Chain Models — Rarity and Exponentiality
(1979) · Applied Mathematical Sciences · doi:10.1007/978-1-4612-6200-8 · Cited by 826
Cited by
Survey of sampling-based methods for uncertainty and sensitivity analysis
Helton, J. C., Johnson, J. D., Sallaberry, C. J., & Storlie, C. B. (2006) · Reliability Engineering & System Safety · doi:10.1016/j.ress.2005.11.017 · Cited by 1,237
Optimization of computer simulation models with rare events
Rubinstein, R. Y. (1997) · European Journal of Operational Research · doi:10.1016/s0377-2217(96)00385-2 · Cited by 682
Proceedings of Winter Simulation Conference
(1994) · Proceedings of Winter Simulation Conference WSC-94 · doi:10.1109/wsc.1994.717062 · Cited by 540
Model-based evaluation: from dependability to security
Nicol, D. M., Sanders, W. H., & Trivedi, K. S. (2004) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2004.11 · Cited by 510
Proceedings of the 2002 Winter Simulation Conference
(2002) · Proceedings of the Winter Simulation Conference · doi:10.1109/wsc.2002.1166355 · Cited by 456
Zhao, D., Lam, H., Peng, H., Bao, S., LeBlanc, D. J., Nobukawa, K., & Pan, C. S. (2017) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2016.2582208 · Cited by 445
Effective bandwidth in high-speed digital networks
Chang, C.-S., & Thomas, J. A. (1995) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.400664 · Cited by 407
Rare Event Simulation using Monte Carlo Methods
(2009) · Wiley eBooks · doi:10.1002/9780470745403 · Cited by 404
Importance Sampling for Portfolio Credit Risk
Glasserman, P., & Li, J. (2005) · Management Science · doi:10.1287/mnsc.1050.0415 · Cited by 322
Quick simulation: a review of importance sampling techniques in communications systems
Smith, P. J., Shafi, M., & Gao, H. (1997) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.585771 · Cited by 292
Helton, J. C., Davis, F. J., & Johnson, J. D. (2005) · Reliability Engineering & System Safety · doi:10.1016/j.ress.2004.09.006 · Cited by 278
Accelerated Evaluation of Automated Vehicles in Car-Following Maneuvers
Zhao, D., Huang, X., Peng, H., Lam, H., & LeBlanc, D. J. (2018) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2017.2701846 · Cited by 253
Metadata
- Authors
- Heidelberger, P.
- Venue
- ACM Transactions on Modeling and Computer Simulation
- Published
- 1995-01
- Volume
- 5
- Issue
- 1
- Pages
- 43-85
- ISSN
- 1049-3301 (ISSN-L)
- 1558-1195
- OpenAlex
- W2146416787
- Cited by
- 545
- References
- 31
- FWCI
- 25.10
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.