Optimal Sampling of Overflow Paths in Jackson Networks

• 成果类型: Article
• 署名作者: Blanchet, Jose
• 署名单位: Columbia University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2013.0586
• 发表日期: 2013
• 页码: 698-719
• 关键词: multiclass queuing-networks; rare-event simulation; large deviations; STABILITY

摘要

We consider the problems of computing overflow probabilities at level N in any subset of stations in a Jackson network and of simulating sample paths conditional on overflow. We construct algorithms that take O(N) function evaluations to estimate such overflow probabilities within a prescribed relative accuracy and to simulate paths conditional on overflow at level N. The algorithms that we present are optimal in the sense that the best possible performance that can be expected for conditional sampling involves Omega(N) running time. As we explain in our development, our techniques have the potential to be applicable to more general classes of networks.