Statistical Multiplexing and the Case Against Reserved Circuits

A telephone call reserves a pair of wires, or one channel of a multiplexed carrier, for its entire duration. The reservation is symmetric and unconditional: it holds while two people talk, while one of them is silent, and while the handset is set down between sentences. A T1 carrier, the standard North American digital trunk, carries 24 such channels at 64 kbit/s each inside a 1.544 Mbit/s line. Every one of those 24 channels belongs to exactly one conversation from setup to teardown, and the engineering that sized the trunk was the engineering of peak-hour blocking probability, not of average load.

The alternative that displaced this model on data networks inverts the assumption. If a source is silent, its share of the line is available to someone else, and the network collects a dividend from the mismatch between each source’s average rate and its peak. That dividend is statistical multiplexing, and it is the entire economic argument behind packet switching. The argument is old enough to have been made twice, independently, in the 1960s, and it is worth separating its three distinct claims: multiplexing gain, path redundancy, and survivability. Only the first is a property of packets as such.

Two independent statements of the same idea

Paul Baran’s RAND memoranda of 1964 argued for a communications system that would survive the loss of individual links and nodes. His design divided traffic into standardized message blocks, routed each block independently through a mesh of redundant links, and deliberately avoided any central switching point. The redundancy claim and the block claim travelled together in that work, which is why the survivability story is often mistaken for the whole argument.

Donald Davies at the National Physical Laboratory reached the queueing conclusion from the other direction, starting from time-sharing terminals whose traffic was bursty and cheap to delay. Davies coined the term packet for a short block of data carrying its own destination information, and the NPL network designed in the late 1960s around that idea was sized for the observation that interactive traffic occupies a fraction of its nominal rate. Where Baran’s motive was hardness against attack, Davies’ was efficient use of an expensive leased line.

The ARPANET, contracted in 1968 and first operating with four nodes at the end of 1969, inherited the mechanism rather than either motive. Its leased 50 kbit/s links between Interface Message Processors were expensive and its host traffic was bursty, so the multiplexing gain was the practical justification. The survivability properties were real but incidental to the procurement.

What a packet actually buys

Consider a link of capacity $C$ bits per second shared by $n$ sources. Under reservation, each source is granted a fixed rate $C/n$ and the link is fully committed whether or not the sources transmit. A source that needs more than $C/n$ is refused or shaped; a source that needs less leaves the remainder idle, and idle capacity cannot be reclaimed because the slot is assigned by position in a multiplexing frame.

Under statistical multiplexing, each source sends a block whenever it has one, and blocks queue for the link in arrival order. The link is busy whenever at least one source has data waiting, so the fraction of capacity wasted falls toward zero as the number of sources rises, provided their bursts are not correlated. This is the same result as a bank of telephone lines sized for a call center: a pool of $n$ circuits serving bursty arrivals can carry more offered load than $n$ dedicated circuits, at a cost measured in the probability that a block waits.

That cost is not small, and it is the part of the argument most often skipped. Queueing delay is convex in load. For a single server with random arrivals, the mean time in system is

$$T = \frac{1}{\mu - \lambda} = \frac{1/\mu}{1 - \rho},$$

where $1/\mu$ is the mean service time and $\rho = \lambda/\mu$ is utilization. At half load a block waits on average twice the service time; at 90 percent load, ten times. The multiplexing gain is purchased with a delay that grows without bound as the link approaches saturation, and the shape of that curve is why every later congestion-control mechanism in the network exists.

def mean_system_time(service_time, utilization):
    """M/M/1 mean time in system, in the same units as service_time."""
    if not 0.0 <= utilization < 1.0:
        raise ValueError("utilization must be in [0, 1)")
    return service_time / (1.0 - utilization)

for rho in (0.2, 0.5, 0.8, 0.95):
    print(f"rho={rho:0.2f}  delay={mean_system_time(1.0, rho):0.2f} service times")

The output is arithmetic, not measurement: 1.25, 2, 5, and 20 service times. Nothing about a particular network is implied.

The header is the price of independence

A packet must be self-describing, because no per-flow state is assumed to exist at each switch. That self-description is pure overhead, and its size relative to payload is the second axis of the trade. The ARPANET host-to-IMP leader was a fixed 32 bits carrying destination host and link number, message type, and a checksum; a host message was capped at roughly a thousand bytes, so the leader cost a fraction of a percent on full messages and a large fraction on short ones. The design decision recorded in the ARPANET work was to batch short messages into longer ones rather than pay the header on each keystroke.

Modern headers make the same trade at a different scale. An IPv4 header is 20 bytes minimum and a TCP header another 20, so a 40-byte payload inside TCP over IPv4 spends half the link on headers unless header compression or a larger payload amortizes it. The independence gained is that no switch needs to know about the flow; the cost is that every switch must parse, and every payload must carry its own address.

Where reservation still wins

Statistical multiplexing is a bad fit for traffic with a hard delay bound and a constant rate. A digitized voice channel produces 64 kbit/s continuously and tolerates only a narrow range of variation in inter-packet arrival; queueing that traffic behind file transfers produces gaps that the receiver hears as artifacts. This is why the telephone network stayed circuit-switched long after data moved to packets, and why later packet networks reintroduced reservation-like mechanisms for real-time flows rather than relying on best-effort queueing.

The general statement is that multiplexing gain depends on the ratio of peak to mean rate and on the tolerance for delay. Sources that are bursty and delay-tolerant gain; sources that are smooth and delay-sensitive do not. Correlated bursts destroy the gain entirely: if every source transmits at once, the pool behaves like a single overloaded link and the queue grows without limit. The multiplexing dividend assumes independence, and real traffic at a common bottleneck is often synchronized by the very congestion it causes.

There is a second cost to reservation that does not appear in the utilization arithmetic. A reserved circuit must be established before any data flows, and the establishment takes a round trip through whatever signalling system allocates the channels. In the telephone network that signalling is out-of-band and the setup cost is small relative to a conversation of minutes. For a data transfer of a few hundred bytes, the setup dominates: a request that would take one round trip under packet switching takes three or four when a circuit must be reserved, used, and released. The crossover is a function of the transfer size, and it falls in the range where interactive terminal traffic lives, which is exactly the traffic Davies was designing for.

Three claims that are not the same claim

Baran’s redundant mesh, Davies’ queueing efficiency, and the ARPANET’s store-and-forward hops are routinely compressed into one origin story. They are separable. A circuit-switched network can be built with redundant paths, and a packet network can be built as a single tree. The distributed-routing question is treated in ARPANET IMPs and the 1822 Host Interface, where the forwarding decision lives; the queueing consequence of too many sources chasing one link is the subject of AIMD Congestion Control and the Collapse It Prevented.

What packet switching did not settle is reliability. The ARPANET’s links were themselves reliable, error-corrected hop by hop, and each IMP acknowledged messages to its neighbour. A packet could be lost only when a queue overflowed or a link failed, and the host protocols of the early 1970s assumed a fairly quiet subnet underneath them. The decision to move retransmission and ordering to the endpoints, where the application’s tolerance for delay is known, came later and is the substance of The TCP/IP Split and the End-to-End Argument. Once that move was made, the queueing delay computed above stopped being an inconvenience and became a control signal: a growing queue means the endpoints are offering more than the path can carry, and the only place to react is at the source.