M/M/1 Queue

The simplest nontrivial queue: Poisson arrivals (rate $\lambda$), exponential service times (rate $\mu$), one server, FIFO, infinite capacity.

Utilization: $\rho =\lambda /\mu ,\text{stable iff }\rho <1$

Steady-state results (memorize these for queueing questions): $L=\frac{\rho }{1-\rho },L_q=\frac{{\rho }^2}{1-\rho }$ $W=\frac{1}{\mu -\lambda },W_q=\frac{\rho }{\mu -\lambda }$

Where $L$ / $W$ include the one in service; $L_q$ / $W_q$ exclude it. All follow from Little + the geometric distribution of queue length.

The “hockey stick”: plot $W$ vs $\rho$. Linear up to about $\rho =0.7$, vertical past 0.9. That’s why systems in production typically target $\rho$ around 0.5–0.7; the latency penalty for pushing utilization higher is brutal.

The exponential service-time assumption is unrealistic; real service times have more variance than exponential. M/G/1 (general service distribution) captures this via the Pollaczek–Khinchine formula, where latency scales with the variance of service time, not just the mean.

From ECE459 L32

Markov = memoryless: arrivals Poisson, inter-arrivals exponential, service exponential. Utilization $\rho =\lambda s$ (arrival rate × service time).

Jeff’s working formulas [Wil13b]: $T_q=\frac{s}{1-\rho },W=\frac{{\rho }^2}{1-\rho },T_q^{\prime }=T_q-s=\frac{s\rho }{1-\rho }$

• $T_q$: average completion time (wait + service).
• $W$: average queue length.
• $T_q^{\prime }$: pure waiting time.

Jobs-in-system: $\rho /(1-\rho )$. Prob of exactly $x$ jobs: $(1-\rho ){\rho }^x$. Prob $>n$: $1-{\sum }_{i=0}^n(1-\rho ){\rho }^i$.

Example [Wil13b]

Server: $s=10$ ms, exponential. Over 30 min, 117 000 jobs. $\lambda =65$ req/s, so $\rho =0.65$.

• $T_q=0.01/0.35=28.6$ ms.
• $W=0.65^2/0.35=1.21$ jobs.

Printer example [Wil13b]

$s=2$ min, jobs every 2.5 min ⇒ $\lambda =0.4$, $\rho =0.8$. $T_q=2/0.2=10$ min. Ouch.

Buy a 2× faster printer? $s=1$, $\rho =0.4$, $T_q=1/0.6=1.67$ min (1:40). Much better, when utilization is low. Compare against the two-printer solution in k.

Related

• Queueing Theory
• k
• Little’s Law