TY - JOUR

T1 - Fast simulation of a queue fed by a superposition of many (heavy-tailed) sources

AU - Boots, N.K.

AU - Mandjes, M.R.H.

PY - 2002

Y1 - 2002

N2 - We consider a queue fed by a large number, say n, on-off sources with generally distributed on- and off-times. The queueing resources are scaled by n: The buffer is B ≡ nb and the link rate is C ≡ nc. The model is versatile. It allows one to model both long-range-dependent traffic (by using heavy-tailed 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 probability decays exponentially in n. Therefore, if n grows large, naive simulation is too time-consuming and fast simulation techniques have to be used. Due to the exponential decay (in n), importance sampling with an exponential change of measure goes through, irrespective of the on-times being heavy 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 different from many other studies (usually relying on large buffer asymptotics). Numerical examples show that our procedure improves considerably over naive simulation. We present accelerations, we discuss the influence of the shape of the distributions on the overflow probability, and we describe the limitations of our technique.

AB - We consider a queue fed by a large number, say n, on-off sources with generally distributed on- and off-times. The queueing resources are scaled by n: The buffer is B ≡ nb and the link rate is C ≡ nc. The model is versatile. It allows one to model both long-range-dependent traffic (by using heavy-tailed 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 probability decays exponentially in n. Therefore, if n grows large, naive simulation is too time-consuming and fast simulation techniques have to be used. Due to the exponential decay (in n), importance sampling with an exponential change of measure goes through, irrespective of the on-times being heavy 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 different from many other studies (usually relying on large buffer asymptotics). Numerical examples show that our procedure improves considerably over naive simulation. We present accelerations, we discuss the influence of the shape of the distributions on the overflow probability, and we describe the limitations of our technique.

U2 - 10.1017/s026996480216205x

DO - 10.1017/s026996480216205x

M3 - Article

SN - 0269-9648

VL - 16

SP - 205

EP - 232

JO - Probability in the Engineering and Informational Sciences

JF - Probability in the Engineering and Informational Sciences

ER -