Estimating buffer overflows in three stages using cross-entropy

Pieter-Tjerk de Boer, Dirk Kroese, R.Y. Rubinstein

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

    17 Citations (Scopus)
    14 Downloads (Pure)

    Abstract

    In this paper we propose a fast adaptive Importance Sampling method for the efficient simulation of buffer overflow probabilities in queueing networks. The method comprises three stages. First we estimate the minimum Cross-Entropy tilting parameter for a small buffer level; next, we use this as a starting value for the estimation of the optimal tilting parameter for the actual (large) buffer level; finally, the tilting parameter just found is used to estimate the overflow probability of interest. We recognize three distinct properties of the method which together explain why the method works well; we conjecture that they hold for quite general queueing networks. Numerical results support this conjecture and demonstrate the high efficiency of the proposed algorithm.
    Original languageUndefined
    Title of host publicationProceedings of the 2002 Winter Simulation Conference (WSC 2002)
    EditorsJ.L. Snowdon, J.M. Charnes, E. Yücesan, C.H. Chen
    Place of PublicationUSA
    PublisherAssociation for Computing Machinery (ACM)
    Pages301-309
    Number of pages9
    ISBN (Print)0-7803-7615-3
    DOIs
    Publication statusPublished - Dec 2002
    Event2002 Winter Simulation Conference - San Diego, United States
    Duration: 8 Dec 200211 Dec 2002

    Publication series

    Name
    PublisherACM-IEEE
    Volume1

    Conference

    Conference2002 Winter Simulation Conference
    Abbreviated titleWSC 2002
    CountryUnited States
    CitySan Diego
    Period8/12/0211/12/02

    Keywords

    • EWI-24108
    • IR-37982
    • METIS-206977

    Cite this

    de Boer, P-T., Kroese, D., & Rubinstein, R. Y. (2002). Estimating buffer overflows in three stages using cross-entropy. In J. L. Snowdon, J. M. Charnes, E. Yücesan, & C. H. Chen (Eds.), Proceedings of the 2002 Winter Simulation Conference (WSC 2002) (pp. 301-309). USA: Association for Computing Machinery (ACM). https://doi.org/10.1109/WSC.2002.1172899
    de Boer, Pieter-Tjerk ; Kroese, Dirk ; Rubinstein, R.Y. / Estimating buffer overflows in three stages using cross-entropy. Proceedings of the 2002 Winter Simulation Conference (WSC 2002). editor / J.L. Snowdon ; J.M. Charnes ; E. Yücesan ; C.H. Chen. USA : Association for Computing Machinery (ACM), 2002. pp. 301-309
    @inproceedings{34ab4dc28a4b4cb883494f0f0a94d4e8,
    title = "Estimating buffer overflows in three stages using cross-entropy",
    abstract = "In this paper we propose a fast adaptive Importance Sampling method for the efficient simulation of buffer overflow probabilities in queueing networks. The method comprises three stages. First we estimate the minimum Cross-Entropy tilting parameter for a small buffer level; next, we use this as a starting value for the estimation of the optimal tilting parameter for the actual (large) buffer level; finally, the tilting parameter just found is used to estimate the overflow probability of interest. We recognize three distinct properties of the method which together explain why the method works well; we conjecture that they hold for quite general queueing networks. Numerical results support this conjecture and demonstrate the high efficiency of the proposed algorithm.",
    keywords = "EWI-24108, IR-37982, METIS-206977",
    author = "{de Boer}, Pieter-Tjerk and Dirk Kroese and R.Y. Rubinstein",
    note = "Imported from research group DACS (ID number 281)",
    year = "2002",
    month = "12",
    doi = "10.1109/WSC.2002.1172899",
    language = "Undefined",
    isbn = "0-7803-7615-3",
    publisher = "Association for Computing Machinery (ACM)",
    pages = "301--309",
    editor = "J.L. Snowdon and J.M. Charnes and E. Y{\"u}cesan and C.H. Chen",
    booktitle = "Proceedings of the 2002 Winter Simulation Conference (WSC 2002)",
    address = "United States",

    }

    de Boer, P-T, Kroese, D & Rubinstein, RY 2002, Estimating buffer overflows in three stages using cross-entropy. in JL Snowdon, JM Charnes, E Yücesan & CH Chen (eds), Proceedings of the 2002 Winter Simulation Conference (WSC 2002). Association for Computing Machinery (ACM), USA, pp. 301-309, 2002 Winter Simulation Conference, San Diego, United States, 8/12/02. https://doi.org/10.1109/WSC.2002.1172899

    Estimating buffer overflows in three stages using cross-entropy. / de Boer, Pieter-Tjerk; Kroese, Dirk; Rubinstein, R.Y.

    Proceedings of the 2002 Winter Simulation Conference (WSC 2002). ed. / J.L. Snowdon; J.M. Charnes; E. Yücesan; C.H. Chen. USA : Association for Computing Machinery (ACM), 2002. p. 301-309.

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

    TY - GEN

    T1 - Estimating buffer overflows in three stages using cross-entropy

    AU - de Boer, Pieter-Tjerk

    AU - Kroese, Dirk

    AU - Rubinstein, R.Y.

    N1 - Imported from research group DACS (ID number 281)

    PY - 2002/12

    Y1 - 2002/12

    N2 - In this paper we propose a fast adaptive Importance Sampling method for the efficient simulation of buffer overflow probabilities in queueing networks. The method comprises three stages. First we estimate the minimum Cross-Entropy tilting parameter for a small buffer level; next, we use this as a starting value for the estimation of the optimal tilting parameter for the actual (large) buffer level; finally, the tilting parameter just found is used to estimate the overflow probability of interest. We recognize three distinct properties of the method which together explain why the method works well; we conjecture that they hold for quite general queueing networks. Numerical results support this conjecture and demonstrate the high efficiency of the proposed algorithm.

    AB - In this paper we propose a fast adaptive Importance Sampling method for the efficient simulation of buffer overflow probabilities in queueing networks. The method comprises three stages. First we estimate the minimum Cross-Entropy tilting parameter for a small buffer level; next, we use this as a starting value for the estimation of the optimal tilting parameter for the actual (large) buffer level; finally, the tilting parameter just found is used to estimate the overflow probability of interest. We recognize three distinct properties of the method which together explain why the method works well; we conjecture that they hold for quite general queueing networks. Numerical results support this conjecture and demonstrate the high efficiency of the proposed algorithm.

    KW - EWI-24108

    KW - IR-37982

    KW - METIS-206977

    U2 - 10.1109/WSC.2002.1172899

    DO - 10.1109/WSC.2002.1172899

    M3 - Conference contribution

    SN - 0-7803-7615-3

    SP - 301

    EP - 309

    BT - Proceedings of the 2002 Winter Simulation Conference (WSC 2002)

    A2 - Snowdon, J.L.

    A2 - Charnes, J.M.

    A2 - Yücesan, E.

    A2 - Chen, C.H.

    PB - Association for Computing Machinery (ACM)

    CY - USA

    ER -

    de Boer P-T, Kroese D, Rubinstein RY. Estimating buffer overflows in three stages using cross-entropy. In Snowdon JL, Charnes JM, Yücesan E, Chen CH, editors, Proceedings of the 2002 Winter Simulation Conference (WSC 2002). USA: Association for Computing Machinery (ACM). 2002. p. 301-309 https://doi.org/10.1109/WSC.2002.1172899