{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:19Z","timestamp":1750308739066,"version":"3.41.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2007,4,1]],"date-time":"2007-04-01T00:00:00Z","timestamp":1175385600000},"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":[[2007,4]]},"abstract":"<jats:p>In this article, we propose state-dependent importance sampling heuristics to estimate the probability of population overflow in Jackson queueing networks. These heuristics capture state-dependence along the boundaries (when one or more queues are empty), which is crucial for the asymptotic efficiency of the change of measure. The approach does not require difficult (and often intractable) mathematical analysis and is not limited by storage and computational requirements involved in adaptive importance sampling methodologies, particularly for a large state space. Experimental results on tandem, parallel, feed-forward, and feedback networks with a moderate number of nodes suggest that the proposed heuristics may yield asymptotically efficient estimators, possibly with bounded relative error, when applied to queueing networks wherein no other state-independent importance sampling techniques are known to be efficient. The heuristics are robust and remain effective for larger networks. Moreover, insights drawn from the basic networks considered in this article help understand sample path behavior along the boundaries, conditional on reaching the rare event of interest. This is key to the application of the methodology to networks of more general topologies. It is hoped that empirical findings and insights in this paper will encourage more research on related practical and theoretical issues.<\/jats:p>","DOI":"10.1145\/1225275.1225281","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Efficient importance sampling heuristics for the simulation of population overflow in Jackson networks"],"prefix":"10.1145","volume":"17","author":[{"given":"Victor F.","family":"Nicola","sequence":"first","affiliation":[{"name":"University of Twente, AE Enschede, The Netherlands"}]},{"given":"Tatiana S.","family":"Zaburnenko","sequence":"additional","affiliation":[{"name":"University of Twente, AE Enschede, The Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2007,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1060.0291"},{"volume-title":"Tech. Rep. RC 16280, IBM Research Division","year":"1990","author":"Anantharam V.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.2307\/3318578"},{"volume-title":"Queueing: Theory, Methods and Open Problems","year":"1995","author":"Asmussen S.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","first-page":"267","article-title":"Exponential convergence for Monte Carlo particle transport","volume":"50","author":"Booth T.","year":"1985","journal-title":"Trans. ANS"},{"volume-title":"Proceedings of the 2000 Winter Simulation Conference. IEEE Computer Society Press","author":"Boots N.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Bucklew J. 2004. Introduction to Rare Event Simulation. Springer-Verlag New York.   Bucklew J. 2004. Introduction to Rare Event Simulation. Springer-Verlag New York.","DOI":"10.1007\/978-1-4757-4078-3"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-5316(94)90005-1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1983.1103345"},{"key":"e_1_2_1_10_1","unstructured":"de Boer P. 2000. Analysis and efficient simulation of queuing models of telecommunication systems. Ph.D. dissertation. University of Twente.  de Boer P. 2000. Analysis and efficient simulation of queuing models of telecommunication systems. Ph.D. dissertation. University of Twente."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147224.1147226"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/ett.4460130403"},{"volume-title":"Proceedings of the 2001 Winter Simulation Conference. IEEE Computer Society Press","author":"Desai P.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.234852"},{"key":"e_1_2_1_15_1","unstructured":"Dupuis P. Sezer A. and Wang H. 2005. Dynamic importance sampling for queuing networks. Preprint.  Dupuis P. Sezer A. and Wang H. 2005. Dynamic importance sampling for queuing networks. Preprint."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1080\/10451120410001733845"},{"key":"e_1_2_1_17_1","first-page":"49","article-title":"Fast estimation of the statistics of excessive backlogs in tandem networks of queues","volume":"23","author":"Frater M.","year":"1989","journal-title":"Austral. Telecomm. Res."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02031598"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.106155"},{"key":"e_1_2_1_20_1","unstructured":"Garvels M. 2000. The splitting method in rare event simulation. Ph.D. dissertation. University of Twente Twente The Netherlands.  Garvels M. 2000. The splitting method in rare event simulation. Ph.D. dissertation. University of Twente Twente The Netherlands."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.47.4.585"},{"volume-title":"Proceedings of the 32nd Conference on Decision and Control. IEEE Computer Society Press","author":"Glasserman P.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/203091.203093"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.35.11.1367"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Hammersley J. and Handscomb D. 1964. Monte Carlo Methods. Methuen London UK.  Hammersley J. and Handscomb D. 1964. Monte Carlo Methods. Methuen London UK.","DOI":"10.1007\/978-94-009-5819-7"},{"key":"e_1_2_1_26_1","first-page":"172","article-title":"A scheme for adaptive biasing in importance sampling","volume":"52","author":"Heegaard P.","year":"1998","journal-title":"AE\u00dc Internat. J. Electron. Commun."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/203091.203094"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1113316.1113317"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/566392.566394"},{"key":"e_1_2_1_30_1","unstructured":"Kelly F. 1979. Reversibility and Stochastic Networks. Wiley New York.  Kelly F. 1979. Reversibility and Stochastic Networks. Wiley New York."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1029962748"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/566392.566395"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/379525.379528"},{"volume-title":"Proceedings of the 2005 Winter Simulation Conference. IEEE Computer Society Press","author":"Nicola V.","key":"e_1_2_1_34_1"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/QEST.2005.15"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1190095.1190119"},{"volume-title":"Proceedings of the 2006 Winter Simulation Conference. IEEE Computer Society Press","author":"Nicola V.","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.8649"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/974734.974735"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/511442.511444"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.106154"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.2307\/3214800"},{"volume-title":"Proceedings of INFOCOM'94","author":"Veciana G. D.","key":"e_1_2_1_43_1"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1002\/ett.4460130409"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.2307\/3213100"},{"volume-title":"Proceedings of the 5th St. Petersburg Workshop on Simulation (SPWS'05)","author":"Zaburnenko T.","key":"e_1_2_1_46_1"}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1225275.1225281","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1225275.1225281","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:08Z","timestamp":1750278128000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1225275.1225281"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,4]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,4]]}},"alternative-id":["10.1145\/1225275.1225281"],"URL":"https:\/\/doi.org\/10.1145\/1225275.1225281","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"type":"print","value":"1049-3301"},{"type":"electronic","value":"1558-1195"}],"subject":[],"published":{"date-parts":[[2007,4]]},"assertion":[{"value":"2007-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}