Fast simulation of the leaky bucket algorithm

Victor F. Nicola; Gertjan J.A. Hagesteijn; Byurig G. Kim

doi:10.1109/WSC.1994.717144

Fast simulation of the leaky bucket algorithm

Victor F. Nicola, Gertjan J.A. Hagesteijn, Byurig G. Kim

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

2 Citations (Scopus)

451 Downloads (Pure)

Abstract

We use fast simulation methods, based on importance sampling, to efficiently estimate cell loss probability in queueing models of the Leaky Bucket algorithm. One of these models was introduced by Berger (1991), in which the rare event of a cell loss is related to the rare event of an empty finite buffer in an "overloaded" queue. In particular, we propose a heuristic change of measure for importance sampling to efficiently estimate the probability of the rare empty-buffer event in an asymptotically unstable GI/GI/1/k queue. This change of measure is, in a way, "dual" to that proposed by Parekh and Walrand (1989) to estimate the probability of a rare buffer overflow event. We present empirical results to demonstrate the effectiveness of our fast simulation method. Since we have not yet obtained a mathematical proof, we can only conjecture that our heuristic is asymptotically optimal, as k/spl rarr//spl infin/.

Original language	English
Title of host publication	Proceedings of the 1994 Winter Simulation Conference
Editors	J.D. Tew, S. Manivannan, D.A. Sadowski, A.F. Seil
Place of Publication	Orlando, FL, USA
Publisher	IEEE
Number of pages	8
ISBN (Print)	9780780321090
DOIs	https://doi.org/10.1109/WSC.1994.717144
Publication status	Published - 14 Nov 1994
Event	1994 Winter Simulation Conference - Orlando, United States Duration: 11 Dec 1994 → 12 Dec 1994

Conference

Conference	1994 Winter Simulation Conference
Abbreviated title	WSC 1994
Country/Territory	United States
City	Orlando
Period	11/12/94 → 12/12/94

Access to Document

10.1109/WSC.1994.717144

Nicola1994fastFinal published version, 945 KB

Cite this

@inproceedings{1c79e356b83b4aac86029d95c453feb2,

title = "Fast simulation of the leaky bucket algorithm",

abstract = "We use fast simulation methods, based on importance sampling, to efficiently estimate cell loss probability in queueing models of the Leaky Bucket algorithm. One of these models was introduced by Berger (1991), in which the rare event of a cell loss is related to the rare event of an empty finite buffer in an {"}overloaded{"} queue. In particular, we propose a heuristic change of measure for importance sampling to efficiently estimate the probability of the rare empty-buffer event in an asymptotically unstable GI/GI/1/k queue. This change of measure is, in a way, {"}dual{"} to that proposed by Parekh and Walrand (1989) to estimate the probability of a rare buffer overflow event. We present empirical results to demonstrate the effectiveness of our fast simulation method. Since we have not yet obtained a mathematical proof, we can only conjecture that our heuristic is asymptotically optimal, as k/spl rarr//spl infin/.",

author = "Nicola, {Victor F.} and Hagesteijn, {Gertjan J.A.} and Kim, {Byurig G.}",

year = "1994",

month = nov,

day = "14",

doi = "10.1109/WSC.1994.717144",

language = "English",

isbn = "9780780321090",

editor = "J.D. Tew and S. Manivannan and D.A. Sadowski and A.F. Seil",

booktitle = "Proceedings of the 1994 Winter Simulation Conference",

publisher = "IEEE",

address = "United States",

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

}

TY - GEN

T1 - Fast simulation of the leaky bucket algorithm

AU - Nicola, Victor F.

AU - Hagesteijn, Gertjan J.A.

AU - Kim, Byurig G.

PY - 1994/11/14

Y1 - 1994/11/14

N2 - We use fast simulation methods, based on importance sampling, to efficiently estimate cell loss probability in queueing models of the Leaky Bucket algorithm. One of these models was introduced by Berger (1991), in which the rare event of a cell loss is related to the rare event of an empty finite buffer in an "overloaded" queue. In particular, we propose a heuristic change of measure for importance sampling to efficiently estimate the probability of the rare empty-buffer event in an asymptotically unstable GI/GI/1/k queue. This change of measure is, in a way, "dual" to that proposed by Parekh and Walrand (1989) to estimate the probability of a rare buffer overflow event. We present empirical results to demonstrate the effectiveness of our fast simulation method. Since we have not yet obtained a mathematical proof, we can only conjecture that our heuristic is asymptotically optimal, as k/spl rarr//spl infin/.

AB - We use fast simulation methods, based on importance sampling, to efficiently estimate cell loss probability in queueing models of the Leaky Bucket algorithm. One of these models was introduced by Berger (1991), in which the rare event of a cell loss is related to the rare event of an empty finite buffer in an "overloaded" queue. In particular, we propose a heuristic change of measure for importance sampling to efficiently estimate the probability of the rare empty-buffer event in an asymptotically unstable GI/GI/1/k queue. This change of measure is, in a way, "dual" to that proposed by Parekh and Walrand (1989) to estimate the probability of a rare buffer overflow event. We present empirical results to demonstrate the effectiveness of our fast simulation method. Since we have not yet obtained a mathematical proof, we can only conjecture that our heuristic is asymptotically optimal, as k/spl rarr//spl infin/.

U2 - 10.1109/WSC.1994.717144

DO - 10.1109/WSC.1994.717144

M3 - Conference contribution

SN - 9780780321090

BT - Proceedings of the 1994 Winter Simulation Conference

A2 - Tew, J.D.

A2 - Manivannan, S.

A2 - Sadowski, D.A.

A2 - Seil, A.F.

PB - IEEE

CY - Orlando, FL, USA

T2 - 1994 Winter Simulation Conference

Y2 - 11 December 1994 through 12 December 1994

ER -

Fast simulation of the leaky bucket algorithm

Abstract

Conference

Access to Document

Fingerprint

Cite this