11.3 The MM1 Queue

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:

• The cumulative distribution function (CDF) of an exponentially distributed random variable X with parameter l is given by

  Equation 11.3.7

  

  
  

• The average and the standard deviation of an exponentially distributed random variable with parameter l are both equal to 1/l. Therefore, the coefficient of variation of an exponentially distributed random variable is equal to 1. The exponential is the only continuous distribution with coefficient of variation equal to 1.

• If interarrival times are exponentially distributed with parameter l, then the probability of observing exactly k arrivals in a given time period from time 0 to time t is:

  Equation 11.3.8

  

  
  

  This is a Poisson distribution with parameter l. A Poisson distribution arises when arrivals come from a large number of independent sources.

• Poisson arrivals imply that interarrival times are exponentially distributed.

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 l_i = l and m_i = m = 1/E[S] the probability p_k that there are k customers in the queuing station can be computed as

Equation 11.3.9

where r = lE[S]. See Exercise 11.2. The following results for M/M/1 can be obtained from the probabilities p_k and from Little's Law:

Equation 11.3.10

Equation 11.3.11

Equation 11.3.12

Equation 11.3.13

Example 11.2.

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.