Page 230 - A First Course In Stochastic Models

QUEUEING NETWORKS 223

In other words, the arrival theorem states that in steady state the customer-average
probability distribution of the state seen by an arriving customer (not counting this
customer) is the same as the time-average probability distribution of the state in the
closed network with one customer less. A special case of the arrival theorem was
encountered in the Engset model; see relation (5.2.4). The product-form solution
is crucial for the arrival theorem. It is noted that the arrival theorem remains valid
for the closed network with a BCMP service discipline at each station. Then the
product-form solution

p(n 1 , . . . , n K ) = Cp 1 (n 1 ) · · · p K (n K )
holds for appropriate probability distributions {p 1 (n 1 )}, . . . , {p K (n K )}.
To calculate the average number of customers and the average sojourn times at
the different stations, we take the fixed number of customers moving around in the
network as parameter. For the closed network with a fixed number of m customers,
define the following long-run averages:

L m (j) = the average number of customers present at station j,
W m (j) = the average sojourn time of a customer at station j on
each visit,
λ m (j) = the average number of arrivals per time unit at station j.
Note that λ m (j) also gives the average throughput at station j. Also, by Little’s
formula, λ m (j)/µ j gives the long-run fraction of time the server at station j is
busy. For a constant γ m > 0, we have by (5.6.13) that
λ m (j) = γ m π j , j = 1, . . . , K, (5.6.17)
where the π j are the equilibrium probabilities associated with the Markov matrix
P =(p ij ). By Little’s formula,
L m (j) = λ m (j)W m (j), j = 1, . . . , K. (5.6.18)

Obviously, we have
K

L m (j) = m. (5.6.19)
j=1
The arrival theorem implies the key relation

1
W m (j) = 1 + L m−1 (j) , j = 1, . . . , K. (5.6.20)
µ j
To see this, note that an arriving customer at node j sees on average

n j π j (n 1 , . . . , n K ) = n j p m−1 (n 1 , . . . , n K ) = L m−1 (j)
(n 1 ,... ,n K ): (n 1 ,... ,n K ):
n 1 +···+n K =m−1 n 1 +···+n K =m−1