5.4.3 Three-Server Example (infinite Line Capacity)

To serve as both an example of the use of the hypercube model and a vehicle to derive its general mathematical structure, we consider the simple three-server city shown in Figure 5.11. This city is partitioned into 10 geographical atoms, each acting as an independent Poisson generator of service requests. For ease of presentation, we will assume that the mean service time of each unit n is the same known constant ^-1. (There is, in general, no additional complexity in allowing mean service times to be server dependent; see Problem 5.13.)

Throughout the remainder of this chapter, we assume that the hypercube model has infinite queue capacity. Some results for the zero-capacity case are presented in the problems at the end of the chapter.

The rates _j, of arrival of requests from each atom j are shown in the figure (expressed in arrivals per mean service time unit), with ₅, for instance, equaling 0.15 request per mean service time unit. Each unit has a primary response area, consisting of a set of atoms to which it would always be given first dispatch preference. For instance, the primary response area for unit 2 consists of atoms 3, 5, and 6. The unit given second dispatch preference for an atom is selected on the basis of geographical proximity. The complete dispatch preference policy, by atom, is shown in Table 5-4. Note, for instance, that unit 1 is the primary backup unit for all service requests in both primary response areas 2 and 3; thus, not only does unit 1 face a heavy workload from its own primary response area (50 percent of the city's workload), but it is also the first backup unit for the rest of the city as well. Note, too, that primary response area 1 is itself split with respect to a first backup unit for unit 1: unit 2 is the first backup unit for atoms 1 and 2, whereas unit 3 is the first backup unit for atom 4. In writing and solving the equilibrium equations for the hypercube model, there is in general no additional complexity incurred by making the dispatch preferences (as displayed in Table 5-4) as complicated as one desires.

If we are only interested in workload-oriented performance measures, it is not necessary to specify the interatom travel-time matrix _ij) nor is it necessary to specify the probabilistic locations of servers who are free (i.e., not serving customers). All we need to know to set up the hypercube model are the dispatch preferences, atom-specific arrival rates, mean service times, and queueing behavior (infinite capacity here).

In this example we have set all the mean service times equal to the same constant. With this restriction, the queueing system in the aggregate (if one is not concerned with the identity of busy servers) is simply the M / M / N system, as discussed in Chapter 4. But the state space in which the identities of servers are retained is more complicated than the set of nonnegative integers which is adequate for the M / M / N model. Symbolically, if we say that b_n = state of server n (b_n = 0 for "free," or b_n = 1 for "busy"), the system state is given by B = {b_N,b_N-1 ,..., b₁}The collection of all possible B's is denoted by C_N, corresponding to the vertices of an N-dimensional hypercube. The weight of B, denoted w(B), is equal to the number of busy servers in the state B; thus, w(B) = b_n. For instance, the weight of {0, 1, 1} is 2, of {0, 0, 0} is 0.

For the case of equal mean service times, we can use the concept of weight of a state to relate the hypercube state space to the simpler M / M / N state space. This equivalence is obtained by collecting together all states having equal weight, say w₀; their summed probability of occurrence is equal to the comparable probability of state S_w0, occurring in the M / M / N model (using the results of Chapter 4). For instance, the states 001, 010, and 100 all have weight 1, and their summed probability must equal the probability of state S₁, in the M / M / N model. One way of demonstrating this equivalence is shown in Figure 5.12, in which all hypercube states having equal weight are grouped together vertically. Figure 5.12 also shows explicitly the infinite tail that augments the hypercube state space to allow the possibility of a queue. Since this infinite tail behaves in just the same manner as the infinite tail of the M / M / N model, we will not explicitly add it to the more geometrically oriented "cubic" state space shown in Figure 5.13. In this figure, the collection of states 001, 010, and 100 can be seen to intersect a plane at a generalized 45^o angle to the origin; that is, each side of the cube cut by this plane is cut at a 45^o angle and, measured along the cube's edges, the plane is a distance 1 from the origin.

We can generalize this concept to N dimensions, defining

H_n set of states having weight n
= {B C_N : w(B) = n} n = 0, 1, . . . , N

