Ch 5: Network components (links and switches)

Source: Sterbenz & Touch 2001, Ch 5 (pp. 165–284), read in full. Page numbers are the book’s printed pages. This is the chapter that matters most for trading networks: how a switch can forward without store-and-forward, where buffers sit, what head-of-line blocking costs, and why packet rate matters more than bandwidth.

Numbering note: the packet-rate principle is printed as “S-II.4p” on p. 254 but listed as S-I.3 in Appendix A. These notes use the Appendix A IDs.

The chapter in one paragraph

Links: propagation speed depends on the medium; link protocols should scale with rate; the Ethernet story shows a protocol surviving by turning into a switched point-to-point mesh. Switches: old routers were slow because every packet crossed a shared bus into a shared CPU and memory and was stored before forwarding. Fast packet switches fixed this with per-connection state, hardware pipelines and cut-through. The fabric is where blocking happens: buffer placement, head-of-line blocking, virtual output queues, crossbars and multistage networks, and how to replicate multicast. IP switches then had to do the same at line rate without connection state, which turns lookup, classification and scheduling into the hard problems.

Links (pp. 167–194)

Propagation speed (pp. 167–169): v = c/n. Fiber glass has n ≈ 1.45–1.48, so light travels at about 0.68c. The fastest media are vacuum (1.0c), air and some coax (very near 1.0c); the slowest are fiber and twisted pair (about two-thirds of c). The propagation speed has nothing to do with a link’s “speed”, which is its symbol rate (p. 167).

• Fiber limits (pp. 170–171): attenuation leaves a usable window of about 800–1700 nm (about 20 THz), and dispersion (intermodal, chromatic, polarization mode) limits the bandwidth–distance product. Multimode fiber (50–85 µm core) is cheap and short; single-mode (8–10 µm core) plus erbium-doped fiber amplifiers made long-haul possible.
• Wireless (pp. 171–173): received power falls with 1/r² in free space and faster with multipath (exponent toward 4 in cities). To higher layers a fading channel looks like randomly varying capacity.
• Three link classes (pp. 176–182): dedicated point-to-point, multiplexed (TDM, WDM), shared medium (which needs addresses and a MAC protocol). Link protocols should scale with bandwidth (L-8C): SONET was designed to; Ethernet had to be reworked for each generation (p. 176).
• Example 5.1, SONET (pp. 177–179): STS-1 is 51.84 Mb/s with an 810-byte frame every 125 µs, timed for PCM voice. OC-192c carries 9.95 Gb/s on the line and 9.62 Gb/s of payload (Table 5.3). Packet over SONET runs IP over PPP over SONET.
• WDM (pp. 180–181): 4–8 OC-192 channels per fiber in the late 1990s, over 1 Tb/s feasible in the early 2000s; fiber nonlinearities (Raman and Brillouin scattering, cross-phase modulation, four-wave mixing) trade the number of wavelengths against distance.
• Example 5.2, Ethernet (pp. 182–185): CSMA/CD kept delay fairly uniform up to about 50% offered load and rose sharply around 80%, so shared Ethernet should stay below about 50% load for low latency (p. 182, footnote 7). The frame is preamble + SFD, a 14-byte MAC header, payload, and a 4-byte FCS trailer. The 512-bit slot time limited a collision domain to 2,800 m at 10 Mb/s and 205 m at 100 Mb/s; Gigabit Ethernet added carrier extension and frame bursting, neither used in full duplex. Ethernet won by becoming a switched point-to-point mesh while keeping its frame (p. 183).
• Link-layer components (pp. 188–192): optical amplifiers every few hundred km, electronic regeneration (2R/3R) every few thousand km; bridges became learning bridges, then hubs, then layer 2 switches. They must keep up with line rate without adding significant delay (L-IIc).
• Example 5.3, SONET rings (p. 191): automatic protection switching wraps the ring around a cut. The book prints “50 µs is the standard recovery time” (checked on the page image); the standard figure is 50 ms (see the verification log in the group README). The book’s real point: APS duplicates what IP rerouting should do (End-to-End Argument), but IP routing of the day converged too slowly to replace it.
• Support for higher layers (pp. 192–195): tell upper layers why loss happened (L-4F), and fix problems at the lowest layer that can react; filter early — discard frames not meant for you as low and as early as possible (L-4f); switched LANs must still offer broadcast and multicast (L-2C).

