Simulation run lengths to estimate blocking probabilities

Abstract

We derive formulas approximating the asymptotic variance of four estimators for steady-state blocking probability in a multiserver loss system, exploiting diffusion process limits. These formulas can be used to predict simulation run lengths required to obtain desired statistical precision before the simulation has been run, which can aid in the design of simulation experiments. They also indicate that one estimator can be much better than another, depending on the loading. An indirect estimator based on estimating the mean occupancy is significantly more (less) efficient than a direct estimator for heavy (light) loads. A major concern is the way computational effort scales with system size. For all the estimators, the asymptotic variance tends to be inversely proportional to the system size, so that the computational effort (regarded as proportional to the product of the asymptotic variance and the arrival rate) does not grow as system size increases. Indeed, holding the blocking probability fixed, the computational effort with a good estimator decreases to zero as the system size increases. The asymptotic variance formulas also reveal the impact of the arrival-process and service-time variability on the statistical precision. We validate these formulas by comparing them to exact numerical results for the special case of the classical Erlang M/M/s/0 model and simulation estimates for more general G/GI/s/0 models. It is natural to delete an initial portion of the simulation run to allow the system to approach steady state when it starts out empty. For small to moderately size systems, the time to approach steady state tends to be negligible compared to the time required to obtain good estimates in steady state. However, as the system size increases, the time to approach steady state remains approximately unchanged, or even increases slightly, so that the computational effort associated with letting the system approach steady state becomes a greater portion of the overall computational effort as system size increases.

References

