Simple and efficient importance sampling scheme for a tandem queue with server slow-down

D.I. Miretskiy, Willem R.W. Scheinhardt, M.R.H. Mandjes

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

13 Downloads (Pure)

Abstract

This paper considers importance sampling as a tool for rare-event simulation. The system at hand is a so-called tandem queue with slow-down, which essentially means that the server of the first queue (or: upstreanm queue) switches to a lower speed when the second queue (downstream queue) exceeds some threshold. The goal is to assess to what extent such a policy succeeds in protecting the first queue, and therefore we focus on estimating the probability of overflow in the downstream queue. It is known that in this setting importance sampling with traditional state-independent distributions performs poorly. More sophisticated state-dependent schemes can be shown to be asymptotically efficient, but their implementation may be problematic, as for each state the new measure has to be computed. This paper presents an algorithm that is considerably simpler than the fully state-dependent scheme; it requires low computational effort, but still has high efficiency.
Original languageUndefined
Title of host publicationProceedings of the 7th Internationals Workshop on Rare Event Simulation, RESIM 2008
Place of PublicationRennes, France
PublisherINRIA
Pages38-49
Number of pages12
ISBN (Print)not assigned
Publication statusPublished - 2008

Publication series

Name
PublisherINRIA

Keywords

  • IR-69815
  • EWI-17342
  • METIS-264511

Cite this

Miretskiy, D. I., Scheinhardt, W. R. W., & Mandjes, M. R. H. (2008). Simple and efficient importance sampling scheme for a tandem queue with server slow-down. In Proceedings of the 7th Internationals Workshop on Rare Event Simulation, RESIM 2008 (pp. 38-49). Rennes, France: INRIA.
Miretskiy, D.I. ; Scheinhardt, Willem R.W. ; Mandjes, M.R.H. / Simple and efficient importance sampling scheme for a tandem queue with server slow-down. Proceedings of the 7th Internationals Workshop on Rare Event Simulation, RESIM 2008. Rennes, France : INRIA, 2008. pp. 38-49
@inproceedings{6344f4e843be49da952605f7f0c92820,
title = "Simple and efficient importance sampling scheme for a tandem queue with server slow-down",
abstract = "This paper considers importance sampling as a tool for rare-event simulation. The system at hand is a so-called tandem queue with slow-down, which essentially means that the server of the first queue (or: upstreanm queue) switches to a lower speed when the second queue (downstream queue) exceeds some threshold. The goal is to assess to what extent such a policy succeeds in protecting the first queue, and therefore we focus on estimating the probability of overflow in the downstream queue. It is known that in this setting importance sampling with traditional state-independent distributions performs poorly. More sophisticated state-dependent schemes can be shown to be asymptotically efficient, but their implementation may be problematic, as for each state the new measure has to be computed. This paper presents an algorithm that is considerably simpler than the fully state-dependent scheme; it requires low computational effort, but still has high efficiency.",
keywords = "IR-69815, EWI-17342, METIS-264511",
author = "D.I. Miretskiy and Scheinhardt, {Willem R.W.} and M.R.H. Mandjes",
year = "2008",
language = "Undefined",
isbn = "not assigned",
publisher = "INRIA",
pages = "38--49",
booktitle = "Proceedings of the 7th Internationals Workshop on Rare Event Simulation, RESIM 2008",

}

Miretskiy, DI, Scheinhardt, WRW & Mandjes, MRH 2008, Simple and efficient importance sampling scheme for a tandem queue with server slow-down. in Proceedings of the 7th Internationals Workshop on Rare Event Simulation, RESIM 2008. INRIA, Rennes, France, pp. 38-49.

Simple and efficient importance sampling scheme for a tandem queue with server slow-down. / Miretskiy, D.I.; Scheinhardt, Willem R.W.; Mandjes, M.R.H.

Proceedings of the 7th Internationals Workshop on Rare Event Simulation, RESIM 2008. Rennes, France : INRIA, 2008. p. 38-49.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Simple and efficient importance sampling scheme for a tandem queue with server slow-down

AU - Miretskiy, D.I.

AU - Scheinhardt, Willem R.W.

AU - Mandjes, M.R.H.

PY - 2008

Y1 - 2008

N2 - This paper considers importance sampling as a tool for rare-event simulation. The system at hand is a so-called tandem queue with slow-down, which essentially means that the server of the first queue (or: upstreanm queue) switches to a lower speed when the second queue (downstream queue) exceeds some threshold. The goal is to assess to what extent such a policy succeeds in protecting the first queue, and therefore we focus on estimating the probability of overflow in the downstream queue. It is known that in this setting importance sampling with traditional state-independent distributions performs poorly. More sophisticated state-dependent schemes can be shown to be asymptotically efficient, but their implementation may be problematic, as for each state the new measure has to be computed. This paper presents an algorithm that is considerably simpler than the fully state-dependent scheme; it requires low computational effort, but still has high efficiency.

AB - This paper considers importance sampling as a tool for rare-event simulation. The system at hand is a so-called tandem queue with slow-down, which essentially means that the server of the first queue (or: upstreanm queue) switches to a lower speed when the second queue (downstream queue) exceeds some threshold. The goal is to assess to what extent such a policy succeeds in protecting the first queue, and therefore we focus on estimating the probability of overflow in the downstream queue. It is known that in this setting importance sampling with traditional state-independent distributions performs poorly. More sophisticated state-dependent schemes can be shown to be asymptotically efficient, but their implementation may be problematic, as for each state the new measure has to be computed. This paper presents an algorithm that is considerably simpler than the fully state-dependent scheme; it requires low computational effort, but still has high efficiency.

KW - IR-69815

KW - EWI-17342

KW - METIS-264511

M3 - Conference contribution

SN - not assigned

SP - 38

EP - 49

BT - Proceedings of the 7th Internationals Workshop on Rare Event Simulation, RESIM 2008

PB - INRIA

CY - Rennes, France

ER -

Miretskiy DI, Scheinhardt WRW, Mandjes MRH. Simple and efficient importance sampling scheme for a tandem queue with server slow-down. In Proceedings of the 7th Internationals Workshop on Rare Event Simulation, RESIM 2008. Rennes, France: INRIA. 2008. p. 38-49