15.2 Analytical modeling examples

---

15.2 Analytical modeling examples

To better understand how these techniques can be used to model and analyze a system, we will undertake two studies: one for the early well-known Honeywell Experimental Distributed Processing system (HXDP) and the other for the token bus. In both cases, similar quantities are sought-namely, average scan time (time for control to sequence around once) versus message size. The intent is to analyze the efficiency of the control protocol and network characteristics.

15.2.1 HXDP model

Introduction

The HXDP system consists of processors connected to interface units that are joined by a bit-serial global bus. Bus allocation is governed by the vector-driven proportional access mechanism. Prior to system initialization, the 256-bit vectors are set for each processor so that for each time slice one, and only one, interface unit has a 1 in its index. The number of different schedules (possible combinations of 1s and 0s) for a system containing N interface units is, therefore, theoretically equal to N × N²⁵⁶, which is exorbitant even when N = 2. This scheme, however, cycles through the same pattern over and over again. Nonetheless, rather than develop a model allowing for any of the possible schedules, it was decided to constrain the allowable schedules to ease the computation.

It is assumed, consequently, that the schedule mechanism is as follows: Every interface unit is assigned a 1 only once in the index, after which the initial pattern repeats itself until the 256th index for processor N is set; this pattern is termed a scan block. The interface units, in turn, are sequentially logically numbered and are given a logical unit number.

One illustration of such a schedule with the corresponding scan blocks would be for four IUs (see Figure 15.2). One schedule would contain 256/4 = 64 scan blocks. Another schedule might be as shown in Figure 15.3. The sequence of events in the constrained system is then as follows: The reallocation signal arrives at logical unit 1 (the IU with the first 1 bit); if there is a message waiting service, the interface unit is granted the bus and the message is serviced. Once the message arrives at the destination, an acknowledgment is sent back to the source, after which a reallocation signal is sent out, the index is updated, and the next logical IU gets bus access. The sequence proceeds until IU N is serviced, after which (because of the assumptions) logical unit 1 is serviced. This continues ad infinitum.

Figure 15.2: Scan blocks.

Figure 15.3: Another scan block.

The scan time is, then, the time it takes to scan through the logical sequence of IUs once-that is, through the scan block. Table 15.1 lists the terms and their definitions.

Table 15.1: Symbols and Their Definitions

Symbol	Definition
N	Number of interface units in the system
Tsi	Time requirement to service a message at interface unit i
Tri	Time delay associated with the reallocation signal passing from interface unit with logical sequence i to i + 1
λi	Average message arrival rate at interface unit i
τ	Time to scan through entire sequence of IUs
	Average or expected scan
∂i	Set equal to 1 or 0 depending on whether IU has message awaiting transmittal or not
Ts	The time it takes to send the message of predetermined constant size from IUi to IUi+1 separated by distance d
Tack	The time it takes to send the acknowledgment from IUi to IUi+1 separated by distance d
TR	The time it takes to send the reallocation signal from IUi to IUi+1 separated by distance d
P	The probability of an arbitrary interface unit requiring service during one scan

Analytical modeling of the HXDP bus

It is assumed that the messages are arriving at an exponential rate. The probability that an arbitrary interface unit will require service during one scan is:

(15.1) 

where f_τ(t)is the probability density function of the scan time. For λt small, we use the approximation that e^-λt ≅ 1- λt. Thus:

(15.2) 

For varying message arrival rates = λ_i, this evaluation becomes:

(15.3) 

∇τ_i, which is the segment of the scan time that can be attributed to IU_i, is:

(15.4) 

where T_ack is the time it takes for acknowledgment (ack) to be sent back to i, if there was a message received, and T_r is the time it takes for the reallocation signal to go from IU logical number i to IU logical i + 1. But ξ_i can only take on values 0 or 1, and we assume that a uniform destination distribution and an IU in the HXDP system communicates with itself via the bus:

(15.5) 

This implies that:

(15.6) 

where |i - k| represents the number of interface units away from the source interface unit i where interface unit k is located.

Substituting we get:

(15.7) 

Thus:

(15.8) 

where index i denotes the logical number of the interface unit.

The main constraint on the model is:

(15.9) 

The effect on the average scan time, τ, can now be determined by varying any combination of the following parameters:

1. The number of interface units, N

2. The arrival rates, λ_k

3. The logical numbering of the interface units

4. The distances between neighboring interface units

5. The average size of the arriving messages

Graphic outputs

Figures 15.4 through 15.7 show the resultant computations for the scan time versus the message size for various changes in arrival rate, processor location, and quantity. These results will be compared with those of the simulator described later in this chapter.

