skip to main content
article

Efficient simulation of buffer overflow probabilities in jackson networks with feedback

Published: 01 October 2005 Publication History

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]
Avram, F., Dai, J., and Hasenbein, J. 2001. Explicit solutions for variational problems in the quadrant. Queueing Syst. 37, 261--291.
[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]
Calvin, J. M., Glynn, P. W., and Nakayama, M. K. 2001. Steady state simulation analysis: importance sampling using the semiregenerative method. In Proceedings of the 2001 Winter Simulation Conference. IEEE Press, Piscataway, New Jersey, 441--450.
[6]
Chang, C. S., Heidelberger, P., Juneja, S., and Shahabuddin, P. 1994. Effective bandwidth and fast simulation of ATM intree networks. Performance Evaluation 20, 45--65.
[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]
Glasserman, P. and Kou, S. 1995. Analysis of an importance sampling estimator for tandem queues. ACM Trans. Model. Comput. Simul. 5, 22--42.
[14]
Glynn, P. and Iglehart, D. 1989. Importance sampling for stochastic simulations. Manage. Sci. 35, 11, 1367--1392.
[15]
Glynn, P. and Whitt, W. 1992. The asymptotic efficiency of simulation estimators. Oper. Res. 40, 505--520.
[16]
Glynn, P. W., Heidelberger, P., Nicola, V. F., and Shahabuddin, P. 1993. Efficient estimation of the mean time between failures in nonregenerative dependability models. In Proceedings of the 1993 Winter Simulation Conference. IEEE Press, Piscataway, New Jersey, 311--316. G. W. Evans, M. Mollaghasemi, E. C. Russell and W. E. Biles (eds.).
[17]
Heidelberger, P. 1995. Fast simulation of rare events in queueing and reliability models. ACM Trans. Model. Comput. Simul. 5, 1, 43--85.
[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]
Juneja, S. 2001. Importance sampling and the cyclic approach. Oper. Res. 49, 6, 900--912.
[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]
Kroese, D. and Nicola, V. 2002. Efficient simulation of a tandem Jackson network. ACM Trans. Model. Comput. Simul. 12, 2, 119--141.
[23]
Lecuyer, P. and Champoux, Y. 1996. Importance sampling for large ATM-Type queueing networks. In Proceedings of the 1996 Winter Simulation Conference. IEEE Press, Piscataway, New Jersey, 309--316.
[24]
Lecuyer, P. and Champoux, Y. 2001. Estimating small cell-loss ratios in ATM switches via importance sampling. ACM Trans. Model. Comput. Simul. 11, 1, 76--105.
[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]
Randhawa, R. S. and Juneja, S. 2004. Combining importance sampling and temporal difference control variates to simulate Markov chains. ACM Trans. Model. Comput. Simul. 14, 1--30.
[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.

Cited By

View all
  • (2020)Approximation of the exit probability of a stable Markov modulated constrained random walkAnnals of Operations Research10.1007/s10479-020-03693-7Online publication date: 30-Jun-2020
  • (2019)Excessive backlog probabilities of two parallel queuesAnnals of Operations Research10.1007/s10479-019-03324-wOnline publication date: 20-Jul-2019
  • (2018)Approximation of excessive backlog probabilities of two tandem queuesJournal of Applied Probability10.1017/jpr.2018.6055:3(968-997)Online publication date: 16-Nov-2018
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Modeling and Computer Simulation
ACM Transactions on Modeling and Computer Simulation  Volume 15, Issue 4
October 2005
97 pages
ISSN:1049-3301
EISSN:1558-1195
DOI:10.1145/1113316
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2005
Published in TOMACS Volume 15, Issue 4

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Importance sampling
  2. Jackson networks
  3. asymptotic optimality
  4. queueing networks
  5. rare event simulation
  6. variance reduction

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 16 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2020)Approximation of the exit probability of a stable Markov modulated constrained random walkAnnals of Operations Research10.1007/s10479-020-03693-7Online publication date: 30-Jun-2020
  • (2019)Excessive backlog probabilities of two parallel queuesAnnals of Operations Research10.1007/s10479-019-03324-wOnline publication date: 20-Jul-2019
  • (2018)Approximation of excessive backlog probabilities of two tandem queuesJournal of Applied Probability10.1017/jpr.2018.6055:3(968-997)Online publication date: 16-Nov-2018
  • (2013)Optimal Sampling of Overflow Paths in Jackson NetworksMathematics of Operations Research10.1287/moor.2013.058638:4(698-719)Online publication date: 1-Nov-2013
  • (2013)Efficient importance sampling schemes for a feed-forward networkACM Transactions on Modeling and Computer Simulation10.1145/251745023:4(1-19)Online publication date: 16-Dec-2013
  • (2013)Rare event simulation of non-Markovian queueing networks using RESTART methodSimulation Modelling Practice and Theory10.1016/j.simpat.2013.05.01237(70-78)Online publication date: Sep-2013
  • (2011)Analysis of a Splitting Estimator for Rare Event Probabilities in Jackson NetworksStochastic Systems10.1287/11-SSY0261:2(306-339)Online publication date: Dec-2011
  • (2011)Rare‐Event SimulationHandbook of Monte Carlo Methods10.1002/9781118014967.ch10(381-419)Online publication date: 20-Sep-2011
  • (2010)The cross-entropy method with patching for rare-event simulation of large Markov chainsEuropean Journal of Operational Research10.1016/j.ejor.2010.07.002207:3(1380-1397)Online publication date: Dec-2010
  • (2010)Asymptotically optimal importance sampling for Jackson networks with a tree topologyQueueing Systems: Theory and Applications10.1007/s11134-009-9139-464:2(103-117)Online publication date: 1-Feb-2010
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media