Ch 7: End-to-end protocols

Source: Sterbenz & Touch 2001, Ch 7 (pp. 343–429), read in full. Page numbers are the book’s printed pages. This chapter gives the vocabulary for how market data and order traffic are protected: open-loop vs closed-loop control, ARQ vs forward error correction vs plain repetition, and why stale data is no better than lost data.

The chapter in one paragraph

The transport layer turns hop-by-hop services into an end-to-end path: framing, multiplexing, connection state, error control, flow control and congestion control. At high data rates, data transfer shrinks but round trips do not, so every mechanism that waits for feedback (setup, acknowledgment, retransmission) dominates the delay. The book’s answer: use open-loop control where you know the path (rate control, FEC, redundancy), keep closed-loop control for what really needs it, decouple error control from flow and congestion control, and let the application frame its own data when it can handle loss and reordering better than the transport.

The end-to-end arguments, used properly (pp. 345–352)

• Per-hop checks are not enough: errors happen between the protected links, from software bugs, poorly designed NICs and memory errors in routers [Stone 2000]; only an end-to-end checksum catches them (pp. 346–347).
• Hop-by-hop copies of an end-to-end function are worth it when they help end-to-end performance (T-3A): Ethernet’s fast local error detection, link-level FEC or retransmission on lossy wireless links (p. 347).
• Two common misreadings (p. 348): E2E-Only (never duplicate an end-to-end function per hop) and Everything-E2E (push everything to the endpoints). The book rejects both; ask instead whether the per-hop copy improves end-to-end performance. That is why it questions SONET protection switching (see Ch 5).
• “In the network” has three meanings (p. 350): functional (which layer does it), topological (where the box sits), administrative (who owns it).

Mechanisms and service models (pp. 352–357)

• Six end-to-end mechanisms: framing, multiplexing, connection/state management, error control, flow control, congestion control (pp. 352–353).
• Service model: transfer mode (datagram, connection, transaction, continuous stream), reliability, delivery order, traffic characteristics (pp. 353–354).
• Transport protocols range from general purpose (TCP) to modular, application-oriented and special purpose; what matters is that unneeded services do not slow down the needed ones (T-IV, p. 355).

Open-loop vs closed-loop control (pp. 357–359)

• Open loop: the sender acts on state set up in advance from what is known about the path (rate control, FEC). It needs a-priori knowledge and does not adapt.
• Closed loop: the sender adjusts from feedback, end-to-end or helped by hop-by-hop feedback. It must converge fast without oscillating (T-6Da); additive increase/multiplicative decrease is the usual balance. Closed loops only pay off for associations lasting many round trips.
• “Closed-loop control mechanisms are sensitive to both round-trip time and the bandwidth–delay product; open-loop control is not. Thus, as network bandwidth increases … there is incentive to rely more heavily on open-loop control” (p. 359).

What high speed does to state (pp. 360–364)

• Connection shortening (pp. 360–362, Fig. 7.6): higher rates shrink the transmission time but not the propagation time. As the rate goes to infinity, reliably delivering a block takes about 1.5 RTT (handshake plus data plus final ACK), and one mid-stream retransmission pushes it to about 2.5 RTT.
• State updates come more often, and the two ends are always at least one propagation delay out of sync (one RTT if you ask for the other side’s state) (pp. 362–364).
• Reliable multicast needs O(n) state and control messages for 1-to-n and O(n²) for n-to-n unless aggregated; many multicast applications do not need full reliability and can lean on open-loop control and soft state (p. 364).

Transfer modes (pp. 364–373)

• Datagram (p. 365): no setup, so the delay is just transmission plus propagation. “A datagram transport protocol (such as UDP or TP0) has only framing and multiplexing functionality. The lack of end-to-end state establishment does not allow for any closed-loop control.” Reliability can only be improved statistically. When an application periodically synchronizes state and needs only some messages delivered, “retransmission of information is best handled in application state machines”.
• Connection (pp. 365–369): a three-way handshake; the initiator can send after about 1 RTT, the called side after about 1.5 RTT. Phases: establishing, initializing (until state converges, e.g. slow start), steady state, closing. If any part of the path is connectionless, the transport must manage the connection itself (p. 367).
• Transactions (pp. 370–371): put the setup and the request in one packet and the acceptance and first data in one reply, for a single round trip (T-6A).
• Continuous media (pp. 371–373): timing beats completeness. “A packet that is significantly out of order is no better than a lost packet.” Use a playout buffer to absorb jitter and reorder (T-I.2), with open-loop error and rate control plus occasional feedback. Hop-by-hop reliability can hurt here, because link retransmissions reorder the stream.

Keeping state cheap (pp. 373–378)

