Page 228 - A First Course In Stochastic Models

QUEUEING NETWORKS 221

Proof The proof is along the same lines as that of Theorem 5.6.1. The equilibrium
equations of the Markov process {X(t)} are given by

K

p(n) µ j = p(n + e i − e j )µ i p ij .
j:n j >0 j:n j >0 i=1
It suffices to verify that (5.6.14) satisfies the node local balance equations

K

p(n)µ j = p(n + e i − e j )µ i p ij (5.6.15)
i=1
for each j. To do so, note that the solution (5.6.14) has the property

−1

π i π j
p(n + e i − e j ) = p(n). (5.6.16)
µ i µ j
Hence, after substitution of (5.6.16) in (5.6.15), it suffices to verify that
−1
K

π i π j

µ j = µ i p ij , j = 1, . . . , K.
µ i µ j
i=1
This relation is indeed true since it coincides with the equilibrium equation (5.6.11).
This completes the proof.
A computational difficulty in applying the product-form solution (5.6.14) is the
determination of the normalization constant C. Theoretically this constant can be
found by summing p(n 1 , . . . , n K ) over all possible states (n 1 , . . . , n K ). How-
ever, the number of possible states (n 1 , . . . , n K ) such that K n i = M equals
i=1
M+K−1 . This is an enormous number even for modest values of K and M. Hence

M
a direct summation to compute the constant C is only feasible for relatively small
values of K and M. There are several approaches to handle the dimensionality
problem, including the Gibbs sampler from Section 3.4.3. We discuss here only
the mean-value algorithm.
Mean-value analysis

The mean-value algorithm is a numerically stable method for the calculation of
the average number of customers at station j, the average amount of time a
customer spends at station j on each visit and the average throughput at station
j. The so-called arrival theorem underlies the mean-value algorithm. To formu-
late this theorem, it is convenient to express explicitly the dependency of the state
probability p(n 1 , . . . , n K ) on the number of customers in the network. We write
p(n 1 , . . . , n K ) = p m (n 1 , . . . , n K ) for the network with a fixed number of m
customers. For any state (n 1 , . . . , n K ) with n 1 + · · · + n K = M the equilibrium
probability p M (n 1 , . . . , n K ) can be interpreted as the long-run fraction of time