Skip to content

Queuing Models: M/M/1, M/M/c, Limited Waiting Space and M/G/1

CSIR NET queuing theory: birth-death steady state, Little's law, M/M/1, M/M/1/K, M/M/c, M/M/c/K, Erlang formulas and the Pollaczek-Khinchine M/G/1 result.

  • 18 min read
  • Updated
On this page · 15 sections
  1. Prerequisites
  2. The Hook: One Fast Counter or Two Slow Ones?
  3. Notation and the Language of Queues
  4. M/M/1
  5. M/M/1/K: Limited Waiting Space
  6. M/M/c
  7. M/M/c/K and the Erlang Loss Formula
  8. M/G/1: General Service Times
  9. Memory Tricks
  10. Don’t Confuse
  11. Common Mistakes
  12. Practice
  13. Quick Revision Table
  14. Key Takeaways
  15. What’s Next

Prerequisites

The Hook: One Fast Counter or Two Slow Ones?

Notation and the Language of Queues

Kendall’s notation \( A/B/c/K \): arrival process / service-time distribution / number of servers / system capacity (in service plus waiting). M means Markovian (Poisson arrivals, exponential service), D deterministic, G general, \( E_k \) Erlang. Capacity \( K = \infty \) is omitted. The discipline is FCFS unless stated.

SymbolMeaning
\( \lambda \)arrival rate (customers per unit time)
\( \mu \)service rate of one server; mean service time \( \frac{1}{\mu} \)
\( \rho \)traffic intensity (utilisation): \( \frac{\lambda}{\mu} \) for one server, \( \frac{\lambda}{c\mu} \) for \( c \) servers
\( a = \frac{\lambda}{\mu} \)offered load in erlangs
\( p_n \)steady-state probability of \( n \) customers in the system
\( L, L_q \)mean number in the system, in the queue
\( W, W_q \)mean time in the system, in the queue

Poisson arrivals and exponential inter-arrival times are the same thing: arrivals form a Poisson process of rate \( \lambda \) if and only if the inter-arrival times are independent exponentials with mean \( \frac{1}{\lambda} \).

Little’s law

For any queue in steady state (very general conditions, any distributions, any discipline),

$$\boxed{L = \lambda W, \qquad L_q = \lambda W_q, \qquad W = W_q + \frac{1}{\mu}.}$$

With a finite waiting room, replace \( \lambda \) by the effective arrival rate \( \lambda_{\text{eff}} \), the rate of customers who actually join. Little’s law turns any one of \( L, L_q, W, W_q \) into the other three.

Birth-death steady state

In a Markovian queue the number in system \( N(t) \) is a birth-death process: from state \( n \), up at rate \( \lambda_n \), down at rate \( \mu_n \). The steady-state balance equations (rate out = rate in) reduce to the cut equations \( \lambda_{n-1} p_{n-1} = \mu_n p_n \), so

$$p_n = p_0 \prod_{i=1}^{n} \frac{\lambda_{i-1}}{\mu_i}, \qquad p_0 = \left[1 + \sum_{n \ge 1}\prod_{i=1}^{n}\frac{\lambda_{i-1}}{\mu_i}\right]^{-1}.$$

A steady state exists if and only if the sum is finite. Every model below is this formula with a particular choice of \( \lambda_n, \mu_n \).

graph LR
    S0((0)) -- "λ0" --> S1((1))
    S1 -- "μ1" --> S0
    S1 -- "λ1" --> S2((2))
    S2 -- "μ2" --> S1
    S2 -- "λ2" --> S3((3))
    S3 -- "μ3" --> S2
    S3 -.-> S4((...))

M/M/1

\( \lambda_n = \lambda \), \( \mu_n = \mu \). Steady state iff \( \rho = \frac{\lambda}{\mu} < 1 \).

