Queuing theory in delay systems

Queuing theory is the mathematical study of waiting lines. In a delay system, a call or packet that finds all servers busy waits in a queue instead of being lost. Queuing theory predicts how long it waits and how many wait, given the arrival rate, service rate and number of servers.

Principles of queuing theory

 arrivals   +-------------+    +-----------+
 --lambda-->| queue/buffer|--->| N servers |--> out
            +-------------+    | rate mu   |
                               +-----------+

1. Arrival process: usually Poisson with mean rate $\lambda$ (exponential inter-arrival times).
2. Service process: holding/transmission time, often exponential with mean $1/\mu$.
3. Servers: N trunks, operators, processors or output links.
4. Queue capacity and discipline: finite or infinite buffer; FIFO, priority, etc.
5. Kendall notation A/B/C/K/N/D summarises the system (e.g. M/M/1, M/M/N).
6. Traffic intensity $A = \lambda/\mu$ Erlangs; utilisation per server $\rho = A/N$ must be below 1, otherwise the queue grows without limit.
7. Little's law: $L = \lambda W$ and $L_q = \lambda W_q$ (mean number = arrival rate × mean time).

Key delay-system results

• M/M/1: $W_q = \dfrac{\rho}{\mu(1-\rho)}$, $L_q = \dfrac{\rho^2}{1-\rho}$, $P(\text{wait}) = \rho$.
• M/M/N (Erlang C): probability of delay $C(N,A)$; mean delay of all calls $W = \dfrac{C(N,A)\,h}{N-A}$; probability of waiting longer than t: $C(N,A)\,e^{-(N-A)t/h}$.
• M/D/1 (fixed packet length): $W_q = \dfrac{\rho}{2\mu(1-\rho)}$, half that of M/M/1.

Applications in telecommunication networks

• Common-control exchanges: callers wait for dial tone (register/processor queue); designed so that, e.g., not more than 1.5% wait over 3 s.
• Call centres and operator services: number of agents chosen with Erlang C for a target service level.
• Packet networks (routers, switches, ATM): packets queue in output buffers; queuing delay, jitter and buffer overflow (loss) are predicted with M/M/1, M/D/1 or M/M/1/K.
• Signaling links (SS7) and processors: message delay versus link load.

How queuing theory helps manage delay and improve service

1. Dimensioning: finds the minimum number of servers or link capacity for a target mean delay or probability of delay.
2. Load limits: shows that delay rises sharply as $\rho \to 1$ (e.g. M/M/1 $W/h$ = 2 at $\rho = 0.5$ but 10 at $\rho = 0.9$), so links are kept at moderate utilisation.
3. Buffer sizing: chooses queue length K to balance packet loss and delay.
4. Scheduling and priority: priority queues give voice/video low delay while data waits (QoS).
5. Trunking efficiency: shows one large pooled server group gives less delay than several small separate groups.
6. Capacity planning and SLAs: predicts performance as traffic grows, guiding upgrades before service degrades.