A large deviations analysis of the transient of a queue with many Markov fluid inputs
- 1 January 2002
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Modeling and Computer Simulation
- Vol. 12 (1), 1-26
- https://doi.org/10.1145/511442.511443
Abstract
This article analyzes the transient buffer content distribution of a queue fed by a large number of Markov fluid sources. We characterize the probability of overflow at time t , given the current buffer level and the number of sources in the on-state. After scaling buffer and bandwidth resources by the number of sources n , we can apply large deviations techniques. The transient overflow probability decays exponentially in n . In case of exponential on/off sources, we derive an expression for the decay rate of the rare event probability under consideration. For general, Markov fluid sources, we present a plausible conjecture. We also provide the "most likely path" from the initial state to overflow (at time t ). Knowledge of the decay rate and the most likely path to overflow leads to (i) approximations of the transient overflow probability, and (ii) efficient simulation methods of the rare event of buffer overflow. The simulation methods, based on importance sampling, give a huge speed-up compared to straightforward simulations. The approximations are of low computational complexity, and accurate, as verified by means of simulation experiments.Keywords
This publication has 22 references indexed in Scilit:
- Conditioned asymptotics for tail probabilities in large multiplexersPerformance Evaluation, 1998
- A Weak Convergence Approach to the Theory of Large DeviationsWiley Series in Probability and Statistics, 1997
- Buffer overflow asymptotics for a buffer handling many traffic sourcesJournal of Applied Probability, 1996
- Fast simulation of rare events in queueing and reliability modelsACM Transactions on Modeling and Computer Simulation, 1995
- Quick simulation of ATM buffers with on-off multiclass Markov fluid sourcesACM Transactions on Modeling and Computer Simulation, 1993
- How large delays build up in a GI/G/1 queueQueueing Systems, 1989
- Large deviations and rare events in the study of stochastic algorithmsIEEE Transactions on Automatic Control, 1983
- Stochastic Theory of a Data-Handling System with Multiple SourcesBell System Technical Journal, 1982
- Superimposed renewal processes and storage with gradual inputStochastic Processes and their Applications, 1974
- On Deviations of the Sample MeanThe Annals of Mathematical Statistics, 1960