Page 377 - A First Course In Stochastic Models

372 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

Thus we have a computationally useful algorithm for the waiting-time distribution
when the probabilities π j can be efficiently computed. These probabilities are the
unique solution to the equilibrium equations

∞

π j = π k p kj , j = 0, 1, . . . (9.5.2)
k=0
together with the normalizing equation j=0 j = 1, where the p ij are the one-step
∞
π
transition probabilities of the Markov chain {X n }. The p ij are easily found. Since
service completions of phases occur according to a Poisson process with rate µ as
long as the server is busy, it is readily seen that for any i ≥ 0
m i+k−j
∞ −µt (µt)
p ij = q k e a(t) dt, 1 ≤ j ≤ i + m,
0 (i + k − j)!
k=max(j−i,1)
where a(t) denotes the probability density of the interarrival time. The geometric
tail approach from Section 3.4.2 can be used to reduce the infinite system of linear
equations (9.5.2) to a finite system of linear equations. To see that

π j+1
∼ η as j → ∞ (9.5.3)
π j
for some constant 0 < η < 1, note that for any i ≥ 0 the one-step transition
probability p ij equals 0 for j > i + m and depends on i and j only through the
difference j − i for j ≥ 1. Next we can apply a general result from Section 3.4.2
to obtain (9.5.3). Using the expression for p ij , the equation (3.4.9) reduces after
some algebra to
m
∞

m −µ(1−w)t m−i
w − e a(t) dt q i w = 0. (9.5.4)
0
i=1
The decay factor η is the largest root on (0,1) of this equation. By replacing π j
for j ≥ M by π M η j−M for an appropriately chosen integer M, we obtain a finite
system of linear equations.

9.5.2 Coxian-2 Services

Suppose that the service time S of a customer has a Coxian-2 distribution with
parameters (b, µ 1 , µ 2 ). That is, S is distributed as U 1 with probability 1 − b and
S is distributed as U 1 + U 2 with probability b, where U 1 and U 2 are indepen-
dent exponentials with respective means 1/µ 1 and 1/µ 2 . Then the waiting-time
distribution function W q (x) allows for the explicit expression
1 − W q (x) = a 1 e −η 1 x + a 2 e −η 2 x , x ≥ 0, (9.5.5)