Recent research

In 1998 and 1999, research within Stieltjes on heavy tails in queues has focused on two topics. The first topic is, whether other service disciplines than FCFS may lead to a less detrimental response time behaviour. For the $M/G/1$ queue with the Processor Sharing discipline [14] and the $M/G/1$ queue with the Last-Come-First-Served Preemptive Resume discipline [8], important disciplines that both play a key role in queueing networks of so-called product-form, the response time tail behaviour turns out to be regularly varying of index $- \nu$ iff the service time tail behaviour is regularly varying of index $- \nu$. Hence these disciplines result in better tail behaviour of sojourn times than FCFS. In a series of studies (see, e.g., [5]) we have also investigated the workload tail behaviour of service systems with Generalized Processor Sharing (GPS). GPS-based scheduling algorithms, such as Weighted-Fair-Queueing, have emerged as an important mechanism for achieving differentiated Quality-of-Service in networks with integrated traffic services. We have identified conditions under which, in GPS, traffic of one class does not suffer from heavier-tailed traffic of another class.

The second topic is the heavy-traffic behaviour of a queue with heavy-tailed service time distribution. A queueing system is said to be in heavy traffic when its traffic load $\rho \rightarrow 1$. This topic is of theoretical interest, since in the traditional heavy-traffic limit theorems it is assumed that the second moments of service and interarrival times are finite, whereas (2) with $1 < \nu < 2$ leads to an infinite second moment. The topic is also of practical interest, since heavy-traffic limit theorems may give rise to useful approximations [6] in situations with a reasonably light traffic load. One can identify a coefficient of contraction $\Delta(\rho)$ such that $\Delta(\rho)$ times the waiting time has a proper limiting distribution for $\rho \uparrow 1$. One of the results obtained in [7] reads:

For the stable $M/G/1$ FCFS queue with regularly varying service time distribution with mean $\beta$ and of index $- \nu$, as specified in (2), the `contracted' waiting time $\Delta(\rho) W/\beta$ converges in distribution for $\rho \uparrow 1$. The limiting distribution is specified by its Laplace-Stieltjes transform $1/(1+r^{\nu-1})$, ${\rm Re}~r \geq 0$, and the coefficient of contraction $\Delta(\rho)$ is the root of the equation $- \Gamma(1- \nu) x^{\nu-1} L(x) = (1-\rho)/\rho$, with $x>0$, with the property that $\Delta(\rho) \downarrow 0$ for $\rho \uparrow 1$.

This result strongly differs from the case of a service time distribution with finite variance; there the coefficient of contraction behaves like $1-\rho$ instead of $(1-\rho)^{1/(\nu-1)}$, and the limiting distribution is the negative exponential distribution (hence with Laplace-Stieltjes distribution $1/(1+r)$).

Many challenging unsolved problems remain. In particular, one would like to know the tail behaviour of the workload in the case of fluid queues fed by multiple sources, some of which have heavy-tailed on-periods; and the related problem of the asymptotics of multiserver queues with heavy-tailed service time distributions also remains open.