What a switch does (pp. 195–201)

Why traditional routers were slow (pp. 199–201): a computer with network interfaces on a bus. Every packet paid the store-and-forward time t_b; packets competed for one CPU and one memory, which raised the forwarding delay t_f; and every packet crossed the bus twice, which capped the number of interfaces. Moving processing onto the interfaces with bus-master transfers (NSFNET routers, mid-1990s) removed the CPU bottleneck but kept a store-and-forward hop on each interface and the single bus.

The ideal switch (p. 201): R = ∞, D = 0 and unlimited ports. “In the ideal case, nodes should pipeline and cut through packets with zero per packet delays” (S-II.3).

Fast packet switches (pp. 202–225)

• Goals (p. 202): simple per-packet work thanks to connection state, no store-and-forward, no shared bus, QoS guarantees.
• Label swapping (pp. 203–205): the connection ID (label) indexes a small, dense table that returns the outgoing label, the output port and the connection state. Labels are local to each hop and assigned by the downstream node; only incoming labels must be unique.
• Cut-through (p. 205): the input queue “need only be a per byte shift register that delays the packet long enough for a hardware-based index to return the new CID label and output port”. If nothing blocks inside the switch and the output is free, the leading edge of a packet leaves before its trailing edge has arrived; this is cut-through [Kermani 1979].
• Packet size (pp. 206–212): fixed cells make switch pipelines simple; variable packets avoid a global size decision and segmentation. Too large hurts short real-time packets queued behind them; too small leaves no time to decide. Processing budget per packet (Table 5.4, p. 207):

• Middle grounds: a few discrete packet sizes (the book even suggests scaling the cell with the link rate, 64 B at OC-3 up to 4 KB at OC-192, to keep the packet time constant), or variable packets on the links with segmentation into internal cells inside each switch, which adds latency and still leaves a flow exposed to the largest packet on the link (pp. 209–211).
• Packet structure (pp. 213–215): the header carries what is needed before the packet enters the fabric (protocol ID, type, connection ID, QoS, length, header check); the trailer carries what is computed over the payload (CRC). The trailer is “essential to allow cut-through if a packet can be longer than the data pipeline in a node”. Fields byte aligned and simply encoded (S-8B).
• Example 5.4, ATM (pp. 216–217): a 53-byte cell left a budget of 2.8 µs at OC-3 and about 700 ns at OC-12, which only full-custom chips could meet; segmentation chips arrived more than a year after interface chips. With no sequence number, cells had to stay in order, which ruled out path diversity and striping.
• Example 5.5, MPLS (pp. 218–219): a 4-byte shim with a 20-bit label, 3-bit class of service, bottom-of-stack bit and 8-bit TTL; label stacks generalize ATM’s two-level VP/VC hierarchy; labels are distributed by LDP or RSVP-TE.
• Traffic management (pp. 219–223): the leaky bucket polices average rate and burst size (a one-token bucket polices peak rate); excess traffic is dropped or marked. Four hop-by-hop congestion-avoidance tools: admission control, input policing, a congestion bit, output shaping (S-6Cc). If bandwidth is cheap, overprovision and keep the algorithms simple (S-2B). Separate queues per class, or per connection, keep bursty TCP from hurting streaming traffic (p. 222).
• Hardware vs software (pp. 223–224): the datapath has to be hardware. “FPGAs (field programmable gate arrays) have dramatically increased in performance and reliability in the late 1990s, making them a candidate for such applications” (p. 224).

Switch fabrics (pp. 226–249)

