M/M/k Queue

Poisson arrivals (rate $\lambda$), exponential service times (rate $\mu$ per server), $k$ identical servers sharing one FIFO queue.

Utilization per server: $\rho =\lambda /(k\mu ),\text{stable iff }\rho <1$

The probability of all servers busy (thus arrivals having to queue) is the Erlang C formula:

$C(k,\lambda /\mu )=\frac{(k\rho {)}^k/(k!(1-\rho ))}{{\sum }_{n=0}^{k-1}(k\rho {)}^n/n!+(k\rho {)}^k/(k!(1-\rho ))}$

From it: $W_q=\frac{C(k,\lambda /\mu )}{k\mu -\lambda },W=W_q+1/\mu$

Key practical result: shared queue beats sharded queue. Given $k$ servers handling arrival rate $\lambda$:

• One queue, $k$ servers: average wait is much smaller.
• $k$ independent M/M/1’s, each seeing $\lambda /k$: average wait is much larger.

Why: with $k$ independent queues you get stuck behind one slow job; in a shared queue any free server takes the next customer. This is why supermarkets moved to single-line, multi-register. Also why server farms put work on a shared queue, not round-robin to per-server queues.

From ECE459 L32

Per-server utilization $\rho =\lambda s/N$. Intermediate shorthand $K$ (no intrinsic meaning, just keeps formulas tidy): $K=\frac{{\sum }_{i=0}^{N-1}(\lambda s{)}^i/i!}{{\sum }_{i=0}^N(\lambda s{)}^i/i!}$

Probability a new job has to wait (all servers busy): $C=\frac{1-K}{1-\lambda sK/N}$

Completion and queue length: $T_q=\frac{Cs}{k(1-\rho )}+s,W=C\frac{\rho }{1-\rho }$

Printer example continued [Wil13b]

From 1: one slow printer $T_q=10$ min; one 2× printer $T_q=1:40$.

Two slow printers ($N=2$, $\lambda s=0.8$):

• $K=(1+0.8)/(1+0.8+0.32)=0.849$.
• $C=0.229$.
• $T_q=2.38$ min.

Two takeaways: (1) doubling printers made jobs ~4× faster, not 2×. (2) the single fast printer still wins at low utilization; it processes each job faster. The two-printer solution pulls ahead as utilization climbs toward 100%.

Related

• 1
• Queueing Theory
• Load Balancing