11.8 Concluding Remarks

Single queue systems provide useful information when estimating waiting times due to contention for shared resources. The M/G/1 queue is one of the most studied queuing systems. A large number of results are available, including vacationing servers and different priority scheduling schemes. Approximate results for G/G/1 and G/G/c are also given. The following chapters consider networks of queues, where individual queues are interconnected .

11.9 Exercises

Show that in a G/G/1 queue, the average number of customers at the server is equal to the utilization of the server.
Derive Eqs. (11.3.9) and (11.3.11) using the Generalized Birth-Death theorem.
Derive the average waiting time for M/M/1 from Eq. (11.7.30).
Consider two Web clusters, A and B. Cluster A has n servers and cluster B has m (m > n) servers. Requests arrive at each cluster at a rate of l requests/sec. A load balancer in front of each cluster evenly distributes the requests to each server in the cluster. The average service time of a request in cluster A is x seconds and the average service time of a request in cluster B is k x x where k > 1. The service time of a request in either cluster has an arbitrary distribution. Derive an expression for the value of m so that the average response of a request in cluster A is the same as in cluster B.
A computer system receives requests from a Poisson process at a rate of 10 requests/sec. Assume that 30% of the requests are of type a and the remaining are of type b . The average service times and the coefficients of variation of the service times for these two types of requests are: E [ S _a ] = 0.1 seconds, , E [ S _b ] = 0.08 seconds, and . Compute the average response time for each type of request under each of the following scenarios: 1) requests of type a and b have equal priorities, 2) requests of type a have non-preemptive priority over requests of type b , 3) requests of type b have non-preemptive priority over requests of type a , 4) requests of type a have preemptive priority over requests of type b , and 5) requests of type b have preemptive priority over requests of type a .
Consider the class 3 requests in Example 11.7 when the server uses a preemptive resume scheduling policy (see Section 11.6.2). It is stated the performance (i.e., the waiting time) of the highest priority requests (i.e., class 3 in this case) is not affected by the lower priority requests. Prove this statement by computing the waiting time of class 3 requests using vanilla M/G/1 results (i.e., from Section 11.4). Compare the result to the value computed in Section 11.6.2.

Bibliography

[1] D. Gross and C. M. Harris, Fundamentals of Queueing Theory , 3rd ed., Wiley-Interscience, 1998.

[2] L. Kleinrock, Queueing Systems, Vol I: Theory , John Wiley & Sons, New York, 1975.

[3] L. Kleinrock, Queueing Systems, Vol II: Computer Applications , John Wiley & Sons, New York, 1976.

[4] R. Nelson, Probability, Stochastic Processes, and Queuing Theory: The Mathematics of Computer Performance Modelling , Springer Verlag, New York, 1995.