Here H_n is the set of states intersecting a hyperplane located a distance n from the origin (distance measured in a "right-angle" way along edges of the cube), situated at a generalized 45^o angle with respect to the origin. We sometimes refer to H_n as the nth hyperplane from the origin, recognizing that, in fact, it is made up of only a finite number of points (states).

Exercise 5.1: Argue that the number of points or states in H_n is equal to

In extending the model to N dimensions it becomes cumbersome to denote each state as an N-digit binary number. Thus, we are motivated to use a state indexing scheme that corresponds in a natural way to the binary state representation. The index we choose is simply the decimal integer numerical value associated with each binary representation. For example, for the N = 3 unit problem, we have

This correspondence is shown in Figure 5.13.

In general, for an N-unit problem, the indexed states run from B₀ to B_{2^N -1}. For a generic state B = {b_N, b_N-1, . . . , b₁}, its index value is simply

(B) = b_N2^N-1 + b_N-12^N-2 + . . . + b₁

In the reverse direction, for each positive integer k there corresponds a unique B_k such that (B_k) = k. For instance, for an N = 9 problem, k = 492 corresponds to B₄₉₂ = {1, 1, 1, 1, 0, 1, 1, 0, 0} since (B₄₉₂) = 492.

State-to-state transitions. With the hypercube model transitions occur between states just as they do with other queuing models. The hypercube model assumes that only one unit is assigned to each service request. Thus, assuming that it is virtually impossible for two requests to arrive simultaneously, a transition from state (0, 0, 0) to state (0, 1, 0) would be allowable, whereas a two-step transition from state (0, 0, 0) to state (0, 1, 1) would not (since it implies that two free units become busy at the same instant). Likewise, if we assume that each of the busy units is working independently at its particular location to complete service on its current service request, it is virtually impossible for two busy units to become free simultaneously. Thus, a transition from state (1, 0, 1) to state (0, 0, 1) is allowable, whereas a two-step transition from state (1, 0, 1) to state (0, 0, 0) is not.

Summarizing, any one-step transition is allowable; all multistep transitions are not allowable. Transitions can be thought of as occurring only between states in adjacent hyperplanes from the origin. One's intuition is again assisted by visualizing these transitions to occur on the hypercube. Since a one-step transition causes only one of the "O's" or "1's" to change in the system-state description (meaning that only one unit's state changes), we can visualize the transition as occurring along an edge of the hypercube. (An edge is a straight line connecting two adjacent vertices of the hypercube.) For instance, referring again to Figure 5.13, a transition from state (0, 0, 1) to state (1, 0, 1) occurs along the rightmost edge of the cube.

As an example of combining the concepts of state and transition, consider our three-unit city, which starts with all units free. Suppose that the following events then occur:

1. A request for service arrives from atom 6.

2. A request for service arrives from atom 1.

3. Unit 2 completes service on its request.

4. A request for service arrives from atom 4.

5. A request for service arrives from atom 3.

Recalling that atom 6 is within unit 2's primary response area, the request for service from atom 6 would result in unit 2 becoming busy, yielding a transition from state (0, 0, 0) to state (0, 1, 0). Likewise, the next request for service would cause unit 1 to become busy, resulting in a transition from state (0, 1, 0) to state (0, 1, 1). Next, when unit 2 becomes free, the system makes a transition to state (0, 0, 1). Next, when a request for service arrives from atom 4, in unit 1's primary response area, we note that unit 1 is already busy servicing a request. Since the primary backup unit, unit 3, is available, it is dispatched to the scene, resulting in an interresponse area assignment. The system now undergoes a transition from state (0, 0, 1) to state (1, 0, 1). Finally, when a request arrives from atom 3, unit 2 is dispatched, causing the system to enter a saturation state (1, 1, 1). (Any additional service requests arriving while all servers are busy would be delayed in queue.)

Summarizing the example above, the sequence of states occupied by the system is as follows:

Now the value of the cube as an aid in visualizing the behavior of the system is seen in Figure 5.14, which depicts the states occupied and the state-tostate transitions as a sequence of connected trips along edges of the cube.

