4.10.2 State-Transition-Diagram Approach to Networks with Blocking Effects
Whenever the arrival of users at a queueing network constitutes a Poisson process and each queueing system in the network has negative exponential service times, it is possible, at least in principle, to obtain the properties of the queueing network under steady-state conditions by using the following twostep approach:
STEP 1: Prepare a state-transition diagram that shows all the possible states that the
STEP 2: Write and solve the balance equations for the steady-state probabilities of the
This approach will be one of the fundamental ideas that Chapter 5 will develop with respect to a specific but very rich family of queueing systems. In this section we shall only illustrate the approach with reference to series queueing networks with blocking effects. One of the main points that the reader should take note of is how this approach can deal with interactions between the component queueing systems of the network.
To describe the state of the network we now need two index numbers: one to indicate the
state of facility 1 and the second to indicate the state of facility 2. Facility 2 can be
either empty (0 users in the facility) or contain 1 user; facility 1 can be empty (0
users) or full and busy (1 user) or idle but full due to blocking from another user in
facility 2. We indicate this last condition by the letter b, for "blocked."
Thus, the possible network states are 00, 01, 10, 11, and b1, with the first index number,
by convention, denoting the state of facility 1. Note that state b0 cannot exist.
where the meaning of each of the steady-state probabilities Pij is obvious.
Using (4.117) and any four of the five equations in (4.116) and solving for the five steady-state probabilities, we obtain
Of more interest, however, are the effects of blocking (and of the zero queueing capacity) on the performance of the queueing network. For example, the mean number of busy servers in the network is
while the fraction of potential users lost is given by
Theoretically, this type of
approach can, as noted above, be applied to any queueing network-no matter how complex-as
long as the queue capacities for every element of the network are finite. 16
When all queue capacities are finite, there is a finite number of possible network states
and, consequently, a finite number of balance equations which determine the steady-state
probabilities (see Problem 4.13).