QuantityFormula
\( p_n \)\( (1 - \rho)\rho^n \) (geometric); \( p_0 = 1 - \rho \)
\( P(N \ge n) \)\( \rho^n \)
\( L \)\( \frac{\rho}{1 - \rho} = \frac{\lambda}{\mu - \lambda} \)
\( L_q \)\( \frac{\rho^2}{1 - \rho} = \frac{\lambda^2}{\mu(\mu - \lambda)} \)
\( W \)\( \frac{1}{\mu - \lambda} \)
\( W_q \)\( \frac{\rho}{\mu - \lambda} = \frac{\lambda}{\mu(\mu - \lambda)} \)
Time in system (FCFS)exponential with rate \( \mu - \lambda \): \( P(\text{time} > t) = e^{-(\mu - \lambda)t} \)
Wait in queue\( P(W_q = 0) = 1 - \rho \); \( P(W_q > t) = \rho\,e^{-(\mu - \lambda)t} \)
Mean queue length when the queue is non-empty\( \frac{1}{1 - \rho} \)
Mean busy period\( \frac{1}{\mu - \lambda} \)

Note \( L - L_q = \rho \), the mean number in service: true for every stable single-server queue with unlimited waiting room (with finite capacity it is \( 1 - p_0 \)).

The blow-up. \( L = \frac{\rho}{1 - \rho} \) is 1 at \( \rho = 0.5 \), 9 at \( \rho = 0.9 \), 99 at \( \rho = 0.99 \). Running a server close to full utilisation is expensive in waiting.

M/M/1/K: Limited Waiting Space

At most \( K \) customers in the system (1 in service, \( K - 1 \) waiting); arrivals finding \( K \) present are lost. \( \lambda_n = \lambda \) for \( n < K \), 0 at \( K \). A steady state exists for every \( \rho \) (finite state space).

$$p_n = \frac{(1 - \rho)\rho^n}{1 - \rho^{K+1}} \ (\rho \ne 1), \qquad p_n = \frac{1}{K + 1} \ (\rho = 1), \qquad n = 0, 1, \dots, K.$$
QuantityFormula
Blocking (loss) probability\( p_K \)
Effective arrival rate\( \lambda_{\text{eff}} = \lambda(1 - p_K) = \mu(1 - p_0) \)
\( L \)\( \frac{\rho}{1 - \rho} - \frac{(K + 1)\rho^{K+1}}{1 - \rho^{K+1}} \) (\( \rho \ne 1 \)); \( \frac{K}{2} \) (\( \rho = 1 \))
\( L_q \)\( L - (1 - p_0) \)
\( W, W_q \)\( \frac{L}{\lambda_{\text{eff}}} \), \( \frac{L_q}{\lambda_{\text{eff}}} \)

The identity \( \lambda(1 - p_K) = \mu(1 - p_0) \) is “rate in = rate out”: customers join at rate \( \lambda_{\text{eff}} \) and leave at rate \( \mu \) whenever the server is busy.

M/M/c

\( c \) identical servers, one queue. \( \lambda_n = \lambda \); \( \mu_n = n\mu \) for \( n \le c \), \( c\mu \) for \( n \ge c \). With \( a = \frac{\lambda}{\mu} \) and \( \rho = \frac{a}{c} \), a steady state exists iff \( \rho < 1 \), i.e. \( \lambda < c\mu \).

$$p_n = \begin{cases} \dfrac{a^n}{n!}\,p_0, & 0 \le n \le c, \\[2mm] \dfrac{a^n}{c!\,c^{n-c}}\,p_0, & n \ge c, \end{cases} \qquad p_0 = \left[\sum_{n=0}^{c-1}\frac{a^n}{n!} + \frac{a^c}{c!\,(1 - \rho)}\right]^{-1}.$$
QuantityFormula
Probability an arrival must wait (Erlang C)\( C(c, a) = P(N \ge c) = \dfrac{a^c}{c!\,(1 - \rho)}\,p_0 \)
\( L_q \)\( \dfrac{a^c \rho}{c!\,(1 - \rho)^2}\,p_0 = C(c, a)\,\dfrac{\rho}{1 - \rho} \)
\( L \)\( L_q + a \) (mean number of busy servers is \( a \))
\( W_q, W \)\( \frac{L_q}{\lambda} \), \( W_q + \frac{1}{\mu} \)

For \( c = 1 \) these reduce to M/M/1. With infinitely many servers (M/M/\( \infty \)) nobody waits and \( N \sim \text{Poisson}(a) \).

M/M/c/K and the Erlang Loss Formula

