Page 393 - A First Course In Stochastic Models

388 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

on c, as opposed to exact methods for which the computing times quickly increase
when c gets larger. For the first c state probabilities, we have
app exp
p = p , j = 0, 1, . . . , c − 1, (9.6.20)
j j
exp
where p denotes the state probability p j in the M/M/c queue. To prove (9.6.20),
j
sum both sides of (9.6.3) over j ≥ c. This yields
∞
app app
ρ
p = p . (9.6.21)
j 1 − ρ c−1
j=c
By (5.1.8) and (9.6.12),
exp cρ exp app cρ app
p = p and p = p for 1 ≤ j ≤ c − 1,
j j−1 j j−1
j j
app exp
Hence, for some constant γ, p = γp for 0 ≤ j ≤ c−1. To verify that γ = 1,
j j
we use (9.6.21) and (5.1.9) to obtain
c−1 c−1
ρ app app exp " exp #
p = 1 − p j = 1 − γp j = 1 − γ 1 − P
1 − ρ c−1 delay
j=0 j=0
γρ exp
= 1 − γ + p c−1 .
1 − ρ
app app
and so ρp / (1 − ρ) = 1 − γ + ρp / (1 − ρ). This implies that γ = 1 and
c−1 c−1
so (9.6.20) holds. The relation (9.6.20) says that the approximate queueing system
behaves like an M/M/c queue when not all of the c servers are busy. As a by-
∞

product of the above proof, we find for the delay probability P delay = p j
j=c
that
app exp
P = P ,
delay delay
exp
where P denote Erlang’s delay probability in the M/M/c queue. It has long
delay
been known that Erlang’s delay probability gives a good approximation to the
delay probability in the general M/G/c queue. Further support for the quality
of the approximation to the state probabilities p j is provided by the result that
app app
p /p is asymptotically exact as j → ∞. This result will be proved below.
j j−1
The generating function
app exp
The algorithm in Section 5.1 gives a very simple scheme to compute p = p
j j
for 0 ≤ j ≤ c − 1. Define the generating function
∞
app j
P q (z) = p z , |z| ≤ 1.
c+j
j=0