Fast simulation of a queue fed by a superposition of many (heavy-tailed) sources
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 $Bequiv nb$ and link rate is $Cequiv nc$. The model is versatile: it allows us to model both <em>long range dependent</em> traffic (by using heavy-tailed distributed on-periods) and <em>short range dependent</em> 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 the number of sources grows large, naive simulation is too time-consuming, and we have touse fast simulation techniques instead. Due to the exponential decay (in $n$), importance sampling with an exponential change of measure essentially goes through, irrespective of the on-times being heavy-tailed or light-tailed. An asymptotically 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 different from many other studies (usually relying on large buffer asymptotics). We provide numerical examples to show that the resulting importance sampling procedure indeed improves considerably over naive simulation. We present some accelerations. Finally, we give short comments on the influence of the shape of the distributions on the loss probability, and we describe the limitations of our technique.
|Queueing theory (msc 60K25)|
|Logistics (theme 3), Energy (theme 4)|
|CWI. Probability, Networks and Algorithms [PNA]|
Boots, N.K, & Mandjes, M.R.H. (2002). Fast simulation of a queue fed by a superposition of many (heavy-tailed) sources. CWI. Probability, Networks and Algorithms [PNA]. CWI.