Overflow behavoir in queues with many long-tailed inputs
We consider a fluid queue fed by a superposition of $n$ homogeneous on-off sources with generally distributed on- and off-periods. We scale buffer space $B$ and link rate $C$ by $n$, such that we get $nb$ and $nc$, respectively. Then we let $n$ grow large. In this regime, the overflow probability decays exponentially in the number of sources $n$; we specifically examine the situation in which also $b$ is large. We explicitly compute asymptotics for the case in which the on-periods have a subexponential distribution, e.g., Pareto, Lognormal, or Weibull. We provide a detailed interpretation of our results. Crucial is the shape of the function $v(t) := - log Pr( A^* > t )$ for large~$t$, $A^*$ being the residual on-period. If $v(.)$ is slowly varying (e.g., Pareto, Lognormal), then, during the trajectory to overflow, the input rate will only slightly exceed the link rate. Consequently, the buffer will fill `slowly', and the typical time to overflow will be `more than linear' in the buffer size. In contrast, if $v(.)$ is regularly varying of index strictly between 0 and 1 (e.g., Weibull), then the input rate will significantly exceed the link rate, and the time to overflow is essentially proportional to the buffer size. In both cases there is a substantial fraction of the sources that remain in the on-state during the entire path to overflow, while the other sources contribute at mean rate. These observations lead to straightforward approximations for the overflow probability. These approximations can be extended to the case of heterogeneous sources; the results provide further insight into the so-called reduced-load approximation.
|Queueing theory (msc 60K25), Performance evaluation; queueing; scheduling (msc 68M20), Operations research and management science (msc 90Bxx), Queues and service (msc 90B22)|
|Logistics (theme 3), Energy (theme 4)|
|CWI. Probability, Networks and Algorithms [PNA]|
Mandjes, M.R.H, & Borst, S.C. (1999). Overflow behavoir in queues with many long-tailed inputs. CWI. Probability, Networks and Algorithms [PNA]. CWI.