Rare-event simulation for tandem queues: a simple and efficient importance sampling scheme
This paper focuses on estimating the rare event of overflow in the downstream queue of a Jacksonian two-node tandem queue, relying on importance sampling. It is known that in this setting ‘traditional’ state-independent schemes perform poorly. More sophisticated state-dependent schemes yield asymptotic efficiency. Their drawback, however, is that they require a per-state computation of the new measure, so that it still consumes considerable machine time. The contribution of this paper is a scheme that combines asymptotic efficiency with low complexity. It retains the quality of the original state-dependent scheme, but its implementation is almost as simple as for state-independent analogues.
|Keywords||queueing, importance sampling, rare events, large deviations, tandem network|
|MSC||Queueing theory (msc 60K25)|
|THEME||Logistics (theme 3), Energy (theme 4)|
|Series||CWI. Probability, Networks and Algorithms [PNA]|
|Project||QoS Differentiation Mechanisms: Scheduling Algorithms|
|Note||Part of this research has been funded by the Dutch BSIK/BRICKS project. This article is also the result of joint research in the 3TU Centre of Competence NIRICT (Netherlands Institute for Research on ICT) within the Federation of Three Universities of Technology in The Netherlands|
Miretskiy, D.I, Mandjes, M.R.H, & Scheinhardt, W.R.W. (2008). Rare-event simulation for tandem queues: a simple and efficient importance sampling scheme. CWI. Probability, Networks and Algorithms [PNA]. CWI.