14.4 Multiclass Closed Models with LD Devices

The algorithm for solving a multiple-class closed QN with load-dependent devices is given in this section. It is an extension of the approximate algorithm for multiple classes given in Chapter 13 for incorporating load-dependent devices discussed previously in this chapter. It is assumed in this section that the service-rate multiplier of any load-dependent device is class independent (i.e., if device i is load-dependent, then a_i,r(j) = a_i(j) for all classes r).

The basis for the algorithm lies in obtaining an appropriate expression for the marginal probability, , of finding j customers at load-dependent device i given that the QN population vector is . This probability can be obtained from the local balance equations of the network states [9] as

Equation 14.4.12

where is the total number of customers in the network. As in the load-independent case, the dependency on values derived by removing one customer from each class makes an exact MVA solution for even moderate size QNs very expensive. To overcome this problem, it is assumed, as an approximation, that

Equation 14.4.13

In other words, it is assumed that the removal from the QN of one customer of class r does not significantly affect the overall queue length distribution at device i [9]. Using Eq. (14.4.13) in Eq. (14.4.12) and the fact that , it follows that

Equation 14.4.14

Solving Eq. (14.4.14) recursively one can obtain a closed-form expression for as a function of can be obtained by requiring all probabilities to sum to 1 (see Exercise 14.5). Thus,

Equation 14.4.15

Equation 14.4.16

The generalization of Eq. (14.3.9) for the multiple-class case is

Equation 14.4.17

Using the approximation given in Eq. (14.4.13) in Eq. (14.4.17), it follows that

Equation 14.4.18

The values of the probabilities P_i(j 1 | ) are needed to compute the residence time . To compute these probabilities the values of the throughputs X_0,r() are needed, which depend back on the residence time values. The following iterative approach is proposed:

1. Estimate initial values for the throughputs X_0,r(). These estimates can be obtained by approximating the throughput by its asymptotic upper bound, namely . Although this is a loose upper bound, it serves as a starting point for the iteration discussed here.

2. Using Eqs. (14.4.15) and (14.4.16), compute the probabilities P_i(j | ).

3. Compute the residence times using Eq. (14.4.18).

4. Compute new values for the throughputs using Little's result as

   

   
   

5. If the relative error between the throughputs obtained in the current iteration and the previous iteration is greater than a certain tolerance (e.g., 10 ⁴) then go to step 2. Otherwise, compute the final metrics and stop.

This approach is specified in detail in the algorithm of Figure 14.7. The notation K_r indicates the number of devices for which D_i,r > 0.

Example 14.4.

Consider the client-server architecture shown in Figure 14.3. Suppose the application layer is designed to support up to 80 running processes simultaneously. Each application process receives a client request, executes the application logic, and interacts with the database server. After monitoring the application processes, the performance analyst identified three types of processes (i.e., in terms of resource usage) corresponding to the three most common client requests. During the monitoring period, the application had 35 processes running on average. The application architect wants to determine the average database response time in order to understand the impact on the database if the number of application processes is changed. The analyst decides to use a three-class closed model with an LD device to represent the two-tier architecture depicted in Figure 14.8.

The database server is assumed to have one processor and one disk. The requests are categorized as being of three types: trivial, average, and complex, according to their use of database resources. Ten application processes are responsible for submitting trivial requests, 20 for submitting average requests, and five for complex ones. By measuring the application processes, the analyst parameterizes the behavior of the processes as summarized in Table 14.4. There are various ways of estimating disk service demands. For random data access, as is the case of this example, the service demand could be determined by multiplying the number of I/Os issued by a process by the average disk access time (i.e., average seek time plus the average latency plus the average transfer time, which is a function of the I/O size). However, most modern disk systems have a cache at the controller for caching data recently read or written to the disk [20]. Cache hits are relatively rare for random access, but are higher for sequential access. When estimating service demands from measurement data, all the specific features of the disk architecture are captured by the measuring process. The disk demands reported in Table 14.4 reflect this measurement data. The LAN is assumed to be a 10-Mbps Ethernet with a slot duration S of 51.2 msec. The average network service demands per transaction class can be computed as the average number of packets x the average packet length divided by the network bandwidth. This gives values 0.16, 0.41, and 1.27 msec for trivial, average, and complex requests, respectively. The network is modeled as a load-dependent device with a class independent service rate function m(n). To use Eq. (14.3.11) for the Ethernet throughput, the average packet length over all classes is computed from the data in Table 14.4 as follows:

The average number of packets per request, P_req, is given by

Table 14.4. Parameterization Data for the Example of Multiclass Load-Dependent MVA

Req. Type	% of Req.	Think Time sec	Avg. No. Packets/Req.	Avg. Packet Length per Req. (bits)	Disk Demand (msec)	Processor Demand (msec)
Trivial	16.4	0.1	2	800	8	1.6
Average	63.9	0.2	3	1382	14	10.1
Complex	19.3	0.4	9	1410	25	16.8

The service rate in requests/sec for the network is equal to its service rate in packets/sec divided by the average number of packets per transaction. The algorithm of Fig 14.7 yields the performance metrics shown in Table 14.5. In this particular example, convergence is achieved after 16 iterations for a tolerance of 10 ⁴.

Table 14.5. Metrics for Example of Multiclass Load-Dependent MVA

Req. Type	Residence Time (sec)			Response Time (sec)	Throughput (req/s)
	Network	Processor	Disk
Trivial	0.00017	0.0034	0.164	0.167	37.34
Average	0.00044	0.0213	0.288	0.310	39.23
Complex	0.00134	0.0355	0.515	0.552	5.25

Figure 14.7. Approximate multiclass MVA algorithm with LD devices.

Figure 14.8. Performance model of a two-tier client-server architecture.