Previous Table of Contents Next


1.  Compute the mean and standard deviations of the variables:

Similarly,

462,661,024 - 18 × 4889.42
s2xr =
= 1379.5
17
2.  Normalize the variables to zero mean and unit standard deviation. The normalized values xs and xr, are given by


The normalized values are shown in the fourth and fifth columns of Table 6.4.
3.  Compute the correlation among the variables:

4.  Prepare the correlation matrix:

5.  Compute the eigenvalues of the correlation matrix. This is done by solving the characteristic equation. Using I to denote an identity matrix,


or

(λ - 1)2 - 0.9162 = 0

  
The eigenvalues are 1.916 and 0.084.
6.  Compute the eigenvectors of the correlation matrix. The eigenvector q1 corresponding to λ1 = 1.916 is defined by the following relationship:

Cq1 = λ1q1

  
or


or

q11 = q21

  
Restricting the length of the eigenvector to 1, the following vector is the first eigenvector:


Similarly, the second eigenvector is

7.  Obtain principal factors by multiplying the eigenvectors by the normalized vectors:

8.  Compute the values of the principal factors. These are shown in the last two columns of Table 6.4.
9.  Compute the sum and sum of squares of the principal factors. The sum must be zero. The sum of squares give the percentage of variation explained. In this case, the sums of squares are 32.565 and 1.435. Thus, the first factor explains 32.565/(32.565 + 1.435), or 95.7%, of the variation. The second factor explains only 4.3% of the variation and can thus be ignored.
10.  Plot the values of principal factors. The results are shown in Figure 6.3. Notice that most of the variation is along the first principal factor. Ile variation along the second factor is negligible.
The value of the factor y1 can be used to classify the stations as low-, medium-, or high-load stations. Alternately, the pair (y1 y2) can be used to classify the stations, but the gain over using y1 alone would be small.


FIGURE 6.3  Packets sent and received data plotted along the principal-component axes.

6.7 MARKOV MODELS

Sometimes, it is important to have not only the number of service requests of each type but also their order. The next request is generally determined by the last few requests. If it is assumed that the next request depends only on the last request, then the requests follow a Markov model. Actually, the term is used in a more general sense of system states rather than for user requests. That is, if the next system state depends only on the current system state, the system follows a Markov model. Such models are commonly used in queueing analysis and are described in detail in Part VI. For now, it is sufficient to understand that such models can be described by a transition matrix, which gives the probabilities of the next state given the current state. For example, the transition probability matrix for a job’s transition between the CPU, disk, and terminal is shown in Table 6.5. The corresponding state transition diagram is shown in Figure 6.4. After each visit to the CPU, the probability that the job will move to the disk is 0.3, the probability of it going to the terminal is 0.1, and so on.

Transition matrices are used not only for resource transitions but also for application transitions. For example, if the users in a software development environment run editors, compilers, linkers, and applications, a transition probability matrix can be used to characterize the probability of a user running software of type j after running the software of type i.

TABLE 6.5 Transition Probability Matrix

From/To CPU Disk Terminal

CPU 0.6 0.3 0.1
Disk 0.9 0 0.1
Terminal 1 0 0


FIGURE 6.4  State transition diagram for a Markov model.

Transition matrices have also been used to specify page reference locality. In this case, the matrix entries specify the probability of the program referencing page (or module) i after referencing page (or module) j.

The transition probabilities give a more accurate picture of the order of requests than the frequency of requests. Given the same relative frequency of requests of different types, it is possible to realize the frequency with several different transition matrices. Each matrix may result in a different performance of the system. Therefore, in some cases it is important to measure the transition probabilities directly on the real system and to represent them in the workload model.

Example 6.2 Traffic monitoring on a computer network showed that most of the packets were of two sizes—small and large. The small packets constituted 80% of the traffic. A number of different transition probability matrices will result in an overall average of 80% of small packets. Two of the possibilities are as follows:
1.  An average of four small packets are followed by an average of one big packet. A sample sequence, using s for small and b for big, is ssssbssssbssss. In this sequence, three of the four small packets are followed by another small packet. Also, every big packet is followed by a small packet. The corresponding transition probability matrix is
Next Packet
Current
Packet Small Large

Small 0.75 0.25
Large 1 0


Previous Table of Contents Next

Copyright © John Wiley & Sons, Inc.