A large deviations analysis of the transient of a queue with may Markov fluid inputs: approximations and fast simulation

M.R.H. Mandjes, Annemarie Ridder

Research output: Contribution to journalArticleAcademicpeer-review

10 Citations (Scopus)

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.
Original languageUndefined
Article number10.1145/511442.511443
Pages (from-to)1-26
Number of pages26
JournalACM transactions on modeling and computer simulation
Volume12
Issue number1
DOIs
Publication statusPublished - 2002

Keywords

  • IP routers
  • Importance sampling simulations
  • Transient probabilities
  • Queuing theory
  • Large deviations asymptotics
  • ATM multiplexers
  • METIS-207013
  • IR-71581
  • Calculus of variations
  • Buffer overflow
  • EWI-17940

Cite this

@article{78a486af3c7b4a9484eebcbe345959c6,
title = "A large deviations analysis of the transient of a queue with may Markov fluid inputs: approximations and fast simulation",
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 = "IP routers, Importance sampling simulations, Transient probabilities, Queuing theory, Large deviations asymptotics, ATM multiplexers, METIS-207013, IR-71581, Calculus of variations, Buffer overflow, EWI-17940",
author = "M.R.H. Mandjes and Annemarie Ridder",
year = "2002",
doi = "10.1145/511442.511443",
language = "Undefined",
volume = "12",
pages = "1--26",
journal = "ACM transactions on modeling and computer simulation",
issn = "1049-3301",
publisher = "Association for Computing Machinery (ACM)",
number = "1",

}

A large deviations analysis of the transient of a queue with may Markov fluid inputs: approximations and fast simulation. / Mandjes, M.R.H.; Ridder, Annemarie.

In: ACM transactions on modeling and computer simulation, Vol. 12, No. 1, 10.1145/511442.511443, 2002, p. 1-26.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - A large deviations analysis of the transient of a queue with may Markov fluid inputs: approximations and fast simulation

AU - Mandjes, M.R.H.

AU - Ridder, Annemarie

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

KW - IP routers

KW - Importance sampling simulations

KW - Transient probabilities

KW - Queuing theory

KW - Large deviations asymptotics

KW - ATM multiplexers

KW - METIS-207013

KW - IR-71581

KW - Calculus of variations

KW - Buffer overflow

KW - EWI-17940

U2 - 10.1145/511442.511443

DO - 10.1145/511442.511443

M3 - Article

VL - 12

SP - 1

EP - 26

JO - ACM transactions on modeling and computer simulation

JF - ACM transactions on modeling and computer simulation

SN - 1049-3301

IS - 1

M1 - 10.1145/511442.511443

ER -