Fast Simulation of a Queue fed by a Superposition of Many (Heavy-Tailed) Sources

Nam Kyoo Boots () and Michel Mandjes
Additional contact information
Nam Kyoo Boots: Vrije Universiteit Amsterdam
Michel Mandjes: Bell Laboratories/Lucent Technologies

No 01-050/4, Tinbergen Institute Discussion Papers from Tinbergen Institute

Abstract: We consider a queue fed by a large number, say n, of on-off sources with generally distributed on-and off-times. The queueing resources are scaled by n: the buffer is B=nb and link rate is C=nc.The model is versatile: it allows us to model both long range dependent traffic (by using heavy-tailed distributed on-periods) and short range dependent traffic (by using light-tailed on-periods).A crucial performance metric in this model is the steady-state buffer overflow probability.This overflow probability decays exponentially in the number of sources n. Therefore, if thenumber of sources grows large, naive simulation is too time-consuming, and we have to use fastsimulation techniques instead. Due to the exponential decay (in n), importance sampling with an exponential change of measureessentially goes through, irrespective of the on-times being heavy-tailed or light-tailed. Anasymptotically optimal change of measure is found by using large deviations arguments. Notably,the change of measure is not constant during the simulation run, which is essentially differentfrom many other studies (usually relying on large buffer asymptotics).We provide numerical examples to show that the resulting importance sampling procedure indeedimproves considerably over naive simulation. We present some accelerations. Finally, we give shortcomments on the influence of the shape of the distributions on the loss probability, and wedescribe the limitations of our technique.

Keywords: long-range dependence; importance sampling; queueing theory; large deviations asymptotics; buffer overflow; heavy-tailed random variables (search for similar items in EconPapers)
Date: 2001-05-17
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://papers.tinbergen.nl/01050.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:tin:wpaper:20010050

Access Statistics for this paper

More papers in Tinbergen Institute Discussion Papers from Tinbergen Institute Contact information at EDIRC.
Bibliographic data for series maintained by Tinbergen Office +31 (0)10-4088900 ().