Page 385 - A First Course In Stochastic Models

380 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

c ∞
λD(z−1) k−c
λD(z−1)
= e p k + e p k z
k=0 k=c+1
c c
c λD(z−1) −c k
λD(z−1) −c
= e z p k z + e z P (z) − p k z .
k=0 k=0
This gives the desired result
c−1 k c
k=0 p k (z − z )
P (z) = c λD(1−z) . (9.6.6)
1 − z e
The generating function P (z) is the ratio of two functions that allow for an ana-
lytic continuation outside the unit circle. Next the asymptotic expansion (9.6.2) fol-
lows by applying Theorem C.1 in Appendix C. Also, we obtain after considerable
algebra from (9.6.6) that the average queue size is given by

 
c−1
1 2
L q =  (cρ) − c(c − 1) + {c(c − 1) − j(j − 1)} p j  . (9.6.7)
2c(1 − ρ)
j=2
An expression for the average delay in queue per customer next follows by using
Little’s formula L q = λW q .

The discrete FFT method for the state probabilities
An alternative method for the computation of the probabilities p j is to use the
discrete FFT method. We cannot directly apply this method to (9.6.6) since the
expression for P (z) involves the unknowns p 0 , . . . , p c−1 . However, by a generally
useful method, we can obtain from (9.6.6) an explicit expression for P (z). The
method is to compute first the zeros of the denominator on the right-hand side of
c λD(1−z)
(9.6.6) in the region |z| ≤ 1 in the complex plane. The denominator 1−z e
has c distinct zeros z 0 , z 1 , . . . , z c−1 inside or on the unit circle, where z 0 = 1. A
simple algorithm for the computation of these roots is given in Appendix G. Each
zero z k must also be a zero of the numerator on the right-hand side of (9.6.6) for
∞
j
the simple reason that P (z) = j=0 p j z is analytic for |z| ≤ 1. Thus we can
write (9.6.6) as
c−1
δ(z − 1)
P (z) = c λD(1−z) (z − z k )
1 − z e
k=1
for some constant δ. Since P (1) = 1, we find by using L’Hˆ opital’s rule that
c−1

δ = −c(1 − ρ)/ (1 − z k ) .
k=1