6
THE SINGLE SERVER QUEUE:
HEAVY TAILS AND HEAVY TRAFFIC
O. J. B
OXMA
Department of Mathematics and Computing Science,
Eindhoven University of Technology, 5600 MB Eindhoven, The Netherlands;
and CWI, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands
J. W. C
OHEN
CWI, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands
6.1 INTRODUCTION
Recently, there has been much interest in the behavior of queues with heavy-tailed
service time distributions. This interest has been triggered by a large number of
traf®c measurements on modern communication network traf®c (e.g., see Willinger
et al. [38] for Ethernet LAN traf®c, Paxson and Floyd [30] for WAN traf®c, and
Beran et al. [3] for VBR video traf®c; see also various chapters in this volume).
These measurements and their statistical analysis (e.g., see Leland et al. [26])
suggest that modern communication traf®c often possesses the properties of self-
similarity and long-range dependence. A natural possibility to introduce long-range
dependence in an input traf®c process is to take a ¯uid queue and to assume that at
least one of the input quantities I (on or off periods in the ¯uid queue fed by on=off
sources) has the following ``heavy-tail'' behavior:
PI > t$
t3I
h
n
t
Àn
; 6:1
Self-Similar Network Traf®c and Performance Evaluation, Edited by Kihong Park and Walter Willinger

x3I
Ltx
Lx
 1; Vt > 0:
LÁ could, for instance, be a constant or a logarithmic function. If Eq. (6.2) holds,
then we write PG > Á P Àn.
Regular variation is an important asymptotic concept in probabilistic analysis.
The main reference text is the book by Bingham et al. [5].
An early result concerning regular variation in queueing theory is due to Cohen
[13]. He proved the following result for the GI=G=1 queue under the ®rst-come-®rst-
served (FCFS) discipline: the tail of the waiting time distribution is regularly varying
of index 1 À n if and only if the tail of the service time distribution is regularly
varying of index Àn; n > 1. This result has turned out to be very useful in relating
the regularly varying tail behavior of on periods of on=off sources in ¯uid queues to
the buffer content [7, 8]; see also Jelenkovic and Lazar [23] and Rolski et al. [32].
Cohen's result implies that, in the case of regular variation, the tail of the waiting
time distribution is one degree heavier than that of the service time distribution. For
1 < n < 2, the mean of the service time distribution is ®nite, but the mean of the
waiting time distribution is in®nite.
The ®rst issue that we consider in this chapter is whether other service disciplines
besides FCFS may lead to a less detrimental waiting time behavior. We consider the
M=G=1 queue with the processor sharing (PS) discipline and the M=G=1 queue with
the last-come-®rst-served preemptive resume (LCFS-PR) discipline. Note that PS
and LCFS-PR are well-known and important disciplines, that both play a key role in
product-form networks. For both disciplines, the waiting time tail behavior turns out
to be regularly varying of index Àn iff the service time tail behavior is regularly
varying of index Àn. We refer to Anantharam [2] for a related investigation of the
in¯uence of the service discipline on the tail behavior of a single server queue.
144
THE SINGLE SERVER QUEUE: HEAVY TAILS AND HEAVY TRAFFIC

