Fast simulation of the leaky bucket algorithm

Nicola, Victor F. and Hagesteijn, Gertjan A. and Kim, Byung G. (1994) Fast simulation of the leaky bucket algorithm. In: Winter Simulation Conference, WSC 1994, 1994, Orlando, Florida, USA.

Preview

PDF
945Kb

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/.
Item Type:	Conference or Workshop Item
Copyright:	©1994 IEEE
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Telematics Systems and Services (TSS)
Link to this item:	http://purl.utwente.nl/publications/15917
Official URL:	http://dx.doi.org/10.1109/WSC.1994.717144
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 112799