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

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

doi:10.1007/978-3-642-10406-0_8

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

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

Stochastic Operations Research

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

1 Downloads (Pure)

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 language	Undefined
Title of host publication	Network Control and Optimization, Proceedings of the Third EURO-NF Conference (NET-COOP)
Place of Publication	Berlin
Publisher	Springer
Pages	107-120
Number of pages	14
ISBN (Print)	978-3-642-10405-3
DOIs	https://doi.org/10.1007/978-3-642-10406-0_8
Publication status	Published - 2009
Event	3rd Euro-NF Conference on Network Control and Optimization, NET-COOP 2009 - Eindhoven, Netherlands Duration: 23 Nov 2009 → 25 Nov 2009 Conference number: 3

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Number	5894
Volume	5894
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	3rd Euro-NF Conference on Network Control and Optimization, NET-COOP 2009
Abbreviated title	NET-COOP
Country/Territory	Netherlands
City	Eindhoven
Period	23/11/09 → 25/11/09

Keywords

IR-69811
EWI-17326
METIS-264504

Access to Document

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

http://eprints.eemcs.utwente.nl/secure2/17326/01/2009-XMiretskiyScheinhardtMandjes.pdf

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). Springer. https://doi.org/10.1007/978-3-642-10406-0_8

@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 {\textquoteleft}traditional{\textquoteright} 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 ; 3rd Euro-NF Conference on Network Control and Optimization, NET-COOP 2009 ; Conference date: 23-11-2009 Through 25-11-2009",

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)",

address = "Germany",

}

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 proceeding › Conference contribution › Academic › peer-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 - Conference code: 3

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

T2 - 3rd Euro-NF Conference on Network Control and Optimization, NET-COOP 2009

Y2 - 23 November 2009 through 25 November 2009

ER -