Fast simulation of the leaky bucket algorithm

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

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    2 Citations (Scopus)
    390 Downloads (Pure)


    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 languageEnglish
    Title of host publicationProceedings of the 1994 Winter Simulation Conference
    EditorsJ.D. Tew, S. Manivannan, D.A. Sadowski, A.F. Seil
    Place of PublicationOrlando, FL, USA
    Number of pages8
    ISBN (Print)9780780321090
    Publication statusPublished - 14 Nov 1994
    Event1994 Winter Simulation Conference - Orlando, United States
    Duration: 11 Dec 199412 Dec 1994


    Conference1994 Winter Simulation Conference
    Abbreviated titleWSC 1994
    Country/TerritoryUnited States


    Dive into the research topics of 'Fast simulation of the leaky bucket algorithm'. Together they form a unique fingerprint.

    Cite this