Monte Carlo Summation and Integration Applied to Multiclass Queuing Networks

Keith W. Ross, Danny H.K. Tsang, Jie Wang

    Research output: Contribution to journalArticlepeer-review

    Abstract

    Although many closed multiclass queuing networks have a product-form solution, evaluating their performance measures remains nontrivial due to the presence of a normalization constant. We propose the application of Monte Carlo summation in order to determine the normalization constant, throughputs, and gradients of throughputs. A class of importance-sampling functions leads to a decomposition approach, where separate single-class problems are first solved in a setup module, and then the original problem is solved by aggregating the single-class solutions in an execution model. We also consider Monte Carlo methods for evaluating performance measures based on integral representations of the normalization constant; a theory for optimal importance sampling is developed. Computational examples are given that illustrate that the Monte Carlo methods are robust over a wide range of networks and can rapidly solve networks that cannot be handled by the techniques in the existing literature.

    Original languageEnglish (US)
    Pages (from-to)1110-1135
    Number of pages26
    JournalJournal of the ACM (JACM)
    Volume41
    Issue number6
    DOIs
    StatePublished - Jan 11 1994

    Keywords

    • gradient estimation
    • product-form queuing networks
    • variation reduction

    ASJC Scopus subject areas

    • Software
    • Control and Systems Engineering
    • Information Systems
    • Hardware and Architecture
    • Artificial Intelligence

    Fingerprint Dive into the research topics of 'Monte Carlo Summation and Integration Applied to Multiclass Queuing Networks'. Together they form a unique fingerprint.

    Cite this