Category list

2.13 QN Models

A more formal and complete definition of a QN model is given here. A QN is a collection of K interconnected queues. A queue includes the waiting line and the resource that provides service to customers. Customers move from one queue to the other until they complete their execution and may be grouped into one or more customer classes. In some cases, customers may be allowed to switch to other classes when they move between queues.

A QN can be open, closed, or mixed depending on its customer classes: open if all classes are open, closed if all classes are closed, and mixed if some classes are open and some are closed. The solution of open , closed, and mixed QNs under certain assumptions was first presented in [1] and is discussed in more detail in Part II.

The input parameters to a QN model are divided into two groups:

Workload intensity. These parameters provide an indication of the load of the system. It can be measured in terms of arrival rates for open classes or in terms of customer population for closed classes.
Service demands. These parameters specify the total average service time provided by a specific resource to a given class of requests . Service demands do not generally depend on the load on the system. In some situations, however, there may be a dependence. An example is the service demand on the paging disk, which is a function of the page fault rate. In a poorly tuned system, the number of page faults may increase with the number of jobs.

Workload classes can also be characterized as transaction, batch , and interactive . A transaction workload is modeled as an open class with a workload intensity represented by an arrival rate (see the example of Section 2.3). A batch workload is modeled as a closed class whose workload intensity is represented by the number of customers of that class in the QN (see the example of a report generation class in Section 2.5). An interactive workload is a closed class used to model situations where requests are submitted by a fixed number, M , of terminals or client machines. The workload intensity in this case is represented by the number of terminals M and by the average think time, Z . The think time is defined as the time elapsed since a reply to a request is received until the next request is submitted by the same terminal or client (see the client/server example of Section 2.7). Table 2.3 summarizes the parameters that must be specified for each of these three types of workloads.

Table 2.3. Parameters per Class Type

Parameter	Type of Class
Parameter	tch	Interactive	Transaction
Service demands
Priority
Customer population
Average arrival rate
Number of terminals
Think time

A queue in a QN is specified by the type of resource (i.e., LI, LD, or D) and the queuing discipline (e.g., FCFS, priority, RR, PS). The following basic notation is used throughout the rest of the book. Additional notation will be introduced as needed.

K : number of queues in a QN.
R : number of customer classes of a QN.
: vector of arrival rates for an open multiclass QN; l _r ( r = 1, ···, R ) is the average arrival rate of customers of class r .
: customer population vector for a closed multiclass QN; N _r ( r = 1, ···, R ) is the number of customers of class r .
D _i,r : service demand of class r ( r = 1, ···, R ) customers at queue i ( i = 1, ···, K ).
Prior ( r ): priority of class r . Priorities are numbered from 1 to P with the highest priority numbered 1.
X _0,

r : throughput of class r customers.
R _0,

r : average response time of class r customers

QNs may also exhibit characteristics such as blocking, SRP, contention for software resources, and class-switching.

Example 2.1.

Consider the example of Section 2.4 and the data in Table 2.1. Assume that the total arrival rate is 1.5 tps and that each I/O takes an average of 0.01 seconds. Thus, the service demand at the disk for each class is equal to the average number of I/Os multiplied by the average time per I/O. For example, the service demand at the disk for trivial transactions is 0.055 (= 5.5x0.01) seconds. A complete description of the QN for the example of Section 2.4 is given in Table 2.4. By solving this QN using the methods and tools presented in later chapters of this book, the following response times are obtained: R _0,1 = 0.23 sec, R _0,2 = 1.10 sec, and R _0,3 = 5.08 sec.

Table 2.4. QN Specification for Example 2.1

K = 2; R = 3 Open QN			Queue type/Sched. Discipline
K = 2; R = 3 Open QN			LI/PS	LI/FCFS
Class (r)	Type	l _r (tps)	D _CPU, r (sec)	D _disk, r (sec)
1 (Trivial)	open	0.675	0.04	0.055
2 (Medium)	open	0.375	0.18	0.289
3 (Complex)	open	0.450	1.20	0.850

Example 2.2.

Consider now the QN shown in Fig. 2.3. Assume that two batch applications execute concurrently to generate management reports at night when no online activity is allowed. One of the applications generates sales reports and the other generates marketing reports . Both are multithreaded processes. The first application runs as a collection of five threads and the second as a collection of ten threads. Each thread generates one report. A complete description of the QN for the example of Section 2.4 is given in Table 2.5. By solving this QN using the methods and tools presented in later chapters of this book, one obtains the following throughputs: X _0,1 = 23.2 reports/ hour and X _0,2 = 24.6 reports/hour.