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

    graphics/11equ37.gif


  • 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

    graphics/11equ38.gif


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

Equation 11.3.9

graphics/11equ39.gif


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:

Equation 11.3.10

graphics/11equ310.gif


Equation 11.3.11

graphics/11equ311.gif


Equation 11.3.12

graphics/11equ312.gif


Equation 11.3.13

graphics/11equ313.gif


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.



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