Now at most \( K \ge c \) in the system. The \( p_n \) are the M/M/c expressions for \( n \le K \), with

$$p_0 = \left[\sum_{n=0}^{c}\frac{a^n}{n!} + \frac{a^c}{c!}\sum_{n=c+1}^{K}\rho^{\,n-c}\right]^{-1},$$

and a steady state for every \( \rho \). For \( \rho \ne 1 \),

$$L_q = \frac{p_0\,a^c\rho}{c!\,(1 - \rho)^2}\left[1 - \rho^{K-c+1} - (K - c + 1)(1 - \rho)\rho^{K-c}\right],$$

\( \lambda_{\text{eff}} = \lambda(1 - p_K) \), \( W_q = \frac{L_q}{\lambda_{\text{eff}}} \), \( W = W_q + \frac{1}{\mu} \), \( L = \lambda_{\text{eff}} W \).

For \( \lambda = 6 \), \( \mu = 4 \), \( c = 2 \), \( K = 4 \): \( p_0 = \frac{128}{653} \approx 0.196 \), \( p_4 = \frac{81}{653} \approx 0.124 \), \( L_q = \frac{270}{653} \approx 0.413 \). Two waiting places cut the queue from 1.93 to 0.41, at the price of losing 12.4% of customers.

No waiting room (\( K = c \)): M/M/c/c, the Erlang loss system. Arrivals finding all servers busy are lost:

$$p_n = \frac{a^n / n!}{\sum_{j=0}^{c} a^j / j!}, \qquad B(c, a) = p_c = \frac{a^c / c!}{\sum_{j=0}^{c} a^j / j!} \quad \text{(Erlang B)}.$$

For \( c = 2 \), \( a = 1.5 \): \( B = \frac{1.125}{1 + 1.5 + 1.125} = \frac{9}{29} \approx 0.310 \).

M/G/1: General Service Times

Poisson arrivals at rate \( \lambda \), one server, service time \( S \) with any distribution, mean \( E[S] = \frac{1}{\mu} \), variance \( \sigma^2 \). With \( \rho = \lambda E[S] < 1 \), the Pollaczek-Khinchine (P-K) mean-value formula is

$$\boxed{L_q = \frac{\lambda^2\sigma^2 + \rho^2}{2(1 - \rho)}, \qquad W_q = \frac{\lambda E[S^2]}{2(1 - \rho)},}$$

with \( L = L_q + \rho \), \( W = W_q + E[S] \), and \( p_0 = 1 - \rho \) still.

Service distribution\( \sigma^2 \)\( L_q \)
Exponential (M/M/1)\( \frac{1}{\mu^2} \)\( \frac{\rho^2}{1 - \rho} \)
Deterministic (M/D/1)0\( \frac{\rho^2}{2(1 - \rho)} \): half of M/M/1
Erlang-\( k \) (\( M/E_k/1 \))\( \frac{1}{k\mu^2} \)\( \frac{k + 1}{2k}\cdot\frac{\rho^2}{1 - \rho} \)

Variability costs waiting. For fixed mean service time, \( L_q \) increases linearly with the variance. Removing all variability halves the queue relative to exponential service.

M/G/1 is not a birth-death chain (the remaining service time is not memoryless); it is analysed through the embedded Markov chain at departure instants, which is where the full P-K transform formula for the distribution of \( N \) comes from.

Memory Tricks

Don’t Confuse

ThisvsThat
M/M/c: \( \rho = \frac{\lambda}{c\mu} \), stable iff \( \lambda < c\mu \)offered load \( a = \frac{\lambda}{\mu} \) (can exceed 1)
Erlang C: probability of waiting (infinite queue)Erlang B: probability of being lost (no queue)
\( K \) = capacity of the whole systemnumber of waiting places \( K - c \)
\( \lambda \) in Little’s law for infinite capacity\( \lambda_{\text{eff}} = \lambda(1 - p_K) \) with finite capacity
One fast server: smaller \( L \), \( W \)\( c \) slow servers: smaller \( L_q \), \( W_q \) (same total capacity)
\( p_0 = 1 - \rho \) in M/G/1the rest of the distribution of \( N \) is not geometric unless service is exponential

Common Mistakes

Practice