Figure 15.4: Scan time versus message size, configuration 1.

Figure 15.5: Scan time versus message size, configuration 2.

Figure 15.6: Scan time versus message size, configuration 1b.

Figure 15.7: Scan time versus message size, configuration 2b.

15.2.2 Token bus distributed system

Introduction

The token bus distributed processing system (a local computer network) consists of processors connected to interface units, which, in turn, are connected by a common communications medium: the global bus. The allocation of the bus is controlled by the cyclic passing of tokens in a sequential manner from lowest numbered interface unit (IU) to the next highest until all numbered IUs have been interrogated and serviced. The sequential numbering is determined during power-up, and once steady state has been reached may be assumed to remain constant for modeling purposes. If an IU requires no service, control is passed to the next IU with an associated delay. The time it takes for the control to pass through the sequence completely is termed the scan time (as previously discussed).

Rather than investigating the entire token bus system, per se, emphasis will be on the bus, or the IU and bus layer, for modeling purposes. The main body of the example documents the development of the analytical models-in particular, the solution of the models for the value of the average scan time. The analytical computation of the scan time allows one to further determine such interesting and practical bus parameters as average message waiting time, average queue length, and bus use. From the derived formulas, one can readily ascertain the effect on bus parameters of increasing the number of processors, altering the sequential placement of processors, or varying the message arrival rates.

Preliminary formulations and definitions

The message arriving at the processor is assumed to follow a Poisson distribution-in other words:

(15.10) 

where P(r,t) is the probability that r messages arrive in time t, with each message being of the same size.

Service is required if there are one or more message arrivals in time t or:

(15.11) 

Since the assumption is that steady state has been reached, we can let fλ(t) denote the probability density function of the scan time τ. The corresponding cumulative distribution is then equal to:

(15.12) 

Let P denote the probability of an arbitrary processor requiring service during one scan:

(15.13) 

If more than one arrival occurs at any processor in any scan, that arrival can be considered blocked. This message will then have to wait at least one scan time before it can be placed on the bus. This implies that:

(15.14) 

(15.15) 

To enable the evaluation of P, for e^-λt ≅ 1-λt, implies that:

(15.16) 

which is equal to , by definition of expected value.

The relationship of will be used for all the models for simplification purposes. For clarity and convenience, Table 15.2 contains the symbols and their corresponding definitions, which will be used in the development of the analytical models.

Table 15.2: Symbols and Their Definitions

Symbol	Definition
N	Number of processors and consequently number of interface units due to a one-to-one correspondence in the system
Ts	The time required to service a message at an interface unit
Tsi	The time required to service a message at an interface unit i
Tc	Time delay associated with control (token) passing from an interface unit to its physically nearest neighbor interface unit
Tci	Time delay associated with control (token) passing from an interface unit with logical sequence number i to its neighbor interface unit i + 1
λ	Average message arrival rate at interface unit
λi	Average message arrival rate at interface unit i
τ	Time to scan through entire sequence of IUs
	Average or expected scan
∂i	Set equal to 1 or 0 depending upon whether IU has message awaiting transmittal or not
d	Distance between interface units i and i + 1
ts	The time it takes to send the message of predetermined constant size from IUi to IUi+1 separated by distance d
UF	Bus use factor
P	The probability of an arbitrary interface unit requiring service during one scan

Analytical modeling of the token bus

The analytical models developed for the token bus will be presented in an order reflecting an increasing degree of complexity and, consequently, a relaxation of the corresponding mathematical assumptions. In each of the models, a steady state, constant message size, and equal spacing between processors will be assumed. In addition, once the IU has been given control of the bus, it will be assumed that the message buffer for the interface unit will be emptied instantaneously onto the bus. The underlying specific assumptions in each case will be clearly outlined.

Case I

In the basic analytical model, it will be assumed that the arrival rate of messages at each of the N interface units is equivalent and is represented by λ. In addition, it is assumed that once steady state has been reached, the sequential (logical) numbering of the interface units is identical to the physical numbering (spatial numbering from left to right)-that is, it follows the representation shown in Figure 15.8.

Figure 15.8: Physical and logical numbering of interface units.

If we let T_c denote the time delay associated with the token (control) passing from one interface unit to another, the T_ci for each interface unit may be considered the same, since it has been assumed that the processors are equidistant from one another, and, consequently, the control will need to traverse the same distance from a processor to its next (with next highest sequence number) neighbor.

