Ch 1–2: Fundamentals and design principles

Source: Sterbenz & Touch 2001, Ch 1 (pp. 1–12) and Ch 2 (pp. 13–77), read in full. Page numbers are the book’s printed pages. The principles are listed one per line in 01-principles-map.md; this file covers the reasoning and the examples behind them.

Ch 1 in brief

• High-performance networking means high bandwidth and low latency, and the metric that matters is delay. If moving data between applications took zero time, it would not matter whether they sat in one room or on two continents (p. 2).
• Delay has two parts: the time to push a chunk out of the sender (size ÷ rate) and the time to cross the network. For a 1-bit chunk bandwidth hardly matters: even a 9600 b/s line adds only 104 µs (p. 2).
• Bandwidth matters because big chunks must move fast. For interactive use the response must be under a second, ideally about 100 ms; a 1 KB page then needs about 100 kb/s, and a 1 MB image about 100 Mb/s (p. 2).
• Three kinds of application (p. 3): bandwidth only (remote backup: terabytes in hours instead of weeks), latency only (voice, process control), and both (interactive web with 100 ms response). The book is about the third kind.
• The book gives no number for “high speed” on purpose: the principles should hold from gigabit to petabit. The usable rate also drops from the core to the edge and up the stack. In the late 1990s, SONET links ran at tens of Gb/s, switches at several Gb/s per port, host interfaces at 10–100 Mb/s and applications at a few Mb/s (pp. 3–4).
• Bandwidth–delay product: a path of rate r bit/s and delay d s holds rd bits in flight. A control loop sees 2rd bits go by before its action takes effect, so by then the condition it reacted to may be gone (p. 5).
• Legacy and heterogeneity block clean redesigns. “Proposals as drastic as the complete replacement of IP by ATM in the Internet are dead on arrival” (p. 5).

The delay model (pp. 21–25)

The book’s central formula, for a chunk of b bits on a path of bandwidth r:

D = (1 + h + c) · b/r + t_p

Bandwidth shrinks the b/r terms. Nothing shrinks the propagation part of t_p except a shorter path (III.1). The multiplier (1 + h + c) is why the book insists on Store-and-Forward Avoidance (II.3): “the best we can possibly do is the single transmission delay at the sending system, resulting in a zero-copy system” (p. 25).

Note: charging each copy a full b/r is the book’s simplification. A memory copy runs at memory speed, not link speed; the point is that every extra pass over the data adds a term that grows with b.

On lossy links, the book says to treat retransmissions as a loss of effective bandwidth rather than added latency, because bandwidth measures (forward error correction) fix it better than a shorter path would (p. 22).

The ideal network and the axioms (pp. 23–31)

• The ideal network is invisible to applications: infinite bandwidth (R = ∞) and zero delay (D = 0). Decomposed (Fig. 2.2), every piece must meet the same ideal: CPU and memory in each host, and nonblocking switches (pp. 23–24). The whole book is about how close real systems can get.
• Corollaries of the paths goal (II): find and set up paths (II.1); protect them, either by overprovisioning or by QoS reservations, because “application demand fills the available pipes” (II.2, p. 25); avoid store-and-forward and copies (II.3); avoid blocking from colliding paths or growing queues (II.4); avoid shared-medium contention (II.5); keep control cheap on the critical path (II.6); trade reliability and security against speed (II.7).
• Constraints (III) with the book’s examples: a crossbar needs n² switch elements for n ports, a multistage network only n·log₂n (p. 29). IPv6 was delayed because NAT hacks kept IPv4 alive (p. 30). Ethernet kept its name while CSMA/CD became irrelevant and 8B/10B replaced Manchester coding (p. 30). The ATM payload of 48 bytes was the average of two competing proposals, 32 and 64 (p. 31).

Design principles: the reasoning that matters

Time scales (p. 32). What you optimize spans at least 18 orders of magnitude: years to deploy a protocol, days to reconfigure a network, then session, connection, packet, cell, byte and bit times.

Selective optimization (1, 1A). A path with segment latencies 50 + 2 + 25 + 10 = 87: the second segment is 0.02 of the total, so removing it entirely changes nothing (p. 35). For a 100 ms interactive budget, WAN latency matters far more than LAN latency, but LAN latency still matters for distributed processing and feedback control with tight bounds (p. 35).

Critical path (1B), three observations (pp. 35–36):

