M/G/1 results cannot be used when the interarrival time distribution is not exponentially distributed. However, the approximation
where Ca is the coefficient of variation of the interarrival time is useful .
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.
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 is the inverse of the average arrival rate. Thus, = 1/80 = 0.0125 sec. The coefficient of variation of the interarrival time is Ca = sa = 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:
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
Figure 11.4. A single waiting line with multiple servers.
The exact solution for G/G/c is not known but its average waiting time can be approximated by
This equation is Erlang's C formula . 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
because Ca = 1 and Cs = 1 for this case.
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.