A Fast Cross-Entropy Method for Estimating Buffer Overflows in Queueing Networks
Authors:
- 1 July 2004
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Management Science
- Vol. 50 (7) , 883-895
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 study various properties of the method in more detail for the M/M/1 queue and conjecture that similar properties also hold for quite general queueing networks. Numerical results support this conjecture and demonstrate the high efficiency of the proposed algorithm.Keywords
This publication has 20 references indexed in Scilit:
- Application of the Cross-Entropy Method to the Buffer Allocation Problem in a Simulation-Based EnvironmentAnnals of Operations Research, 2005
- Adaptive state‐ dependent importance sampling simulation of markovian queueing networksEuropean Transactions on Telecommunications, 2002
- Quick estimation of rare events in stochastic networksIEEE Transactions on Reliability, 1997
- Stochastic gradient optimization of importance sampling for the efficient simulation of digital communication systemsIEEE Transactions on Communications, 1995
- Regenerative rare events simulation via likelihood ratiosJournal of Applied Probability, 1994
- Statistical optimization of dynamic importance sampling parameters for efficient simulation of communication networksIEEE/ACM Transactions on Networking, 1993
- An algorithmic approach to the optimization of importance sampling parameters in digital communication system simulationIEEE Transactions on Communications, 1993
- Optimally efficient estimation of the statistics of rare events in queueing networksIEEE Transactions on Automatic Control, 1991
- A quick simulation method for excessive backlogs in networks of queuesIEEE Transactions on Automatic Control, 1989
- Natural Exponential Families with Quadratic Variance FunctionsThe Annals of Statistics, 1982