Efficient simulation of buffer overflow probabilities in jackson networks with feedback

ABSTRACT

Consider a Jackson network that allows feedback and that has a single server at each queue. The queues in this network are classified as a single ‘target’ queue and the remaining ‘feeder’ queues. In this setting we develop the large deviations limit and an asymptotically efficient importance sampling estimator for the probability that the target queue overflows during its busy period, under some regularity conditions on the feeder queue-length distribution at the initiation of the target queue busy period. This importance sampling distribution is obtained as a solution to a non-linear program. We especially focus on the case where the feeder queues, at the initiation of the target queue busy period, have the steady state distribution corresponding to these instants. In this setting, we explicitly identify the importance sampling distribution when the feeder queue service rates exceed a specified threshold. We also relate our work to the existing large deviations literature to develop a perspective on successes and limitations of our results.

REFERENCES

• 1: Anantharam, V., Heidelberger, P., and Tsoucas., P. 1990. Analysis of rare events in continuous time Markov chains via time reversal and fluid approximation. Rep. RC 16280, IBM, Yorktown Heights, New York.
• 2: Atar, R. and Dupuis, P. 1999. Large deviations and queuing networks: Methods for rate function identification. Stochastic Process. Appl. 84, 255--296.
• 3: F. Avram , J. G. Dai , J. J. Hasenbein, Explicit Solutions for Variational Problems in the Quadrant, Queueing Systems: Theory and Applications, v.37 n.1-3, p.259-289, March 2001 [doi>10.1023/A:1011004620420]
• 4: Beck, B., Dabrowski, A., and McDonald, D. 1999. A unified approach to fast teller queues and ATM. Adv. Appl. Prob. 31, 758--787.
• 5: 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
• 6: 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
• 7: Chen, H. and Yao, D. D. 2001. Fundamentals of Queueing Networks: Performance, Asymptotics and Optimization. Springer-Verlag, New York.
• 8: Cogburn, R. 1975. A uniform theory for sums of Markov chain transition probabilities. The Annals of Probability 3, 191--214.
• 9: Dembo, A. and Zeitouni, O. 1998. Large Deviations Techniques and Applications, 2nd ed. Springer, New York, NY.
• 10: Dupuis, P. and Ellis, R. S. 1995. The large deviations principle for a general class of queuing systems. Trans. Amer. Math. Soc. 347, 2689--2751.
• 11: Dupuis, P. and Ramanan, K. 2002. A time-reversed representation for the tail probabilities of stationary reflected Brownian motion. Stochastic Process. Appl. 98, 253--287.
• 12: Frater, M., Lennon, T., and Anderson, B. 1991. Optimally efficient estimation of the statistics of rare events in queueing networks. IEEE Trans. Auto. Cont. 36, 1395--1405.
• 13: 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]
• 14: 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]
• 15: 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]
• 16: 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]
• 17: 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]
• 18: Ignatiouk-Robert, I. 2000. Large deviations of Jackson networks. The Annals of Applied Probability 10, 3, 962--1001.
• 19: Ignatyuk, I., Malyshev, V., and Scherbakov, V. 1994. Boundary effects in large deviations problems. Russian Math. Surveys 49, 2, 41--99.
• 20: Sandeep Juneja, Importance Sampling and the Cyclic Approach, Operations Research, v.49 n.6, p.900-912, November 2001 [doi>10.1287/opre.49.6.900.10016]
• 21: Juneja, S. and Nicola, V. 2003. Efficient simulation of buffer overflow probabilities in queuing networks with probabilistic routing. Tech. Rep. Tata Institute of Fundamental Research STCS-03/01. Available at authors web pages.
• 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, 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 [doi>10.1145/256562.256637]
• 24: 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]
• 25: Parekh, S. and Walrand, J. 1989. A quick simulation method for excessive backlogs in networks of queues. IEEE Trans. Auto. Cont. 34, 1, 54--66.
• 26: 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]
• 27: Walrand, J. 1988. An Introduction to Queuing Networks. Prentice Hall, Englewood, New Jersey.
• 28: Williams, D. 1991. Probability with Martingales. Cambridge University Press, Cambridge.
• 29: Zeevi, A. and Glynn, P. W. 2005. Estimating tail decays for stationary sequences via extreme values. To appear in Adv. Appl. Probab.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.1 Simulation Theory

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory; Stochastic processes

General Terms:
Algorithms, Performance, Theory

Keywords:
Importance sampling, Jackson networks, asymptotic optimality, queueing networks, rare event simulation, variance reduction