11.7 Approximation Results


M/G/1 results cannot be used when the interarrival time distribution is not exponentially distributed. However, the approximation

Equation 11.7.25

graphics/11equ725.gif


where Ca is the coefficient of variation of the interarrival time is useful [2].

This approximation is exact for M/G/1. To verify this, note that in the M/G/1 case, Ca = 1 since interarrival times are exponentially distributed. Thus, the first term of the equation becomes one and the second term is the M/G/1 result of Eq. (11.4.14). The approximation of Eq. (11.7.25) is good for G/M/1 queues. It is "fair" for G/G/1 queues and improves as r increases.

Example 11.8.

Measurements taken from a storage device used by a database server indicate that I/O requests arrive at an average rate of 80 requests/sec. The standard deviation of the interarrival time is measured as 0.025 sec. The average I/O time is measured as 0.009 sec with a standard deviation of 0.003 sec. What is the approximate waiting time of an I/O request at the storage device?

The average interarrival time graphics/306fig01.gif is the inverse of the average arrival rate. Thus, graphics/306fig01.gif = 1/80 = 0.0125 sec. The coefficient of variation of the interarrival time is Ca = sagraphics/306fig01.gif = 0.025/0.0125 = 2. The utilization of the storage device is r = l x E[S] = 80 x 0.009 = 0.72. The coefficient of variation of the service time is Cs = ss/E[S] = 0.003/0.009 = 1/3. Equation (11.7.25) can be used to approximate the average waiting time at the storage device:

Equation 11.7.26

graphics/11equ726.gif


If Ca were equal to one, the average waiting time would be 0.0129 sec according to the M/G/1 result (i.e., Eq. (11.4.14)). This example further demonstrates the rule of thumb that increased variability (as indicated by the coefficient of variation) hurts performance).

Consider now the queue of Fig. 11.4 which has c identical servers and a single waiting line. This is known as the G/G/c queue and its utilization is

Equation 11.7.27

graphics/11equ727.gif


Figure 11.4. A single waiting line with multiple servers.

graphics/11fig04.gif

The exact solution for G/G/c is not known but its average waiting time can be approximated by

Equation 11.7.28

graphics/11equ728.gif


where

Equation 11.7.29

graphics/11equ729.gif


This equation is Erlang's C formula [2]. The error in the approximation of Eq. (11.7.28) increases with Ca and with Cs. In the case of an M/M/c system (i.e., exponentially distributed interarrival times and exponentially distributed service times), the approximation of Eq. (11.7.28) is an exact solution and becomes

Equation 11.7.30

graphics/11equ730.gif


because Ca = 1 and Cs = 1 for this case.

Example 11.9.

A computer system receives requests that require an average of 2 seconds of service time. The coefficient of variation of the service time is 0.5 and the coefficient of variation of the interarrival time is 0.8. What is the minimum number of processors that should be used to keep the average response time below 2.5 seconds when the utilization of the system is 80%.

The question can be answered by using the G/G/c approximation of Eq. (11.7.28). The required parameters are: r = 0.80, Ca = 0.8, Cs = 0.5, and E[S] = 2 sec. The number of processors, c, is varied from 1 to 8. The results are presented in Table 11.3, which shows that at least 5 processors are needed.

Table 11.3. Response Time (sec) vs. No. Processors

No. Processors

Avg. Response Time (sec)

1

5.56

2

3.58

3

2.96

4

2.66

5

2.49

6

2.38

7

2.31

8

2.25



Performance by Design. Computer Capacity Planning by Example
Performance by Design: Computer Capacity Planning By Example
ISBN: 0130906735
EAN: 2147483647
Year: 2003
Pages: 166

Similar book on Amazon

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net