Ch 6: End systems

Source: Sterbenz & Touch 2001, Ch 6 (pp. 285–342), read in full. Page numbers are the book’s printed pages. For a trading engineer this chapter is the theory behind kernel bypass: copies, context switches, user/kernel crossings, interrupts vs polling, and what belongs on the NIC.

Numbering note: the chapter prints some IDs differently from Appendix A (Context Switch Avoidance is “E-II.6a” in the chapter, E-II.6c in the appendix; the ILP principle is “E-4E” vs E-4D; the chapter’s closing list swaps the labels of copy minimization and remapping). These notes use the Appendix A IDs.

The chapter in one paragraph

Without a fast, short path between the NIC and application memory, the host is the bottleneck however fast the network is (E-II). Find the real bottleneck by measuring: in the late 1980s people blamed the transport protocol, but the costs were in the operating system, in per-byte work (copies, checksums) and in timers. The target is a zero-copy path, about one context switch per application data unit, few user/kernel crossings, polling where arrivals are predictable, all protocol passes done in one loop (ILP), a bypass path for the common case, a nonblocking path from NIC to memory, and a NIC whose hardware/software split is set by the packet interarrival time.

Find the real bottleneck first (pp. 285–291)

• Application primacy for hosts (E-I): “a statement like ‘This implementation of TCP runs at 1 Gb/s’ is not terribly useful unless it is accompanied by what sort of application workload is running” (p. 286).
• Three late-1980s conjectures (p. 290): EC1 a new transport protocol enables high speed; EC2 running protocols on the network interface does; EC3 implementing protocol functions in hardware does. Each has some basis, but none helps unless it hits the bottleneck.
• Clark’s 1989 analysis of TCP/IP showed the real overheads were in the operating system, per-byte operations (checksumming, copying) and timer management (p. 290). TCP stayed, so the practical work became optimizing and extending it (E-III.7, p. 291).

Why traditional hosts were slow (pp. 291–294)

• The network interface was treated as just another I/O device behind general-purpose I/O controllers built for everything from disks to printers.
• Fig. 6.4: with one process per protocol layer, every packet crossed several context switches (application → transport → network → OS → I/O processor) and was copied at each layer. “Layered protocol architecture does not depend on a layered process implementation” (E-4A), and networking must be a first-class part of host design, like memory or graphics (E-I.4).

The ideal: zero copy (pp. 294–296)

• Goal: data moves between application memory and the network with no per-packet store-and-forward and no extra per-byte loops (E-II.3). Pipelining does not count as copying.
• Each separate pass over the data costs k·b·t/w: k passes over b bits, w bits per step of time t (p. 295).
• Semantics can force one copy: a reliable sender must keep transmitted data until it is acknowledged, and Unix socket semantics force a single-copy transmit path (pp. 295, 330).
• The book’s model: application memory with sequential ports wired straight to the network (“memory as a network”). Too simple in practice: the network loses, duplicates and reorders, and the receiver has to know where each piece of data belongs.

Protocol software (pp. 296–301)

• Optimize the critical path by execution time, not instruction count: keep loops inside the instruction cache, align data to cache lines. “A single read from off chip can take more time than the entire rest of the path” (p. 297, footnote 9).
• Three kinds of protocol work (pp. 298–300): data manipulation (move data, check errors, keep retransmission copies, encrypt, convert formats) is on the critical path; transfer control (rate and flow control, detecting loss and misordering, acknowledging, demultiplexing, timestamping, framing) is on it if later packets depend on it; asynchronous control (connection setup, routing, sessions) is not. Example: the only in-band part of an acknowledgment may be incrementing a counter; building and sending the ACK can happen off the critical path (p. 299).
• Parallelizing protocol code gives nothing on one processor, and on several it is limited by state shared between packets (reordering, loss recovery) (pp. 300–301).

The operating system (pp. 301–309)