All questions below are original practice questions written for this page. They are not from any CSIR NET paper. In Level 3, as in Part C, one or more options may be correct.

Level 1: Foundation

  1. State Little’s law for the queue (waiting line only).
  2. In M/M/1 with \( \rho = 0.6 \), what fraction of time is the server idle?
  3. By what factor does deterministic service reduce \( L_q \) compared with exponential service of the same mean?
Answers
  1. \( L_q = \lambda W_q \) (with \( \lambda_{\text{eff}} \) if customers can be lost).
  2. \( p_0 = 1 - \rho = 0.4 \).
  3. By half: \( \frac{\rho^2}{2(1 - \rho)} \) against \( \frac{\rho^2}{1 - \rho} \).

Level 2: Part B Style

Practice Q1. Customers arrive at a single counter as a Poisson process with rate 6 per hour; service is exponential with mean 7.5 minutes. The mean waiting time in the queue (minutes) is

(a) 7.5 (b) 22.5 (c) 30 (d) 45

Answer: (b)

\( \mu = 8 \) per hour, \( \rho = 0.75 \), \( W_q = \frac{\rho}{\mu - \lambda} = \frac{0.75}{2} = 0.375 \) h = 22.5 min. (c) is \( W \), the time in the system.

Practice Q2. In an M/M/1/3 queue with \( \lambda = \mu \), the proportion of arriving customers who are turned away is

(a) \( \frac{1}{8} \) (b) \( \frac{1}{4} \) (c) \( \frac{1}{3} \) (d) \( \frac{1}{2} \)

Answer: (b)

At \( \rho = 1 \), \( p_n = \frac{1}{K + 1} = \frac{1}{4} \) for \( n = 0, 1, 2, 3 \). Poisson arrivals see time averages, so the loss proportion is \( p_3 = \frac{1}{4} \).

Practice Q3. In an M/G/1 queue, \( \lambda = 3 \) per hour and service times have mean 15 minutes and standard deviation 10 minutes. The mean number in the queue is

(a) 1.125 (b) 1.625 (c) 2.25 (d) 2.375

Answer: (b)

P-K: \( \rho = 0.75 \), \( \lambda^2\sigma^2 = 9 \times \frac{1}{36} = 0.25 \); \( L_q = \frac{0.25 + 0.5625}{0.5} = 1.625 \). (a) is M/D/1, (c) M/M/1, (d) is \( L \).

Practice Q4. For an M/M/2 queue with \( \lambda = 6 \) and \( \mu = 4 \) per hour, the probability that an arriving customer has to wait is

(a) \( \frac{1}{7} \) (b) \( \frac{9}{28} \) (c) \( \frac{9}{14} \) (d) \( \frac{3}{4} \)

Answer: (c)

\( a = 1.5 \), \( \rho = 0.75 \), \( p_0 = \frac{1}{7} \). Erlang C \( = \frac{a^2}{2!(1 - \rho)}p_0 = \frac{2.25}{0.5}\cdot\frac{1}{7} = \frac{9}{14} \). (a) is \( p_0 \); (b) is \( W_q \) in hours; (d) is \( \rho \).

Level 3: Part C Style

Practice Q5. Customers arrive as a Poisson process with rate \( \lambda = 6 \) per hour. System A is one exponential server with rate 8 per hour; system B is two exponential servers each with rate 4 per hour and a single queue. Which statements are true?

(a) Both systems are stable. (b) The mean number in the queue is smaller in B. (c) The mean time in the system is smaller in B. (d) The mean number in the system is smaller in A.

Answer: (a), (b) and (d)
  • (a) True. A: \( \lambda < \mu = 8 \). B: \( \lambda < 2 \times 4 = 8 \).
  • (b) True. \( L_q^A = 2.25 \), \( L_q^B = \frac{27}{14} \approx 1.93 \).
  • (c) False. \( W^A = 0.5 \) h, \( W^B = \frac{4}{7} \approx 0.571 \) h.
  • (d) True. \( L^A = 3 \), \( L^B = \frac{24}{7} \approx 3.43 \) (consistent with Little: \( L = 6W \)).

Practice Q6. An M/M/1/2 queue has \( \lambda = 3 \) and \( \mu = 2 \) per hour. Which statements are true?

