M/M/1 queue
In
Model definition
An M/M/1 queue is a stochastic process whose
- Arrivals occur at rate λ according to a Poisson processand move the process from state i to i + 1.
- Service times have an exponential distribution with rate parameter μ in the M/M/1 queue, where 1/μ is the mean service time.
- All arrival times and services times are (usually) assumed to be independent of one another.[2]
- A single server serves customers one at a time from the front of the queue, according to a first-come, first-serveddiscipline. When the service is complete the customer leaves the queue and the number of customers in the system reduces by one.
- The buffer is of infinite size, so there is no limit on the number of customers it can contain.
The model can be described as a
on the state space {0,1,2,3,...}. This is the same continuous time Markov chain as in a
Stationary analysis
The model is considered stable only if λ < μ. If, on average, arrivals happen faster than service completions the queue will grow indefinitely long and the system will not have a stationary distribution. The stationary distribution is the limiting distribution for large values of t.
Various performance measures can be computed explicitly for the M/M/1 queue. We write ρ = λ/μ for the utilization of the buffer and require ρ < 1 for the queue to be stable. ρ represents the average proportion of time which the server is occupied.
The probability that the stationary process is in state i (contains i customers, including those in service) is[3]: 172–173
Average number of customers in the system
We see that the number of customers in the system is geometrically distributed with parameter 1 − ρ. Thus the average number of customers in the system is ρ/(1 − ρ) and the variance of number of customers in the system is ρ/(1 − ρ)2. This result holds for any work conserving service regime, such as processor sharing.[4]
Busy period of server
The busy period is the time period measured between the instant a customer arrives to an empty system until the instant a customer departs leaving behind an empty system. The busy period has probability density function[5][6][7][8]
where I1 is a
The Laplace transform of the M/M/1 busy period is given by[11][12][13]: 215
which gives the moments of the busy period, in particular the mean is 1/(μ − λ) and variance is given by
Response time
The average response time or sojourn time (total time a customer spends in the system) does not depend on scheduling discipline and can be computed using Little's law as 1/(μ − λ). The average time spent waiting is 1/(μ − λ) − 1/μ = ρ/(μ − λ). The distribution of response times experienced does depend on scheduling discipline.
First-come, first-served discipline
For customers who arrive and find the queue as a stationary process, the response time they experience (the sum of both waiting time and service time) has Laplace transform (μ − λ)/(s + μ − λ)[14] and therefore probability density function[15]
Processor sharing discipline
In an M/M/1-PS queue there is no waiting line and all jobs receive an equal proportion of the service capacity.[16] Suppose the single server serves at rate 16 and there are 4 jobs in the system, each job will experience service at rate 4. The rate at which jobs receive service changes each time a job arrives at or departs from the system.[16]
For customers who arrive to find the queue as a stationary process, the Laplace transform of the distribution of response times experienced by customers was published in 1970,[16] for which an integral representation is known.[17] The waiting time distribution (response time less service time) for a customer requiring x amount of service has transform[3]: 356
where r is the smaller root of the equation
The mean response time for a job arriving and requiring amount x of service can therefore be computed as x μ/(μ − λ). An alternative approach computes the same results using a spectral expansion method.[4]
Transient solution
We can write a probability mass function dependent on t to describe the probability that the M/M/1 queue is in a particular state at a given time. We assume that the queue is initially in state i and write pk(t) for the probability of being in state k at time t. Then[2][18]
where is the initial number of customers in the station at time ,, and is the
Diffusion approximation
When the utilization ρ is close to 1 the process can be approximated by a reflected Brownian motion with drift parameter λ – μ and variance parameter λ + μ. This heavy traffic limit was first introduced by John Kingman.[20]
References
- ISBN 0-87335-181-9.
- ^ ISBN 0471491101.
- ^ a b Harrison, Peter; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison–Wesley.
- ^ doi:10.1023/A:1013913827667. Archived from the original(PDF) on 2006-11-29.
- .
- JSTOR 2237497.
- MR 0097132.
- ISBN 1118211642.
- ^ Adan, Ivo. "Course QUE: Queueing Theory, Fall 2003: The M/M/1 system" (PDF). Retrieved 2012-08-06.
- ISBN 978-0-691-14062-9.
- ISBN 978-0-387-00211-8.
- .
- ISBN 0471491101.
- ISBN 3-540-57297-X.
- ISBN 978-0-691-14062-9.
- ^ .
- JSTOR 2101088.
- ISBN 978-1-4612-7029-4.
- .
- JSTOR 2984229.