Page 410 - A First Course In Stochastic Models

THE GI/G/c QUEUE 405

Moreover, by rate out of state (n, i) = rate into state (n, i),

[min(n, c)µ + α]p ni = αp n,i+1 + min(n + 1, c)µp n+1,i + αq i p n−1,1
for n ≥ 0 and 1 ≤ i ≤ m, where p n,m+1 = p −1,1 = 0 by convention. Again a
rather simple solution procedure can be given in view of
p n+1,i
= η, n ≥ c and 1 ≤ i ≤ m.
p n,i
A proof of this result will not be given here. The decay factor η is the unique
solution to the equation

m i
α

η = q i
[cµ(1 − η) + α] i
i=1
on the interval (0, 1). By substitution of (9.7.18) into the balance equation for p ni ,
we obtain for each n ≥ 0 that

[min(n, c)µ + α]p ni = αp n,i+1 + min(n + 1, c)µp n+1,i
m

+ q i min(n, c)µ p nj , 1 ≤ i ≤ m. (9.7.19)
j=1

In particular, since p c+1,i = ηp ci for 1 ≤ i ≤ m,
m

(cµ + α)p ci = αp c,i+1 + cµηp ci + q i cµ p cj , 1 ≤ i ≤ m. (9.7.20)
j=1
The probabilities p 0 , . . . , p c can now be computed as follows.

Algorithm
Step 0. Calculate the decay factor η. Let p c1 := 1.
Step 1. Solve the linear equations (9.7.20) with 2 ≤ i ≤ m to obtain p for
ci
2 ≤ i ≤ m.
Step 2. For k = c − 1, . . . , 0, solve the linear equations (9.7.19) with n = k to
obtain p for 1 ≤ i ≤ m.
ki
m
Step 3. Calculate p := j=1 p nj for n = 0, 1, . . . , c and normalize the p as
n
n
  −1
c−1
p
c
p n :=  p +  p , n = 0, 1, . . . , c.
j n
j=0 1 − η
The algorithm requires that a system of linear equations of order m is solved c
times. This is computationally feasible provided m is not too large.