Introduction

Technological developments have in recent years led to dramatic changes in the way humans exchange information. Examples are provided by the Internet and mobile communications. These new forms of communication have, in their turn, given rise to exciting and challenging new problems in the performance analysis of network congestion. In this note we discuss one of the hottest topics in this area, viz., the influence of heavy-tailed input processes on network performance measures. This is a topic that is also actively studied in Stieltjes. We first present a global outline of the topic, and subsequently some of our own research in this field.

In classical applications of teletraffic theory, the service time distributions in queueing models were usually assumed to have a negative exponential tail. In modern applications of teletraffic theory, the assumption of exponential tails often appears to be invalid. Plots of traffic measurements for traffic in Ethernet Local Area Networks [13], Wide Area Networks [12] and Variable Bit Rate (VBR) video [1] have shown a striking similarity when one considers a time period of hours, minutes or milliseconds: Bursty subperiods are alternated by less bursty subperiods on each scale. This scale-invariant or self-similar feature of traffic and the related phenomenon of long-range dependence (i.e., the integral over time of the covariance of the traffic rate diverges) were also convincingly demonstrated in [11] using a careful statistical analysis - and they are incompatible with exponential traffic assumptions.

A natural model for long-range dependence (LRD) in a traffic process is a fluid queue fed by one or more on/off sources (viz., sources that alternate between active and silent periods), under the assumption that the distribution of the on-period $A$ of a source has the following non-exponential behaviour:

${\mathbb P}[A>t] \sim h_{\zeta} t^{-\zeta}, ~~~ t \rightarrow \infty ,$ (1)

with $h_{\zeta}$ a positive constant and $1<\zeta<2$ (here $f(t) \sim g(t)$ means that $f(t)/g(t) \rightarrow 1$ as $t \rightarrow \infty$). When at least one of the sources exhibits such heavy-tail behaviour, the cumulative input process is LRD [9]. As observed in [13], in many cases on-periods (or off-periods, which also give rise to LRD) of actual traffic sources do indeed exhibit such a heavy-tail behaviour. The occurrence of heavy-tailed on- and/or off-periods of sources seems to provide the most natural explanation of LRD and self-similarity in aggregated packet traffic. There are indeed many phenomena in modern communication traffic that fit such a description, like file sizes in Internet traffic (one can think of postscript files sent by email) and lengthy telephone connections via a modem.

These observations have triggered much research on fluid queues with, in particular, heavy-tailed on-period distributions (cf. the survey [9]). In its turn, this leads to an interest in the effect of heavy-tailed service time distributions in ordinary single server queues. There appears to be a considerable similarity in behaviour of both types of queues. In particular, the buffer content process at embedded moments of the fluid queue with exponential off-periods can be expressed as the waiting time in a certain $M/G/1$ queue.

An important class of heavy-tailed probability distributions is the class of regularly varying [2] distributions of index $- \nu$, $\nu \in (1,2)$. When $G$ is a nonnegative random variable, then ${\mathbb P}[G > x]$ is said to be regularly varying at infinity of index $- \nu$ when

${\mathbb P}[G>x] = x^{-\nu} L(x), ~~~ x \geq 0,$ (2)

with $L(x)$ a slowly varying function at infinity, i.e.,

$${\rm lim}_{x \rightarrow \infty} \frac{L(tx)}{L(x)} = 1, ~~~ \forall t > 0.$$

$L(\cdot)$ could for instance be a constant, or a logarithmic function.

An early result concerning regular variation in queueing theory is due to Cohen [10]. He proved the following result for the $GI/G/1$ queue under the First-Come-First-Served (FCFS) discipline: The tail of the waiting time distribution is regularly varying of index $1-\nu$ if and only if the tail of the service time distribution is regularly varying of index $- \nu$, $\nu > 1$. This result has turned out to be very useful in relating the regularly varying tail behaviour of on-periods of on/off sources in fluid queues to the buffer content [3, 4].

Cohen's result implies that, in the case of regular variation, the tail of the waiting and response time distributions is one degree heavier than that of the service time distribution. For $1 < \nu < 2$, the mean of the service time distribution is finite, but the mean of the waiting time distribution is infinite.