Page 199 - A First Course In Stochastic Models

192 MARKOV CHAINS AND QUEUES

for all j and (5.1.9),
ρ
P delay = p c−1 . (5.1.10)
1 − ρ
It is also possible to give an explicit expression for the delay probability:

c
(cρ) /c!
P delay = c−1 . (5.1.11)
k
c
[(cρ) /c! + (1 − ρ) (cρ) /k!]
k=0
The delay probability for the M/M/c queue is often called Erlang’s delay prob-
∞

ability. Given the representation L q = (j − c)p j for the long-run average
j=c
queue size, it follows from p j = ρ j−c+1 p c−1 for j ≥ c that
ρ 2
L q = 2 p c−1 . (5.1.12)
(1 − ρ)
Under the assumption that customers are served in order of arrival, define the
steady-state waiting-time probability W q (x) in the same way as for the M/M/1
queue. The formula (5.1.5) generalizes to
ρ −cµ(1−ρ)x
W q (x) = 1 − p c−1 e , x ≥ 0. (5.1.13)
1 − ρ
This result is obtained by a slight modification of the derivation of (5.1.5). Since
the service times are exponentially distributed and the minimum of c (remaining)
service times has an exponential distribution with mean 1/(cµ), service completions
occur according to a Poisson process with rate cµ as long as c or more customers
are present. Thus the conditional delay in queue of a customer finding j ≥ c other
customers present upon arrival has an Erlang (j −c+1, cµ) distribution. This gives

j−c
∞ k
−cµx (cµx)
1 − W q (x) = π j e , x ≥ 0,
k!
j=c k=0
which leads to (5.1.13) after some algebra. In particular, the average delay in queue
of a customer equals
ρ
W q = p c−1 (5.1.14)
cµ(1 − ρ) 2
in agreement with (5.1.12) and Little’s formula L q = λW q . Also, by Little’s
formula, the long-run average number of busy servers equals cρ; see Section 2.3
Thus the long-run fraction of time that a given server is busy equals ρ.

5.1.3 The Output Process and Time Reversibility
Define for the M/M/c queue
T n = the epoch at which the nth service completion occurs.

Then the following important result holds for the output process.