• Context switches cost “hundreds of RISC instructions” [Mogul 1991] (p. 302). They come from page faults, blocking I/O and scheduler preemption. Aim for at most one per application data unit (E-II.6c); threads make switches cheaper because they share an address space.
• Interrupts vs polling (pp. 303–304): an interrupt lets the process do other work until data arrives, but costs a context switch. Polling is cheaper when you know when data will arrive. The poll interval is the trade-off: too short wastes cycles, too long delays data and needs more buffer. The two combine: “polling can be used to handle the interburst packets, with an interrupt per burst” (p. 304).
• User vs kernel (pp. 304–305): a protocol in user space needs several system calls per packet (buffers, scheduling, device access); a kernel protocol needs one crossing per call. Each crossing costs authorization checks, buffer copies and indirection (E-II.6k).
• Remapping instead of copying (pp. 305–308): hand a received buffer to the application by editing its page table instead of copying the data (E-II.3m). It is not free: page tables and the TLB must be updated and pages pinned and locked, and “in some 1990s operating systems, the cost of remapping a page is as costly as copying all the data in the page” (p. 308, footnote 20).
• Reserve host resources (E-II.2, pp. 308–309): a share of CPU, memory for buffers, and interconnect bandwidth, if the host is contended.

Protocol optimizations (pp. 309–313)

• Protocol bypass [Woodside 1990] (pp. 309–310, Fig. 6.10): find the frequent operations and put them in one bypass path with no internal concurrency. Send and receive filters match each packet against a template (as in TCP header prediction [Jacobson 1990]); matching packets take the bypass, everything else goes through the normal stack.
• Integrated layer processing [Clark 1990] (pp. 311–313, Fig. 6.11): do framing, checksum, encryption and the copy in one loop instead of one loop per layer. Limits: presentation conversion that changes the data size, and the whole loop must fit in cache.
• Microprotocols (p. 313): composable protocol pieces. Unix System V streams were elegant but so slow that BSD sockets became the API in general use.

Host organization (pp. 313–326)

• A shared bus gives each of n units at most w/(n·t); DMA offloads copying from the CPU but still contends for the bus; separate memory and I/O buses help; large systems use a crossbar between CPUs, I/O processors and memory (pp. 314–318).
• The NIC-to-memory path must be nonblocking and must not interfere with CPU–memory traffic or other I/O (E-II.4). Two ways to attach the NIC (pp. 318–321): on the processor–memory interconnect (uniform memory, but the NIC and CPUs contend: give network traffic priority and CPUs stall, don’t and the NIC needs big buffers), or through dedicated multiport memory (isolated, but costly, and data must already be in that memory to avoid a copy).
• The NIC need not write to main memory: “in data-intensive distributed processing applications we may wish for the network interface to transfer directly to 2nd level cache” (p. 322).
• Parallel processors on one NIC give about 2× (send vs receive), about 5× at most [Touch 1995a]; Amdahl’s law and synchronization eat the rest. Splitting by connection or flow scales best (pp. 323–324).
• Several NICs: split flows across them, not packets (packets would be reordered). In a NUMA multiprocessor, a single NIC makes the processor it is attached to a bottleneck; with one NIC per processor, incoming data must reach the right one (E-II.4m, pp. 324–325).

The network interface (pp. 326–340)

• Offloading is old: IBM ran SNA on 3705 communications processors attached to System/360 in the 1960s. The XTP Protocol Engine (Example 6.1) was a late-1980s attempt at a new protocol in VLSI (pp. 327–328).
• What to offload (p. 329): work done best while data moves between network and memory, work that needs special hardware, and per-byte work such as checksums and encryption. Moving work to the NIC does not help by itself (E-1Ci).
• Hardware vs embedded processor on the NIC is decided by the packet interarrival time (E-1Ch). Table 6.1 (p. 332), instructions available per packet:

A budget of 25 instructions is “marginal, at best; 80 instructions is more likely to be feasible” (footnote 27). Below that, the processor saturates (Fig. 6.19) and the work must move into hardware.

