M/M/1 queue

An M/M/1 queueing node

In queueing theory, a discipline within the mathematical theory of probability, an M/M/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process and job service times have an exponential distribution. The model name is written in Kendall's notation. The model is the most elementary of queueing models^[1] and an attractive object of study as closed-form expressions can be obtained for many metrics of interest in this model. An extension of this model with more than one server is the M/M/c queue.

Model definition

An M/M/1 queue is a stochastic process whose state space is the set {0,1,2,3,...} where the value corresponds to the number of customers in the system, including any currently in service.

Arrivals occur at rate λ according to a Poisson process and 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.
A single server serves customers one at a time from the front of the queue, according to a first-come, first-served discipline. 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 continuous time Markov chain with transition rate matrix

Q={\begin{pmatrix}-\lambda &\lambda \\\mu &-(\mu +\lambda )&\lambda \\&\mu &-(\mu +\lambda )&\lambda \\&&\mu &-(\mu +\lambda )&\lambda &\\&&&&\ddots \end{pmatrix}}

on the state space {0,1,2,3,...}. This is the same continuous time Markov chain as in a birth–death process. The state space diagram for this chain is as below.

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 p_k(t) for the probability of being in state k at time t. Then^[2]

p_{k}(t)=e^{-(\lambda +\mu )t}\left[\rho ^{\frac {k-i}{2}}I_{k-i}(at)+\rho ^{\frac {k-i-1}{2}}I_{k+i+1}(at)+(1-\rho )\rho ^{k}\sum _{j=k+i+2}^{\infty }\rho ^{-j/2}I_{j}(at)\right]

where $\rho =\lambda /\mu$ , $a=2{\sqrt {\lambda \mu }}$ and I_k is the modified Bessel function of the first kind. Moments for the transient solution can be expressed as the sum of two monotone functions.^[3]

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.

Number of customers in the system

The probability that the stationary process is in state i (contains i customers, including those in service) is^[4]^:172–173

\pi _{i}=(1-\rho )\rho ^{i}.\,

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 − ρ)². This result holds for any work conserving service regime, such as processor sharing.^[5]

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^[6]^[7]^[8]^[9]

f(t)={\begin{cases}{\frac {1}{t{\sqrt {\rho }}}}e^{-(\lambda +\mu )t}I_{1}(2t{\sqrt {\lambda \mu }})&t>0\\0&{\text{otherwise}}\end{cases}}

where I₁ is a modified Bessel function of the first kind,^[10] obtained by using Laplace transforms and inverting the solution.^[11]

The Laplace transform of the M/M/1 busy period is given by^[12]^[13]^[14]^:215

\mathbb {E} (e^{-\theta F})={\frac {1}{2\lambda }}(\lambda +\mu +\theta -{\sqrt {(\lambda +\mu +\theta )^{2}-4\lambda \mu }})

which gives the moments of the busy period, in particular the mean is 1/(μ − λ) and variance is given by

{\frac {1+{\frac {\lambda }{\mu }}}{\mu ^{2}(1-{\frac {\lambda }{\mu }})^{3}}}.

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 transform (μ − λ)/(s + μ − λ)^[15] and therefore probability density function^[16]

f(t)={\begin{cases}(\mu -\lambda )e^{-(\mu -\lambda )t}&t>0\\0&{\text{otherwise.}}\end{cases}}

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.^[17] 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.^[17]

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,^[17] for which an integral representation is known.^[18] The waiting time distribution (response time less service time) for a customer requiring x amount of service has transform^[4]^:356

W^{\ast }(s|x)={\frac {(1-\rho )(1-\rho r^{2})e^{-[\lambda (1-r)+s]x}}{(1-\rho r^{2})-\rho (1-r)^{2}e^{-(\mu /r-\lambda r)x}}}

where r is the smaller root of the equation

\lambda r^{2}-(\lambda +\mu +s)r+\mu =0.

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.^[5]

Diffusion approximation

When the utilisation ρ is close to one 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.^[19]

References

↑ Sturgul, John R. (2000). Mine design: examples using simulation. SME. p. vi. ISBN 0-87335-181-9.
↑ Kleinrock, Leonard (1975). Queueing Systems Volume 1: Theory. p. 77. ISBN 0471491101.
↑ Abate, J.; Whitt, W. (1987). "Transient behavior of the M/M/l queue: Starting at the origin" (PDF). Queueing Systems 2: 41. doi:10.1007/BF01182933.
1 2 Harrison, Peter; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison–Wesley.
1 2 Guillemin, F.; Boyer, J. (2001). "Analysis of the M/M/1 Queue with Processor Sharing via Spectral Theory" (PDF). Queueing Systems 39 (4): 377. doi:10.1023/A:1013913827667.
↑ Abate, J.; Whitt, W. (1988). "Simple spectral representations for the M/M/1 queue" (PDF). Queueing Systems 3 (4): 321. doi:10.1007/BF01157854.
↑ Keilson, J.; Kooharian, A. (1960). "On Time Dependent Queuing Processes". The Annals of Mathematical Statistics 31 (1): 104–112. doi:10.1214/aoms/1177705991. JSTOR 2237497.
↑ Karlin, Samuel; McGregor, James (1958). "Many server queueing processes with Poisson input and exponential service times". Pacific J. Math. 8 (1): 87–118. doi:10.2140/pjm.1958.8.87. MR 0097132.
↑ Gross, Donald; Shortle, John F.; Thompson, James M.; Harris, Carl M. "2.12 Busy-Period Analysis". Fundamentals of Queueing Theory. Wiley. ISBN 1118211642.
↑ Adan, Ivo. "Course QUE: Queueing Theory, Fall 2003: The M/M/1 system" (PDF). Retrieved 2012-08-06.
↑ Stewart, William J. (2009). Probability, Markov chains, queues, and simulation: the mathematical basis of performance modeling. Princeton University Press. p. 530. ISBN 0-691-14062-6.
↑ Asmussen, S. R. (2003). "Queueing Theory at the Markovian Level". Applied Probability and Queues. Stochastic Modelling and Applied Probability 51. pp. 60–31. doi:10.1007/0-387-21525-5_3. ISBN 978-0-387-00211-8.
↑ Adan, I.; Resing, J. (1996). "Simple analysis of a fluid queue driven by an M/M/1 queue". Queueing Systems 22: 171. doi:10.1007/BF01159399.
↑ Kleinrock, Leonard (1975). Queueing Systems: Theory, Volume 1. Wiley. ISBN 0471491101.
↑ Harrison, P. G. (1993). "Response time distributions in queueing network models". Performance Evaluation of Computer and Communication Systems. Lecture Notes in Computer Science 729. pp. 147–164. doi:10.1007/BFb0013852. ISBN 3-540-57297-X.
↑ Stewart, William J. (2009). Probability, Markov chains, queues, and simulation: the mathematical basis of performance modeling. Princeton University Press. p. 409. ISBN 0-691-14062-6.
1 2 3 Coffman, E. G.; Muntz, R. R.; Trotter, H. (1970). "Waiting Time Distributions for Processor-Sharing Systems". Journal of the ACM 17: 123. doi:10.1145/321556.321568.
↑ Morrison, J. A. (1985). "Response-Time Distribution for a Processor-Sharing System". SIAM Journal on Applied Mathematics 45 (1): 152–167. doi:10.1137/0145007. JSTOR 2101088.
↑ Kingman, J. F. C.; Atiyah (October 1961). "The single server queue in heavy traffic". Mathematical Proceedings of the Cambridge Philosophical Society 57 (4): 902. doi:10.1017/S0305004100036094. JSTOR 2984229.

Queueing theory

Single queueing nodes	D/M/1 queue M/D/1 queue M/D/c queue M/M/1 queue Burke's theorem M/M/c queue M/M/∞ queue M/G/1 queue Pollaczek–Khinchine formula Matrix analytic method M/G/k queue G/M/1 queue G/G/1 queue Kingman's formula Lindley equation Fork–join queue Bulk queue

Arrival processes	Poisson process Markovian arrival process Rational arrival process

Queueing networks	Jackson network Traffic equations Gordon–Newell theorem Mean value analysis Buzen's algorithm Kelly network G-network BCMP network

Service policies	FIFO LIFO Processor sharing Round-robin Shortest job first Shortest remaining time

Key concepts	Continuous-time Markov chain Kendall's notation Little's law Product-form solution Balance equation Quasireversibility Flow-equivalent server method Arrival theorem Decomposition method Beneš method

Limit theorems	Fluid limit Mean field theory Heavy traffic approximation Reflected Brownian motion

Extensions	Fluid queue Layered queueing network Polling system Adversarial queueing network Loss network Retrial queue

Information systems	Data buffer Erlang (unit) Erlang distribution Flow control (data) Message queue Network congestion Network scheduler Pipeline (software) Quality of service Scheduling (computing) Teletraffic engineering

Category

Stochastic processes

Discrete time	Bernoulli process Branching process Chinese restaurant process Galton–Watson process Independent and identically distributed random variables Markov chain Moran process Random walk Loop-erased Self-avoiding

Continuous time	Bessel process Birth–death process Brownian motion Bridge Excursion Fractional Geometric Meander Cauchy process Contact process Continuous-time random walk Cox process Diffusion process Empirical process Feller process Fleming–Viot process Gamma process Hunt process Interacting particle systems Itô diffusion Itô process Jump diffusion Jump process Lévy process Local time Markov additive process McKean–Vlasov process Ornstein–Uhlenbeck process Poisson process Compound Non-homogeneous Point process Schramm–Loewner evolution Semimartingale Sigma-martingale Stable process Superprocess Telegraph process Variance gamma process Wiener process Wiener sausage

Both	Branching process Gaussian process Hidden Markov model (HMM) Markov process Martingale Differences Local Sub- Super- Random dynamical system Regenerative process Renewal process White noise

Fields and other	Dirichlet process Gaussian random field Gibbs measure Hopfield model Ising model Potts model Boolean network Markov random field Percolation Pitman–Yor process Point process Cox Poisson Random field Random graph

Time series models	Autoregressive conditional heteroskedasticity (ARCH) model Autoregressive integrated moving average (ARIMA) model Autoregressive (AR) model Autoregressive–moving-average (ARMA) model Generalized autoregressive conditional heteroskedasticity (GARCH) model Moving-average (MA) model

Financial models	Black–Derman–Toy Black–Karasinski Black–Scholes Chen Constant elasticity of variance (CEV) Cox–Ingersoll–Ross (CIR) Garman–Kohlhagen Heath–Jarrow–Morton (HJM) Heston Ho–Lee Hull–White LIBOR market Rendleman–Bartter SABR volatility Vašíček Wilkie

Actuarial models	Bühlmann Cramér–Lundberg Risk process Sparre–Anderson

Queueing models	Bulk Fluid Generalized queueing network M/G/1 M/M/1 M/M/c

Properties	Càdlàg paths Continuous Continuous paths Ergodic Exchangeable Feller-continuous Gauss–Markov Markov Mixing Piecewise deterministic Predictable Progressively measurable Self-similar Stationary Time-reversible

Limit theorems	Central limit theorem Donsker's theorem Doob's martingale convergence theorems Ergodic theorem Fisher–Tippett–Gnedenko theorem Large deviation principle Law of large numbers (weak/strong) Law of the iterated logarithm Maximal ergodic theorem Sanov's theorem

Inequalities	Burkholder–Davis–Gundy Doob's martingale Kunita–Watanabe

Tools	Cameron–Martin formula Convergence of random variables Doléans-Dade exponential Doob decomposition theorem Doob–Meyer decomposition theorem Doob's optional stopping theorem Dynkin's formula Feynman–Kac formula Filtration Girsanov theorem Infinitesimal generator Itô integral Itô's lemma Kolmogorov continuity theorem Kolmogorov extension theorem Lévy–Prokhorov metric Malliavin calculus Martingale representation theorem Optional stopping theorem Prokhorov's theorem Quadratic variation Reflection principle Skorokhod integral Skorokhod's representation theorem Skorokhod space Snell envelope Stochastic differential equation Tanaka Stopping time Stratonovich integral Uniform integrability Usual hypotheses Wiener space Classical Abstract

Disciplines	Actuarial mathematics Econometrics Ergodic theory Extreme value theory (EVT) Large deviations theory Mathematical finance Mathematical statistics Probability theory Queueing theory Renewal theory Ruin theory Statistics Stochastic analysis Time series analysis Machine learning

List of topics Category

This article is issued from Wikipedia - version of the Sunday, December 13, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.