Efficient heuristics for the simulation of population overflow in series and parallel queues

ABSTRACT

In this paper we propose state-dependent importance sampling heuristics to estimate the probability of population overflow in Markovian networks of series and parallel queues. These heuristics capture state-dependence along the boundaries (when one or more queues are empty) which is critical for the asymptotic optimality of the change of measure. The approach does not require difficult (and often intractable) mathematical analysis or costly optimization involved in adaptive importance sampling methodologies. Experimental results on tandem and parallel networks with a moderate number of nodes yield asymptotically efficient estimates (often with bounded relative error) where no other state-independent importance sampling techniques are known to be efficient. Insight drawn from simulating basic networks in this paper promises the applicability of the proposed methodology to larger networks with more general topologies.

REFERENCES

• 1: Ahamed, T. P. I., V. S. Borkar, and S. K. Juneja (2004). Adaptive importance sampling technique for Markov chains using stochastic approximation. Operations Research. Accepted.
• 2: Asmussen, S., and R. Y. Rubinstein (1995). Steady state rare events simulation in queueing models and its complexity properties. In Advances in Queueing: Theory, Methods and Open problems, ed. J. H. Dshalalow, 429--461. CRC Press, New York.
• 3: Anantharam, V., P. Heidelberger, and P. Tsoucas (1990). Analysis of rare events in continuous time Markov chains via time reversal and fluid approximation. IBM Research Report RC 16280, Yorktown Heights, New York.
• 4: de Boer, P. T. (2000). Analysis and efficient simulation of queueing models of telecommunication systems. PhD Thesis, University of Twente.
• 5: 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
• 6: de Boer, P. T., and V. F. Nicola (2002). Adaptive state-dependent importance sampling simulation of Markovian queueing networks. European Transactions on Telecommunications 13 (4): 303--315.
• 7: de Boer, P. T. (2004). Analysis of sate-independent IS measures for the two-node tandem queue. International Workshop on Rare Event Simulation (RESIM'04), Budapest, Hungary.
• 8: 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
• 9: Cottrell, M., J.-C. Fort, and G. Malgouyres (1983). Large deviations and rare events in the study of stochastic algorithms. IEEE Trans. on Automatic Control28 (9) 907--920.
• 10: De Veciana, G., C. Courcoubetis, and J. Walrand (1994). Decoupling bandwidths for networks: A decomposition approach to resource management for networks. In Proceedings of INFOCOM'94, IEEE Press, 466--473.
• 11: Frater, M. R., and B. D. O. Anderson (1989). Fast estimation of the statistics of excessive backlogs in tandem networks of queues. Australian Telecommun. Res.23 (1) 49--55.
• 12: Frater, M. R., T. M. Lenon, and B. D. O. Anderson (1991). Optimally efficient estimation of the statistics of rare events in queueing networks. IEEE Trans. Autom. Control 36: 1395--1405.
• 13: Frater, M. R., and B. D. O. Anderson (1994). Fast simulation of buffer overflows in tandem networks of GI/GI/1 queues. Ann. Oper. Res.49 207--220.
• 14: Garvels, M. J. J. (2000). The splitting method in rare event simulation. PhD Thesis, University of Twente.
• 15: Paul Glasserman , Philip Heidelberger , Perwez Shahabuddin , Tim Zajic, Multilevel Splitting for Estimating Rare Event Probabilities, Operations Research, v.47 n.4, p.585-600, April 1999 [doi>10.1287/opre.47.4.585]
• 16: Paul Glasserman , Shing-Gang Kou, Analysis of an importance sampling estimator for tandem queues, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.5 n.1, p.22-42, Jan. 1995 [doi>10.1145/203091.203093]
• 17: Glasserman, P., and Y. Wang (1997). Counterexamples in importance sampling for large deviations probabilities. Ann. Appl. Probab. 7 (3) 731--746.
• 18: 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]
• 19: Philip Heidelberger, Fast simulation of rare events in queueing and reliability models, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.5 n.1, p.43-85, Jan. 1995 [doi>10.1145/203091.203094]
• 20: 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 [doi>10.1145/1113316.1113317]
• 21: Kelly, F. P. (1979). Reversibility and Stochastic Networks. Wiley, New York.
• 22: 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 [doi>10.1145/566392.566395]
• 23: 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 [doi>10.1145/379525.379528]
• 24: Victor F. Nicola , Tatiana S. Zaburnenko, Importance Sampling Simulation of Population Overflow in Two-node Tandem Networks, Proceedings of the Second International Conference on the Quantitative Evaluation of Systems (QEST'05) on The Quantitative Evaluation of Systems, p.220, September 19-22, 2005 [doi>10.1109/QEST.2005.15]
• 25: 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
• 26: Parekh, S., and J. Walrand (1989). A quick simulation method for excessive backlogs in networks of queues. IEEE Transactions on Automatic Control 34: 54--66.
• 27: 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 [doi>10.1145/974734.974735]
• 28: Reuven Y. Rubinstein, Cross-entropy and rare events for maximal cut and partition problems, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.12 n.1, p.27-53, January 2002 [doi>10.1145/511442.511444]
• 29: Sadowsky, J. S. (1991). Large deviations theory and efficient simulation of excessive backlogs in a GI/GI/m queue. IEEE Trans. on Automatic Control36 1383--1394.
• 30: Tsoucas, P. (1992). Rare events in series of queues. J. Appl. Probab. 29 168--175.
• 31: Villen-Altamirano, M., and J. Villen-Altamirano (2002). Analysis of RESTART simulation: theoretical basis and Sensitivity study. European Transactions on Telecommunications13 (4) 373--386.
• 32: Weber, R. R. (1979). The interchangeability of M/M/1 queues in series. Journal of Applied Probability 16: 690--695.
• 33: Zaburnenko, T. S., and V. F. Nicola (2005). Efficient heuristics for simulating population overflow in tandem networks. In Proceedings of the 5th St. Petersburg Workshop on Simulation (SPWS'05), ed. S. M. Ermakov, V. B. Melas, and A. N. Pepelyshev, 755--764. St. Petersburg University Publishers.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.1 Simulation Theory
      I.6.8 Types of Simulation

General Terms:
Experimentation, Theory