Consider a distributed system environment, made up of a collection of clients and servers connected via a high speed local area network (LAN). Servers are placed in the system to provide service upon request. A file server is a key component of this kind of environment. Its purpose is to provide file services for the client processes on the network. Basically, a file server is composed of processors, memory, and a disk subsystem. The workload of a file server can be viewed as a series of file service requests such as read, write, create, and remove, which arrive from the workstations via the LAN. The operation of a file server can be viewed as follows. Requests arrive to the server. A typical request enters the server, possibly queues up while waiting for some resource (processor, memory, disks) to become available, obtains service from the resources, and exits the server. The number of requests being handled concurrently by the server varies over time depending on factors such as the load placed by the clients (i.e., the request arrival rate), the file system capacity, the available memory, and the processor speed. A file server is a good example of a system suitable to be modeled as an open model. It exhibits the key characteristic of open systems: the variation of the number of customers over time. In practice, the number of customers (transactions, processes, requests) varies dynamically, due to such factors such as process termination, process initiation, and process spawning. An open class is able to represent this variation because it has a potentially unlimited number of customers. Chapter 10 introduces and analyzes the birth-death system, which gives the underlying theory for single-class open model. This analysis is extended here to multiclass models. Figure 13.5. Approximate MVA algorithm for multiple classes.
The load intensity of a multiclass model with R open classes and K devices is represented by the vector = (l1,l2, ···, lR), where lr indicates the arrival rate of class r customers. As illustrated in Figure 13.6, the goal of the analysis of multiclass open models is to determine, for each class, performance measures such as average response time, , and queue lengths, , as a function of the load intensity, . Figure 13.6. Multiple class open models.
13.6.1 Analysis of Multiclass Open ModelsIn steady state, the throughput of class r equals its arrival rate. Thus, Equation 13.6.11
The application of Little's Law to each device gives Equation 13.6.12
where Ri,r () is the average class r customer response time per visit to device i. The average residence time for the entire execution is R'i,r = Vi,rRi,r. Using the Forced Flow Law and Eq. (13.6.11), the throughput of class r is Equation 13.6.13
Using Eq. (13.6.13) in Eq. (13.6.12) the average queue length per device for each class becomes Equation 13.6.14
Combining the Utilization Law and the Forced Flow Law, the utilization of device i by class r customers can be written as Equation 13.6.15
Thus, to compute the average number of class r customers in service center i, is needed as a function of the input parameters (i.e., and the service demands Di,r's). The average time a class r customer spends at a device, from arrival until completion, has two components: the time for receiving service and the time spent in queue. The latter is equal to the time required to service customers that are currently in the device when the customer arrives. Thus, Equation 13.6.16
where is the average queue length at device i seen by an arriving class r customer when the load on the system is For delay servers, = Di,r. The arrival theorem [17] states that in an open product-form queuing network, a class r arriving customer at service center i sees the steady-state distribution of the device state, which is given by the queue length. (Note: This is consistent with the arrival theorem result concerning closed systems. In closed systems, an arriving customer see the steady-state distribution with itself removed. In an open system, since there is an infinite customer population, removing oneself from the network has no effect. Thus, the steady-state distribution seen by an arriving customer is equal to the overall steady-state distribution.) Thus, Equation 13.6.17
From Eqs. (13.6.16) and (13.6.17), we get Equation 13.6.18
Substituting Eq. (13.6.18) into Eq. (13.6.14), yields Equation 13.6.19
Notice that expression [1 + in Eq. (13.6.19) does not depend on class r. As a consequence, for any two classes r and s, we have Equation 13.6.20
Using Eq. (13.6.20) and considering the fact that , Eq. (13.6.19) can be rewritten as Equation 13.6.21
Applying Little's Law to Eq. (13.6.21), the average residence time for class r customers at device i is Equation 13.6.22
The interaction among the open classes of a multiclass model is explicitly represented by the term of Eq. (13.6.22), which corresponds to the total utilization of device i by all the classes in the model. The analysis of a product-form model with multiple open classes begins with the constraint that 1 for all devices of the network and proceeds with the formulas summarized in Figure 13.7. From Eq. (13.6.15), the stability condition for an open model is Equation 13.6.23
or Equation 13.6.24
13.6.2 Open Models: Case StudyConsider a distributed environment made up of a number of client diskless computers connected via a high-speed LAN to a file server, composed of a single processor and one large disk. The company is planning to double the number of client computers. Because the system performance is critically dependent on the file server, management wishes to assess the impact of the expansion before it is implemented. So, the first question to be answered is: What is the predicted performance of the file server if the number of diskless workstations doubles? Following the modeling paradigm of Figure 10.1, the initial step is constructing the baseline model, which begins with the workload characterization. The workload to the file server consists of file service requests, which can be grouped into three classes: read, write, and all others. The latter comprises control requests of the network file system and other file service requests less used. During a period of one hour, the file server was monitored and the following measurement data were collected over one hour: 18,000 reads, 7,200 writes, 3,600 file service requests other than reads and writes, processor utilization at 32%, and disk utilization at 48%. Figure 13.7. Formulas for models with multiple open classes.
The measurement data also provide resource utilization on a per-class basis, as shown in Table 13.8. Using the measurement data and the operational relationship (Di,r = Ui,r/X0,r), each request is characterized in terms of its service demands. Once Di,r has been calculated, it is possible to compute Vi,r using the disk service time provided by the manufacturer. For the processor, the parameter Vproc,r is calculated using the following expression that relates the visit ratio at the processor to the visit ratios at the I/O devices in a central server model
Equation 13.6.25
where devices 2 through K are the I/O devices. Table 13.8 summarizes the parameters that characterize the file server workload. Motivated by simplicity, the analyst in charge of the capacity planning project decided to construct a single-class model of the file server. The model constructed is an open model where only the file service components (processor and disk) are directly represented. It is assumed that the file server has enough memory so that no request queues for memory. The workstations are implicitly represented in the workload model by the file service requests generated by them. The larger the number of workstations, the larger the request arrival rate. The single-class model equivalent to the three-class model is obtained by calculating the aggregate demands.
By solving the model, the following residence times are obtained: = 0.04/(1 0.32) = 0.059 and = 0.06/(1 0.48) = 0.115. The sum gives an average request response time of 0.174 seconds. To answer the "what if" question, it is necessary to change the baseline model to reflect the effects of doubling the number of workstations. Since this number is not directly specified in the input parameters, some assumptions are necessary. It is assumed that the new workstations will have the same usage as the installed ones. This means they will run the same group of applications and will generate file service requests that follow the current pattern of requests. Thus, by increasing the number of workstations by 100%, the request arrival rate, likewise, is assumed to increase by 100%. Letting lnew = 2 x 8 = 16, the model is re-solved to obtain the predicted measures.
Therefore, if the number of workstations were doubled, the file server disk would saturate and the average request response time would increase from 0.174 sec to 1.611 sec, an 825% increase! The model clearly indicates that the server would be bogged down and users would suffer with long response times at the workstations. Now consider some possible alternatives to support system expansion without impairing service levels. The current system performance will be used as a basis for the comparison of the various alternatives under consideration. Each alternative is evaluated by considering the relative change in system performance from the baseline model.
For each alternative, a three-class model is evaluated according to the formulas of Figure 13.7. The model inputs consist of parameters from Table 13.8 and those that were calculated to represent each specific change in the baseline model. Table 13.9 summarizes the performance measures obtained for the three alternatives. To obtain a rank of the alternatives in terms of performance, aggregate response time is first calculated for each alternative, which is the average of the individual classes weighted by the class throughput. Table 13.10 displays the aggregate response times as well as the relative change in the response time from the baseline model. The pure expansion refers to the alternative that just increases the number of workstations. All alternatives assume that the number of workstations will be doubled.
From the file server perspective, the best alternative is the upgrade in the disk subsystem, because it considerably diminishes the demand on the original disk. The client cache, although seemingly worse than the server cache, may be the best alternative from the system viewpoint. The key issue in this alternative is the reduction in the number of times that a user process goes to the file server. This reduction implies less overhead of network access, which in many systems has a high cost. |