1. Transfer control such as flow control and framing is on the critical path, even if it runs per frame rather than per byte.
2. The critical path can split into parallel branches that rejoin.
3. Dependencies count. If only 1% of packets need a slow transformation but packet order must be kept, every later packet waits behind it. That rare operation is on the critical path; speed it up or redesign so it is not.

Functional partitioning (1C): decide what goes into scarce, fast technology (hardware vs software, cache vs memory, custom vs semicustom chips) only after 1A and 1B tell you what needs speed (p. 36).

Resource trade-offs (2). Resources are bandwidth, processing and memory (B, P, M); latency is the constraint. The trade-offs move over time: bandwidth was expensive in early networks, became cheap with fiber, and then processing and memory became cheaper still (2A, p. 38). Parts that are hard to upgrade, such as transoceanic cables and last-mile wiring, should be heavily overprovisioned from the start (2B, p. 38). Multicast saves link bandwidth and sender work (2C, p. 39).

End-to-end argument (3). An end-to-end function is not the composition of per-hop functions, because you cannot control what happens between the hops (f ≠ f1∘f2∘f3). Encryption is the simple case: if data is in the clear anywhere along the way, there is no confidentiality (pp. 39–40). Per-hop duplicates are still worth it when they improve end-to-end performance, e.g. link-level error control on lossy wireless links (3A, p. 40).

Layering (4). Layering is a good way to think, and a bad way to implement: OSI-era stacks with one process per layer copying PDUs over IPC were “extraordinarily inefficient” (pp. 44–45). Layers can also fight each other: TCP slow start over an ATM connection with a guaranteed rate wastes the reservation by starting slow (4C, p. 46). Example 2.1 shows TCP/IP over ATM ending up with five layers handling transport, network and link functions (p. 49). Interrupts handle asynchronous events but are expensive; polling avoids that cost when you know when data will be there (4H, p. 48).

State (5) (pp. 50–54):

• Stateless: decide per packet, nothing installed. Soft state: installed when needed, removed if not refreshed. Hard state: installed by signaling, kept until removed.
• Hard state makes per-packet decisions fast but costs setup time and makes recovery harder; long flows amortize the setup, short transactions do not (5A).
• Ways to reduce state: aggregate over time (per flow, not per packet), over space (per group of nodes), update less often or only on significant change, limit how far updates travel, compress (5B, p. 52).
• Scope of information (5D): with a high bandwidth–delay product, a decision that needs a round trip or global state comes too late; decide quickly on local information (p. 53).

Control latency (6) (pp. 54–60):

• Minimize round trips (6A). A request/response can be cut to 1 round trip and a sender-initiated transfer to half of one (p. 55). Three techniques: hop-by-hop acknowledgments (a PROCEEDING message lets each hop use a short timer instead of waiting for an end-to-end timeout, Fig. 2.11); parameter ranges instead of single values (a request for “4–10” is cut to 8 by one node and 5 by the receiver in one pass, instead of several REJECT/retry rounds, Fig. 2.12); and overlapping control with data.
• Open-loop control acts on what is known in advance about the path; closed-loop control reacts to feedback. Use open loop to avoid waiting for the loop to converge (6D, p. 59).
• Separate control mechanisms (6E): treating every loss as congestion is wrong on lossy links. The right response to errors (retransmit, add FEC) increases load, which is exactly the wrong response to congestion (p. 60).

Data and PDUs (7, 8). Structure data so something useful can be processed early (p. 61). Small PDUs multiplex well but leave little time per packet; large ones are efficient but delay other flows; fixed sizes simplify switches but force segmentation and reassembly (8A, p. 62). Fields should be byte aligned and fixed length (8B). Timers and sequence numbers must have enough bits for future RTTs and bandwidth–delay products (8C, p. 63).

Design techniques (pp. 63–72)