1. ASMUSSEN, S. 1989. Validating heavy traffic performance of regenerative simulation. Stochastic Models 5, 617-628.]]
2. ASMUSSEN, S. 1992. Queueing simulation in heavy traffic. Math. Oper. Res. 17, 84-111.]]
3. BACCELLI, F. AND BREMAUD, P. 1994. Elements of Queueing Theory. Springer Verlag, Berlin.]]
4. BENES, V.E. 1961. The covariance function of a simple trunk group, with applications to traffic measurements. Bell Syst. Tech. J. 40, 117-148.]]
5. BERGER, A. W. AND WHl~l~r, W. 1992. The Brownian approximation for rate-control throttles and the G/G/1/C queue. J. Discrete Event Dynamic Syst. 2, 7-60,]]
6. BILLINGSLEY, P. 1968. Convergence of Probability Measures. Wiley, New York.]]
7. BOgOVKOV, A. A. 1967. On limit laws for service processes in multi-channel systems. Siberian Math. J. 8, 746-763.]]
8. BOROVKOV, A. A. I976. Stochastic Processes in Queueing Theory. Springer Verlag, New York.]]
9. BOROVKOV, A.A. 1984. Asymptotic Methods in Queuing Theory. Wiley, New York.]]
10. CARSON, J. S. AND LAW, A. M. 1980. Conservation equations and variance reduction in queueing simulations. Oper. Res. 28, 535-546.]]
11. Cox, D. R. AND MILLER, H.D. 1965. The Theory of Stochastic Processes. Wiley, New York.]]
12. DAVlS, J., MASSE~, W. A., AND WHITT, W. 1995. Sensitivity to the service-time distribution in the nonstationary Erlang loss model. Manage. Sci. 41, 1107-1116.]]
13. ECKBERO, A.E. 1983. Generalized peakedness of teletraffic processes. In Proceedings of the Tenth International Teletraffic Congress (Montreal, June), 4.4b.3.]]
14. EICK, S. G., MASSEY, W. A., AND WHITT, W. 1993. The physics of the MJG/oo queue. Oper. Res. 41,731-742.]]
15. ERRAMILLI, A., GORDON, g., AND WILLINGER, W. 1994. Applications of fractals in engineering for realistic traffic processes. In Proceedings of ITC '94. J. Labetoullle and J. W. Roberts, Eds., Elsevier, Amsterdam, 35-44.]]
16. ETHIER, S. N. AND KURTZ, T. G. 1986. Characterization and Approximation of Markov Processes. Wiley, New York.]]
17. FENDICK, K. W. AND WHITT, W. 1989. Measurements and approximations to describe the offered traffic and predict the average workload in a single-server queue. In Proc. IEEE 77, 171-194.]]
18. GLY~N, P. W~ 1982. On the Markov property of the GUG/~ Gaussian limit. Adv. Appl. Probab. 14, 191-194.]]
19. GLYNN, P. W. AND WHITT, W. 1989, Indirect estimation via L = AW. Oper. Res. 37, 82-103.]]
20. GLYNN, P. W. ANO WmTT, W. 1991. A new view of the heavy-traffic limit theorem for infinite-server queues. Adv. Appl. Probab. 23, 188-209.]]
21. GLYNN, P. W. AND WmTT, W. 1992. The asymptotic efficiency of simulation estimators. Oper. Res. 40, 505-520.]]
22. GLYNN, P. W., MELAMED, B., AND WHITT, W. 1993. Estimating customer and time averages. Oper. Res. 41,400-408.]]
23. GRASSMANS:, W. K. 1987. The asymptotic variance of a time average in a birth-death process. Ann. Oper. Res. 8, 165-174.]]
24. HALFIN~ S. AND WHITT, W. 1981. Heavy-traffic limits for queues with many exponential servers. Oper. Res. 29, 567-587.]]
25. HEYMAN, D.P. 1980. Comments on a queueing inequality. Manage. Sci. 26, 956-959.]]
26. JAGERMAN, D.L. 1974. Some properties of the Erlang loss functions. Bell Syst. Tech. J. 53, 525-551.]]
27. KELLY, F.P. 1991. Loss networks. Ann. Appl. Probab. I, 319-378.]]
28. LAVENBERG, S. S., MOELLER, W. L., AND WELCH, P. D. 1982. Statistical results on control variables with application to queueing network simulation. Oper. Res. 30, 182-202.]]
29. LAw, A. M. 1975. Efficient estimators for simulated queueing systems. Manage. Sci. 22, 30-41.]]
30. LUCANTON1, D.M. 1993. The BMAP/G/1 queue: A tutorial. In Models and Techniques for Performance Evaluation of Computer and Communications Systems. L. Donatiello and R.]]
31. Nelson, Eds., Springer-Verlag, New York, 330-358.]]
32. MASSEY, W. A. AND WHITT, W. 1993. Networks of infinite-server queues with nonstationary Poisson input. Queueing Syst., 13, 183-250.]]
33. MELAMED, B. AND WHITT, W. 1990. On arrivals that see time averages. Oper. Res. 38, 156-172.]]
34. MITRA, D. ANn WEISS, A. 1989. The transient behavior in Erlang's model for large trunk groups and various traffic conditions. In Teletraffic Science for the New Cost-Effective Systems, Networks and Services, Proceedings of ITC 12, M. Bonatti, Ed., North Holland, Amsterdam, 1367-1374.]]
35. NEUTS, M.F. 1989. Structured Stochastic Matrices of M/G/1 Type and Their Applications. Marcel Dekker, New York.]]
36. PAXSON, V. AND FLOYD, S. 1995. Wide area traffic: The failure of Poisson modeling. IEEE/ ACM Trans. Networking 3,226-244.]]
37. RIOm~AN, J. 1962. Stochastic Service Systems. Wiley, New York.]]
38. Ross, K W. 1995. Multiservice Loss Models for Broadband Telecommunication Networks. Springer Verlag, London.]]
39. Ross, K. W. AND WANG, J. 1992. Monte Carlo summation applied to product-form loss networks. Probab. Eng. Inf. Sci. 6, 323-348.]]
40. Ross, S.M. 1993. Introduction to Probability Models, fifth ed. Academic Press, New York,]]
41. SOBEL, M. 1980. Simple inequalities for multiserver queues. Manage. Sci. 26, 951-956.]]
42. SRIKANT, R. AND WmTT, W. 1995. Variance reduction in simulations of loss models. AT&T Bell Laboratories, Murray Hill, NJ. Oper. Res. (submitted).]]
43. TAKACS, L.1962. Introduction to the Theory of Queues. Oxford University Press, New York.]]
44. WH1TT, W. 1981.Comparing counting processes and queues. Adv. Appl. Probab. 13, 207- 22O.]]
45. WHITT, W.1982. On the heavy-traffic limit theorem for GI/G/~ queues. Adv. Appl. Probab. 14, 171-190.]]
46. WHITT, W. 1984.Heavy traffic approximations for service systems with blocking. AT&T Bell Lab. Tech. J. 63, 689-708.]]
47. WH~TT, W. 1989. Planning queueing simulations. Manage. Sci. 35, 1341-1366.]]
48. WHITT, W. 1991a. The efficiency of one long run versus independent replications in steadystate simulation. Manage. Sci. 37, 645-666.]]
49. WHiI'r, W. 1991b. A review of L = )~W and extensions. Queueing Syst. 9, 235--268.]]
50. WHilSt, W. 1992. Asymptotic formulas for Markov processes with applications to simulation. Oper. Res. 40, 279-291.]]
51. WILLIAMS, R. J. 1992. Asymptotic variance parameters for the boundary local times of reflected Brownian motion on a compact interval. J. Appl. Probab. 29, 996-1002.]]
52. WILLINGER, W. 1995. Traffic modeling for high-speed networks: theory versus practice. In IMA Volumes in Mathematics and its Applications, F. P. Kelly and R. J. Williams Eds., Springer-Verlag, New York (to appear).]]
53. WOLFF, R.W. 1982. Poisson arrivals see time averages. Oper. Res. 30, 223-231.]]

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Simulation types and techniques

      • Discrete-event simulation

• General and reference

  • Cross-computing tools and techniques

    • Measurement

    • Metrics

• Mathematics of computing

  • Probability and statistics

    • Statistical paradigms

      • Queueing theory