• Fabric control: centralized, distributed (per input port), or self-routing (an internal header steers the packet) (p. 226).
• Blocking: strictly nonblocking, wide-sense nonblocking (nonblocking if paths are chosen by an algorithm), rearrangeably nonblocking (may reroute existing paths), virtually nonblocking (blocking so rare it is second order, e.g. one drop per hour on an OC-192 link) (pp. 226–227). Prefer strictly or wide-sense to avoid rearrangement delay (S-II.4f).
• Burst collision (Fig. 5.25, pp. 227–228): two well-behaved bursty flows heading for the same output will overlap whenever their burst lengths differ. “This happens even when the aggregate bandwidth can be handled on the output link.” So the switch must buffer somewhere, or drop.
• Buffer placement (pp. 228–230): unbuffered (optical switches), internally buffered fabric, input queues, output queues, both, or a central shared buffer.
• Head-of-line blocking (pp. 230–232): with FIFO input queues, a packet for a free output waits behind one for a busy output, capping throughput at 2 − √2 ≈ 58.6% [Karol 1987]. Output queuing avoids it but needs the fabric to drain inputs fast enough: speedup (worst case S = n; in practice “several times”; strict nonblocking with speedup 2 and an O(n) scheduler), internal buffering, or internal expansion such as a Clos network (S-II.4q).
• Virtual output queues (pp. 232–233): one queue per output at every input (n² queues) or non-FIFO linked lists, plus a scheduler that matches inputs to free outputs.
• Bus fabric (pp. 233–234): aggregate rate w/t for width w and clock period t, shared by all ports; good for 8 to 32 ports at most; multicast is free.
• Shared memory fabric (pp. 234–236): memory density grows exponentially but access time does not; “cut-through paths are not easily supported and packets must typically be completely read into memory before being output” (p. 235).
• 2×2 elements and crossbars (pp. 236–241): elements have straight, cross and duplicate states (duplicate = multicast). A crossbar needs n² crosspoints, is internally nonblocking, and an electronic crosspoint passes the row on even when it turns the signal, so multicast comes for free (p. 239). Practical single-stage size is up to about 128 ports; 1,024 ports would need over a million crosspoints. Optical MEMS crosspoints switch in microseconds; LiNbO3 couplers in about 1 ns.
• Multistage networks (pp. 241–246): O(n log n) elements. A delta network is self-routing (each stage reads one bit of the output port) and keeps packets in order, but loads links unevenly; adding randomizing stages (Benes) balances load but reorders packets, so outputs need resequencing buffers. Slicing the datapath across m parallel planes gives m× speed, but there is no point going faster than the input and output processing.
• Multicast in the fabric (S-2C, pp. 246–249): “Switches should provide native multicast support to conserve bandwidth and avoid latency of repeated transmission.” In a crossbar, a multicast packet may find only some of its outputs free. No fanout splitting waits until all are free; fanout splitting serves the free ones now and keeps the rest (the residue) for later, which is work-conserving and gives higher throughput. Schedulers trade throughput (concentrate the residue) against fairness (weight by waiting time). Multistage switches use a copy network followed by a routing network, making copies as late as possible.

Fast datagram (IP) switches (pp. 249–274)

• Why IP won (pp. 249–250): TCP/IP was entrenched, and Ethernet became switched and fast. So: apply the fast-packet-switching techniques to datagrams (S-1Bd).
• Architecture (pp. 251–253): per-port forwarding processors, or a pool of shared forwarding engines (headers cross the fabric; scales the packet rate independently of ports).
• Packet rate (pp. 253–254): Internet packets were 40–1500 bytes, almost half at or near the minimum. The rule of thumb of 1 Mpps per Gb/s assumes 1,000-bit average packets, but anything serial in the pipeline must keep up with minimum-size packets, or one small packet delays the rest; a 64-byte frame on Gigabit Ethernet already needs more than 1.5 Mpps. Parallel forwarding engines can be sized for the average, but they reorder packets and add jitter (S-I.3).
• Lookup (pp. 254–268):
  • A directly indexed table is impossible for 32-, 48- or 128-bit addresses.
  • Judge an algorithm by its worst-case lookup time, memory and update time. “Occasional worst-case lookup times may delay subsequent lookups, causing packets to back up in an input queue and be dropped” (p. 256). Updates had to be fast too: route flapping in the 1990s meant up to 100 updates per second.
  • Options: trees (O(log N)), hashing (one access unless collisions; source hashing; the IPv6 flow label), binary CAMs for exact matches (about 10× the cost per bit of RAM, and power-hungry), tries for longest prefix match (worst case 32 memory accesses for IPv4, 128 for IPv6) with path compression and multibit strides, ternary CAMs with a priority encoder, and a two-level direct table because most prefixes are 24 bits or shorter [Gupta 1998].
  • Example 5.6, IP: forwarding means lookup, TTL decrement and an incremental checksum fix; IPv4 software forwarding took about 200 RISC instructions when the route was cached. IPv6 simplified things: fixed 40-byte header, flow label, no header checksum, no fragmentation by routers.
  • By the end of the 1990s “datagram lookup is now generally considered a solved problem” (p. 268).