• Hard state is deterministic; soft state adapts and survives failures (T-5A).
• Share state across connections between the same hosts (RTT, path MTU), spatially or over time, so new transfers skip initialization; “state shared is fate shared” (T-5B, pp. 374–377). Examples: T/TCP (Example 7.3), persistent HTTP connections (Example 7.4).
• Start new connections from past estimates so they converge faster (T-5E, p. 378).

Framing and multiplexing (pp. 378–386)

• Packet size at the transport layer (pp. 378–382): small packets mean more frequent per-packet state updates; large packets reduce that but coarsen control and delay others at multiplexing points (Fig. 7.14, the same picture as the burst collision of Fig. 5.25). Grouping small messages (e.g. Nagle’s grouping of Telnet characters into one TCP packet, p. 380) saves overhead, but “multiplexing small ADUs or control messages into a single larger packet can be difficult, and may cause unacceptable delay to wait to fill the packet” (p. 381).
• Find the path MTU and never fragment hop by hop (T-5F, p. 382).
• Application Layer Framing (pp. 382–383): match application data units to transport units so the application can place data as it arrives and handle loss and reordering itself, and so packets can be prioritized individually (T-4C).
• Multiplex once, not at every layer (T-4A, pp. 384–386); each extra multiplexing point adds delay and merges flows into shared fate.

Error control (pp. 386–400)

Errors (pp. 386–390): bit errors are rare on fiber (around 10⁻¹²); on wired networks most loss is congestion, often as bursts. Misordering comes from multiple paths, striping, multi-path fabrics, retransmissions and reroutes; “in high-speed networks it is better to avoid the latency of retransmission with receiver reordering” (p. 388). Losing one fragment means resending the whole packet, which can drive congestion collapse (p. 389).

Sequence numbers (p. 391): the space must not wrap while old packets can still be alive: 2ⁿ > (t_rexmit + 2·t_MPL + t_ACK)·r_pkt [Watson 1981]. Fields tied to the bandwidth–delay product need room or a scale factor (T-8C).

Closed-loop retransmission (ARQ) (pp. 391–397):

• Go-back-n: one loss stalls the stream for more than an RTT and resends everything after it; it couples error and flow control.
• NAKs: faster and fewer messages when loss is rare, but the sender cannot tell a silent receiver from a dead one, so NAKs need a liveness poll.
• Fast retransmit: several duplicate ACKs signal a loss before the timer expires (TCP uses three).
• Selective repeat: the receiver buffers and acknowledges out-of-order packets; with rate-based flow control this decouples error, flow and congestion control (T-6E).
• ACK aggregation: piggybacking, delayed ACKs, bit vectors.
• Multicast ACK implosion (Fig. 7.18): if every receiver acknowledges the source, the links near the root drown; use NAKs with polling, aggregate ACKs in the tree, or retransmit locally.
• Timers: too short wastes retransmissions, too long wastes time; estimate RTT with an average plus variance.

Open-loop error control (pp. 398–400) fits when all of these hold: the application tolerates some statistical loss; it has (near) real-time latency needs that a retransmission round trip would break; the path is long or has a high bandwidth–delay product; and the receivers can absorb the extra data and decode it.

• FEC adds h check bits to b data bits, costing (b+h)/b bandwidth versus roughly n·b for ARQ retransmissions at retransmission probability n. “If loss in a network is primarily due to congestion, then using FEC will reduce the goodput of the network” (p. 399). Use FEC for low-latency open-loop control when bandwidth is available and statistical loss is acceptable (T-6De).
• Hybrid: FEC sets a reliability floor, ARQ provides full reliability for those who need it.
• Repetition (p. 400): plain resending is “rarely useful”, because a simple erasure code gives the same protection with less overhead (1.5× for a 2-out-of-3 code vs 2× for sending everything twice), and repeats sent back to back do not survive burst errors. Two variants are useful: periodic updates of state where a lost message only slows convergence, and spatial redundancy, sending copies over several paths (flooding, spray routing).

Flow and congestion control (pp. 400–422)

