Page 225 - A First Course In Stochastic Models

218 MARKOV CHAINS AND QUEUES

The partial balance equations (5.6.5) and (5.6.6) are characteristic for the product-
form solution. These equations express that

the rate out of a state due to a change at node j
= the rate into that state due to a change at node j (5.6.9)
for each j = 0, 1, . . . , K, where node 0 corresponds to the outside world. This
property of node local balance is in general not satisfied in a stochastic network, but
can indeed be verified for the Jackson network model. The product-form solution
(5.6.3) can be expressed as

p(n) = p 1 (n 1 ) · · · p K (n K ), (5.6.10)
where for any k the probability distribution {p k (n), n = 0, 1, . . . } of the number
of customers present at station k is the same as the equilibrium distribution of
the number of customers present in an M/M/1 queue with arrival rate λ k and
service rate µ k . In other words, in steady state the number of customers at the
different service stations are independent of each other and the number at station
k behaves as if station k is an M/M/1 queue with arrival rate λ k and service
rate µ k . The result (5.6.10) is remarkable in the sense that in the network model
the composite arrival process at station k is in general not a Poisson process. An
easy counterexample is provided by a single-station network with feedback; that
is, a customer served at the station goes immediately back to the station with a
positive probability. Suppose that in this network the arrival rate from outside is
very small and the service rate is very large. Then, if the feedback probability is
close to 1, two consecutive arrivals at the station are highly correlated and so the
arrival process is not Poisson.
The Jackson network model can be generalized to allow each service station to
have multiple servers with exponential service times. If station j has c j servers,
the ergodicity condition (5.6.2) is replaced by λ j /(c j µ j ) < 1. Then the node
local balance equation (5.6.9) can again be verified and the equilibrium distribu-
tion {p(n)} of the numbers of customers present at the different stations has the
product form (5.6.10), where the probability distribution {p k (n)} of the number of
customers present at station k is the same as the equilibrium distribution of the
number of customers present in an M/M/c queue with arrival rate λ k , service
rate µ k and c = c k servers. Note that the multi-server M/M/c queue with service
rate µ can be regarded as a single-server queue with state-dependent service rate
µ(n) =min(n, c)µ when n customers are present. Indeed it can be shown that
the product-form solution also applies to the Jackson network model with state-
dependent service rates provided that the service rate at each station depends only
on the number of customers present at that station. More about the product-form
solution and its ramifications can be found in the books of Boucherie (1992) and
Van Dijk (1993). In these references the product-form solution is also linked to
the concept of insensitivity. Insensitivity of the stochastic network holds when the
condition of node local balance is sharpened to job local balance, requiring that