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.
Additional Metadata
Keywords queueing, importance sampling, rare events, large deviations, tandem network
MSC Queueing theory (msc 60K25)
THEME Logistics (theme 3), Energy (theme 4)
Publisher CWI
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
Citation
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.