Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 38 Β· Getting Started

Kendall Notation: Naming Queue Models

Read and write Kendall notation such as M/M/1, M/D/1 and G/G/c. Learn what each letter means and how variability is measured.

Queueing theorists use a short code to name a model. Instead of a paragraph, you write M/M/1 or M/G/c/K. The system is called Kendall notation, after the statistician David Kendall. Once you can read it, textbooks, papers and software documentation become much easier to follow.

The pattern A/S/c/K/N/D

The full notation has up to six slots separated by slashes:

Slot Meaning Common symbols
A Interarrival time distribution M, D, Ek, G
S Service time distribution M, D, Ek, G
c Number of parallel servers 1, 2, 3, ..., ∞
K Maximum number in the system omitted means ∞
N Size of the customer population omitted means ∞
D Service discipline omitted means FIFO

The first three slots are always written. The last three appear only when they differ from the defaults. So M/M/1 means exponential interarrival times, exponential service, one server, unlimited room, infinite population, FIFO.

The distribution letters

  • M stands for Markovian (memoryless). Interarrival times are exponential, which means arrivals form a Poisson process. Service times are exponential.
  • D stands for deterministic: a constant time, such as exactly 30 seconds.
  • Ek is an Erlang-k distribution, the sum of k independent exponential phases. It is more regular than exponential.
  • G stands for general: any distribution at all. A formula for G holds for every distribution that fits the other conditions.
  • GI means general independent interarrival times; some books write GI/G/1 to be precise.

The letter M is used for both arrivals and service, but it always means "exponential times", which is the memoryless distribution.

Examples

Notation Reading
M/M/1 Poisson arrivals, exponential service, one server
M/M/3 Same, but three servers sharing one line
M/D/1 Poisson arrivals, constant service time, one server
M/G/1 Poisson arrivals, any service distribution, one server
M/M/1/10 M/M/1 where at most 10 customers fit in the system
M/M/∞ Infinite servers (no waiting at all)
M/M/1/∞/∞/LIFO M/M/1 served last in, first out

A parser in code

The following TryIt turns a Kendall string into English. It is a tiny stand-in for the reasoning you do when you read a model name.

Python Kendall notation reader

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Variability: why the letters matter

The letters mainly capture how variable the times are. A common measure is the squared coefficient of variation (SCV): SCV = variance / meanΒ². Higher SCV means more erratic times, which usually means longer queues.

Distribution SCV
Deterministic (D) 0
Erlang-k (Ek) 1/k
Exponential (M) 1
Hyperexponential (mixture of speeds) greater than 1

Let us estimate the SCV from samples to see the ordering.

Python Measuring variability

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The hyperexponential has mean 0.9 Γ— 0.5 + 0.1 Γ— 5.5 = 1.0, but a much larger SCV. When you meet G in later chapters, the SCV is the quantity that appears in the formulas.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. What does M/M/2 mean?

    The third slot is the number of servers, and the two M's are exponential interarrival and service times.
  2. 2. What does the symbol D mean in M/D/1?

    In the service slot, D means the service time is a fixed constant.
  3. 3. Which has the smallest squared coefficient of variation?

    A constant time has zero variance, so its SCV is 0. Erlang-2 has 1/2 and exponential has 1.
  4. 4. If K and N are left out of the notation, what is assumed?

    Omitted slots take defaults: unlimited room, infinite population, FIFO.

Summary

  • Kendall notation A/S/c/K/N/D names a queueing model; the last three slots default to ∞, ∞ and FIFO.
  • M is exponential, D is constant, Ek is Erlang-k, G is general.
  • SCV measures variability: 0 for D, 1/k for Ek, 1 for M.
  • More variability usually means longer waits.

Next: Poisson Arrivals