M/M/1 & M/M/c Kendall Notation Queuing Delay Analyzer

1. The Foundations of Queuing Theory: David G. Kendall’s Notation

In 1953, British statistician David G. Kendall formalized a standardized shorthand classification for stochastic queuing processes, universally adopted across telecommunications engineering, operations research, and computer science. Kendall’s notation takes the generalized structural form:

Where each position defines a fundamental mathematical constraint of the waiting line architecture:

• A (Arrival Process Distribution): The statistical distribution governing inter-arrival intervals between incoming requests. Common classifications include M (Markovian or memoryless, Poisson arrival process where inter-arrival times are exponentially distributed), D (Deterministic, where arrivals occur at rigid, fixed time intervals), and G (General or arbitrary distribution with known mean and variance).
• S (Service Time Distribution): The probability distribution governing the duration required to process a single unit of work. Typical values include M (exponentially distributed service durations), D (constant processing times, such as fixed-size cell transmission), and G (general service distributions).
• c (Number of Parallel Servers): The quantity of identical, independent service channels operating in parallel, drawing from a common shared waiting line buffer.
• K (System Storage Capacity): The maximum finite number of customers permitted in the system simultaneously (both in service and awaiting service in the buffer). When K = ∞, the capacity is unconstrained, which is the implicit default when omitted.
• N (Calling Population Size): The pool of potential sources generating traffic. When omitted, N = ∞ (infinite calling source assumption, as in public telephone networks or the open Internet).
• D (Queue Scheduling Discipline): The algorithm deciding which waiting request receives service next. Standard disciplines include First-In, First-Out (FIFO / FCFS), Last-In, First-Out (LIFO), Processor Sharing (PS), and Priority Queuing (PQ). When omitted, FIFO is universally assumed.

Under this notation, an M/M/1 queue denotes an infinite-capacity, single-server system with Poisson arrivals and exponential service times. An M/M/c queue represents a multi-server pool where c parallel servers feed from a single aggregated FIFO queue.

2. The Fundamental Memoryless Property of Markovian Queues

The hallmark of the letter M in Kendall notation is the memoryless property (Markovian property). A continuous random variable X is memoryless if and only if:

In practical telecommunications terms, this mathematical truth establishes that the remaining service time of an active packet transmission or phone conversation is completely independent of how long the packet has already been transmitting. The probability of completing within the next millisecond remains strictly constant:

Because the exponential distribution is the only continuous distribution possessing this property, the stochastic evolution of the queue length can be modeled as a continuous-time Markov birth-death chain, yielding elegant, closed-form analytical solutions for steady-state system occupancy without tracking historical dwell times.

3. Little’s Law: The Invariant Pillar of Operations Research

Published in 1961 by John Dutton Conant Little, Little’s Law establishes a mathematically rigorous relationship between mean queue occupancy, arrival rate, and average transit time:

Where:

• L = Average total number of jobs/packets residing in the system (both waiting and actively in service).
• L_q = Average number of jobs/packets waiting in the queue buffer.
• λ = Long-term average arrival rate into the system (jobs or packets per unit time).
• W = Average total sojourn time spent by a job in the system (queuing delay plus active transmission time).
• W_q = Average delay spent purely waiting in the queue buffer prior to commencement of service.

The astonishing power of Little’s Law lies in its complete operational universality: it requires no assumptions regarding arrival distributions, service distributions, or queue scheduling disciplines. So long as the system is stable (ρ < 1.0) and transitions are conservative (no packets created or destroyed within the system), Little’s Law holds with mathematical certainty.

4. The Non-Linear “Hockey Stick” Latency Explosion

One of the most dangerous misconceptions in network capacity planning is the assumption of linear degradation. In an M/M/1 queuing system, the mean total sojourn time W scales inversely with the remaining server headroom:

Where ρ = λ / μ represents the server utilization. Notice the term 1 / (1 - ρ), known as the latency dilation multiplier:

• At ρ = 50%: Multiplier = 1 / (1 - 0.50) = 2.00× (Delay is exactly double the bare transmission time).
• At ρ = 75%: Multiplier = 1 / (1 - 0.75) = 4.00× (Delay has quadrupled).
• At ρ = 80%: Multiplier = 1 / (1 - 0.80) = 5.00× (Entering the “knee” of the exponential curve).
• At ρ = 90%: Multiplier = 1 / (1 - 0.90) = 10.00× (Delay is 10 times bare service time).
• At ρ = 95%: Multiplier = 1 / (1 - 0.95) = 20.00× (Severe bufferbloat and latency inflation).
• At ρ = 98%: Multiplier = 1 / (1 - 0.98) = 50.00× (Imminent buffer overflow and packet drop collapse).
• As ρ → 100%: W → ∞.

In production carrier IP backbones and data center egress fabrics, operating sustained utilization above 75% to 80% is considered catastrophic. Because traffic is stochastic and bursty, minor 10% microbursts occurring near the curve’s knee push utilization past 90%, precipitating bufferbloat, tail drops, TCP retransmission storms, and session timeouts.

5. Architectural Trade-Off: Single Fast Server vs. Multiple Slower Servers (M/M/1 vs. M/M/c)

A classic optimization dilemma in telecommunications engineering compares provisioning a single ultra-high-speed link of capacity C = cμ (e.g., a single 100 Gbps port) versus bonding c parallel links of capacity μ (e.g., ten 10 Gbps ports):

While both topologies deliver identical total bandwidth (cμ), the single fast server provides vastly superior latency:

In the single fast server, active service time is reduced by a factor of c (10 ms becomes 1 ms). Furthermore, a single consolidated queue prevents head-of-line blocking where one server sits momentarily idle while another server’s dedicated queue backs up. Multi-server pools (M/M/c) are deployed primarily when physical silicon, link boundaries, or human agent constraints make a single monolithic server impossible.

6. Variance Reduction: The Power of Deterministic Scheduling (Pollaczek-Khinchine Formula)

When service durations are not exponential but follow a general distribution with mean 1/μ and variance σ², the system becomes an M/G/1 queue governed by the famous Pollaczek-Khinchine (P-K) formula:

For exponential service times, variance is maximum: σ² = 1/μ², which simplifies to the standard M/M/1 result:

However, when packets or service durations are completely deterministic and uniform (σ² = 0, as in ATM cell networks or unfragmented fixed-size MTU frames), the variance term vanishes:

This profound result demonstrates that eliminating service duration variability cuts the average queue depth and waiting delay exactly in half without adding a single megabit of extra physical line capacity.