Another essential time parameter is the time it takes to service a message for any interface unit. In a ring topology with a token-passing scheme one could consider T_s, which is the time required to service a processor, to average out to the same value over time for all processors. Reference [22] shows that the same conclusion cannot be reached for the bus topology. Time to service a message is a function to the destination IU. Therefore, the placement of the source IU within the bus topology will affect the average time it takes to service one of its messages. For example, if N = 3, we have the configuration shown in Figure 15.9.

Figure 15.9: Token bus with three interface units.

For interface unit 1 to transmit a message to processor 2, the message will have to traverse the distance from 1 to 2; for interface unit 1 to transmit a message to 3, it will have to traverse the distance from 1 to 3. If we represent the equal distance between two neighboring interface units as d, and we let each of the other IUs be potential similar message destinations (e.g., a uniform distribution for message destinations is assumed):

(15.17) 

where d/velocity estimate = t_s = time to send the message of the chosen size from i to i + 1:

(15.18) 

For processor 2, as the source processor, the corresponding equation becomes:

(15.19) 

Let T_si denote the time it takes to service a message at interface unit i. The time it takes for the token to pass from the ith IU to the i + 1st interface unit may then be expressed as:

(15.20) 

The total scan time becomes:

(15.21) 

Now, taking expectations of both sides of equation (15.21) we get the average value of scan time as:

(15.22) 

Next, by definition of the expected value of product:

(15.23) 

Since it was mentioned previously that T_si is a function of the distance that the message has to travel, and since ξ_i can only take on the value 0 to 1:

(15.24) 

where i - k represents the number of interface units away from the source interface unit i, the destination interface unit k is located, and any interface unit other than i has an equally likely probability of being a destination interface unit. That is, a probability 1/N - 1.

P is the probability derived in the preliminary formulation. In summary:

(15.25) 

Substituting into (15.25):

(15.26) 

This equation is valid, based upon the assumption and approximations if, and only if:

(15.27) 

Case II

In this model, we relax the assumptions that all the interface units have identical message arrival rates equal to λ, by allowing for message arrival rates of λ_i for interface unit i. However, we retain the assumption of the hypothetical, logical, or physical configuration, which, in turn, will be eliminated in the subsequent case. The relaxation of the assumptions is being done in a gradual manner to emphasize the evolutionary nature of the development of the analytical models. The relaxation of the equivalent message arrival rates will allow for a greater realm of applicability and consequently, of testing but will, naturally, complicate the ultimate formula for τ.

Since each interface unit now has a characteristic message arrival rate, λi for interface unit i, P now becomes:

(15.28) 

Equation (15.21) is still applicable-that is:

(15.29) 

Furthermore, τ is still:

(15.30) 

where:

(15.31) 

(15.32) 

(15.33) 

Substituting

(15.34) 

Thus,

(15.35) 

Case III

This model incorporates major modifications, which should permit the model to better reflect the actual system. In particular, it is assumed that once steady state has been reached, the logical numbering does not have to reflect the physical location, but, in fact, the steady-state configuration could be as shown in Figure 15.10.

Figure 15.10: Mapping logical to physical location.

The logical sequence numbering of the token bus system may assume any out of the N! possible, different choices of the steady state with an equal probability. Therefore, it is of the utmost importance to develop a model that can reflect all N! of the possible combinations.

Consequently, T_c, now, is not a constant but must in some sense reflect the time it takes for the token to travel the distance from interface unit i to interface unit i + 1.

Let i represent the logical sequence number of the interface unit; then ∇τ_i = ξ_iT_si + T_ci; where T_ci = the time for a token to traverse the distance from the IU with logical sequence i to the IU with logical sequence i + 1 (N+ 1 becomes IU 1).

In the previous models, the logical sequence number and the physical number of the interface units were identical; therefore, it was not necessary to state explicitly the correspondence of the index i.

The total scan time is now expressed by:

(15.36) 

The average value of scan time equals:

(15.37) 

which, for a known configuration, is equal to:

(15.38) 

N + 1 denotes 1, due to cycling, where t_c is the time it takes for the control to pass from any interface unit k to physical unit k + 1.

We have previously evaluated:

(15.39) 

and, in order to take advantage of the results, the index k will denote the physical number of the interface unit, while the index i will denote the logical number of it.

Combining the results and making the substitution:

(15.40) 

we get:

(15.41) 

From equation (15.41), the effect on the average scan time can be determined by varying any combination of the following variables:

1. The number of interface units, N

2. The arrival rates, λ_k, of the messages at the interface units with logical numbers, k

3. Varying the logical sequential numbering of the interface units

4. Varying the distances between neighboring interface units

5. Varying the average size of the messages arriving at the interface units

The main constraint of the model is:

(15.42) 

---