Rare-event simulation for tandem queues: a simple and efficient importance sampling scheme

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

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

1 Citation (Scopus)

Abstract

This paper focuses on estimating the rare event of overflow in the downstream queue of a tandem Jackson 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 statedependent scheme, but its implementation is almost as simple as for state-independent analogues.
Original languageUndefined
Title of host publicationNetwork Control and Optimization, Proceedings of the Third EURO-NF Conference (NET-COOP)
Place of PublicationBerlin
PublisherSpringer
Pages107-120
Number of pages14
ISBN (Print)978-3-642-10405-3
DOIs
Publication statusPublished - 2009
Event3rd Euro-NF Conference on Network Control and Optimization, NET-COOP 2009 - Eindhoven, Netherlands
Duration: 23 Nov 200925 Nov 2009
Conference number: 3

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Number5894
Volume5894
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference3rd Euro-NF Conference on Network Control and Optimization, NET-COOP 2009
Abbreviated titleNET-COOP
CountryNetherlands
CityEindhoven
Period23/11/0925/11/09

Keywords

  • IR-69811
  • EWI-17326
  • METIS-264504

Cite this

Miretskiy, D. I., Scheinhardt, W. R. W., & Mandjes, M. R. H. (2009). Rare-event simulation for tandem queues: a simple and efficient importance sampling scheme. In Network Control and Optimization, Proceedings of the Third EURO-NF Conference (NET-COOP) (pp. 107-120). (Lecture Notes in Computer Science; Vol. 5894, No. 5894). Berlin: Springer. https://doi.org/10.1007/978-3-642-10406-0_8
Miretskiy, D.I. ; Scheinhardt, Willem R.W. ; Mandjes, M.R.H. / Rare-event simulation for tandem queues: a simple and efficient importance sampling scheme. Network Control and Optimization, Proceedings of the Third EURO-NF Conference (NET-COOP). Berlin : Springer, 2009. pp. 107-120 (Lecture Notes in Computer Science; 5894).
@inproceedings{c84cb053ad774fd3b8fa129fd964b6cc,
title = "Rare-event simulation for tandem queues: a simple and efficient importance sampling scheme",
abstract = "This paper focuses on estimating the rare event of overflow in the downstream queue of a tandem Jackson 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 statedependent scheme, but its implementation is almost as simple as for state-independent analogues.",
keywords = "IR-69811, EWI-17326, METIS-264504",
author = "D.I. Miretskiy and Scheinhardt, {Willem R.W.} and M.R.H. Mandjes",
note = "10.1007/978-3-642-10406-0_8",
year = "2009",
doi = "10.1007/978-3-642-10406-0_8",
language = "Undefined",
isbn = "978-3-642-10405-3",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
number = "5894",
pages = "107--120",
booktitle = "Network Control and Optimization, Proceedings of the Third EURO-NF Conference (NET-COOP)",

}

Miretskiy, DI, Scheinhardt, WRW & Mandjes, MRH 2009, Rare-event simulation for tandem queues: a simple and efficient importance sampling scheme. in Network Control and Optimization, Proceedings of the Third EURO-NF Conference (NET-COOP). Lecture Notes in Computer Science, no. 5894, vol. 5894, Springer, Berlin, pp. 107-120, 3rd Euro-NF Conference on Network Control and Optimization, NET-COOP 2009, Eindhoven, Netherlands, 23/11/09. https://doi.org/10.1007/978-3-642-10406-0_8

Rare-event simulation for tandem queues: a simple and efficient importance sampling scheme. / Miretskiy, D.I.; Scheinhardt, Willem R.W.; Mandjes, M.R.H.

Network Control and Optimization, Proceedings of the Third EURO-NF Conference (NET-COOP). Berlin : Springer, 2009. p. 107-120 (Lecture Notes in Computer Science; Vol. 5894, No. 5894).

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

TY - GEN

T1 - Rare-event simulation for tandem queues: a simple and efficient importance sampling scheme

AU - Miretskiy, D.I.

AU - Scheinhardt, Willem R.W.

AU - Mandjes, M.R.H.

N1 - 10.1007/978-3-642-10406-0_8

PY - 2009

Y1 - 2009

N2 - This paper focuses on estimating the rare event of overflow in the downstream queue of a tandem Jackson 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 statedependent scheme, but its implementation is almost as simple as for state-independent analogues.

AB - This paper focuses on estimating the rare event of overflow in the downstream queue of a tandem Jackson 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 statedependent scheme, but its implementation is almost as simple as for state-independent analogues.

KW - IR-69811

KW - EWI-17326

KW - METIS-264504

U2 - 10.1007/978-3-642-10406-0_8

DO - 10.1007/978-3-642-10406-0_8

M3 - Conference contribution

SN - 978-3-642-10405-3

T3 - Lecture Notes in Computer Science

SP - 107

EP - 120

BT - Network Control and Optimization, Proceedings of the Third EURO-NF Conference (NET-COOP)

PB - Springer

CY - Berlin

ER -

Miretskiy DI, Scheinhardt WRW, Mandjes MRH. Rare-event simulation for tandem queues: a simple and efficient importance sampling scheme. In Network Control and Optimization, Proceedings of the Third EURO-NF Conference (NET-COOP). Berlin: Springer. 2009. p. 107-120. (Lecture Notes in Computer Science; 5894). https://doi.org/10.1007/978-3-642-10406-0_8