Title :
Fast simulation of the Leaky Bucket algorithm
Author :
Nicola, Victor F. ; Hagesteijn, Gertjan A. ; Kim, Byung G.
Author_Institution :
Tele-Inf. & Open Syst., Twente Univ., Enschede, Netherlands
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→∞.
Keywords :
asynchronous transfer mode; digital simulation; probability; queueing theory; simulation; telecommunication congestion control; Leaky Bucket algorithm; cell loss; cell loss probability; empty finite buffer; fast simulation methods; heuristic change; importance sampling; mathematical proof; overloaded queue; probability; queueing models; rare buffer overflow event; rare empty-buffer event; unstable queue; usage parameter control; Asynchronous transfer mode; Buffer storage; Communication system traffic control; Contracts; Counting circuits; Monte Carlo methods; Open systems; Particle measurements; Quality of service; Traffic control;
Conference_Titel :
Simulation Conference Proceedings, 1994. Winter
Print_ISBN :
0-7803-2109-X
DOI :
10.1109/WSC.1994.717144