{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:42:32Z","timestamp":1750308152051,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2005,10,1]],"date-time":"2005-10-01T00:00:00Z","timestamp":1128124800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Comput. Simul."],"published-print":{"date-parts":[[2005,10]]},"abstract":"<jats:p>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 \u2018target\u2019 queue and the remaining \u2018feeder\u2019 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.<\/jats:p>","DOI":"10.1145\/1113316.1113317","type":"journal-article","created":{"date-parts":[[2006,2,6]],"date-time":"2006-02-06T15:07:09Z","timestamp":1139238429000},"page":"281-315","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Efficient simulation of buffer overflow probabilities in jackson networks with feedback"],"prefix":"10.1145","volume":"15","author":[{"given":"Sandeep","family":"Juneja","sequence":"first","affiliation":[{"name":"Tata Institute of Fundamental Research, Mumbai, India"}]},{"given":"Victor","family":"Nicola","sequence":"additional","affiliation":[{"name":"University of Twente, AE Enschede, The Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2005,10]]},"reference":[{"volume-title":"Analysis of rare events in continuous time Markov chains via time reversal and fluid approximation. Rep. RC 16280","author":"Anantharam V.","key":"e_1_2_1_1_1","unstructured":"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 . 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."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S0304-4149(99)00051-4","article-title":"Large deviations and queuing networks: Methods for rate function identification","volume":"84","author":"Atar R.","year":"1999","unstructured":"Atar , R. and Dupuis , P. 1999 . Large deviations and queuing networks: Methods for rate function identification . Stochastic Process. Appl. 84 , 255 -- 296 . Atar, R. and Dupuis, P. 1999. Large deviations and queuing networks: Methods for rate function identification. Stochastic Process. Appl. 84, 255--296.","journal-title":"Stochastic Process. Appl."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011004620420"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"758","DOI":"10.1239\/aap\/1029955203","article-title":"A unified approach to fast teller queues and ATM","volume":"31","author":"Beck B.","year":"1999","unstructured":"Beck , B. , Dabrowski , A. , and McDonald , D. 1999 . A unified approach to fast teller queues and ATM . Adv. Appl. Prob. 31 , 758 -- 787 . Beck, B., Dabrowski, A., and McDonald, D. 1999. A unified approach to fast teller queues and ATM. Adv. Appl. Prob. 31, 758--787.","journal-title":"Adv. Appl. Prob."},{"volume-title":"Proceedings of the 2001 Winter Simulation Conference. IEEE Press","author":"Calvin J. M.","key":"e_1_2_1_5_1","unstructured":"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. 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."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-5316(94)90005-1"},{"key":"e_1_2_1_7_1","unstructured":"Chen H. and Yao D. D. 2001. Fundamentals of Queueing Networks: Performance Asymptotics and Optimization. Springer-Verlag New York.  Chen H. and Yao D. D. 2001. Fundamentals of Queueing Networks: Performance Asymptotics and Optimization. Springer-Verlag New York."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1214\/aop\/1176996393","article-title":"A uniform theory for sums of Markov chain transition probabilities","volume":"3","author":"Cogburn R.","year":"1975","unstructured":"Cogburn , R. 1975 . A uniform theory for sums of Markov chain transition probabilities . The Annals of Probability 3 , 191 -- 214 . Cogburn, R. 1975. A uniform theory for sums of Markov chain transition probabilities. The Annals of Probability 3, 191--214.","journal-title":"The Annals of Probability"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Dembo A. and Zeitouni O. 1998. Large Deviations Techniques and Applications 2nd ed. Springer New York NY.  Dembo A. and Zeitouni O. 1998. Large Deviations Techniques and Applications 2nd ed. Springer New York NY.","DOI":"10.1007\/978-1-4612-5320-4"},{"key":"e_1_2_1_10_1","first-page":"2689","article-title":"The large deviations principle for a general class of queuing systems","volume":"347","author":"Dupuis P.","year":"1995","unstructured":"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 . 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.","journal-title":"Trans. Amer. Math. Soc."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/S0304-4149(01)00151-X","article-title":"A time-reversed representation for the tail probabilities of stationary reflected Brownian motion","volume":"98","author":"Dupuis P.","year":"2002","unstructured":"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 . 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.","journal-title":"Stochastic Process. Appl."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"1395","DOI":"10.1109\/9.106155","article-title":"Optimally efficient estimation of the statistics of rare events in queueing networks","volume":"36","author":"Frater M.","year":"1991","unstructured":"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 . 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.","journal-title":"IEEE Trans. Auto. Cont."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/203091.203093"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.35.11.1367"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.40.3.505"},{"volume-title":"Proceedings of the 1993 Winter Simulation Conference. IEEE Press","author":"Glynn P. W.","key":"e_1_2_1_16_1","unstructured":"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.). 10.1145\/256563.256657 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.). 10.1145\/256563.256657"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/203091.203094"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"962","DOI":"10.1214\/aoap\/1019487515","article-title":"Large deviations of Jackson networks","volume":"10","author":"Ignatiouk-Robert I.","year":"2000","unstructured":"Ignatiouk-Robert , I. 2000 . Large deviations of Jackson networks . The Annals of Applied Probability 10 , 3, 962 -- 1001 . Ignatiouk-Robert, I. 2000. Large deviations of Jackson networks. The Annals of Applied Probability 10, 3, 962--1001.","journal-title":"The Annals of Applied Probability"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1070\/RM1994v049n02ABEH002204","article-title":"Boundary effects in large deviations problems","volume":"49","author":"Ignatyuk I.","year":"1994","unstructured":"Ignatyuk , I. , Malyshev , V. , and Scherbakov , V. 1994 . Boundary effects in large deviations problems . Russian Math. Surveys 49 , 2, 41 -- 99 . Ignatyuk, I., Malyshev, V., and Scherbakov, V. 1994. Boundary effects in large deviations problems. Russian Math. Surveys 49, 2, 41--99.","journal-title":"Russian Math. Surveys"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.49.6.900.10016"},{"key":"e_1_2_1_21_1","volume-title":"Tech. Rep. Tata Institute of Fundamental Research STCS-03\/01. Available at authors web pages.","author":"Juneja S.","year":"2003","unstructured":"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. 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."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/566392.566395"},{"volume-title":"Proceedings of the 1996 Winter Simulation Conference. IEEE Press","author":"Lecuyer P.","key":"e_1_2_1_23_1","unstructured":"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. 10.1145\/256562.256637 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. 10.1145\/256562.256637"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/379525.379528"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1109\/9.8649","article-title":"A quick simulation method for excessive backlogs in networks of queues","volume":"34","author":"Parekh S.","year":"1989","unstructured":"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 . 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.","journal-title":"IEEE Trans. Auto. Cont."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/974734.974735"},{"volume-title":"An Introduction to Queuing Networks","author":"Walrand J.","key":"e_1_2_1_27_1","unstructured":"Walrand , J. 1988. An Introduction to Queuing Networks . Prentice Hall , Englewood, New Jersey. Walrand, J. 1988. An Introduction to Queuing Networks. Prentice Hall, Englewood, New Jersey."},{"volume-title":"Probability with Martingales","author":"Williams D.","key":"e_1_2_1_28_1","unstructured":"Williams , D. 1991. Probability with Martingales . Cambridge University Press , Cambridge . Williams, D. 1991. Probability with Martingales. Cambridge University Press, Cambridge."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Zeevi A. and Glynn P. W. 2005. Estimating tail decays for stationary sequences via extreme values. To appear in Adv. Appl. Probab.  Zeevi A. and Glynn P. W. 2005. Estimating tail decays for stationary sequences via extreme values. To appear in Adv. Appl. Probab.","DOI":"10.1017\/S0001867800012933"}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1113316.1113317","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1113316.1113317","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:18:47Z","timestamp":1750263527000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1113316.1113317"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,10]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2005,10]]}},"alternative-id":["10.1145\/1113316.1113317"],"URL":"https:\/\/doi.org\/10.1145\/1113316.1113317","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"type":"print","value":"1049-3301"},{"type":"electronic","value":"1558-1195"}],"subject":[],"published":{"date-parts":[[2005,10]]},"assertion":[{"value":"2005-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}