Transition rates on the hypercube. We are now ready to link the arrival rates and the service rates to states and transitions on the hypercube. Referring again to Figure 5.13, suppose that the system is in the "empty state," (0, 0, 0). Recall that 0.75 request for service arrives per unit time from unit 1's primary response area, 0.35 from unit 2's primary response area, and 0.40 from unit 3's. Also recall that time is measured in mean service time units. Then, from state (0, 0, 0), there is a rate of transition to state (0, 0, 1) equal to 0.75 request per unit time. Likewise, there is a rate of transition from state (0, 0, 0) to state (0, 1, 0) equal to 0.35 per hour and to state (1, 0, 0) equal to 0.40 per unit time. These state-to-state transition rates can be drawn onto the cube as shown in Figure 5.15. In a similar manner, the transition rate from any state to any adjacent state having one less unit busy is 1 per unit time, and these transition rates are depicted in Figure 5.16.

We have now filled in the transition rates from state (0, 0, 0) and all the rates corresponding to completions of service. For convenience, the latter type of transitions are called "downward" transitions, indicating that the total number of busy units has dropped down by one. Transitions that result in a unit being dispatched are called "upward" transitions, because the total number of busy units has gone up by one. The careful reader will notice that we have not yet specified most of the upward transitions. This is due to the fact that upward transition rates depend on the dispatcher's selection strategy, and this complicates the specification of most of the upward transition rates.

One further set of upward transition rates is particularly easy to specify. Since all service requests that arrive are serviced immediately (i.e., they incur no queue delay) if at least one response unit is available, all states that are unit distance from the saturation state (states 011, 101, and 110 in our example) must have an upward transition rate equaling the total system-wide request rate (= 1.5 in this case). Thus, all upward transition rates into state 111 must equal 1.5 in our example.

To compute the values of the remaining upward transition rates, consider for instance the transition rate from state 001 to state 101. This rate will consist of the sum of two rates: the rate of service requests from unit 3's primary response area plus the overflow rate from that part of unit 1's primary response area assigned to unit 3 as the first backup unit. The first rate is simply 0.40 request per unit time. The second is the arrival rate from atom 4 (0.25 request per unit time), since the first backup unit for atom 4 (in unit 1's primary response area) is unit 3. (Unit 2 is the first backup unit for the other atoms in unit 1's primary response area.) Thus, the net upward transition rate from state 001 to state 101 is (0.40 + 0.25) = 0.65 request per unit time. In a like manner, the remaining upward transition rates can be found.

The entire state-transition diagram for this example (excluding the infinite tail) is shown in Figure 5.17.

Steady-state balance equations. Although it is instructive to visualize this process on a three-dimensional cube (or a square, for N = 2), no such visual aids are available for N > 3. Thus, one should be able to write down the equilibrium equations of balance without resorting to the visual aid. We do this below, utilizing our knowledge that sums of steady-state probabilities along given hyperplanes from the origin must equal corresponding state probabilities from the simple M / M / N model.

We define

P_ijk steady-state probability that the system is in state {i, j, k}, i, j, k = 0, 1

P{S_i} steady-state probability that the equivalent M / M / 3 system is in state S_i

P_Q steady-state probability that a queue of positive length exists

P{S0}
	(5.21a)

P{S1} = P{S0} = 0.31579	(5.21b)
P{S2} = P{S0} = 0.23684	(5.21c)
P{S3} = P{S0} = 0.11842	(5.21d)
PQ = P{Si} = P{S0} 0.11842	(5.21e)

Using these results, we can now write the hypercube equilibrium equations for nonsaturated system states:

1. Empty state P000 = P{S0} = = 0.2105	(5.22)
2. Full state (no queue) P111 = P{S3} = = 0.11842	(5.23)
3. First hyperplane from the origin P001 + P010 + P100 = P{S1} = = 0.31579	(5.24)
4. Second hyperplane from the origin P110 + P101 + P011 = P{S2} = = 0.23684	(5.25)
5. Balance of flow about state 001	(5.26)
6. Balance of flow about state 100 P100( + 1) = P000(0.40) + 1(P110 + P101)	(5.27)
7. Balance of flow about state 011
(5.28)
8. Balance of flow about state 101 P101 ( + 2) = 1P111 + P001(0.4 + 0.25) + P100 (0.75 + 0.40)	(5.29)

We solve this set of equations by eliminating the following variables, in order, by use of the designated equations:

After about 15 or 20 minutes with an electronic hand calculator, we arrive at the following values for the state probabilities: