Markovian Queues

A Markovian queue has Poisson arrivals and exponential service times, making the number of customers a continuous-time Markov chain whose equilibrium can be solved explicitly.

Definition

A Markovian queue is a service system in which customers arrive according to a Poisson process and require independent exponential service times, so the number in the system evolves as a birth-death continuous-time Markov chain with explicit steady-state and waiting-time distributions.

Scope

This topic covers Kendall's notation for queueing systems, the single-server M/M/1 queue and its geometric stationary distribution, multi-server M/M/c and loss systems, the Erlang B and C formulas, stability and the traffic intensity, and the derivation of mean queue length, waiting time, and busy-period quantities from the underlying birth-death process.

Core questions

• How does the M/M/1 queue arise as a birth-death process and what is its stationary distribution?
• What condition on the traffic intensity ensures the queue is stable?
• How are mean queue length and waiting time obtained, and how is Little's law applied?
• How do multiple servers and finite capacity change the Erlang formulas?

Key theories

M/M/1 stationary distribution and stability

The number in an M/M/1 queue has a geometric stationary distribution with parameter equal to the traffic intensity, the ratio of arrival to service rate, and the queue is stable precisely when this ratio is less than one.

Erlang loss and delay formulas

For multi-server systems the Erlang B formula gives the blocking probability in a loss system and the Erlang C formula gives the probability of waiting in a delay system, both derived from the birth-death balance equations and central to capacity planning.

Clinical relevance

Markovian queues are the foundational models for sizing telephone trunk groups, call-centre staffing, server farms, and service counters, where the Erlang formulas translate offered load and target service levels into the number of servers required.

History

Erlang derived the loss and delay formulas for telephone traffic between 1909 and 1917, Kendall introduced the systematic arrival/service/server notation and the embedded-chain analysis in 1953, and Kleinrock's 1970s treatise applied the theory to computer and communication networks.

Key figures

• Agner Krarup Erlang
• David Kendall
• Leonard Kleinrock

Seminal works

• kleinrock1975

Frequently asked questions

What does M/M/1 mean?

In Kendall's notation the first M denotes Markovian (Poisson) arrivals, the second M denotes exponential service times, and the 1 denotes a single server.

When is a Markovian queue stable?

When the traffic intensity, the arrival rate divided by the total service rate, is less than one; otherwise the queue grows without bound and no stationary distribution exists.