(a) A steady state exists even though \( \lambda > \mu \). (b) The probability that an arrival is lost is \( \frac{9}{19} \). (c) The effective arrival rate is \( \frac{30}{19} \) per hour. (d) The mean time in the system of a customer who joins is \( \frac{L}{\lambda} = \frac{8}{19} \) hours.

Answer: (a), (b) and (c)
  • (a) True. Finite state space \( \{0, 1, 2\} \), irreducible: a unique stationary distribution for any \( \rho \).
  • (b) True. Weights \( 1, \frac{3}{2}, \frac{9}{4} \) sum to \( \frac{19}{4} \); \( p_2 = \frac{9/4}{19/4} = \frac{9}{19} \).
  • (c) True. \( 3\left(1 - \frac{9}{19}\right) = \frac{30}{19} \), which equals \( \mu(1 - p_0) = 2 \cdot \frac{15}{19} \).
  • (d) False. \( L = \frac{24}{19} \), and Little’s law needs \( \lambda_{\text{eff}} \): \( W = \frac{24/19}{30/19} = 0.8 \) h. \( \frac{L}{\lambda} = \frac{8}{19} \) uses the wrong rate.

Practice Q7. A help desk receives Poisson calls at 10 per hour; each call takes an exponential time with mean 15 minutes; calls wait in a single queue for \( c \) identical agents. Which statements are true?

(a) The system is unstable with \( c = 2 \) agents. (b) With \( c = 3 \), \( p_0 = \frac{4}{89} \). (c) With \( c = 3 \), the mean number of calls waiting is about 3.51. (d) With \( c = 3 \), the mean waiting time before an agent answers is about 35 minutes.

Answer: (a), (b) and (c)

\( \lambda = 10 \), \( \mu = 4 \), \( a = 2.5 \).

  • (a) True. \( c\mu = 8 < 10 \): with two agents the queue grows without bound.
  • (b) True. \( c = 3 \), \( \rho = \frac{5}{6} \). \( \sum_{n=0}^{2}\frac{a^n}{n!} = 1 + 2.5 + 3.125 = 6.625 \); \( \frac{a^3}{3!(1 - \rho)} = \frac{15.625}{6 \cdot \frac{1}{6}} = 15.625 \). \( p_0 = \frac{1}{22.25} = \frac{4}{89} \).
  • (c) True. \( L_q = \frac{a^3\rho}{3!(1 - \rho)^2}p_0 = \frac{15.625 \times \frac{5}{6}}{6 \times \frac{1}{36}} \cdot \frac{4}{89} = \frac{625}{178} \approx 3.51 \).
  • (d) False. \( W_q = \frac{L_q}{\lambda} = \frac{125}{356} \) h \( \approx 0.351 \) h \( \approx 21.1 \) min. The figure “35 minutes” comes from misreading 0.351 hours as 35 minutes, a units slip. (The mean time in the system is \( W = W_q + 0.25 \) h \( \approx 36.1 \) min.)

Quick Revision Table

ModelKey results
Little\( L = \lambda W \), \( L_q = \lambda W_q \), \( W = W_q + \frac{1}{\mu} \)
Birth-death\( p_n = p_0\prod_{i \le n}\frac{\lambda_{i-1}}{\mu_i} \)
M/M/1\( p_n = (1 - \rho)\rho^n \); \( L = \frac{\rho}{1 - \rho} \); \( W = \frac{1}{\mu - \lambda} \); \( L_q = \frac{\rho^2}{1 - \rho} \)
M/M/1/K\( p_n \propto \rho^n \), \( n \le K \); \( \lambda_{\text{eff}} = \lambda(1 - p_K) = \mu(1 - p_0) \); always stable
M/M/c\( p_0^{-1} = \sum_{n
Erlang C\( P(\text{wait}) = \frac{a^c}{c!(1 - \rho)}p_0 \)
Erlang B\( \frac{a^c/c!}{\sum_{j \le c} a^j/j!} \)
M/G/1 (P-K)\( L_q = \frac{\lambda^2\sigma^2 + \rho^2}{2(1 - \rho)} \); M/D/1 half of M/M/1

Key Takeaways

What’s Next