Estimating buffer overflows in three stages using cross-entropy

P.T. de Boer; D.P. Kroese; R.Y. Rubinstein

doi:10.1109/WSC.2002.1172899

Estimating buffer overflows in three stages using cross-entropy

P.T. de Boer, D.P. Kroese, R.Y. Rubinstein

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

18 Citations (Scopus)

60 Downloads (Pure)

Abstract

In this paper we propose a fast adaptive Importance Sampling method for the efficient simulation of buffer overflow probabilities in queueing networks. The method comprises three stages. First we estimate the minimum Cross-Entropy tilting parameter for a small buffer level; next, we use this as a starting value for the estimation of the optimal tilting parameter for the actual (large) buffer level; finally, the tilting parameter just found is used to estimate the overflow probability of interest. We recognize three distinct properties of the method which together explain why the method works well; we conjecture that they hold for quite general queueing networks. Numerical results support this conjecture and demonstrate the high efficiency of the proposed algorithm.

Original language	English
Title of host publication	Proceedings of the 2002 Winter Simulation Conference (WSC 2002)
Editors	E. Yücesan, C.-H. Chen, J.L. Snowdon, J.M. Charnes
Place of Publication	Piscataway, NJ
Publisher	IEEE
Pages	301-309
Number of pages	9
ISBN (Print)	0-7803-7615-3, 0-7803-7614-5
DOIs	https://doi.org/10.1109/WSC.2002.1172899
Publication status	Published - Dec 2002
Event	2002 Winter Simulation Conference - San Diego, United States Duration: 8 Dec 2002 → 11 Dec 2002

Conference

Conference	2002 Winter Simulation Conference
Abbreviated title	WSC 2002
Country/Territory	United States
City	San Diego
Period	8/12/02 → 11/12/02

Keywords

2023 OA procedure

Access to Document

10.1109/WSC.2002.1172899

ArticleFinal published version, 813 KBLicence: Taverne

Cite this

@inproceedings{34ab4dc28a4b4cb883494f0f0a94d4e8,

title = "Estimating buffer overflows in three stages using cross-entropy",

abstract = "In this paper we propose a fast adaptive Importance Sampling method for the efficient simulation of buffer overflow probabilities in queueing networks. The method comprises three stages. First we estimate the minimum Cross-Entropy tilting parameter for a small buffer level; next, we use this as a starting value for the estimation of the optimal tilting parameter for the actual (large) buffer level; finally, the tilting parameter just found is used to estimate the overflow probability of interest. We recognize three distinct properties of the method which together explain why the method works well; we conjecture that they hold for quite general queueing networks. Numerical results support this conjecture and demonstrate the high efficiency of the proposed algorithm.",

keywords = "2023 OA procedure",

author = "{de Boer}, P.T. and D.P. Kroese and R.Y. Rubinstein",

year = "2002",

month = dec,

doi = "10.1109/WSC.2002.1172899",

language = "English",

isbn = "0-7803-7615-3",

pages = "301--309",

editor = "E. Y{\"u}cesan and C.-H. Chen and J.L. Snowdon and J.M. Charnes",

booktitle = "Proceedings of the 2002 Winter Simulation Conference (WSC 2002)",

publisher = "IEEE",

address = "United States",

note = "2002 Winter Simulation Conference, WSC 2002 ; Conference date: 08-12-2002 Through 11-12-2002",

}

de Boer, PT, Kroese, DP & Rubinstein, RY 2002, Estimating buffer overflows in three stages using cross-entropy. in E Yücesan, C-H Chen, JL Snowdon & JM Charnes (eds), Proceedings of the 2002 Winter Simulation Conference (WSC 2002). IEEE, Piscataway, NJ, pp. 301-309, 2002 Winter Simulation Conference, San Diego, California, United States, 8/12/02. https://doi.org/10.1109/WSC.2002.1172899

Estimating buffer overflows in three stages using cross-entropy. / de Boer, P.T.; Kroese, D.P.; Rubinstein, R.Y.
Proceedings of the 2002 Winter Simulation Conference (WSC 2002). ed. / E. Yücesan; C.-H. Chen; J.L. Snowdon; J.M. Charnes. Piscataway, NJ: IEEE, 2002. p. 301-309.

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

TY - GEN

T1 - Estimating buffer overflows in three stages using cross-entropy

AU - de Boer, P.T.

AU - Kroese, D.P.

AU - Rubinstein, R.Y.

PY - 2002/12

Y1 - 2002/12

N2 - In this paper we propose a fast adaptive Importance Sampling method for the efficient simulation of buffer overflow probabilities in queueing networks. The method comprises three stages. First we estimate the minimum Cross-Entropy tilting parameter for a small buffer level; next, we use this as a starting value for the estimation of the optimal tilting parameter for the actual (large) buffer level; finally, the tilting parameter just found is used to estimate the overflow probability of interest. We recognize three distinct properties of the method which together explain why the method works well; we conjecture that they hold for quite general queueing networks. Numerical results support this conjecture and demonstrate the high efficiency of the proposed algorithm.

AB - In this paper we propose a fast adaptive Importance Sampling method for the efficient simulation of buffer overflow probabilities in queueing networks. The method comprises three stages. First we estimate the minimum Cross-Entropy tilting parameter for a small buffer level; next, we use this as a starting value for the estimation of the optimal tilting parameter for the actual (large) buffer level; finally, the tilting parameter just found is used to estimate the overflow probability of interest. We recognize three distinct properties of the method which together explain why the method works well; we conjecture that they hold for quite general queueing networks. Numerical results support this conjecture and demonstrate the high efficiency of the proposed algorithm.

KW - 2023 OA procedure

U2 - 10.1109/WSC.2002.1172899

DO - 10.1109/WSC.2002.1172899

M3 - Conference contribution

SN - 0-7803-7615-3

SN - 0-7803-7614-5

SP - 301

EP - 309

BT - Proceedings of the 2002 Winter Simulation Conference (WSC 2002)

A2 - Yücesan, E.

A2 - Chen, C.-H.

A2 - Snowdon, J.L.

A2 - Charnes, J.M.

PB - IEEE

CY - Piscataway, NJ

T2 - 2002 Winter Simulation Conference

Y2 - 8 December 2002 through 11 December 2002

ER -

Estimating buffer overflows in three stages using cross-entropy

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this