11.3 The M/M/1 Queue
The most well-studied special case of the G/G/1 queue occurs when the interarrival times are exponentially distributed and the service times are also exponentially distributed. This queue is referred to as an M/M/1 queue. The "M" stands for Markovian or memoryless. The memoryless property applied to the arrival process means that if the distribution of the time between consecutive arrivals is exponentially distributed with parameter l, then the distribution of the residual time until the next arrival is also exponentially distributed with the same parameter l. Applied to the service time process, the memoryless property indicates that the distribution of the residual service time is the same as that of the service time. The exponential distribution is the only continuous distribution with the memoryless property. Additional important properties of the exponential distribution are:
Because in the M/M/1 queue both the arrival and service processes are Markovian, a simple Markov model (see Chapter 10) can be constructed where the state k is the number of customers in the queuing station. Using the Generalized Birth-Death theorem (see Chapter 10) with li = l and mi = m = 1/E[S] the probability pk that there are k customers in the queuing station can be computed as
where r = lE[S]. See Exercise 11.2. The following results for M/M/1 can be obtained from the probabilities pk and from Little's Law:
A file server receives requests from a Poisson process at a rate of 30 requests/sec. Measurement data indicate that the coefficient of variation of the service time of a request at the file server is very close to 1 and that the average service time of a request is 15 msec. What is the average response time of a request at the file server? What would be the average response time if the arrival rate of requests were to double?
Because the coefficient of variation of the service time is equal to 1, the service time is exponentially distributed. Thus, the M/M/1 results can be used to answer the question. The utilization of the file server is r = lE[S] = 30 x 0.015 = 0.45. The average response time is T = E[S]/(1 r) = 0.015/(1 0.45) = 0.027 seconds. If the arrival rate increases to 60 requests/sec, the utilization becomes r = 60 x 0.015 = 0.90 and the average response time increases to T = 0.015/(1 0.90) = 0.15 seconds. Note that a two-fold increase in the arrival rate produces an increase in the average response time by a factor of 5.6.