Page 68 - A First Course In Stochastic Models

THE POLLACZEK–KHINTCHINE FORMULA 59

2
fixed. Noting that c = 1 for exponentially distributed service times, the expression
S
(2.5.3) can also be written as
1 2
W q = (1 + c )W q (exp), (2.5.4)
S
2
where W q (exp) = ρE(S)/(1 − ρ) denotes the average delay per customer for the
case of exponential services. In particular, writing W q = W q (det) for deterministic
2
services (c = 0), we have
S
1
W q (det) = W q (exp). (2.5.5)
2
It will be seen in Chapter 9 that the structural form (2.5.4) is very useful to design
approximations in more complex queueing models.
Another important feature shown by the Pollaczek–Khintchine formula is that
the average delay and average queue size increase in a non-linear way when the
offered load ρ increases. A twice as large value for the offered load does not imply
a twice as large value for the average delay! On the contrary, the average delay
and the average queue size explode when the average arrival rate becomes very
close to the average service rate. Differentiation of W q as a function of ρ shows
that the slope of increase of W q as a function of ρ is proportional to (1 − ρ) −2 .
As an illustration a small increase in the average arrival rate when the load ρ =
0.9 causes an increase in the average delay 25 times greater than it would cause
when the load ρ = 0.5. This non-intuitive finding demonstrates the danger of
designing a stochastic system with too high a utilization level, since then a small
increase in the offered load will in general cause a dramatic degradation in system
performance.
We have not yet proved the Pollaczek–Khintchine formula. First we give a
heuristic derivation and next we give a rigorous proof.

Heuristic derivation
Tag a customer who arrives when the system has reached statistical equilibrium.
Denote its waiting time in queue by the random variable D tag . Heuristically,
E(D tag ) = W q . By the PASTA property, the expected number of customers in
queue seen upon arrival by the tagged customer equals L q . Noting that ρ is the
long-run fraction of time the server is busy, it also follows that the tagged customer
finds the server busy upon arrival with probability ρ. Using the result (2.1.8) for
the excess variable, it is plausible that the expected remaining service time of the
2
customer seen in service by a Poisson arrival equals 1 E(S )/E(S). Putting the
2
pieces together, we find the relation
2
E(S )
E(D tag ) = L q E(S) + ρ .
2E(S)