same three M =G=1 variants, we present heavy traf®c limit theorems for waiting
times, in the case of a regularly varying service time distribution with an in®nite
variance. In the LCFS-PR case, the sojourn time distribution coincides with the
M=G=1 busy period distribution. The heavy traf®c behavior of the latter distribution
is investigated in detail; the tail behavior of the limiting distribution is studied in
Section 6.4. Heavy traf®c limit theorems for the waiting time in the GI=G=1queue
with the FCFS service discipline are presented in Section 6.5. A distinction is made
between the cases in which the interarrival time distribution has a heavier tail, the
service time distribution has a heavier tail, and both tails are ``just as heavy.'' In
Section 6.6 the input process and the workload process are studied for the GI=G=1
queue with heavy-tailed interarrival and=or service time distribution. The heavy
traf®c behavior of those processes is characterized. Section 6.7 contains conclu-
sions and some topics for further research. (Note: Several of the results in this
chapter have appeared in recent reports of the authors and their colleagues; in those
cases, proofs are generally omitted. Also, several chapters in this volume are related
to the present work. We mention in particular the contributions of JelenkovicÂ
(Chapter 10), of Likhanov (Chapter 8), of Makowski and Parulekar (Chapter 9), of
Norros (Chapter 4), of Brichet et al. (Chapter 5), and of Resnick and Samorodnitsky
(Chapter 7).)
6.1 INTRODUCTION
145
6.2 WAITING TIME TAIL BEHAVIOR
6.2.1 Introduction
In Section 6.1 we have already mentioned a result of Cohen [13] that relates the
(regularly varying) tail behavior of service and waiting times in the GI =G=1 queue
with the FCFS discipline; it shows that the waiting time is ``one degree heavier'' than
the service time tail, in the case of regular variation. In Section 6.2.2 this result, and
an extension, will be discussed in some more detail for the M=G=1 FCFS queue. A
similar result for the M=G=1 queue with the PS discipline (due to Zwart and Boxma
[42]) will be discussed in Section 6.2.3. That result shows that, under processor

; ...; m
n
(and m
0
 1). De®ne
f
n
fsg :À1
n1
ffsgÀ
P
n
j0
m
j
Às
j
j!
"#
:
Lemma 6.2.1. Let n < n < n  1, C ! 0. The following statements are equiva-
lent:
f
n
fsgC  o1s
n
L1=s; s 5 0; s real; 6:3
1 À FtC  o1
À1
n