• Example 6.2, ATM to the desktop (p. 334): at OC-12 a cell arrived about every 780 ns, far too fast for 50 MHz processors, so interfaces needed custom chips and came years late. “ATM forced processing to the worst case … rather than the average case.”
• How low must NIC latency be? (p. 337): for general LAN and WAN use, about 100 µs is enough, because the network adds milliseconds and interactive users allow 100 ms (Second-Order Effect, 1A). But “distributed computing and control-feedback applications may require significantly lower-latency bounds, perhaps on the order of microseconds.”
• NIC pipelines (pp. 337–340, Figs. 6.22–6.23): line coding; serial-to-byte conversion (an 8× drop in internal clock rate); encryption; a checksum computed as data streams past (inserted into a trailer on transmit); byte-order conversion; headers for all layers built from a template in one shot (hardware ILP); header decode behind a small shift delay; scatter/gather DMA; rate scheduling. On receive, “the application must not be able to use the packet until it has fully arrived and passed the check” (p. 339).

Trading-network lens (my mapping)

Kernel bypass is this chapter in one product. AMD’s Onload is “a high performance user-level network stack, which accelerates TCP and UDP network I/O for applications using the BSD sockets on Linux”. It is “a user-level shared library that intercepts network-related system calls and implements the protocol stack, and supporting kernel modules”, and it uses the ef_vi interface of Solarflare NICs (checked: https://github.com/Xilinx-CNS/onload). In the book’s terms: a protocol bypass with a fallback to the normal stack, no copy through the kernel, and no user/kernel crossing per packet. The book judged user-space protocols slow because each packet needed system calls (Fig. 6.8a); bypass stacks avoid that by giving the process direct access to NIC queues. No single source for that last point.

Polling, as Linux does it. NAPI is the book’s hybrid: the device interrupts, then the driver keeps interrupts masked while it polls until the work is done. Busy polling “allows a user process to check for incoming packets before the device interrupt fires” and “trades off CPU cycles for lower latency”; it is enabled per socket with SO_BUSY_POLL or system-wide with the net.core.busy_poll and net.core.busy_read sysctls (checked: https://docs.kernel.org/networking/napi.html). Trading systems go further and dedicate whole cores to spinning on the NIC: principle 4H applied with 2026 prices.

From one context switch per ADU to none. Pinning the hot thread to an isolated core, away from the scheduler and from interrupts, is E-II.6c carried to its limit. No single source.

Cache discipline. The book’s code advice (loops inside the I-cache, data aligned to cache lines, one off-chip read can cost more than the rest of the path) is tick-to-trade coding practice today. Its idea of the NIC writing straight into the cache (p. 322) exists in current server CPUs (for example Intel’s Data Direct I/O). No single source.

NUMA (E-II.4m). Keep the NIC, its queues and interrupts, the buffers and the trading thread on the same CPU socket; crossing sockets adds latency. No single source.

The instruction budget is still the limit. At 10 Gb/s a minimum 64-byte frame arrives every 67 ns, about 200 cycles on a 3 GHz core: the book’s Table 6.1 problem, one generation later. That is why FPGA NICs parse and filter market data in hardware and hand software only the messages it needs (E-1Ch: interarrival time decides). Arithmetic plus No single source.

Benchmark with the application running (E-I). A NIC ping-pong number says as little about tick-to-trade as “this TCP runs at 1 Gb/s” said about applications. Measure under the real workload. My mapping.

Acting before the check. The book insists data must not be used before its check passes (p. 339). Hardware that starts decoding a message before the Ethernet FCS has arrived must be able to throw that work away if the FCS turns out bad. My mapping, No single source.

Self-check

1. What were the three end-system conjectures of the late 1980s, and what did analysis of TCP/IP find instead?
2. What forces a one-copy transmit path with TCP and sockets?
3. How expensive is a context switch according to the book, what is the target per application data unit, and how do threads help?
4. When is polling better than interrupts? What goes wrong if the poll interval is too short or too long? What hybrid does the book suggest, and which Linux mechanism works that way?
5. How does a protocol bypass decide which packets take the fast path?
6. Using Table 6.1, how many instructions does a 1 GHz processor have per 128-byte packet at 10 Gb/s? What does that imply for the NIC design?
7. Why does the book say a 1 µs NIC is not worth building for ordinary LAN/WAN use, and why does trading disagree?
8. What problem does a single NIC create in a NUMA multiprocessor?