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)
    142 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 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
    PublisherIEEE
    Number of pages8
    ISBN (Print)9780780321090
    DOIs
    Publication statusPublished - 14 Nov 1994
    Event1994 Winter Simulation Conference - Orlando, United States
    Duration: 11 Dec 199412 Dec 1994

    Conference

    Conference1994 Winter Simulation Conference
    Abbreviated titleWSC 1994
    CountryUnited States
    CityOrlando
    Period11/12/9412/12/94

      Fingerprint

    Cite this

    Nicola, V. F., Hagesteijn, G. J. A., & Kim, B. G. (1994). Fast simulation of the leaky bucket algorithm. In J. D. Tew, S. Manivannan, D. A. Sadowski, & A. F. Seil (Eds.), Proceedings of the 1994 Winter Simulation Conference Orlando, FL, USA: IEEE. https://doi.org/10.1109/WSC.1994.717144