Lx: 6:5
Pakes [29] has extended this result to the larger class  of subexponential
distributions (i.i.d. stochastic variables X
1
and X
2
have a subexponential tail if
PX
1
 X
2
> t=PX
1
> t$
t3I
2. His result states that PW > Á P  if and only if
PB* > Á P , and if either is the case then
PW > x$
x3I
r
1 À r
PB* > x: 6:6
R
EMARK
6.2.3. Note that the interarrival time distribution has no in¯uence on the
above-mentioned waiting time tail behavior.
R
EMARK
6.2.4. In the case of Poisson arrivals, the Pollaczek±Khintchine formula
reads:

behavior of the distributions of W and B.
6.2 WAITING TIME TAIL BEHAVIOR
147
The possibility of having to wait at least a residual service time explains that the
waiting time tail is one degree heavier than the service time tail: PB > Á P Àn
implies that PB* > Á P 1 À n (cf. Bingham et al. [5]; obviously, integration
increases the index of regular variation by one).
In the next subsections we shall consider two service disciplines in which an
arriving customer does not ®rst have to wait a residual service time, and where the
waiting time tail is just as heavy as the service time tail.
R
EMARK
6.2.5. Denote the steady-state sojourn time by S; in the GI =G=1 FCFS
queue, S 9 W  B, where W and B are independent and where 9 denotes equality
in distribution. Hence
PS > x$
x3I
r
1 À r
PB* > x: 6:9
Denote the steady-state workload by V ; in the GI =G=1 FCFS queue (cf. Cohen [15,
p. 296]),
Ee
ÀsV
1 À r rb*fsgEe
ÀsW
; Re s ! 0: 6:10
Hence, using Lemma 6.2.1, PB > Á P Àn@APV > Á P 1 À n.
R
EMARK

Assume that s
n

n!1
and, similarly, a
n
; r
n
t; t ! 0
n!1
are i.i.d., and that these
sequences are independent. The buffer content W
b
n
at the beginning of the nth
activity period satis®es the recursion
W
b
n1
 max0; W
b
n

^
B
n
À s
n
; n ! 1: 6:13
This is exactly the GI =G=1 Lindley waiting time recursion (identify W

x
Àn
Lx@APS
PS
> x$
x3I
1
1 À r
n
x
Àn
Lx: 6:14
Both relations imply that, in the case of regular variation,
PS
PS
> x$
x3I
PB > 1 À rx: 6:15
Theorem 6.2.7 is proved by deriving a new expression for the LST of the sojourn
time distribution, and applying Lemma 6.2.1. An interpretation of the factor 1 À r
in Eq. (6.15) is the following. When a tagged customer is in the system for a long
time, then the distribution of the total number of customers is approximately equal to
the steady-state distribution of the number of customers in a PS queue with one
permanent customer. The latter model is a special case of the M =G=1 queue with the
generalized processor sharing discipline, as studied in Cohen [14]. It follows from
the results in Cohen [14] that, in steady state, the mean fraction of service given to
the permanent customer in that M =G=1 queue is 1 À r. Hence, if a tagged customer
has been in the M =G=1 PS queue during a large time x, one would expect that the
amount of service received is approximately equal to 1 À rx.
6.2.4 The M=G=1 LCFS-PR Queue

PS
L
> x$
x3I
1
1 À r
PB > 1 À rx: 6:17
R
EMARK
6.2.9. Theorems 6.2.7 and 6.2.8 show that in both PS and LCFS-PR,
regular variation of the service time distribution gives rise to regular variation of the
sojourn time distribution, of the same index. In LCFS±nonpreemptive, it is easily
seen that regular variation of the service time distribution gives rise to regular
variation of the waiting time distribution of one index higher ( just like FCFS). This
result is obtained by applying Lemma 6.2.1 to the waiting time LST (for this LST,
see, e.g., Cohen [15, (III.3.10)]). The increment of the index is not surprising,
sinceÐas in FCFSÐa waiting time may include a residual service time.
6.3 HEAVY TRAFFIC LIMIT THEOREMS FOR THE M =G=1 QUEUE
6.3.1 Introduction
When the variance s
2
of the service time distribution is ®nite, the standard heavy
traf®c limit theorem for the stationary waiting time W in the M =G=1 queue holds,
that is,
lim
r41
PDrW t1À e
Àt
; t ! 0; 6:18
with Dr : l1 À r=1  l

is the root of the equation
r
G2 À n
n À 1
x
nÀ1
Lx1 À r; x > 0; 0 < 1 À r ( 1; 6:19
with the property that D
W
r50 for r 4 1.
Proof. We refer to Boxma and Cohen [10] for a detailed proof of the theorem,
albeit under slightly weaker conditions on the service time distribution. Here we
sketch a different proof. Using the Pollaczek±Khintchine formula (6.7) and Eq.
(6.19) we can write, for Re s ! 0,
Ee
ÀsW

1 À r
1 À rb*fsg

1
1 
r
1 À r
1 À b*fsg

1
1 
1 À b*fsg
G2 À n

lim
r41
Ee
ÀrD
W
rW
lim
r41
1
1 
1 À b*frD
W
rg
G2 À n
n À 1
D
W
r
nÀ1
LD
W
r

1
1  r
nÀ1
: 6:21
j
R
EMARK

D
W
rx=b appears to yield remarkably accurate results, even if the traf®c
load r is much smaller than one (in particular when x is large).
6.3.3 The M=G=1 PS Queue
In view of the fact that, under the processor sharing discipline, no customer ever
waits, it is natural to concentrate on the sojourn time distribution rather than the
waiting time distribution. In Zwart and Boxma [42] a novel expression has been
derived for the LST vfs; tgEe
ÀsS
PS
t
 in the M=G=1 PS queue; here S
PS
t is the
sojourn time of a customer with service request t. This expression leads to a new and
easy proof [42] of the following M =G=1 PS heavy traf®c limit theorem of Sengupta
[34] and of Yashkov [40].
Theorem 6.3.4. If b < I, then
lim
r41
vfs1 À r; tg
1
1  st
; Re s ! 0; t ! 0; 6:22
lim
r41
P1 À rS
PS
t x1 À e