Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 38 · Finite Capacity and Priorities

The M/M/1/K Queue: A Waiting Room With a Limit

Model a single server with a limited waiting room, compute the blocking probability and effective arrival rate, and use Little's Law on the customers who get in.

Real waiting rooms are never infinite. A router has a buffer of a few hundred packets, a clinic has twelve chairs, a phone line holds eight callers. When the system is full, new arrivals are turned away. This lesson studies the simplest such model, the M/M/1/K queue: Poisson arrivals at rate λ, exponential service at rate μ, one server, and a system that holds at most K customers in total (the one in service plus K - 1 waiting).

The big surprise is that a finite queue is always stable. Even when λ is larger than μ, the system cannot grow without bound, because excess customers are lost. The price is not a long wait but a fraction of customers who never get in.

The state probabilities

Let ρ = λ/μ. The number in the system, N, is a birth-death chain on the states 0, 1, ..., K. Balance between neighboring states gives p_n = ρ^n · p_0, and normalizing so the probabilities add to 1 gives:

Text
p_n = (1 - ρ) ρ^n / (1 - ρ^(K+1))     for ρ ≠ 1
p_n = 1 / (K + 1)                      for ρ = 1

Notice that nothing here requires ρ < 1. A heavily overloaded system simply spends most of its time in state K.

Blocking and the effective arrival rate

An arriving customer sees the system full with probability p_K. Because arrivals are Poisson, they see the system in its long-run state (this is the PASTA property: Poisson Arrivals See Time Averages). So the blocking probability is P_block = p_K.

Customers actually admitted arrive at the effective arrival rate:

Text
λ_eff = λ (1 - p_K)

The server's utilization is not ρ any more. The fraction of time it is busy is 1 - p_0, and it also equals λ_eff / μ. Those two expressions must agree, which is a handy check on your arithmetic.

Python Blocking probability of an M/M/1/K queue

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.

Run it and watch the pattern. As K grows, blocking falls quickly, while the mean time in system W creeps up toward the infinite-buffer M/M/1 value 1/(μ - λ) = 1 hour (or whichever time unit you use).

Little's Law with the right rate

Little's Law says L = λ_eff · W. The rate in that formula must be the rate of customers who enter, not the rate who show up. Using λ instead of λ_eff is the most common mistake in finite-capacity problems, and it makes W look too small.

The mean number in the system is L = Σ n p_n. For ρ ≠ 1 it has the closed form:

Text
L = ρ/(1 - ρ) - (K + 1) ρ^(K+1) / (1 - ρ^(K+1))

The mean number waiting is L_q = L - (1 - p_0), since 1 - p_0 is the mean number in service.

Overload is fine, but costly

Try λ > μ. With λ = 6 and μ = 5, ρ = 1.2. In an infinite-buffer queue this would blow up. With K = 10 it settles into a steady state where the server is almost always busy and roughly 1 - μ/λ of the arrivals are lost in the long run.

Python An overloaded finite queue stays stable

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 throughput can never exceed μ, and the two utilization expressions match.

When sizing a buffer, plot blocking against K on a log scale. Each extra slot cuts blocking by roughly a factor of ρ when ρ < 1, so a target such as one lost customer in a thousand tells you quickly how many slots you need.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. An M/M/1/K queue has λ = 3, μ = 2. Is the system stable?

    Only K+1 states exist, so the chain always has a stationary distribution. Overload shows up as heavy blocking, not as unbounded growth.
  2. 2. Which rate must be used in Little's Law L = λ·W for a finite-capacity queue?

    Only admitted customers spend time in the system, so only their rate belongs in Little's Law.
  3. 3. With ρ = 1 and K = 4, what is the blocking probability?

    At ρ = 1 all K+1 = 5 states are equally likely, so p_K = 1/5 = 0.2.
  4. 4. Why can we say an arriving customer is blocked with probability p_K?

    PASTA means a Poisson arrival sees the system in its long-run distribution, so the chance it finds K customers is p_K.

Summary

  • M/M/1/K holds at most K customers; arrivals who find it full are lost.
  • p_n = (1 - ρ)ρ^n / (1 - ρ^(K+1)), or 1/(K+1) when ρ = 1.
  • Blocking is p_K; admitted traffic is λ_eff = λ(1 - p_K).
  • Use λ_eff in Little's Law, and utilization is λ_eff / μ = 1 - p_0.
  • A finite buffer is always stable, even when ρ > 1.

Next: Erlang B and Loss Systems