Summary

  • Receive livelock occurs when arrival interrupts consume the CPU time needed to move packets through protocol, output or application work. The machine runs, but delivered throughput can reach zero.
  • Mogul and Ramakrishnan combined interrupt-triggered polling with round-robin service, per-callback quotas, early discard, downstream queue feedback and a measured CPU share. Polling without a quota still failed.
  • Their receipts came from a slow single-CPU DECstation on 10-Mbit/s Ethernet. The tested five-to-ten-packet quota and queue thresholds were bounded settings, not modern universal defaults.

The machine was busy, but the work never arrived

An interrupt is a promise of urgency. A device tells the processor that something has happened, and the operating system suspends lower-priority work to respond. That bargain is excellent when arrivals are sparse. It becomes perverse when packets arrive faster than the machine can complete them.

In the 4.2BSD-derived design examined by Jeffrey C. Mogul and K. K. Ramakrishnan, a receive interrupt pulled packets from the interface and placed them on an IP input queue. Protocol processing ran later and at lower priority. New arrivals could therefore pre-empt the very work needed to empty the queue. Once input became fast enough, the queue filled, every later packet was discarded after the machine had already spent effort on it, and no packet reached the application or output interface.

The authors called this receive livelock. It was not deadlock: when the input rate fell, the system recovered. During the overload, however, a monitoring panel could show continuous CPU activity and a stream of handled interrupts while useful throughput was zero.

That definition changed the accounting unit. Throughput was not packets noticed by the adapter or copied into memory. It was packets delivered to their ultimate consumer—an application, or the transmitting interface of a router. Receive and transmit were one completion path.

Interrupt priority was a hidden scheduler

The operating-system scheduler did not choose this collapse. In the traditional design, it barely saw the work. Fixed interrupt priorities decided which code ran first, and receive work held an authority stronger than the scheduler's ordinary fairness rules.

The consequences extended beyond lost payload. A router starved of transmit work might delay routing control messages. Neighbours could misread that delay as a link failure and generate more control traffic. A local management process could also lose its chance to run exactly when the machine most needed inspection.

Interrupt batching did not cure the structure. It amortised the cost of entering the handler and could raise the maximum loss-free receive rate, but it merely moved the point at which overload took control. Faster admission was still not guaranteed completion.

An interrupt should wake a poller, not own the CPU

Mogul and Ramakrishnan retained interrupts under light load because they offered low latency without constant polling. Under heavy load, the interrupt handler did almost nothing: it marked the device as needing service, scheduled a polling thread and left further device interrupts disabled.

The polling thread then visited registered event sources in round-robin order. It handled receive and transmit work, gave each callback a packet quota, and enabled an interface's interrupts again only after its pending work drained. Once a packet was accepted from the device, the kernel tried to move it as far toward completion as possible instead of depositing it into another priority boundary.

This was not “interrupts bad, polling good.” Pure polling wastes cycles and increases latency when traffic is quiet. The useful design switched modes: an interrupt discovered unpredictable work; bounded polling controlled predictable saturation.

The no-quota failure

The experiment supplied its own warning against sloganising the result. When the modified kernel polled without a quota, throughput again fell almost to zero above the loss-free rate.

The input callback always found another packet, so it never returned to the polling loop. The loop therefore never reached the transmit-completion callback. Output descriptors were not released, the output queue filled, and packets were discarded later in the path—after more work had been invested in them than in the original kernel.

Polling had changed the mechanism without changing the monopoly. The quota, not the word “polling,” created a turn for output. On the tested hardware, quotas of five to ten packets produced stable, near-optimum forwarding. Larger turns amortised polling overhead but raised latency and starvation risk. The authors explicitly warned that another processor and interface could require another value.

Drop before the investment, then listen to the next queue

Under overload, some offered packets cannot be completed. The question is where the system discovers that fact. Dropping at the interface spends almost nothing. Dropping after driver work, protocol work and queueing burns scarce cycles on a packet that never becomes throughput.

Early discard therefore served efficiency, while feedback served progress. In the screend experiment, the kernel stopped input when the downstream screening queue reached 75% full, resumed at 25% and used an approximately one-millisecond timeout as a safety valve. Those values were explicitly arbitrary. The principle was the evidence loop: when a later stage cannot drain, the entrance must stop pretending that more admission is success.

A second loop measured CPU cycles used by packet processing in ten-millisecond periods. When the configured share was consumed, input paused so user processes and housekeeping could run. The machine became far more responsive to a local user. Network interaction still suffered because overload was being shed as packet loss. Reserved CPU was a bounded improvement, not an availability miracle.

The receipts and their denominator

The router under test was a DECstation 3000/300 running Digital UNIX V3.2, deliberately the slowest available Alpha machine. It connected two otherwise unloaded 10-Mbit/s Ethernets. Each trial sent 10,000 UDP packets with four bytes of payload; the source was not precisely paced, so rates were averages over several seconds.

With the unmodified kernel and user-mode screend, poor overload behaviour began above roughly 2,000 packets per second and complete livelock appeared near 6,000. Without screend, forwarding peaked around 4,700 packets per second, and the authors expected livelock before minimum-sized Ethernet traffic reached its physical maximum.

These numbers are valuable because the report carries their limits. The authors said they could not extrapolate the results to then-modern faster LANs and CPUs. They had not demonstrated true symmetric-multiprocessor behaviour. Their early-drop design decided when to discard, not which application, flow or partial video frame deserved protection.

The paper also says an early version had been deployed in routers used for the NASDAQ financial network. That proves operational contact, not independent validation of every result. The scientific receipt remains the published workload, machine, queues, thresholds and measured output.

A modern echo without a universal recipe

Current Linux NAPI documentation describes a recognisable event shape: a device interrupt schedules a poll instance, drivers keep interrupts masked until polling finishes, and a work budget bounds a poll cycle. Linux also exposes packet and time budgets, backlog limits and explicit trade-offs between batching, CPU use and latency.

That resemblance is useful, but it should not be inflated into a claim that every NAPI path is a direct copy of this paper or that every overloaded host is livelocked. Diagnosis still requires the same disciplined evidence: offered load rises; interrupt or receive work consumes the budget; later stages stop progressing; and useful output falls rather than remaining near capacity.

Google Research now describes Mogul's career across DEC/Compaq WRL, HP Labs and Google's networking infrastructure, along with his work on Internet standards. The receive-livelock paper remains joint work with Ramakrishnan. Its historical force lies less in one kernel patch than in the metric it refused to accept. A busy entrance could not call itself a working system.

Sources