Page 384 - A First Course In Stochastic Models

MULTI-SERVER QUEUES WITH POISSON INPUT 379

Since p j /p j−1 ≈ τ −1 for j large enough, we replace p j for j ≥ M by p M τ −(j−M)
for an appropriately chosen integer M. Then the infinite system of linear equations
(9.6.1) together with the normalizing equation ∞ p j = 1 is reduced to a finite
j=0
system of linear equations of dimension M + 1. A relatively small value of M is
usually good enough for practical purposes. The value of M does not grow beyond
any practical bound when the traffic load on the system gets close to 1. It is an
empirical fact that the asymptotic expansion (9.6.2) already applies for relatively
√
1
small values of j. For practical purposes the value M = (1+ρ)c+10ρ c seems
2
large enough to obtain the state probabilities to at least nine decimal places (e.g.
for c = 25 and ρ = 0.99 we have M = 75, which is in marked contrast with
the brute-force value N = 1056 that is required when the infinite system of linear
∞
p
equations is truncated such that i=N i ≤ 10 −9 ). In general the geometric tail
approach leads to a relatively small system of linear equations that can usually
be solved by a standard Gaussian elimination method. This approach requires that
beforehand we compute the constant τ from (9.6.3). Using logarithms, the equation
(9.6.3) is equivalent to λD(1 − τ) + c ln(τ) = 0. Noting that λD = cρ and using
the transformation η = 1/τ, it follows that τ can be obtained by computing the
unique η ∈ (0, 1) satisfying
ρ(1 − η) + η ln(η) = 0.

We can conclude that the state probabilities in the M/D/c queue can be routinely
computed by solving a finite system of linear equations. An accuracy check on the
calculated values of the p j is Little’s relation
 
c−1 c−1

jp j + c 1 − p j  = λD (9.6.5)

j=1 j=0
for the average number of busy servers. An alternative and more advanced method
for computing the state probabilities is based on the discrete FFT method. Before
giving this method, we derive the generating function of the state probabilities. This
generating function will also be used to verify the asymptotic expansion (9.6.2).

Generating function
∞ j j
p
Let P (z) = j=0 j z for |z| ≤ 1. Multiplying both sides of (9.6.1) by z and
summing over j gives
c ∞ c+j (λD) j−k+c
P (z) = e λD(z−1) p k + z j p k e −λD
(j − k + c)!
k=0 j=1 k=c+1
c (λD) j−k+c
∞
∞

= e λD(z−1) p k + p k z k−c e −λD z j−k+c
(j − k + c)!
k=0 k=c+1 j=k−c