• Scale time and space: either speed up the clock (more bandwidth) or move the applications closer (less propagation). Clock speed cannot fix propagation (pp. 63–64).
• Mask the speed of light: prediction, caching and mirroring, prefetching and presending, autonomy, moving code to the data (pp. 64–65; Ch 8 has the details).
• Specialized hardware helps only for functions on the critical path (p. 65).
• Parallelism and pipelining: converting a bit-serial link to a byte-wide path is an easy 8× (p. 66). n-way parallel hardware costs at least n times as much, and parallel software on one processor usually slows down. An n-stage pipeline gives up to n× throughput; the slowest stage sets the clock, so split long stages (pp. 66–67).
• Order fields for pipelines (pp. 68–69): fields that decide what to do with the payload (connection ID, address, QoS) go in the header; fields computed over the data (checksum) go in the trailer. Then a pipeline much shorter than the packet can process it as it streams through. TCP’s checksum sits in the header and breaks this; an interface can add an internal trailer copy.
• Packet size (p. 69): smaller packets mean less time per packet, which pushes decisions from general-purpose CPUs to embedded controllers to custom hardware. Fixed sizes should be powers of two to fit memories (e.g. 128-byte payload and 16-byte header). Avoid fragmentation and layered multiplexing.
• Example 2.2, the ATM cell (p. 70): 53 bytes (48 + 5), neither a power of two. It was kept small so voice would not need echo cancellation. Cells arrived every 2.73 µs at OC-3 and 682 ns at OC-12, which forced control logic into VLSI instead of microcontroller software and delayed commodity ATM interfaces by a year or two, “which allowed time for 100-Mb/s Ethernet to become the technology of choice”. A 40-byte TCP ACK needs 2 cells.
• Cut-through paths: when the output is free, bypass the FIFO instead of queuing (Fig. 2.16, p. 71). Remapping: hand over a pointer instead of copying a block (Fig. 2.17, pp. 71–72).

Trading-network lens (my mapping)

All of this section is my own application of the book; arithmetic and physics are No single source.

The delay model with today’s numbers. Serialization b/r for one frame (frame bytes only; preamble and inter-frame gap add 20 bytes on the wire):

Propagation: light in fiber covers about 1 km in 4.9–5 µs (refractive index ≈ 1.47), in air about 1 km in 3.3 µs. So a 100 m cross-connect costs about 0.5 µs one way, and over 1000 km a straight-line radio path beats fiber by more than 1.5 ms one way, before counting that fiber routes are longer than the straight line.

What this means:

• In a colocation the t_p propagation term is small, so the (1 + h + c) terms and the time inside hosts and applications dominate. The book’s WAN-centric advice (cut propagation) turns into: remove hops, store-and-forward and copies.
• With 1500-byte frames, three store-and-forward hops add 3.6 µs of serialization alone at 10 Gb/s; cut-through leaves roughly the header time per hop. With small market data frames the gap is smaller, so measure before buying.
• Cut-through has limits that match the book’s Fig. 2.16: it only works when the output port is free. A queued frame waits; and switches generally store and forward when the egress port is faster than the ingress port (an underrun risk). No single source.

Critical path dependency (1B, third observation). A feed handler must process messages in sequence order. A rare message type handled on a slow path, or a gap waiting for recovery, delays every message behind it. That rare path is on the critical path.

Measure before optimizing (1A). Break tick-to-trade into wire → NIC → host stack → application → host stack → NIC → wire and time each part with hardware timestamps. Optimize the largest term first.

Header first, checksum last (2.4.5.1). Ethernet already follows this ordering: destination address first, FCS at the end. That is what lets a cut-through switch forward after reading the header, and it is also why a cut-through switch cannot drop a corrupt frame: the FCS arrives after forwarding has started, so the error only shows up downstream. No single source.

Interrupts vs polling (4H) and resource trade-offs (2A). Trading hosts dedicate CPU cores to busy-polling the NIC: cores became cheap enough that burning one to save the interrupt and wake-up latency is a good trade. The book’s principle, with today’s prices.

Separate control mechanisms (6E) and loss characterization (L-4F). UDP market data has no congestion control, so loss comes from buffer overflow (microbursts) or line errors. Check which: output discards on the switch point to bursts, CRC errors point to a bad link. See ../multicast/02-microburst-buffer.md.

Hard state amortized (5A) and minimize round trips (6A). Order-entry sessions are opened and logged in before the market opens, and feed handlers join their multicast groups at startup, so setup round trips stay off the critical path during trading.

Self-check

1. Write the delay equation. Which term does cut-through switching attack, and which one does a zero-copy host stack attack?
2. Path segments of 50, 2, 25 and 10 µs: which one should you leave alone, and which principle says so?
3. Why can an operation that hits only 1% of packets still be on the critical path?
4. Why should a checksum live in the trailer rather than the header?
5. When is polling better than interrupts, according to the book? Why do trading hosts take it further?
6. Give one open-loop and one closed-loop way to recover lost market data.
7. A path has a one-way delay of 1 ms at 10 Gb/s. How much data is in flight, and why does that hurt feedback control?