• Classification (pp. 268–271): classify before any queuing, within the delay bound of the strictest class (S-II.4c). Geometrically, rules are boxes in an F-dimensional space of header fields; the best algorithms take O((log n)^(F−1)) time with O(n) memory, or O(log n) time with O(n^F) memory. Hardware: TCAMs or parallel matchers; software: grid of tries, tuple space search.
• Output scheduling (pp. 271–274): needed whenever admission control does not bound the input. Fair queuing approximates generalized processor sharing; WFQ costs O(N) per packet in the number of flows, so aggregate into classes and use hierarchical link sharing. Per-flow queues protect short interactive flows from bursty long TCP flows. Keep queues short and drop early (RED) so congestion is signaled before collapse (S-6Cd).
• Active network nodes (pp. 274–279): research of the time; the lasting rule is that extra processing must not slow the fast path (S-II.4a).

Trading-network lens (my mapping)

The medium is a latency choice. From the book’s Table 5.1: fiber about 5 µs/km, radio about 3.3 µs/km, so a straight radio path saves about 1.7 ms per 1,000 km one way. Inside a building, fiber costs about 5 ns per metre, so cable lengths matter only at the nanosecond level. Arithmetic from the book’s table.

Layer-1 switches are the book’s unbuffered crossbar. Arista’s 7130 Connect series forwards port to port in 4 ns with “full signal recovery and regeneration”, does “not buffer or queue data”, and allows one-to-many connections with the same latency (vendor product page, checked: https://www.arista.com/en/products/7130-connect). That is the book’s electronic crosspoint with its free duplicate state (p. 239), used for market data fan-out. The price of having no buffer: two inputs cannot be merged onto one output at layer 1; merging needs a device with buffering and arbitration.

Burst collision is the microburst. Fig. 5.25 is the fan-in problem described by Arista and Pico: feeds that each fit the egress link on average still collide in time, and the switch must queue (latency) or drop (gaps). See ../multicast/02-microburst-buffer.md.

Packet rate, not bandwidth. Market data messages are small, and bursts arrive as packet-rate spikes. At 10 Gb/s a minimum 64-byte frame plus 20 bytes of preamble and gap is 67 ns, or 14.88 million frames per second. Whatever is serial in a NIC, kernel or feed handler must keep up with the worst case (S-I.3); spreading flows over cores, like the book’s parallel forwarding engines, raises throughput but must hash per flow so each feed stays in order. Arithmetic is No single source; the core-spreading comparison is my mapping.

Worst case, not average (p. 256). The book’s warning about an occasional slow lookup backing up the queue applies to any per-message step on the hot path, such as an order-book update that sometimes allocates memory.

Multicast replication has its own scheduling. When a switch replicates a market data packet to many egress ports, a busy output delays only its own copy if the switch splits the fanout, or holds everything if it does not. Latency can therefore differ between subscriber ports of the same switch. My mapping; check the specific switch’s documentation.

Classify at ingress (S-II.4c). QoS marking and ACLs must act at line rate before queuing, so a strict-priority queue for orders actually protects them. My mapping.

FPGAs (p. 224). The book already notes FPGAs as a fast, reprogrammable middle ground for packet processing; trading later put feed handling and order entry on FPGA NICs and switches. No single source.

Protection switching vs redundant feeds. SONET protection takes up to 50 ms and IP reconvergence takes longer, while redundant A/B feeds lose nothing during a single failure. See the JPX and MOEX cases in ../multicast/01-incidents.md. My mapping.

Self-check

1. From Table 5.1, what is the propagation delay per km in fiber and in air, and what does a straight radio path save over 1,000 km?
2. What does the input queue of a cut-through fast packet switch need to be, according to the book?
3. Why does the book say trailers are essential for cut-through?
4. What throughput limit does head-of-line blocking impose, and what are the ways around it?
5. What is the processing budget for a 128-byte packet at 10 Gb/s? For a minimum Ethernet frame including preamble and gap?
6. Why must serial pipeline stages be sized for minimum-size packets, while parallel engines can use the average? What does the parallel approach cost?
7. Two feeds each average 4 Gb/s but burst at line rate into one 10 Gb/s egress port. What does Fig. 5.25 predict?
8. What does the book get wrong about SONET protection switching?