Page 408 - A First Course In Stochastic Models

THE GI/G/c QUEUE 403

for 1 ≤ j ≤ c − 1. Numerical integration must be used to calculate p ∗ for
c−1,j
1 ≤ j ≤ c − 1. A convenient method is Gauss–Legendre integration. The other
coefficients p kj of the linear equations (9.7.13) are simply computed as binomial
coefficients. Once the linear equations (9.7.13) have been solved, we can compute
the various performance measures.
The analysis for the D/M/c queue can straightforwardly be generalized to the
GI/M/c queue. However, in general, the expression for p kj with k ≥ c is quite
complicated and leads to a cumbersome and time-consuming calculation of p ∗ .
c−1,j
Fortunately, a much simpler alternative is available when the interarrival time has
a phase-type distribution.

Coxian-2 arrivals
Suppose that the interarrival time has a Coxian-2 distribution with parameters
(b, λ 1 , λ 2 ). In other words, the interarrival time first goes through phase 1 and
next it is finished with probability 1 − b or goes through a second phase 2 with
probability b, where the phases are independent exponentials with respective means
1/λ 1 and 1/λ 2 .
The state probabilities p j for 0 ≤ j ≤ c can be calculated by using the
continuous-time Markov chain approach. Define X(t) as the number of customers
present at time t and let Y(t) be the phase of the interarrival time in progress at
time t. The process {(X(t), Y(t))} is a continuous-time Markov chain with state
space I = {(n, i) | n = 0, 1, . . . ; i = 1, 2}. Denoting the equilibrium probabilities
of this Markov chain by p ni , we have p n = p n1 + p n2 . By equating the rate at
which the system leaves the set of states having at least n customers present to the
rate at which the system enters this set, we obtain

min(n, c)µ(p n1 + p n2 ) = λ 1 (1 − b)p n−1,1 + λ 2 p n−1,2 , n ≥ 1. (9.7.14)

This system of equations is augmented by the equations

[min(n, c)µ + λ 2 ]p n2 = min(n + 1, c)µp n+1,2 + λ 1 bp n1 , n ≥ 0. (9.7.15)

These equations follow by equating the rate out of state (n, 2) to the rate into
this state. A closer examination of equations (9.7.14) and (9.7.15) reveals that
they cannot be solved recursively starting with p := 1. Nevertheless, a recursive
0
computation of p 0 , . . . , p c is possible since
p n+1,i
= η, n ≥ c and i = 1, 2. (9.7.16)
p ni
The relation (9.7.16) extends the relation p n+1 /p n = η for n ≥ c. A proof of the
relation (9.7.16) is not given here. It can be deduced from Lemma 3.5.10 and gen-
eral results in Takahashi (1981). The constant η can be computed beforehand from
equation (9.7.12). Using the expression for Coxian-2 density given in Appendix B,