• Flow control matches the receiver; congestion control matches the network. Explicit congestion signals let error, flow and congestion control be decoupled; implicit control (inferring congestion from loss) couples them (pp. 400–401).
• Windows must scale with the bandwidth–delay product (p. 402).
• Open-loop rate control (pp. 402–407): works if the path and receiver are known and stable (overprovisioned bandwidth, a provisioned path, or a reservation with admission control), with policing at the network edge. Rate parameters: peak r_p, average r_a, burstiness. Average-rate allocation works only if bursts interleave; they collide (Fig. 5.25), so the real requirement lies between them, r_a < R < r_p. “Statistical multiplexing gains assume that burst arrivals are not correlated; if they are, then more resources will have to be allocated” (p. 407).
• Knee and cliff (Fig. 7.22, pp. 409–411): past the knee, throughput stops rising and delay starts rising as queues build; past the cliff, the network collapses. Congestion avoidance keeps you left of the knee (T-II.4c); congestion control only keeps you left of the cliff.
• Closed-loop window control is self-clocking and conserves packets; TCP uses slow start (exponential) then AIMD, which is stable and fair (pp. 411–415, Example 7.8). Implicit control mistakes link errors for congestion and cuts the window needlessly (p. 415).
• Hybrids (pp. 417–421): dynamic rate control (ATM ABR explicit rate) and pacing packets within the window instead of sending bursts at line rate.
• Example 7.9, TCP for high speed: window scaling, timestamps (RTT measurement, PAWS), SACK, fast retransmit, larger initial window, header prediction from predictable fields (pp. 420–421).

Security (pp. 422–427)

• Only end-to-end security protects end to end; link or edge-to-edge encryption only lowers exposure on part of the path (p. 423). Encryption must come after compression and coding, and hides application information that network services might need (p. 424).
• Key exchange takes several round trips: amortize it over many interactions (p. 425).
• Encryption and per-packet authentication touch every bit, so they are critical-path work (T-1B); MD5 ran at about half the clock rate in MB/s on CPUs of the day, encryption about 10× slower (pp. 425–426).

Trading-network lens (my mapping)

Market data is the datagram case. UDP multicast feeds have no connection and no closed loop at all (p. 365). Reliability moves into the application: the feed’s own sequence numbers, gap detection and recovery logic are Application Layer Framing (T-4C) in practice.

A/B feeds are the book’s spatial redundancy. Sending every packet twice over separate networks is repetition, which the book calls “rarely useful” next to erasure codes. A/B pays 2× bandwidth anyway for three reasons the book’s own principles explain: it survives the loss of a whole path, not just of packets; the first copy to arrive wins, so it adds no decode delay; and the redundant copy does not add load to the congested link, which FEC on the same path would (p. 399). See ../multicast/03-failure-modes.md for how RPF problems can silently remove the B side.

Snapshots are periodic updates. Snapshot or refresh channels resend the current state periodically; a lost update only delays convergence (p. 400). Recovering by snapshot is open loop; asking a retransmission server for the missing range is closed loop and costs at least a round trip.

Recovery is NAK-based, so liveness needs heartbeats. Multicast receivers cannot acknowledge (ACK implosion, Fig. 7.18), so recovery is receiver-driven, the book’s NAK case. NAKs need a liveness check, which is what feed heartbeats provide: silence is only meaningful if the feed promises to say something regularly. No single source.

Late is as bad as lost. “A packet that is significantly out of order is no better than a lost packet” (p. 371), and the book’s real-time rule says not to trade timeliness for reliability (T-I.2). A feed handler that waits too long for a gap fill delivers stale prices, the same point as the Arista Primer’s buffering remark in ../multicast/02-microburst-buffer.md.

Round trips are what remain. Connection shortening (Fig. 7.6) is why any recovery that needs a round trip is so expensive at today’s rates: the data takes nanoseconds to send, a retransmission takes at least an RTT plus detection time. On sparse order-entry TCP sessions there may be no later packets to produce duplicate ACKs, so a lost segment waits for the retransmission timer. No single source for the order-entry part.

Do not wait to fill packets. Grouping small writes saves per-packet overhead but delays the first message (p. 381); order-entry sockets usually disable Nagle’s algorithm (TCP_NODELAY) for this reason. No single source.

Correlated bursts break statistical multiplexing. A market-wide event makes every feed burst at the same moment, which is exactly the correlated case of p. 407. Links that carry several feeds must be sized near the sum of the peaks, not the averages. No single source.

Stay left of the knee. Queuing delay grows well before any loss (Fig. 7.22), so latency-critical links are run at low average utilization. No single source.

Self-check

1. What are the two common misreadings of the end-to-end arguments, and what is the right question to ask instead?
2. Why does reliable delivery approach 1.5 RTT at very high data rates, and what does one retransmission do?
3. What control is possible for a datagram transport such as UDP, and where should retransmission logic live for periodically synchronized state?
4. List the four conditions under which the book recommends open-loop error control. Does market data meet them?
5. Why does the book say pure repetition is rarely useful, and why do A/B feeds use it anyway?
6. Why can’t the receivers of a multicast stream simply acknowledge the source, and what do NAK-based schemes need instead?
7. What does grouping small messages into one packet trade, and why do order-entry sockets avoid it?
8. Where does the bandwidth a bursty flow needs lie, and what makes it rise toward the peak?