Previous Table of Contents Next


CHAPTER 33
OPERATIONAL LAWS

All professional men are handicapped by not being allowed to ignore things which are useless.

— Johann Wolfgang von Goethe

A large number of day-to-day problems in computer systems performance analysis can be solved by using some simple relationships that do not require any assumptions about the distribution of service times or interarrival times. Several such relationships called operational laws were identified originally by Buzen (1976) and later extended by Denning and Buzen (1978).

The word operational means directly measured. Thus, operationally testable assumptions are the assumptions that can be verified by measurements. For example, it is easy to verify whether the assumption of number of arrivals being equal to the number of completions holds for a particular system. Therefore, this assumption, commonly called the job flow balance assumption, is operationally testable. On the other hand, one can never establish through measurement that a set of observed service times is or is not a sequence of independent random variables. Thus, the assumption of independence, although commonly used in stochastic modeling of queues, is not operationally testable.

The operational quantities are the quantities that can be directly measured during a finite observation period. For example, consider the black-box view of a device i shown earlier in Figure 30.3. If we observe the device for a finite time T, we can measure the number of arrivals Ai, the number of completions Ci, and the busy time Bi during this period. All of these are operational quantities. From these we can further derive the following operational quantities:

Notice that these operational quantities are variables that can change from one observation period to the next, but there are certain relationships that hold in every observation period. Such relationships are called operational laws. Several such laws are presented later in this chapter.

33.1 UTILIZATION LAW

Given the number of completions Ci and the busy time Bi of a device i during an observation period T, the following relationship holds among these variables:

or

This relationship is called the utilization law.

The utilization law, as well as other operational laws, is similar to the elementary laws of motion. For example, if a body starts at rest and accelerates at a constant acceleration a for an interval of time t, the distance traveled d is given by

Notice that distance d, acceleration a, and time t are operational quantities. There is no need to consider them as expected values of random variables or to assume a probability distribution for them.

Example 33.1 Consider the network gateway problem of Example 31.1 again. The packets arrive at a rate of 125 packets per second (pps) and the gateway takes an average of two milliseconds to forward them.

Throughput Xi = exit rate = arrival rate = 125 pps

Service time Si = 0.002 second

Utilization Ui = XiSi = 125 × 0.002 = 0.25 = 25%

Although this utilization is the same as that computed in Example 31.1, the key point to note is that while the result of Example 31.1 required assuming the interarrival times and service times to be IID random variables with exponential distribution, in this section we have made no such assumption, and the result is valid for any arrival or service process.

33.2 FORCED FLOW LAW

The forced flow law relates the system throughput to individual device throughputs. In an open model, the number of jobs leaving the system per unit time defines the system throughput. In a closed model, no job actually leaves the system. However, traversing the outside link (the link connecting "Out" to "In" in Figure 32.2) is equivalent to leaving the system and immediately reentering it, and the system throughput is defined as the number of jobs traversing this link per unit time.

If our observation period T is such that the number of job arrivals at each device is the same as the number of job completions, that is,

Ai = Ci

we can say that the device satisfies the assumption of job flow balance. If the observation period T is long, the difference Ai - Ci is usually small compared to Ci. It will be exact if the initial queue length at each device is the same as the final queue length.

Suppose each job makes Vi requests for the ith device in the system, as shown in Figure 33.1. If the job flow is balanced, the number of jobs C0 traversing the outside link and the number of jobs Ci, visiting the ith device are related by


FIGURE 33.1  Internal view of the system.

Thus, the variable Vi is the ratio of visits to the ith device and the outside link. It is therefore called the visit ratio. The system throughput during the observation period is

The throughput of the ith device and the system throughput are therefore related as follows:

In other words,

Xi = XVi (33.1)

This is the forced flow law. It applies whenever the job flow balance assumption is true.

It is clear that if the job flow balance is not true, then either there are some jobs that arrived during the observation period but did not leave or there were some jobs already in the system at the beginning of the observation period. In either case, it is possible that these jobs have not yet made all Vi visits to the ith device and CiC0Vi.

Combining the forced flow law and the utilization law, we get

Utilization of the ith device Ui = XiSi
= XViSi

or

Ui = XDi (33.2)

Here Di = ViSi is the total service demand on the device for all visits of a job. Equation (33.2) states that the utilizations of various devices in the system are proportional to total demand Di per job on the device. Hence, the device with the highest Di has the highest utilization and is the bottleneck device. This result will be used later in Section 33.6.

Example 33.2 In a timesharing system, accounting log data produced the following profile for user programs. Each program requires 5 seconds of CPU time and makes 80 I/O requests to disk A and 100 I/O requests to disk B. The average think time of the users was 18 seconds. From the device specifications, it was determined that disk A takes 50 milliseconds to satisfy an I/O request and disk B takes 30 milliseconds per request. With 17 active terminals, disk A throughput was observed to be 15.70 I/O requests per second. We want to find the system throughput and device utilizations.
This system can be represented by the queueing network model shown earlier in Figure 32.8.Symbolically, we are given the following: DCPU = 5 seconds, VA = 80, VB = 100, Z = 18 seconds, SA= 0.050 second, SB = 0.030 second, N = 17, and XA = 15.70 jobs/second.


Previous Table of Contents Next

Copyright © John Wiley & Sons, Inc.