4. The Data Link Layer
The physical layer hands up an unreliable stream of bits; this chapter is about turning that stream into something a network layer can actually build on — discrete frames, detected errors, arbitrated access to a shared medium, and delivery to the correct neighbour. It covers the mechanisms that make a single hop trustworthy, then the technologies that dominate real networks: Ethernet, switching, VLANs, and address resolution. Almost every "the network is broken" problem that is not a physical fault lives somewhere in this chapter.
<a id="41-framing-and-link-services"></a>
4.1 Framing and Link Services
This subchapter covers the first job of the link layer — imposing structure on a featureless bit stream — along with the service models a link can offer and the protocols that implement them.
Framing Methods: Byte Count, Byte Stuffing, Bit Stuffing
Theory
The physical layer delivers bits, one after another, with no punctuation. But the network layer needs packets — discrete units with a beginning and an end. Somebody has to decide where one unit stops and the next starts, and that job is framing.
The problem is harder than it looks. The obvious approach — put a special marker between frames — immediately runs into the question: what if that marker appears inside the data? The link layer must carry arbitrary bytes, including bytes that look exactly like whatever delimiter you chose. This is the same problem as putting a quotation mark inside a quoted string, and it has the same family of solutions.
Method 1: Byte count. Begin each frame with a field stating how many bytes follow. Simple and efficient. It has one catastrophic weakness: if the count field itself is corrupted, the receiver looks for the next frame boundary in the wrong place and loses synchronisation permanently — every subsequent frame is misparsed, and there is no way to recover except by some external resynchronisation. A single bit error destroys the entire stream, not just one frame. This is why byte count is never used alone.
Method 2: Byte (character) stuffing. Mark frames with a special flag byte at each end. When that byte value occurs in the payload, the sender inserts an escape byte before it; if the escape byte itself occurs, it too is escaped. The receiver removes escapes and treats any unescaped flag as a real boundary. PPP does exactly this with flag 0x7E and escape 0x7D, and — a neat touch — it also XORs the escaped byte with 0x20 so the problematic value never appears on the wire at all.
The cost is variable expansion: a payload consisting entirely of flag bytes doubles in size. The virtue is resynchronisation — after any corruption, the receiver simply waits for the next flag and is back in step.
Method 3: Bit stuffing. Operate on bits rather than bytes. HDLC uses the flag pattern 01111110 and the rule: whenever the sender transmits five consecutive 1 bits in the data, it automatically inserts a 0. The receiver, seeing five 1s followed by a 0, removes that 0. Since the flag contains six 1s, and data can never contain six consecutive 1s after stuffing, the flag is unambiguous.
Bit stuffing is more efficient than byte stuffing — worst-case expansion is 20 percent rather than 100 percent — and allows frames of any bit length, not just whole bytes. It is the classic choice for synchronous serial links (HDLC, SDLC, Frame Relay).
Method 4: Physical layer coding violations. The cleverest approach: use signals that the line code cannot produce from data. Since 4B/5B has 16 unused code words, some become start-of-frame and end-of-frame markers. There is zero overhead and zero ambiguity, because the delimiter is not a bit pattern at all — it is a symbol outside the data alphabet. This is why Ethernet's preamble and start-of-frame delimiter work so cleanly, and it is the same "reserve a code word for control" pattern seen in Chapter 3.
| Method | Overhead | Resynchronises after error | Used by |
|---|---|---|---|
| Byte count | Minimal | No — permanent loss of sync | DDCMP (with other safeguards) |
| Byte stuffing | 0–100% (data-dependent) | Yes | PPP, SLIP |
| Bit stuffing | 0–20% | Yes | HDLC, Frame Relay, USB |
| Coding violation | None | Yes | Ethernet, 802.11, FDDI |
In practice, real protocols combine methods. Ethernet uses a coding-based preamble plus an explicit length/type field plus a CRC plus a minimum interframe gap — defence in depth, because losing frame sync is so damaging.
Examples
Why byte count alone is fatal
intended: [5] A B C D E [3] X Y Z [4] P Q R S
one bit flips in the second count
received: [5] A B C D E [9] X Y Z [4] P Q R S ...
^ receiver now consumes 9 bytes as one frame,
then reads "S" as the next length field,
and is wrong FOREVER. No recovery point exists.
Byte stuffing (PPP): flag 0x7E, escape 0x7D, XOR 0x20
payload: 48 7E 65 7D 6C (contains both special bytes)
on wire: 7E 48 7D 5E 65 7D 5D 6C 7E
^^ ^^ ^^ ^^ ^^ ^^
flag escaped 7E escaped 7D
(7E^20=5E) (7D^20=5D)
The bytes 7E and 7D never appear inside the frame body.
Bit stuffing (HDLC): flag 01111110, stuff a 0 after five 1s
data: 0 1 1 1 1 1 1 1 1 1 1 0
stuffed: 0 1 1 1 1 1[0]1 1 1 1 1[0]1 0
^ ^ inserted zeros
Now no six-1 run exists in the body, so the flag is unmistakable.
FLAG, ESC, XOR_MASK = 0x7E, 0x7D, 0x20
def ppp_stuff(payload: bytes) -> bytes:
out = bytearray([FLAG]) # opening flag
for b in payload:
if b in (FLAG, ESC):
out.append(ESC) # announce an escaped byte
out.append(b ^ XOR_MASK) # transform so the raw value never appears
else:
out.append(b)
out.append(FLAG) # closing flag
return bytes(out)
def ppp_unstuff(frame: bytes) -> bytes:
body, out, escaped = frame[1:-1], bytearray(), False
for b in body:
if escaped:
out.append(b ^ XOR_MASK) # undo the transform
escaped = False
elif b == ESC:
escaped = True # next byte is escaped
else:
out.append(b)
return bytes(out)
payload = bytes([0x48, 0x7E, 0x65, 0x7D, 0x6C])
wire = ppp_stuff(payload)
print("payload:", payload.hex(" "))
print("on wire:", wire.hex(" "), f"({len(wire)} bytes for {len(payload)})")
print("recovered matches:", ppp_unstuff(wire) == payload)
# payload: 48 7e 65 7d 6c
# on wire: 7e 48 7d 5e 65 7d 5d 6c 7e (9 bytes for 5)
# recovered matches: True
def bit_stuff(bits: str) -> str:
out, ones = [], 0
for bit in bits:
out.append(bit)
ones = ones + 1 if bit == "1" else 0
if ones == 5: # five 1s seen -> force a 0
out.append("0")
ones = 0
return "".join(out)
def bit_unstuff(bits: str) -> str:
out, ones, i = [], 0, 0
while i < len(bits):
out.append(bits[i])
ones = ones + 1 if bits[i] == "1" else 0
if ones == 5:
i += 1 # skip the stuffed zero
ones = 0
i += 1
return "".join(out)
data = "011111111111" + "1" * 12
stuffed = bit_stuff(data)
print(f"\ndata ({len(data)} bits): {data}")
print(f"stuffed ({len(stuffed)} bits): {stuffed}")
print(f"expansion: {len(stuffed)/len(data)-1:.1%} (worst case is 20%)")
print("roundtrip:", bit_unstuff(stuffed) == data)
print("flag 01111110 present in body:", "01111110" in stuffed)
# data (24 bits): 011111111111111111111111
# stuffed (28 bits): 0111110111110111110111110111
# expansion: 16.7% (worst case is 20%)
# roundtrip: True
# flag 01111110 present in body: False
Key takeaways
- Framing imposes boundaries on the physical layer's undifferentiated bit stream so discrete units can be delivered upward.
- Byte count is efficient but catastrophically fragile: corrupting the count desynchronises the receiver permanently.
- Byte stuffing escapes flag and escape bytes in the payload (PPP uses
0x7E/0x7Dwith an XOR of0x20); worst-case expansion is 100 percent. - Bit stuffing inserts a 0 after five consecutive 1s so the
01111110flag can never occur in data; worst-case expansion is 20 percent. - Coding violations use symbols outside the data alphabet as delimiters, costing nothing and never colliding with data.
- Stuffing-based and coding-based methods allow the receiver to resynchronise at the next flag; byte count does not.
🧪 Practice
- Apply bit stuffing to
0111111011111110and state the result. Then unstuff your answer to verify.- Compute the worst-case on-wire size of a 1500-byte PPP payload under byte stuffing, and describe the payload that produces it.
- Interview-style: Ethernet uses a length field, yet corrupting it does not desynchronise the receiver the way byte count framing would. Why not? (Hint: consider what else marks the start of an Ethernet frame, and what the minimum interframe gap guarantees.)
Connectionless vs Connection-Oriented Link Service
Theory
Having established how to delimit frames, the next question is what service the link layer promises for them. There are three possible contracts, and they differ in whether delivery is confirmed and whether state is established beforehand.
Unacknowledged connectionless service. The sender transmits a frame and moves on. No connection is established, no acknowledgement is expected, and a lost or corrupted frame is simply gone — the link layer neither notices nor cares. Frames are independent; ordering is not guaranteed (though most media deliver in order naturally).
This is the model of Ethernet and almost all modern wired links, and the reasoning is the end-to-end argument from Chapter 2. On a medium with a bit error rate around 10⁻¹², errors are so rare that paying for per-frame acknowledgement on every frame would be absurd. Recovery is cheaper when handled end to end by TCP, on the rare occasions it is needed.
Acknowledged connectionless service. Each frame is individually acknowledged; unacknowledged frames are retransmitted after a timeout. Still no connection setup, so each frame stands alone — but delivery is confirmed hop by hop.
This is the model of 802.11 (Wi-Fi), and the reasoning is again about error rates. A wireless link may lose one frame in a hundred. Waiting for TCP to notice — a full end-to-end round trip, plus a congestion-window collapse because TCP misreads the loss as congestion — is far more expensive than retransmitting locally in microseconds. This is precisely the "lower-layer reliability as a performance optimisation" case that the end-to-end argument explicitly permits.
Connection-oriented service. The two ends establish a connection, exchange numbered frames with guaranteed in-order delivery and flow control, then tear the connection down. This is the strongest and most expensive contract, historically used by HDLC's balanced mode, X.25's LAPB, and LLC Type 2 for links that were genuinely unreliable — early leased lines with error rates around 10⁻⁵.
| Service | Setup | Acknowledged | Ordered | Error rate it suits | Example |
|---|---|---|---|---|---|
| Unacknowledged connectionless | No | No | Not guaranteed | Very low (10⁻¹²) | Ethernet, LLC Type 1 |
| Acknowledged connectionless | No | Yes | Not guaranteed | Moderate (10⁻²) | 802.11, LLC Type 3 |
| Connection-oriented | Yes | Yes | Yes | High (10⁻⁵) | HDLC/LAPB, LLC Type 2 |
The general principle is worth stating explicitly, because it recurs throughout networking: the right amount of link-layer reliability is a function of the link's error rate and the cost of end-to-end recovery. Reliable delivery on a fibre link is wasted work; unreliable delivery on a satellite or radio link is a performance disaster.
A crucial distinction that trips people up: acknowledged link service does not make the network reliable. Wi-Fi acknowledges each frame on the wireless hop, but the frame can still be dropped by a congested switch three hops later. Link-layer acknowledgement covers one hop only — end-to-end reliability remains the transport layer's job, exactly as the end-to-end argument requires.
Examples
Where each service model puts recovery
UNACKNOWLEDGED (Ethernet) — error handling deferred to TCP
A --frame--> B frame lost
A (silence; nobody at layer 2 notices)
...one end-to-end RTT later...
TCP at the far end detects the gap and retransmits.
Cost of a loss: 1 RTT + a congestion-window reduction.
ACKNOWLEDGED (Wi-Fi) — recovery is local and fast
A --frame--> B frame lost in the air
A (no ACK within SIFS + slot) -> retransmit immediately
A --frame--> B <--ACK-- succeeded
Cost of a loss: microseconds. TCP never even learns it happened.
CONNECTION-ORIENTED (LAPB) — state on both ends
A --SABM------> B set asynchronous balanced mode
A <--UA-------- B connection established
A --I(N(S)=0)-> B numbered information frames, windowed
A <--RR(N(R)=1) B receive ready: acknowledges and grants credit
A --DISC------> B teardown
import random
def simulate(link_loss_rate, service, rtt_ms=80, local_retry_ms=0.5, frames=10_000):
"""Compare recovery cost under each link service model."""
total_delay, retransmissions = 0.0, 0
for _ in range(frames):
attempts = 1
while random.random() < link_loss_rate:
attempts += 1 # frame lost, needs another try
if attempts > 1:
retransmissions += attempts - 1
if service == "acknowledged":
# Recovered locally: cost is a few hundred microseconds each.
total_delay += (attempts - 1) * local_retry_ms
else:
# Unacknowledged: TCP must notice, costing a full RTT each time.
total_delay += (attempts - 1) * rtt_ms
return total_delay, retransmissions
for name, loss in [("fibre (1e-9)", 1e-9), ("Wi-Fi (1e-2)", 1e-2)]:
for service in ("unacknowledged", "acknowledged"):
delay, retx = simulate(loss, service)
print(f"{name} {service:<15}: {retx:>4} retransmits, "
f"{delay:>9.1f} ms of recovery delay")
print()
# fibre (1e-9) unacknowledged : 0 retransmits, 0.0 ms of recovery delay
# fibre (1e-9) acknowledged : 0 retransmits, 0.0 ms of recovery delay
# -> on fibre, acknowledgement buys nothing and costs bandwidth on every frame
#
# Wi-Fi (1e-2) unacknowledged : 101 retransmits, 8080.0 ms of recovery delay
# Wi-Fi (1e-2) acknowledged : 98 retransmits, 49.0 ms of recovery delay
# -> on radio, local acknowledgement is ~165x cheaper in recovery time
Key takeaways
- Link layers offer one of three service models: unacknowledged connectionless, acknowledged connectionless, or connection-oriented.
- Ethernet is unacknowledged connectionless because wired error rates (~10⁻¹²) make per-frame acknowledgement pure overhead.
- 802.11 is acknowledged connectionless because radio error rates (~10⁻²) make an end-to-end recovery round trip far more expensive than a local retry.
- Connection-oriented link service (HDLC/LAPB, LLC Type 2) suits genuinely unreliable links and is now rare.
- The correct level of link reliability depends on the link's error rate and the cost of end-to-end recovery — this is the end-to-end argument's "performance optimisation" clause in action.
- Link-layer acknowledgement covers one hop only and never substitutes for end-to-end reliability.
🧪 Practice
- Classify Ethernet, 802.11, PPP without LCP reliability, and Bluetooth by service model, justifying each from its error environment.
- Explain why adding per-frame acknowledgement to Gigabit Ethernet would reduce throughput rather than improve reliability.
- Interview-style: Wi-Fi acknowledges every frame, so why does TCP still need retransmission when running over Wi-Fi? (Hint: think about how many hops exist between the two TCP endpoints, and which one Wi-Fi covers.)
LLC and MAC Sublayers
Theory
Chapter 2 mentioned that IEEE splits the data link layer into two sublayers. This topic explains why the split exists and why it turned out to matter less than its designers expected — which is itself an instructive story about standards.
The motivation was clean separation of concerns. Some link-layer functions depend intimately on the medium: how you arbitrate access to a shared coaxial cable is nothing like how you arbitrate access to a radio channel. Other functions are identical regardless of medium: deciding which upper-layer protocol a frame belongs to is the same question on Ethernet, Token Ring, or Wi-Fi. So IEEE split them:
- MAC (Media Access Control), the lower sublayer — medium-specific. It handles framing, physical addressing, and medium arbitration. Every 802 technology defines its own: 802.3 for Ethernet, 802.11 for Wi-Fi, 802.15 for WPAN.
- LLC (Logical Link Control), the upper sublayer — medium-independent, defined once in 802.2. It multiplexes upper-layer protocols and optionally provides flow and error control.
The intent was that one LLC implementation would sit atop any MAC, so the network layer would see a uniform interface regardless of the physical technology. Architecturally, this is exactly right.
LLC defines three service types, matching the models from the previous topic:
| LLC type | Service | Use |
|---|---|---|
| Type 1 | Unacknowledged connectionless | The overwhelming default |
| Type 2 | Connection-oriented (windowed, like HDLC) | Legacy SNA, mainframe links |
| Type 3 | Acknowledged connectionless | Industrial control |
The LLC header carries DSAP (Destination Service Access Point) and SSAP (Source Service Access Point), each one byte — the layer 2 demultiplexing keys described in Chapter 2.
Here is where reality diverged from the plan. One byte gives only 256 SAP values, and the space was administered restrictively. Worse, DEC, Intel, and Xerox had already shipped Ethernet II framing years before 802.2 existed, using a 16-bit EtherType field instead — a much larger space, centrally registered, and already working. The industry kept using it.
So Ethernet frames come in two shapes, and the receiver distinguishes them by a clever trick. The two-byte field after the source MAC is interpreted by value:
- ≤ 1500 (0x05DC) — it is a length field, so this is an 802.3 frame with an LLC header inside.
- ≥ 1536 (0x0600) — it is an EtherType, so this is an Ethernet II frame.
The gap between 1500 and 1536 is deliberately reserved so the two interpretations can never be confused. Since the maximum payload is 1500 bytes, no valid length can reach 1536.
SNAP (Sub-Network Access Protocol) is the bridge between the two worlds. When an 802.2 frame needs to carry a protocol that only has an EtherType, it sets DSAP = SSAP = 0xAA, control = 0x03, then adds a 5-byte SNAP header containing an OUI and the EtherType. This costs 8 bytes of overhead to recover what Ethernet II does in 2, which is a fair summary of why Ethernet II won.
In practice: essentially all IPv4 and IPv6 traffic uses Ethernet II framing. LLC/SNAP survives in 802.11 (where the MAC header is followed by an LLC/SNAP header carrying the EtherType), in Spanning Tree BPDUs, and in legacy protocols.
Examples
The two framing formats, distinguished by one field's VALUE
Ethernet II (what your IP traffic actually uses):
| dst MAC 6 | src MAC 6 | EtherType 2 | payload 46-1500 | FCS 4 |
^ >= 0x0600, e.g. 0x0800 = IPv4
IEEE 802.3 + LLC:
| dst MAC 6 | src MAC 6 | Length 2 |DSAP 1|SSAP 1|Ctrl 1| payload | FCS 4 |
^ <= 0x05DC ^^^^^^^^^^^^ the LLC header
3 bytes of overhead
IEEE 802.3 + LLC + SNAP (used by 802.11):
| dst | src | Length |AA|AA|03| OUI 3 | EtherType 2 | payload | FCS |
^^^^^^^^ SNAP escape ^ the EtherType, recovered
8 bytes of overhead to carry 2 bytes of information
The decision rule:
field value <= 1500 -> LENGTH -> 802.3, parse LLC next
field value >= 1536 -> TYPE -> Ethernet II, parse payload directly
1501..1535 -> reserved, never valid
ETHERTYPES = {0x0800: "IPv4", 0x0806: "ARP", 0x86DD: "IPv6",
0x8100: "802.1Q VLAN", 0x88CC: "LLDP"}
LLC_SAPS = {0x42: "Spanning Tree BPDU", 0x06: "IP (legacy)",
0xAA: "SNAP escape", 0xE0: "Novell IPX"}
def parse_frame(frame: bytes) -> str:
dst, src = frame[0:6], frame[6:12]
field = int.from_bytes(frame[12:14], "big")
head = f"dst={dst.hex(':')} src={src.hex(':')} "
if field >= 0x0600: # >= 1536 -> EtherType
return head + f"EtherType=0x{field:04x} ({ETHERTYPES.get(field,'?')}) [Ethernet II]"
# <= 1500 -> length field, so an LLC header follows
dsap, ssap, ctrl = frame[14], frame[15], frame[16]
if dsap == 0xAA and ssap == 0xAA: # SNAP escape
oui = frame[17:20]
etype = int.from_bytes(frame[20:22], "big")
return (head + f"len={field} LLC/SNAP oui={oui.hex(':')} "
f"EtherType=0x{etype:04x} ({ETHERTYPES.get(etype,'?')})")
return head + f"len={field} LLC dsap=0x{dsap:02x} ({LLC_SAPS.get(dsap,'?')})"
eth2 = bytes.fromhex("aabbccddeeff112233445566" "0800" + "00"*46)
llc = bytes.fromhex("0180c2000000112233445566" "0026" "424203" + "00"*35)
snap = bytes.fromhex("aabbccddeeff112233445566" "0030" "aaaa03" "000000" "0800" + "00"*40)
for f in (eth2, llc, snap):
print(parse_frame(f))
# dst=aa:bb:cc:dd:ee:ff src=11:22:33:44:55:66 EtherType=0x0800 (IPv4) [Ethernet II]
# dst=01:80:c2:00:00:00 src=11:22:33:44:55:66 len=38 LLC dsap=0x42 (Spanning Tree BPDU)
# dst=aa:bb:cc:dd:ee:ff src=11:22:33:44:55:66 len=48 LLC/SNAP oui=00:00:00 EtherType=0x0800 (IPv4)
print(f"\nreserved gap: {0x05DC+1}..{0x0600-1} = {1501}..{1535} — never a valid value")
Key takeaways
- IEEE splits layer 2 into MAC (medium-specific: framing, addressing, arbitration) and LLC (medium-independent: protocol multiplexing, optional reliability).
- LLC (802.2) offers Type 1 (unacknowledged connectionless), Type 2 (connection-oriented), and Type 3 (acknowledged connectionless).
- LLC's one-byte DSAP/SSAP proved too small and too late; Ethernet II's 16-bit EtherType won in practice.
- The field after the source MAC is read by value: ≤ 1500 = length (802.3/LLC), ≥ 1536 = EtherType (Ethernet II); 1501–1535 is reserved so the two can never be confused.
- SNAP (DSAP=SSAP=
0xAA) re-introduces an EtherType inside an LLC frame at 8 bytes of overhead. - Virtually all IP traffic uses Ethernet II; LLC/SNAP survives in 802.11, STP BPDUs, and legacy protocols.
🧪 Practice
- A frame's two bytes after the source MAC are
0x0800,0x0045, and0x8100in three different captures. Classify each frame format.- Explain why the values 1501–1535 are reserved, and what would break if the maximum Ethernet payload were raised to 1600 bytes without other changes.
- Interview-style: Why does 802.11 use LLC/SNAP while Ethernet does not, given both need to identify the upper-layer protocol? (Hint: consider that 802.11's MAC header was designed within the IEEE framework, and what field it therefore lacks.)
MTU and Fragmentation at the Link Layer
Theory
Every link technology imposes a Maximum Transmission Unit — the largest payload one frame can carry. Ethernet's is 1500 bytes. This number, chosen in the late 1970s as a compromise between buffer memory cost and efficiency, now constrains essentially the entire Internet.
The MTU exists for several reasons. Large frames monopolise a shared medium, delaying everyone else (a head-of-line blocking concern). They require larger buffers in every device. And critically, since error detection discards an entire frame, a larger frame means more data lost per error — on a link with a given bit error rate, frame loss probability grows with frame size.
The important architectural question is: when a packet is too large for the next link, who splits it?
The link layer's usual answer is nobody — it is not my job. Ethernet simply refuses: hand it a 2000-byte payload and it returns an error. This is deliberate. Fragmentation and reassembly require buffering, state, and reassembly timers, and doing it per hop would push complexity into devices that should stay simple and fast. Instead:
- IPv4 allows routers to fragment packets, with the destination reassembling — a design widely regarded as a mistake, because it costs router performance and creates security and efficiency problems.
- IPv6 removed router fragmentation entirely. A router that receives an oversized packet drops it and returns an ICMPv6 "Packet Too Big" message. The source must discover the path MTU and send smaller packets.
- Some link layers do fragment: 802.11 supports frame fragmentation to improve reliability on lossy channels, and ATM segmented everything into 53-byte cells. These are exceptions.
The mechanism that makes IPv6's approach work is Path MTU Discovery (PMTUD): the sender transmits packets with the Don't Fragment bit set, and any router that cannot forward one returns an ICMP error stating its MTU. The sender reduces accordingly.
PMTUD's famous failure mode — the PMTUD black hole — is one of the most valuable diagnostic patterns in networking. If a misconfigured firewall blocks ICMP (a depressingly common "security" measure), the sender never learns the packet was too big. It keeps retransmitting full-size packets that are silently discarded. The symptom is bizarre and memorable: small transfers work perfectly, large transfers hang. SSH connects and shows a prompt, then freezes when you run a command with long output. A web page's headers arrive but the body never does.
Common MTU values worth knowing:
| Link | MTU | Note |
|---|---|---|
| Ethernet | 1500 | The universal baseline |
| PPPoE (DSL) | 1492 | 8 bytes of PPPoE header |
| 802.11 | 2304 | Usually kept at 1500 for compatibility |
| Jumbo frames | 9000 | Data centre and storage networks |
| IPv6 minimum | 1280 | Every IPv6 link must support at least this |
| WireGuard VPN | 1420 | Tunnel overhead |
| Loopback | 65536 | No physical constraint |
Examples
The PMTUD black hole: why small packets work and large ones vanish
[Host A]---1500---[R1]---1400---[R2]---1500---[Host B]
^ a tunnel reduces the MTU here
HEALTHY:
A sends 1500-byte packet, DF set --> R1 cannot forward
R1 --ICMP "Frag Needed, MTU=1400"--> A
A lowers its path MTU to 1400 and resends. Works.
BLACK HOLE (a firewall drops ICMP):
A sends 1500-byte packet, DF set --> R1 drops it
R1 --ICMP "Frag Needed"--X (firewall discards the ICMP)
A waits... retransmits 1500 bytes... dropped again... forever.
Symptom pattern (the giveaway):
ping (64 bytes) -> works
TCP handshake (40 bytes) -> works, connection ESTABLISHED
ssh login prompt -> works
ls -la /usr/bin -> HANGS
Small = fine, large = dead. Always suspect MTU.
# Find the real path MTU by bisection, using DF-set pings.
$ ping -M do -s 1472 -c 1 example.com # 1472 + 8 ICMP + 20 IP = 1500
# PING example.com (93.184.216.34) 1472(1500) bytes of data.
# 1480 bytes from 93.184.216.34: icmp_seq=1 ttl=56 time=88.1 ms
# -> 1500 fits
$ ping -M do -s 1473 -c 1 example.com
# ping: local error: message too long, mtu=1500
# -> confirms this host's link MTU is 1500
# Through a tunnel with a reduced MTU, a healthy path reports the fix:
$ ping -M do -s 1472 -c 1 10.8.0.5
# From 10.8.0.1 icmp_seq=1 Frag needed and DF set (mtu = 1420)
# ^ this ICMP message is exactly what a black hole would swallow
$ ip route get 10.8.0.5
# 10.8.0.5 dev wg0 src 10.8.0.2 mtu 1420 <- cached path MTU
# Mitigation when ICMP cannot be fixed: clamp TCP's MSS at the gateway.
$ sudo iptables -t mangle -A FORWARD -p tcp --tcp-flags SYN,RST SYN \
-j TCPMSS --clamp-mss-to-pmtu
# Rewrites the MSS in every SYN so endpoints never generate oversized packets.
def mss_for(mtu, ipv6=False, tcp_options=12):
ip_hdr = 40 if ipv6 else 20 # IPv6's fixed header is larger
return mtu - ip_hdr - (20 + tcp_options)
def frames_needed(payload_bytes, mtu):
mss = mss_for(mtu)
n = -(-payload_bytes // mss) # ceiling division
overhead = n * (mtu - mss + 18) # headers + Ethernet framing
return n, overhead
for label, mtu in [("Ethernet", 1500), ("PPPoE", 1492),
("WireGuard", 1420), ("Jumbo", 9000)]:
n, oh = frames_needed(1_000_000, mtu)
print(f"{label:<10} MTU={mtu:<5} MSS={mss_for(mtu):<5} "
f"-> {n:>4} frames, {oh:>7,} bytes of overhead ({oh/1e6:.2%})")
# Ethernet MTU=1500 MSS=1448 -> 691 frames, 48,370 bytes of overhead (4.84%)
# PPPoE MTU=1492 MSS=1440 -> 695 frames, 48,650 bytes of overhead (4.87%)
# WireGuard MTU=1420 MSS=1368 -> 731 frames, 51,170 bytes of overhead (5.12%)
# Jumbo MTU=9000 MSS=8948 -> 112 frames, 7,840 bytes of overhead (0.78%)
# Jumbo frames cut framing overhead roughly sixfold for bulk transfer.
Key takeaways
- The MTU is the largest payload a link's frame can carry; Ethernet's 1500 bytes is the de facto Internet baseline.
- MTUs exist to bound medium occupancy, buffer sizes, and the amount of data lost per corrupted frame.
- Most link layers refuse oversized payloads rather than fragmenting; fragmentation is pushed to IP (IPv4) or to the source (IPv6).
- IPv6 forbids router fragmentation: oversized packets are dropped with an ICMPv6 "Packet Too Big", making PMTUD mandatory.
- A PMTUD black hole — caused by blocking ICMP — produces the signature symptom of small transfers working while large transfers hang.
- MSS clamping at a gateway is the standard workaround when ICMP cannot be unblocked.
- IPv6 requires every link to support an MTU of at least 1280 bytes.
🧪 Practice
- Compute the TCP MSS for an IPv6 connection over a 1492-byte PPPoE link with 12 bytes of TCP options.
- A user reports that SSH connects but hangs on any command producing long output, while ping works. Diagnose it and give two fixes.
- Interview-style: Why did IPv6 remove fragmentation from routers when IPv4 permitted it? (Hint: consider what state and buffering a router must maintain to fragment, and how that interacts with per-packet forwarding at line rate.)
Point-to-Point Protocol
Theory
Ethernet assumes a shared, multi-access medium and therefore needs MAC addresses to say which station a frame is for. But many links connect exactly two devices: a dial-up modem to an ISP, a router to a leased line, a DSL modem to a provider. On such a link, addressing is pointless — there is only one possible recipient.
PPP (Point-to-Point Protocol, RFC 1661) is the standard link layer for these links. It replaced the earlier SLIP, which did framing and nothing else — no error detection, no protocol identification, no address negotiation, no authentication.
PPP has three components, and the separation is worth understanding because it is a clean piece of protocol design:
- Framing — an HDLC-like frame with byte stuffing (the
0x7E/0x7Dscheme from the framing topic) and a CRC for error detection. - LCP (Link Control Protocol) — brings the link up, negotiates options (maximum receive unit, authentication method, compression, magic numbers for loop detection), tests it, and takes it down.
- NCP (Network Control Protocol) — a family of protocols, one per network-layer protocol. IPCP configures IPv4 (including assigning the client an address — which is how dial-up and DSL gave you an IP), IPV6CP configures IPv6.
That three-way split is the key insight: PPP separates link establishment from network configuration, so one link can simultaneously carry IPv4 and IPv6 with independently negotiated parameters.
PPP's frame format is deliberately vestigial in places:
| Field | Size | Value | Purpose |
|---|---|---|---|
| Flag | 1 | 0x7E | Frame delimiter |
| Address | 1 | 0xFF | "All stations" — meaningless on a point-to-point link, kept for HDLC compatibility |
| Control | 1 | 0x03 | Unnumbered information |
| Protocol | 2 | e.g. 0x0021 | Which protocol is in the payload |
| Information | variable | — | The payload |
| FCS | 2 or 4 | — | CRC |
| Flag | 1 | 0x7E | Frame delimiter |
The Address and Control fields are constants on every frame, which is why Address and Control Field Compression is routinely negotiated away.
Authentication is where PPP's practical importance lies, since ISPs must identify subscribers:
- PAP (Password Authentication Protocol) sends username and password in cleartext. Obsolete and unsafe.
- CHAP (Challenge-Handshake Authentication Protocol) is challenge-response: the server sends a random challenge, the client returns a hash of (challenge + secret), and the server verifies it. The password never crosses the link, and because the server can re-challenge at any time during the session, it also defends against session hijacking.
PPPoE (PPP over Ethernet, RFC 2516) deserves special mention because it explains a number many people encounter. DSL providers wanted PPP's authentication and per-subscriber accounting, but the access network was Ethernet. PPPoE encapsulates PPP inside Ethernet frames, adding a 6-byte PPPoE header plus 2 bytes of PPP protocol field — 8 bytes of overhead, reducing the usable MTU from 1500 to 1492. This is the single most common cause of MTU-related problems on consumer broadband.
Examples
PPP session lifecycle: three phases, three protocols
DEAD
| carrier detected
v
ESTABLISH <---- LCP: negotiate MRU, auth method, magic number
| LCP Configure-Ack exchanged both ways
v
AUTHENTICATE <-- CHAP: challenge / response / success
|
v
NETWORK <---- IPCP: "your address is 203.0.113.45, DNS is ..."
| IPV6CP runs independently and in parallel
v
OPEN <---- data flows; LCP Echo-Request keeps the link alive
| LCP Terminate-Request
v
TERMINATE -> DEAD
CHAP, and why the password never crosses the link:
server --> Challenge: random nonce R, id
client --> Response: HASH(id || secret || R)
server: computes the same hash locally and compares
An eavesdropper sees R and the hash but cannot derive the secret,
and a replay fails because R changes every time.
import hashlib, os
def chap_challenge():
return os.urandom(16) # fresh random nonce each session
def chap_response(identifier: int, secret: bytes, challenge: bytes) -> bytes:
# RFC 1994: MD5(id || secret || challenge). MD5 here is historical, not a
# recommendation — modern designs use stronger constructions.
return hashlib.md5(bytes([identifier]) + secret + challenge).digest()
secret, ident = b"subscriber-password", 7
chal = chap_challenge()
resp = chap_response(ident, secret, chal)
print("challenge:", chal.hex())
print("response :", resp.hex())
print("server verifies:", resp == chap_response(ident, secret, chal))
# The secret itself never appears on the wire.
# A replayed response fails against a new challenge:
print("replay against a new challenge:",
resp == chap_response(ident, secret, chap_challenge()))
# replay against a new challenge: False
# PPPoE overhead, and why consumer DSL runs at 1492:
ETH_PAYLOAD = 1500
PPPOE_HDR, PPP_PROTO = 6, 2
print(f"\nEthernet payload : {ETH_PAYLOAD}")
print(f"- PPPoE header : {PPPOE_HDR}")
print(f"- PPP protocol field : {PPP_PROTO}")
print(f"= usable MTU : {ETH_PAYLOAD - PPPOE_HDR - PPP_PROTO}")
# = usable MTU : 1492
# PPP negotiation as it actually appears in logs.
$ sudo pppd call myisp debug
# pppd: Serial connection established.
# pppd: sent [LCP ConfReq id=0x1 <mru 1492> <magic 0x4d2a1f> <pcomp> <accomp>]
# pppd: rcvd [LCP ConfReq id=0x1 <auth chap MD5> <magic 0x7b3e>]
# pppd: sent [LCP ConfAck id=0x1 ...]
# pppd: rcvd [CHAP Challenge id=0x1 <8f3a...>, name = "isp-lns-01"]
# pppd: sent [CHAP Response id=0x1 <c4d2...>, name = "user@isp"]
# pppd: rcvd [CHAP Success id=0x1 "Access granted"]
# pppd: sent [IPCP ConfReq id=0x1 <addr 0.0.0.0> <ms-dns1 0.0.0.0>]
# pppd: rcvd [IPCP ConfNak id=0x1 <addr 203.0.113.45> <ms-dns1 198.51.100.1>]
# ^ the ISP assigns the address here
# pppd: local IP address 203.0.113.45
# pppd: remote IP address 203.0.113.1
$ ip link show ppp0
# 5: ppp0: <POINTOPOINT,MULTICAST,NOARP,UP,LOWER_UP> mtu 1492
# ^^^^ no ARP: only one possible peer
# ^^^^ PPPoE's 8 bytes
Key takeaways
- PPP is the standard link layer for links joining exactly two devices, where MAC addressing is unnecessary.
- It has three parts: HDLC-style framing with byte stuffing and a CRC, LCP for link establishment and option negotiation, and NCP (IPCP, IPV6CP) for per-protocol network configuration.
- Separating LCP from NCP lets one link carry several network protocols with independently negotiated parameters.
- Address (
0xFF) and Control (0x03) are constants retained for HDLC compatibility and usually compressed away. - CHAP authenticates by challenge-response so the secret never crosses the link and replay fails; PAP sends cleartext and is obsolete.
- PPPoE adds 8 bytes of overhead, reducing the MTU to 1492 — the most common source of MTU trouble on consumer broadband.
- A PPP interface needs no ARP, because there is only one possible peer.
🧪 Practice
- List the PPP phases in order and name the protocol responsible for each transition.
- Explain why a PPP interface has the
NOARPflag while an Ethernet interface does not.- Interview-style: Why does PPP separate LCP from NCP instead of negotiating everything at once? (Hint: consider a link that must carry both IPv4 and IPv6, and what happens when one of them fails to negotiate.)
<a id="42-error-detection-and-correction"></a>
4.2 Error Detection and Correction
Bits get corrupted in transit; this subchapter covers the codes that detect corruption, the mathematics that makes some of them far stronger than others, and when it is worth correcting errors rather than simply retransmitting.
Parity Bits and Two-Dimensional Parity
Theory
The physical layer does its best, but bits still flip. Before anything can be done about an error, it must be detected, and detection always works the same way: the sender computes redundant information from the data and appends it; the receiver recomputes and compares. If they disagree, something changed.
The simplest such scheme is a parity bit. Count the 1 bits in the data and append one more bit so that the total is even (even parity) or odd (odd parity). The receiver counts; a mismatch means an error.
Single parity detects any odd number of bit errors — one, three, five. But it is blind to any even number: two flipped bits cancel out and the parity still matches. Since errors on real links often occur in bursts — a lightning strike or a motor starting corrupts a run of adjacent bits — and a burst has a roughly 50 percent chance of containing an even number of errors, single parity misses about half of all real-world error events. It is far too weak for networking, though it survives in memory buses and serial ports.
Two-dimensional parity is a significant improvement built from the same idea. Arrange the data as a grid, compute a parity bit for every row and every column, and add one more for the corner. Now:
- A single-bit error flips exactly one row parity and one column parity. Their intersection identifies the exact bit — so 2D parity does not merely detect a single error, it corrects it.
- All two-bit and three-bit errors are detected.
- Some four-bit errors escape: if errors fall on the four corners of a rectangle, every row and column parity remains correct.
This introduces the concept underlying all coding theory: Hamming distance, the number of positions in which two code words differ. The minimum Hamming distance d of a code determines its power:
- To detect up to d−1 errors, you need minimum distance d.
- To correct up to t errors, you need minimum distance 2t+1 — because each valid code word needs a "sphere" of radius t around it that touches no other code word's sphere.
Single parity has d = 2 (detect 1 error, correct none). Two-dimensional parity has d = 4 (detect 3, correct 1).
| Scheme | Overhead | Detects | Corrects | Hamming distance |
|---|---|---|---|---|
| Single parity | 1 bit | Odd numbers of errors | None | 2 |
| 2D parity (n×m) | n+m+1 bits | All 1, 2, 3-bit errors | Single-bit | 4 |
| Internet checksum | 16 bits | Most, but weak | None | — |
| CRC-32 | 32 bits | All bursts ≤ 32 bits | None | varies |
| Hamming (7,4) | 3 bits | 2-bit errors | Single-bit | 3 |
Examples
Two-dimensional parity: locating a single error by intersection
c1 c2 c3 c4 c5 c6 c7 c8 | row parity
row 1: 1 0 1 1 0 1 0 0 | 0 (four 1s -> even -> 0)
row 2: 0 1 1 0 1 0 1 1 | 1 (five 1s -> odd -> 1)
row 3: 1 1 0 1 1 1 0 0 | 1
row 4: 0 0 1 1 0 0 1 0 | 1
--------------------------------+
col par: 0 0 1 1 0 0 0 1 | 0 <- corner: parity of the parities
Now flip row 2, column 5 in transit:
row 2: 0 1 1 0 0 0 1 1 | 1 <- recomputed parity is 0, sent 1 MISMATCH
^
col 5 recomputed is 1, sent 0 MISMATCH
The failing row and the failing column intersect at exactly ONE cell.
Flip it back: the error is CORRECTED, not merely detected.
The blind spot — four errors at the corners of a rectangle:
row a: ... X ... X ... each row still has an even number of flips
row b: ... X ... X ... each column still has an even number of flips
^ ^ every parity bit checks out. UNDETECTED.
def parity_bit(bits, even=True):
ones = sum(bits)
return (ones % 2) if even else (1 - ones % 2)
def encode_2d(rows):
"""Append a parity bit to each row, then a parity row across the columns."""
coded = [r + [parity_bit(r)] for r in rows]
n_cols = len(coded[0])
# Column parity computed over the DATA rows, including their row-parity column.
col_parity = [parity_bit([r[c] for r in coded]) for c in range(n_cols)]
return coded + [col_parity]
def check_2d(block):
"""Return (row_index, col_index) of a single-bit error, or None if clean."""
data_rows, col_row = block[:-1], block[-1]
bad_rows = [i for i, r in enumerate(data_rows) if parity_bit(r[:-1]) != r[-1]]
bad_cols = [c for c in range(len(col_row))
if parity_bit([r[c] for r in data_rows]) != col_row[c]]
if not bad_rows and not bad_cols:
return None # no error detected
if len(bad_rows) == 1 and len(bad_cols) == 1:
return (bad_rows[0], bad_cols[0]) # locatable -> correctable
return "detected, not correctable"
data = [[1,0,1,1,0,1,0,0],
[0,1,1,0,1,0,1,1],
[1,1,0,1,1,1,0,0],
[0,0,1,1,0,0,1,0]]
block = encode_2d(data)
print("clean block :", check_2d(block))
# clean block : None
import copy
corrupted = copy.deepcopy(block)
corrupted[1][4] ^= 1 # flip one bit
loc = check_2d(corrupted)
print("single-bit error at :", loc)
corrupted[loc[0]][loc[1]] ^= 1 # correct it
print("after correction :", check_2d(corrupted))
# single-bit error at : (1, 4)
# after correction : None
# The rectangle blind spot:
blind = copy.deepcopy(block)
for r, c in [(0,2), (0,5), (2,2), (2,5)]: # four corners of a rectangle
blind[r][c] ^= 1
print("four corner errors :", check_2d(blind), "<- UNDETECTED")
# four corner errors : None <- UNDETECTED
# Hamming distance rules:
for d in range(2, 8):
print(f"minimum distance {d}: detect up to {d-1} errors, correct up to {(d-1)//2}")
# minimum distance 2: detect up to 1 errors, correct up to 0
# minimum distance 3: detect up to 2 errors, correct up to 1
# minimum distance 4: detect up to 3 errors, correct up to 1
# minimum distance 5: detect up to 4 errors, correct up to 2
Key takeaways
- Error detection works by transmitting redundancy: the receiver recomputes it and compares.
- A single parity bit detects any odd number of errors and misses every even number — inadequate for bursty real-world errors.
- Two-dimensional parity detects all 1-, 2-, and 3-bit errors and corrects single-bit errors by intersecting the failing row and column.
- Its blind spot is four errors at the corners of a rectangle, which leaves every parity bit correct.
- Hamming distance governs code power: detecting d−1 errors needs minimum distance d; correcting t errors needs minimum distance 2t+1.
- Correction requires strictly more redundancy than detection, because the code must identify which bit is wrong, not merely that something is.
🧪 Practice
- Compute the even parity bit for
10110101and for11001100. Which single-bit error in the first would go undetected, and why is that a trick question?- Build a 2D parity block for the 4×4 grid of your choice, introduce a single error, and show how the intersection locates it.
- Interview-style: A code has minimum Hamming distance 5. How many errors can it detect, and how many can it correct? Why are these numbers different? (Hint: think about spheres of a given radius around each valid code word and what happens when they must not overlap.)
Internet Checksum
Theory
The Internet checksum (RFC 1071) is the error-detection scheme used by IPv4 headers, TCP, UDP, and ICMP. It is notably weaker than a CRC, and understanding why it was chosen anyway is more instructive than the algorithm itself.
The algorithm is deliberately simple:
- Treat the data as a sequence of 16-bit words.
- Add them using one's complement arithmetic — meaning any carry out of the top bit is added back into the bottom bit ("end-around carry").
- Take the one's complement (bitwise NOT) of the result. That is the checksum.
- The receiver sums everything including the checksum. A correct result is all ones (
0xFFFF), which after complementing is zero.
Why one's complement rather than ordinary addition? Two practical reasons. It is endian-independent — the sum computed on a big-endian machine equals that on a little-endian machine, byte-swapped, so the check still works. And it is incrementally updatable: a router decrementing the TTL can adjust the checksum with a couple of arithmetic operations rather than recomputing over the whole header. On 1980s hardware, that mattered enormously.
The weaknesses are real and worth knowing:
- Reordering 16-bit words is invisible. Addition is commutative, so swapping two words leaves the sum unchanged.
- Compensating errors cancel. Adding 1 to one word and subtracting 1 from another produces the same checksum.
- It misses many burst errors that a CRC of the same width would catch reliably.
- Empirical studies of real Internet traffic have found error rates after checksum validation far higher than theory predicts, because the errors that occur in practice — software bugs, faulty memory, buggy middleboxes — are exactly the structured kind the checksum handles worst.
So why use it? Because of the end-to-end argument. The Internet checksum is not the primary defence — Ethernet's CRC-32 already protects each hop far more strongly. The Internet checksum exists to catch errors the link-layer CRC cannot see: corruption inside a router's memory while the packet sits in a buffer, a bug in a driver, a bad DMA transfer. It is a cheap end-to-end sanity check layered on top of strong per-hop protection, exactly as Saltzer, Reed, and Clark prescribed.
One detail that catches people out: TCP and UDP checksums cover a pseudo-header containing the source IP, destination IP, protocol number, and length — fields belonging to the IP layer. This is a deliberate layering violation, and its purpose is to detect a packet delivered to the wrong host or the wrong protocol. Note also that IPv6 removed the header checksum entirely, on the reasoning that layer 2 protects each hop and layer 4 protects end to end, so the middle layer's weak check was redundant — and making UDP checksums mandatory in IPv6 (they were optional in IPv4) closed the resulting gap.
Examples
One's complement addition, worked through
words: 4500 003c 1c46 4000 4006 0000 c0a8 0001 c0a8 00c7
---- ---- ---- ---- ---- ---- ---- ---- ---- ----
^ checksum field is ZERO while computing
Sum with end-around carry:
4500 + 003c = 453c
453c + 1c46 = 6182
6182 + 4000 = a182
a182 + 4006 = e188
... continuing ...
result overflows 16 bits at some point:
1 a3f1 -> a3f1 + 1 = a3f2 <- the carry wraps to the bottom
final sum = b1e5
checksum = ~b1e5 = 4e1a <- one's complement
Receiver adds EVERYTHING including the checksum:
b1e5 + 4e1a = ffff <- all ones means valid
~ffff = 0000
The weakness, in one line:
word A = 0x1000, word B = 0x2000 sum = 0x3000
word A = 0x2000, word B = 0x1000 sum = 0x3000 <- SWAPPED, undetected
word A = 0x1001, word B = 0x1FFF sum = 0x3000 <- COMPENSATING, undetected
def internet_checksum(data: bytes) -> int:
if len(data) % 2:
data += b"\x00" # pad to a whole number of words
total = 0
for i in range(0, len(data), 2):
total += int.from_bytes(data[i:i+2], "big")
total = (total & 0xFFFF) + (total >> 16) # end-around carry
return ~total & 0xFFFF # one's complement
def verify(data: bytes) -> bool:
"""Summing data that already contains a correct checksum yields 0xFFFF."""
if len(data) % 2:
data += b"\x00"
total = 0
for i in range(0, len(data), 2):
total += int.from_bytes(data[i:i+2], "big")
total = (total & 0xFFFF) + (total >> 16)
return total == 0xFFFF
# A real IPv4 header with the checksum field zeroed:
header = bytes.fromhex("450000 3c1c46400040060000c0a80001c0a800c7".replace(" ", ""))
ck = internet_checksum(header)
print(f"computed checksum: 0x{ck:04x}")
# Insert it at the correct offset (bytes 10-11) and verify:
full = header[:10] + ck.to_bytes(2, "big") + header[12:]
print("verifies:", verify(full))
# verifies: True
# Demonstrating the two structural weaknesses:
a = bytes.fromhex("1000" "2000" "3000" "4000")
b = bytes.fromhex("2000" "1000" "3000" "4000") # two words swapped
c = bytes.fromhex("1001" "1fff" "3000" "4000") # compensating +1 / -1
print(f"\noriginal : 0x{internet_checksum(a):04x}")
print(f"words swapped : 0x{internet_checksum(b):04x} same? {internet_checksum(a)==internet_checksum(b)}")
print(f"compensating : 0x{internet_checksum(c):04x} same? {internet_checksum(a)==internet_checksum(c)}")
# original : 0x9fff
# words swapped : 0x9fff same? True <- reordering is invisible
# compensating : 0x9fff same? True <- offsetting errors cancel
# Incremental update: a router decrementing TTL need not rescan the header.
def incremental_update(old_ck, old_word, new_word):
"""RFC 1624: adjust a checksum for a single changed word."""
s = (~old_ck & 0xFFFF) + (~old_word & 0xFFFF) + new_word
s = (s & 0xFFFF) + (s >> 16)
return ~s & 0xFFFF
old_ttl_word, new_ttl_word = 0x4006, 0x3F06 # TTL 64 -> 63
print(f"\nincremental : 0x{incremental_update(ck, old_ttl_word, new_ttl_word):04x}")
Key takeaways
- The Internet checksum sums 16-bit words in one's complement arithmetic (end-around carry), then complements the result; the receiver's sum of everything should be
0xFFFF. - One's complement was chosen for endian independence and incremental updatability — a router can adjust it after changing the TTL without rescanning.
- It is structurally weak: word reordering and compensating errors are invisible, and many burst errors escape.
- It is acceptable because it is an end-to-end sanity check layered over strong per-hop CRCs, catching corruption inside routers, drivers, and memory that link CRCs cannot see.
- TCP and UDP checksums cover an IP pseudo-header (source, destination, protocol, length) — a deliberate layer violation that detects misdelivery.
- IPv6 removed the header checksum entirely and made UDP checksums mandatory instead.
🧪 Practice
- Compute the Internet checksum of the 16-bit words
0x4500,0x0028,0xABCD,0x0000by hand, showing the end-around carry.- Construct two different 4-word messages with identical checksums, and explain which structural weakness each exploits.
- Interview-style: IPv6 removed the header checksum that IPv4 had. Was this safe? (Hint: identify which layers protect the packet on each hop and end to end, and what changed about UDP checksums in IPv6.)
Cyclic Redundancy Check
Theory
The CRC is the error-detection workhorse of the link layer. Ethernet, Wi-Fi, HDLC, PPP, USB, SATA, and virtually every storage system use one. It is dramatically stronger than a checksum of the same width, and — importantly — it is trivially cheap in hardware, needing nothing but a shift register and a few XOR gates.
The idea is polynomial division over GF(2), which sounds forbidding and is actually simpler than ordinary arithmetic. Treat the message as a polynomial whose coefficients are its bits: 1011 means x³ + x + 1. Pick an agreed generator polynomial G(x) of degree r. Then:
- Append r zero bits to the message.
- Divide by G(x) using modulo-2 arithmetic — which means XOR instead of subtraction, with no borrows and no carries.
- The remainder is the CRC, and it replaces those r appended zeros.
The receiver divides the whole received frame (data plus CRC) by the same G(x). A remainder of zero means no detected error. The reason this works is that appending the remainder makes the transmitted polynomial exactly divisible by G(x).
Why does XOR-based arithmetic make this cheap? Because modulo-2 division needs no comparison of magnitudes — you simply check whether the leading bit is 1. In hardware this becomes a linear feedback shift register that processes a bit per clock, or a table-driven version that processes a byte or more at a time in software.
What makes CRCs strong is that their guarantees are provable, not statistical. For a well-chosen generator of degree r, a CRC detects:
| Error pattern | Guarantee |
|---|---|
| Any single-bit error | Always, if G(x) has at least two non-zero terms |
| Any two isolated bit errors | Always, if G(x) does not divide xᵏ+1 for small k |
| Any odd number of bit errors | Always, if G(x) has (x+1) as a factor |
| Any burst error of length ≤ r | Always |
| Burst of length exactly r+1 | All but 2^−(r−1) of them |
| Longer bursts | All but 2^−r of them |
That burst guarantee is the crucial one. Real link errors are bursty, and CRC-32 catches every burst up to 32 bits long with certainty, plus all but one in four billion of longer ones. No checksum can make a comparable claim.
Standard generators worth recognising:
| Name | Degree | Polynomial (hex) | Used by |
|---|---|---|---|
| CRC-8 | 8 | 0x07 | ATM headers, SMBus |
| CRC-16-CCITT | 16 | 0x1021 | HDLC, PPP, Bluetooth, XMODEM |
| CRC-32 | 32 | 0x04C11DB7 | Ethernet, PPP, PNG, ZIP, gzip |
| CRC-32C | 32 | 0x1EDC6F41 | iSCSI, SCTP, ext4 — hardware-accelerated on modern CPUs |
One essential caveat: a CRC is not a cryptographic hash. It detects accidental corruption superbly and provides no security whatsoever. Because CRC is linear, an attacker who modifies a message can compute exactly which CRC bits to flip to keep it valid. Integrity against a malicious party requires a MAC or signature — which is why TLS adds its own authentication tag rather than trusting Ethernet's FCS.
Finally, note that in Ethernet the FCS is checked and discarded at every hop, and a new one is computed by each switch. So the CRC protects the frame on the wire but not inside the switch — corruption in switch memory produces a frame with a perfectly valid new CRC. This is precisely the gap the end-to-end checksum exists to cover.
Examples
CRC by long division, modulo 2 (XOR, no borrows)
message 1101011011 generator G = 10011 (x^4 + x + 1, degree r = 4)
append 4 zeros: 11010110110000
11010110110000 | 10011
10011 <- XOR whenever the leading bit is 1
-----
10011
10011
-----
00001011 0000
10011
-----
10100
10011
-----
01110 0
10011 ... continues ...
remainder: 1110 <- this is the CRC
transmitted frame: 1101011011 1110
^message^ ^CRC^
Receiver divides the whole thing by G:
remainder 0000 -> accepted
any non-zero remainder -> error detected, frame discarded silently
def crc_bitwise(data_bits: str, generator: str) -> str:
"""Textbook modulo-2 polynomial division: XOR, no carries."""
r = len(generator) - 1
bits = list(data_bits + "0" * r) # append r zeros
for i in range(len(data_bits)):
if bits[i] == "1": # only XOR when leading bit is 1
for j, g in enumerate(generator):
bits[i + j] = str(int(bits[i + j]) ^ int(g))
return "".join(bits[-r:]) # the remainder
msg, gen = "1101011011", "10011"
crc = crc_bitwise(msg, gen)
print(f"message : {msg}")
print(f"CRC : {crc}")
frame = msg + crc
print(f"frame : {frame}")
print(f"verify : remainder = {crc_bitwise(frame, gen)} (zero means clean)")
# message : 1101011011
# CRC : 1110
# frame : 11010110111110
# verify : remainder = 0000 (zero means clean)
# Corrupt any single bit and the remainder becomes non-zero:
bad = list(frame); bad[3] = "0" if bad[3] == "1" else "1"
print(f"corrupted : remainder = {crc_bitwise(''.join(bad), gen)} <- detected")
# CRC-32 as Ethernet computes it:
import zlib
payload = b"\xaa\xbb\xcc\xdd\xee\xff\x11\x22\x33\x44\x55\x66\x08\x00" + b"\x00" * 46
fcs = zlib.crc32(payload) & 0xFFFFFFFF
print(f"\nEthernet FCS: 0x{fcs:08x}")
# Every burst up to 32 bits is caught with certainty:
detected = 0
for start in range(0, len(payload) * 8 - 32):
b = bytearray(payload)
for k in range(32): # flip a 32-bit contiguous burst
bit = start + k
b[bit // 8] ^= (1 << (7 - bit % 8))
if (zlib.crc32(bytes(b)) & 0xFFFFFFFF) != fcs:
detected += 1
total = len(payload) * 8 - 32
print(f"32-bit bursts detected: {detected}/{total} = {detected/total:.1%}")
# 32-bit bursts detected: 448/448 = 100.0% <- a guarantee, not a probability
# Why CRC is NOT security: linearity lets an attacker fix it up.
orig = b"PAY ALICE 100"
forged = b"PAY ALICE 900"
print(f"\ncrc(original) = 0x{zlib.crc32(orig)&0xFFFFFFFF:08x}")
print(f"crc(forged) = 0x{zlib.crc32(forged)&0xFFFFFFFF:08x}")
# Different — but an attacker simply sends the forged message with ITS OWN
# correct CRC. The CRC proves nothing about who wrote the message.
Key takeaways
- A CRC treats the message as a polynomial and transmits the remainder after division by an agreed generator polynomial, using modulo-2 (XOR) arithmetic.
- The receiver divides the received frame by the same generator; a zero remainder means no detected error.
- CRC guarantees are provable, not statistical: a degree-r CRC detects every burst error of length ≤ r, plus all single-bit errors, all odd-bit errors, and all double-bit errors for well-chosen generators.
- CRC-32 (
0x04C11DB7) is Ethernet's FCS; CRC-16-CCITT serves PPP and Bluetooth; CRC-32C is hardware-accelerated on modern CPUs. - Implementation is cheap — a shift register and XOR gates in hardware, a lookup table in software.
- A CRC is not cryptographic: it is linear, so an attacker can forge a message with a valid CRC. Security needs a MAC or signature.
- Ethernet recomputes the FCS at every hop, so it does not protect against corruption inside a switch — hence the end-to-end checksum above it.
🧪 Practice
- Compute the CRC of
110101with generator1011by hand, then verify your answer by dividing the full frame.- Explain why a degree-16 CRC catches every burst of 16 bits or fewer, referring to what a burst of that length means as a polynomial.
- Interview-style: Ethernet has a 32-bit CRC on every frame. Why does TCP add its own much weaker checksum on top? (Hint: trace where a frame's CRC is verified and discarded, and what happens to the data between two such points.)
Hamming Codes and Forward Error Correction
Theory
Everything so far only detects errors, leaving recovery to retransmission. But retransmission is not always possible or sensible. A deep-space probe has a round-trip time measured in hours. A broadcast transmitter has no return channel at all. A hard drive cannot ask the platter to rewrite a sector. In these cases you need FEC (Forward Error Correction): enough redundancy that the receiver can repair errors without asking for anything.
Hamming codes (Richard Hamming, 1950) are the classic construction, and their elegance is worth studying. The insight: instead of one parity bit over everything, use several parity bits, each covering a carefully chosen overlapping subset of positions, so that the pattern of which parity checks fail identifies exactly where the error is.
The construction:
- Number bit positions from 1. Positions that are powers of two (1, 2, 4, 8, …) hold parity bits; all others hold data.
- Parity bit at position 2^k checks every position whose binary representation has bit k set. So p1 checks positions 1,3,5,7,…; p2 checks 2,3,6,7,10,11,…; p4 checks 4,5,6,7,12,…
- The receiver recomputes all parity checks. Interpreting the failures as a binary number gives the syndrome — which is the position of the flipped bit. Zero means no error.
That the syndrome directly yields the error position, with no search, is the beautiful part. It falls straight out of using powers of two as parity positions.
The number of parity bits r needed for m data bits satisfies 2^r ≥ m + r + 1 — the syndrome must be able to name every bit position plus the "no error" case. The standard Hamming(7,4) code carries 4 data bits in 7 total, with minimum distance 3: it corrects any single error or detects any double error, but not both at once. Adding one overall parity bit gives SECDED (Single Error Correct, Double Error Detect), which is what ECC memory uses.
Beyond Hamming, the codes that matter in practice:
| Code | Property | Used by |
|---|---|---|
| Hamming / SECDED | Corrects 1, detects 2 | ECC RAM |
| Reed-Solomon | Corrects symbol bursts | CDs, DVDs, QR codes, DSL, deep space |
| Convolutional + Viterbi | Continuous stream decoding | Legacy cellular, satellite |
| Turbo codes | Near Shannon limit | 3G/4G |
| LDPC | Near Shannon limit, parallel decoding | Wi-Fi 6/7, 5G, DVB-S2, modern SSDs |
Reed-Solomon deserves particular note because it operates on symbols rather than bits, which makes it naturally burst-resistant — an entire corrupted byte counts as one symbol error. This is why a scratched CD still plays.
The general trade is straightforward: FEC costs bandwidth on every transmission, whether or not errors occur; ARQ costs a round trip only when they do. Which is cheaper depends on the error rate and the cost of a round trip. Hybrid ARQ, used in LTE and 5G, combines both — send with FEC, and if decoding still fails, request a retransmission that carries additional redundancy rather than a repeat.
Examples
Hamming(7,4): parity positions are powers of two
position: 1 2 3 4 5 6 7
role: p1 p2 d1 p4 d2 d3 d4
p1 (001) checks positions with bit0 set: 1, 3, 5, 7
p2 (010) checks positions with bit1 set: 2, 3, 6, 7
p4 (100) checks positions with bit2 set: 4, 5, 6, 7
Encode data 1011 (d1=1, d2=0, d3=1, d4=1):
p1 = parity(d1,d2,d4) = parity(1,0,1) = 0
p2 = parity(d1,d3,d4) = parity(1,1,1) = 1
p4 = parity(d2,d3,d4) = parity(0,1,1) = 0
codeword: 0 1 1 0 0 1 1
p1 p2 d1 p4 d2 d3 d4
Now flip position 5 in transit -> 0 1 1 0 1 1 1
p1 check (1,3,5,7): 0^1^1^1 = 1 FAIL -> syndrome bit0 = 1
p2 check (2,3,6,7): 1^1^1^1 = 0 ok -> syndrome bit1 = 0
p4 check (4,5,6,7): 0^1^1^1 = 1 FAIL -> syndrome bit2 = 1
syndrome = 101 binary = 5 <-- the error is at position 5, exactly.
Flip it back. Corrected, with no retransmission.
def hamming_encode(data_bits):
"""Hamming(7,4): parity at positions 1,2,4; data at 3,5,6,7."""
d = list(data_bits)
code = [0] * 8 # index 0 unused; 1-based
code[3], code[5], code[6], code[7] = d[0], d[1], d[2], d[3]
for p in (1, 2, 4): # each parity bit
# Cover every position whose index has this parity bit's bit set.
covered = [i for i in range(1, 8) if i & p and i != p]
code[p] = 0
for i in covered:
code[p] ^= code[i]
return code[1:]
def hamming_decode(received):
code = [0] + list(received) # restore 1-based indexing
syndrome = 0
for p in (1, 2, 4):
parity = 0
for i in range(1, 8):
if i & p: # includes the parity bit itself
parity ^= code[i]
if parity:
syndrome += p # accumulate the failing checks
corrected = list(code)
if syndrome:
corrected[syndrome] ^= 1 # the syndrome IS the position
return [corrected[3], corrected[5], corrected[6], corrected[7]], syndrome
data = [1, 0, 1, 1]
code = hamming_encode(data)
print(f"data : {data}")
print(f"codeword : {code}")
for pos in range(7):
corrupted = list(code)
corrupted[pos] ^= 1 # flip one bit
recovered, syn = hamming_decode(corrupted)
print(f"flip position {pos+1}: syndrome={syn} recovered={recovered} "
f"{'OK' if recovered == data else 'FAILED'}")
# flip position 1: syndrome=1 recovered=[1, 0, 1, 1] OK
# flip position 2: syndrome=2 recovered=[1, 0, 1, 1] OK
# ...
# flip position 7: syndrome=7 recovered=[1, 0, 1, 1] OK
# Every single-bit error is located and repaired.
# How much redundancy does a Hamming code need?
print()
for m in (4, 8, 16, 32, 64, 128):
r = 1
while 2**r < m + r + 1: # the Hamming bound
r += 1
print(f"{m:>4} data bits need {r} parity bits "
f"({r/(m+r):>5.1%} overhead)")
# 4 data bits need 3 parity bits (42.9% overhead)
# 64 data bits need 7 parity bits ( 9.9% overhead)
# 128 data bits need 8 parity bits ( 5.9% overhead)
# Relative overhead falls as blocks grow — why ECC RAM uses 64-bit words.
Key takeaways
- FEC adds enough redundancy for the receiver to repair errors without retransmission — essential when a round trip is impossible or too costly.
- Hamming codes place parity bits at power-of-two positions, each covering an overlapping subset, so the failing checks read directly as the binary position of the error.
- Redundancy required satisfies 2^r ≥ m + r + 1; relative overhead falls as blocks grow.
- Hamming(7,4) has minimum distance 3: correct one error or detect two, not both; adding an overall parity bit gives SECDED, used by ECC RAM.
- Reed-Solomon works on symbols rather than bits, making it naturally burst-resistant — hence CDs, QR codes, and deep-space links.
- LDPC and turbo codes approach the Shannon limit and dominate modern Wi-Fi, 5G, and satellite.
- FEC costs bandwidth always; ARQ costs a round trip only on error. Hybrid ARQ combines both by sending extra redundancy on retransmission.
🧪 Practice
- Encode the data bits
1001using Hamming(7,4), then corrupt position 6 and show how the syndrome locates it.- How many parity bits does a Hamming code need for 256 data bits? Compute the overhead percentage and compare with the 4-bit case.
- Interview-style: Why does a deep-space probe use heavy FEC while a data-centre link uses almost none? (Hint: compare the cost of one retransmission round trip in each setting, and what the error rate is on each link.)
Error Detection vs Correction Trade-offs
Theory
Having seen both families, the engineering question is when to use which. The answer follows from a simple comparison of costs, and the reasoning generalises far beyond networking.
ARQ (Automatic Repeat reQuest) — detect the error and ask for a retransmission:
- Cost when there is no error: almost nothing. A 32-bit CRC on a 1500-byte frame is 0.27 percent overhead.
- Cost when there is an error: one round trip, plus whatever the protocol above does in response (TCP will also halve its congestion window).
- Requires a return channel and tolerance for the added latency.
FEC — send redundancy so errors can be repaired in place:
- Cost when there is no error: the full redundancy, paid on every transmission. A rate-1/2 code doubles everything you send, forever.
- Cost when there is an error: nothing extra. Latency is unchanged.
- Needs no return channel and adds no delay.
So the decision comes down to three questions: How often do errors occur? How expensive is a round trip? Is there a return channel at all?
| Situation | Round-trip cost | Error rate | Right choice |
|---|---|---|---|
| Data-centre fibre | Microseconds | ~10⁻¹⁵ | Detection + ARQ (CRC only) |
| Enterprise Ethernet | Microseconds | ~10⁻¹² | Detection + ARQ |
| Wi-Fi | Microseconds locally | ~10⁻² | Both — FEC in the PHY, ARQ in the MAC |
| LTE / 5G | ~1 ms | ~10⁻¹ pre-FEC | Hybrid ARQ |
| GEO satellite | ~500 ms | Moderate | Heavy FEC |
| Deep space | Hours | High | FEC only — ARQ is useless |
| Broadcast / multicast | No return channel | Varies | FEC only |
| Optical disc, SSD | No retransmission possible | Moderate | FEC only (Reed-Solomon, LDPC) |
Three refinements complete the picture.
Real systems layer both. Wi-Fi runs LDPC at the physical layer to clean up the common case, then MAC-layer acknowledgement and retransmission for what gets through, then TCP end to end. Each layer handles the errors the one below could not, at its own cost scale — a direct application of the end-to-end argument, with lower layers acting as performance optimisations.
Hybrid ARQ is the modern synthesis. LTE and 5G transmit with FEC; if decoding fails, the retransmission carries different parity bits rather than the same data. The receiver combines both attempts — incremental redundancy — so a failed transmission is not wasted work but a partial down payment.
There is a third option: do nothing. For real-time media, a retransmitted video frame arrives after its playback deadline and is worthless. Such applications use UDP, accept loss, and conceal it — error concealment rather than error correction. This is why voice and video run over UDP and why a brief glitch is preferable to a stall.
Examples
Cost structure: the crossover depends on error rate and RTT
total cost = (always-paid redundancy) + (error rate x recovery cost)
ARQ : 0.3% overhead + p x RTT
FEC : 50% overhead + 0
Data-centre link (RTT = 0.1 ms, p = 1e-12):
ARQ : 0.3% + negligible <- clear winner
FEC : 50% + 0 <- paying 50% for nothing
GEO satellite (RTT = 500 ms, p = 1e-2):
ARQ : 0.3% + 0.01 x 500ms = 5 ms average added latency per frame
FEC : 50% + 0 <- winner: bandwidth is cheaper than delay
def arq_cost(p_error, rtt_ms, frame_ms, overhead=0.003):
"""Effective time per successfully delivered frame under ARQ."""
expected_attempts = 1 / (1 - p_error) # geometric distribution
retry_delay = (expected_attempts - 1) * rtt_ms
return frame_ms * (1 + overhead) + retry_delay, overhead
def fec_cost(p_error, rtt_ms, frame_ms, overhead=0.5, residual=1e-9):
"""FEC pays redundancy always; a small residual error rate still needs ARQ."""
retry_delay = (1 / (1 - residual) - 1) * rtt_ms
return frame_ms * (1 + overhead) + retry_delay, overhead
scenarios = [
("Data-centre fibre", 1e-12, 0.1),
("Enterprise Ethernet",1e-9, 1.0),
("Wi-Fi", 1e-2, 0.5),
("GEO satellite", 1e-2, 500.0),
("Deep space", 1e-1, 3_600_000.0),
]
print(f"{'scenario':<22}{'ARQ ms':>10}{'FEC ms':>10} better")
for name, p, rtt in scenarios:
a, _ = arq_cost(p, rtt, frame_ms=0.12)
f, _ = fec_cost(p, rtt, frame_ms=0.12)
print(f"{name:<22}{a:>10.3f}{f:>10.3f} {'FEC' if f < a else 'ARQ'}")
# scenario ARQ ms FEC ms better
# Data-centre fibre 0.120 0.180 ARQ
# Enterprise Ethernet 0.120 0.180 ARQ
# Wi-Fi 0.125 0.180 ARQ
# GEO satellite 5.171 0.180 FEC
# Deep space 400000.1 0.180 FEC
# The crossover is driven almost entirely by round-trip time.
Key takeaways
- ARQ costs almost nothing when errors are rare but one round trip when they occur; it needs a return channel.
- FEC costs its full redundancy on every transmission but adds no latency and needs no return channel.
- The choice depends on error rate, round-trip cost, and whether a return path exists at all.
- Low-error, low-latency links (wired Ethernet, data centres) use detection plus ARQ; high-latency or one-way links (satellite, deep space, broadcast, storage) use FEC.
- Real systems layer both, each layer cleaning up what the one below left, consistent with the end-to-end argument.
- Hybrid ARQ (LTE, 5G) sends FEC first and retransmits additional parity — incremental redundancy — so failed attempts are not wasted.
- For real-time media, the right answer is often neither: accept the loss and conceal it, since a late frame is worthless.
🧪 Practice
- A link has a 1 percent frame error rate and a 2 ms RTT. Compute the average delivery time per frame under ARQ with a 1 ms frame time.
- Explain why streaming video uses UDP and tolerates loss, while downloading the same video file uses TCP and does not.
- Interview-style: 5G uses hybrid ARQ with incremental redundancy rather than plain retransmission. What does this buy? (Hint: consider whether the first, failed transmission contained any useful information the receiver could still combine with the second.)
<a id="43-reliable-delivery-and-flow-control"></a>
4.3 Reliable Delivery and Flow Control
Detecting an error is only useful if something recovers from it; this subchapter builds the sliding-window machinery that turns an unreliable link into a reliable one, and derives why window size — not link speed — usually determines throughput.
Stop-and-Wait Protocol
Theory
The simplest possible reliable protocol: send one frame, wait for an acknowledgement, then send the next. If no ACK arrives before a timer expires, retransmit. It is obviously correct in spirit, and working out exactly why it is not quite correct — and what it costs — teaches most of what matters about reliable delivery.
The first bug: lost acknowledgements create duplicates. If the frame arrives but its ACK is lost, the sender times out and retransmits. The receiver now gets the same frame twice and, with no way to tell, delivers it twice. For a file transfer that corrupts the data; for a bank transfer it debits the account twice.
The fix is a sequence number, and the remarkable thing is how few bits it needs. Since only one frame is outstanding at a time, the receiver only ever needs to distinguish "the frame I expect" from "the one I just got" — so a single bit suffices. Frames alternate 0, 1, 0, 1, and the receiver discards any frame whose number it has already accepted while re-sending the ACK. This is the Alternating Bit Protocol.
The second bug: ACKs need numbers too. If ACKs are unnumbered, a delayed ACK for frame 0 can arrive while frame 1 is in flight and be mistaken for frame 1's acknowledgement. So ACKs carry the sequence number they refer to.
Once correct, the real problem with stop-and-wait is performance. The sender is idle for an entire round trip after every frame. Define:
- transmission time T_t = L / R (frame bits ÷ link rate)
- propagation time T_p — one-way delay
- a = T_p / T_t, the ratio of propagation to transmission time
Then utilisation is:
U = T_t / (T_t + 2·T_p) = 1 / (1 + 2a)
On a LAN, a is tiny and utilisation is fine. On a fast, long link, a is huge and utilisation collapses. This is the bandwidth-delay product problem from Chapter 1 appearing at the link layer: the faster and longer the link, the more data should be in flight, and stop-and-wait insists on exactly one frame.
The numbers are brutal. On a 1 Gb/s transcontinental link with 30 ms RTT, a 1500-byte frame takes 12 microseconds to transmit and then the sender waits 30,000 microseconds. Utilisation is about 0.04 percent — a gigabit link delivering 400 kb/s.
The analogy: stop-and-wait is posting one letter, then waiting for the reply before writing the next. The postal service is not the bottleneck; your protocol is.
Examples
Stop-and-wait timeline, and where the time goes
sender receiver
|---- frame 0 ----\ |
| T_t = 12 us \___ |
| \___ |
| \--------->| (T_p = 15 ms)
| | process
| /----------| ACK 0
| ___/ |
| ___/ |
|<----------------/ | (T_p = 15 ms)
|---- frame 1 ----> |
|
|<-- 12 us busy -->|<---- 30,000 us idle ---->|
Utilisation = 12 / 30,012 = 0.04%
Why one sequence bit is enough:
sender receiver sender receiver
frame(0) ----> accept 0 frame(0) ----> accept 0
ACK(0) <---- ACK(0) X lost
frame(1) ----> accept 1 timeout
frame(0) ----> "already have 0" -> DISCARD
but RESEND ACK(0)
Only two states must be distinguished, so one bit suffices.
def stop_and_wait_utilisation(frame_bytes, link_bps, rtt_ms):
t_transmit = (frame_bytes * 8) / link_bps # seconds to push bits out
t_rtt = rtt_ms / 1000
utilisation = t_transmit / (t_transmit + t_rtt)
return utilisation, t_transmit * 1e6, link_bps * utilisation
links = [
("LAN 1 Gb/s, 0.5 ms", 1e9, 0.5),
("Metro 1 Gb/s, 5 ms", 1e9, 5),
("National 1 Gb/s, 30 ms", 1e9, 30),
("Satellite 10 Mb/s, 500 ms", 10e6, 500),
]
print(f"{'link':<28}{'T_t (us)':>10}{'util':>9}{'effective':>14}")
for name, rate, rtt in links:
u, tt, eff = stop_and_wait_utilisation(1500, rate, rtt)
print(f"{name:<28}{tt:>10.1f}{u:>8.2%}{eff/1e6:>11.2f} Mb/s")
# link T_t (us) util effective
# LAN 1 Gb/s, 0.5 ms 12.0 2.34% 23.44 Mb/s
# Metro 1 Gb/s, 5 ms 12.0 0.24% 2.40 Mb/s
# National 1 Gb/s, 30 ms 12.0 0.04% 0.40 Mb/s
# Satellite 10 Mb/s, 500 ms 1200.0 0.24% 0.02 Mb/s
# A gigabit link delivering 400 kb/s. The link is fine; the protocol is not.
class AlternatingBitSender:
"""One sequence bit is sufficient because only one frame is ever in flight."""
def __init__(self):
self.seq = 0
def send(self, data):
return (self.seq, data)
def on_ack(self, ack_seq):
if ack_seq == self.seq:
self.seq ^= 1 # flip 0<->1 and advance
return "advance"
return "ignore duplicate/stale ACK"
class AlternatingBitReceiver:
def __init__(self):
self.expected = 0
def receive(self, seq, data):
if seq == self.expected:
self.expected ^= 1
return f"deliver {data!r}, ACK {seq}"
# A duplicate: do NOT deliver, but DO re-acknowledge so the sender advances.
return f"DISCARD duplicate {data!r}, re-ACK {seq}"
s, r = AlternatingBitSender(), AlternatingBitReceiver()
print()
print(r.receive(*s.send("A"))) # deliver 'A', ACK 0
print("(ACK lost; sender times out and retransmits)")
print(r.receive(*s.send("A"))) # DISCARD duplicate 'A', re-ACK 0
print(s.on_ack(0)) # advance
print(r.receive(*s.send("B"))) # deliver 'B', ACK 1
Key takeaways
- Stop-and-wait sends one frame and waits for its acknowledgement before sending the next, retransmitting on timeout.
- Without sequence numbers, a lost ACK causes the receiver to accept a duplicate; one bit of sequence number fixes this because only one frame is ever outstanding.
- ACKs must also carry sequence numbers, or a delayed ACK can be mistaken for a later frame's.
- A receiver that sees a duplicate must discard it but re-send the ACK, or the sender will never advance.
- Utilisation is U = 1/(1+2a) where a = propagation ÷ transmission time — it collapses on fast or long links.
- On a 1 Gb/s link with 30 ms RTT, stop-and-wait achieves about 0.04 percent utilisation, which motivates sliding windows.
🧪 Practice
- Compute stop-and-wait utilisation for a 100 Mb/s link with 10 ms RTT carrying 1500-byte frames.
- Draw the message exchange when a frame (rather than its ACK) is lost, and explain why the receiver's behaviour differs from the lost-ACK case.
- Interview-style: Why is one sequence bit sufficient for stop-and-wait but not for a sliding-window protocol? (Hint: count how many distinct frames can be unacknowledged at any moment in each design.)
Sliding Window Concept
Theory
Stop-and-wait wastes a round trip per frame. The fix is obvious once stated: allow several frames to be in flight at once. The sliding window is the mechanism that does this safely, and it is one of the most important ideas in networking — it appears again in TCP, in HTTP/2 flow control, and in QUIC.
The sender maintains a window: a range of sequence numbers it is permitted to have outstanding. Frames within the window may be sent without waiting. As acknowledgements arrive, the window's lower edge advances — it slides — admitting new frames at the top. The window's size caps how much unacknowledged data exists at any moment.
The sender's variables are:
- send_base — the oldest unacknowledged sequence number.
- next_seq — the next number to assign.
- N — window size, so the sender may transmit while
next_seq < send_base + N.
The window serves two distinct purposes that are worth separating, because conflating them causes confusion later:
- Flow control — preventing a fast sender from overwhelming a slow receiver. The receiver advertises how much buffer it has.
- Pipelining — keeping enough data in flight to fill the link's bandwidth-delay product.
The utilisation formula generalises stop-and-wait's, since stop-and-wait is simply the case N = 1:
U = min(1, N · T_t / (T_t + RTT)) = min(1, N / (1 + 2a))
This yields the central design rule: the window must be at least as large as the bandwidth-delay product divided by frame size to fill the link. If it is smaller, the sender stalls waiting for ACKs and throughput is capped at window ÷ RTT — regardless of how fast the link is. This is why a 10 Gb/s transatlantic link with a 64 KB window delivers a few megabits per second, and why TCP window scaling (Chapter 7) had to be invented.
One more constraint matters and is a classic exam trap. Sequence numbers are finite — k bits give 2^k values, and they wrap around. If the window is too large relative to that space, the receiver cannot distinguish a new frame from a retransmitted old one, and the protocol silently corrupts data. The safe limits differ by protocol:
| Protocol | Maximum window with k-bit sequence numbers |
|---|---|
| Go-Back-N | 2^k − 1 |
| Selective Repeat | 2^(k−1) |
The reasoning behind each is developed in the next two topics.
Examples
The window sliding as acknowledgements arrive
window size N = 4, sequence space 0..7
initial: [ 0 1 2 3 ] 4 5 6 7
^send_base ^next_seq
sent but unacknowledged: none yet; 4 frames may be sent
sent 0,1,2,3: [ 0 1 2 3 ] 4 5 6 7
^^^^^^^^^^ all in flight; sender must now WAIT
ACK 0 arrives: 0 [ 1 2 3 4 ] 5 6 7
^send_base ^ frame 4 is now permitted
the window SLID by one, admitting exactly one new frame
ACK 1, ACK 2: 0 1 2 [ 3 4 5 6 ] 7
^ three more frames admitted
Pipelining versus stop-and-wait, same link:
stop-and-wait: |F|--------wait---------|F|--------wait---------|
window N=8: |F|F|F|F|F|F|F|F|----wait----|F|F|F|F|F|F|F|F|--
^ 8x the data in the same round trip
def window_utilisation(window_frames, frame_bytes, link_bps, rtt_ms):
t_transmit = (frame_bytes * 8) / link_bps
t_rtt = rtt_ms / 1000
return min(1.0, window_frames * t_transmit / (t_transmit + t_rtt))
def required_window(link_bps, rtt_ms, frame_bytes):
"""Frames needed in flight to keep a link fully busy: the BDP in frames."""
bdp_bits = link_bps * (rtt_ms / 1000)
return -(-int(bdp_bits) // (frame_bytes * 8)) # ceiling division
links = [("LAN 1Gb/s 0.5ms", 1e9, 0.5), ("National 1Gb/s 30ms", 1e9, 30),
("Transatlantic 10Gb/s 80ms", 10e9, 80), ("Satellite 100Mb/s 500ms", 100e6, 500)]
print(f"{'link':<28}{'window needed':>15}{'BDP':>12}")
for name, rate, rtt in links:
w = required_window(rate, rtt, 1500)
print(f"{name:<28}{w:>13} fr {rate*rtt/1000/8/1e6:>9.2f} MB")
# link window needed BDP
# LAN 1Gb/s 0.5ms 42 fr 0.06 MB
# National 1Gb/s 30ms 2500 fr 3.75 MB
# Transatlantic 10Gb/s 80ms 66667 fr 100.00 MB
# Satellite 100Mb/s 500ms 4167 fr 6.25 MB
print()
for w in (1, 4, 16, 64, 2500):
u = window_utilisation(w, 1500, 1e9, 30)
print(f"window {w:>5} frames -> utilisation {u:>7.2%} "
f"= {1e9*u/1e6:>7.1f} Mb/s of 1000 Mb/s")
# window 1 frames -> utilisation 0.04% = 0.4 Mb/s of 1000 Mb/s
# window 4 frames -> utilisation 0.16% = 1.6 Mb/s of 1000 Mb/s
# window 16 frames -> utilisation 0.64% = 6.4 Mb/s of 1000 Mb/s
# window 64 frames -> utilisation 2.56% = 25.6 Mb/s of 1000 Mb/s
# window 2500 frames -> utilisation 100.00% = 1000.0 Mb/s of 1000 Mb/s
# Throughput is capped by window/RTT, NOT by link speed.
class SlidingWindowSender:
def __init__(self, window_size, seq_bits=3):
self.N = window_size
self.modulus = 2 ** seq_bits
self.send_base = 0
self.next_seq = 0
def can_send(self):
outstanding = (self.next_seq - self.send_base) % self.modulus
return outstanding < self.N
def send(self):
if not self.can_send():
return None # window full: must wait
seq = self.next_seq
self.next_seq = (self.next_seq + 1) % self.modulus
return seq
def on_ack(self, seq):
self.send_base = (seq + 1) % self.modulus # cumulative: slide past it
s = SlidingWindowSender(window_size=4)
print("\nsent:", [s.send() for _ in range(6)])
# sent: [0, 1, 2, 3, None, None] <- blocked after 4; the window is full
s.on_ack(0)
print("after ACK 0, next sends:", [s.send() for _ in range(2)])
# after ACK 0, next sends: [4, None] <- exactly one new frame admitted
Key takeaways
- A sliding window allows up to N frames to be unacknowledged at once, pipelining transmission instead of idling for a round trip per frame.
- The window's lower edge advances as ACKs arrive, admitting new frames at the top.
- It serves two purposes: flow control (protecting a slow receiver) and pipelining (filling the bandwidth-delay product).
- Utilisation is U = min(1, N/(1+2a)); throughput is capped at window ÷ RTT regardless of link speed.
- To fill a link, the window must be at least the bandwidth-delay product in frames — 66,667 frames for a 10 Gb/s transatlantic path.
- Sequence numbers are finite and wrap: Go-Back-N allows a window up to 2^k − 1, Selective Repeat only 2^(k−1).
🧪 Practice
- Compute the window size in 1500-byte frames needed to saturate a 100 Mb/s link with 40 ms RTT.
- A sender uses a 16-frame window on a link with a BDP of 500 frames. What throughput fraction does it achieve, and what is the fix?
- Interview-style: A transfer between two data centres runs at 8 Mb/s over a 10 Gb/s link with 100 ms RTT. The link tests clean. What do you suspect? (Hint: compute what window size 8 Mb/s over 100 ms implies, and compare it to a familiar default buffer size.)
Go-Back-N ARQ
Theory
The sliding window says how many frames may be outstanding. It does not say what to do when one of them is lost. Go-Back-N gives the simplest possible answer: throw away everything from the lost frame onward and resend it all.
The design is defined by one deliberate simplification: the receiver has a window of exactly 1. It accepts only the frame it is expecting next; anything out of order is discarded, even if it arrived intact. That single choice makes the receiver almost stateless — it needs one variable, expected_seq, and no buffers at all.
The consequences follow directly:
- Cumulative acknowledgement. ACK n means "I have received everything up to and including n". A lost ACK is therefore harmless — the next successful ACK covers it. This is a genuinely elegant property.
- On timeout, retransmit the entire window. The sender has no information about which frames after the lost one arrived, and since the receiver discarded them anyway, it resends all N.
- Out-of-order frames are wasted work. Frames that crossed the link successfully are discarded and must cross it again.
The name describes the behaviour: when frame n is lost, the sender goes back N frames and starts again.
The sequence number constraint is worth deriving, since it appears constantly in exams. With k bits there are 2^k sequence numbers. Suppose the window were the full 2^k. The sender transmits all 2^k frames; all arrive; all ACKs are lost. The sender times out and resends the entire window, starting with sequence 0. But the receiver is now expecting sequence 0 of the next batch — and cannot tell the retransmission from new data. It accepts a duplicate as fresh. Limiting the window to 2^k − 1 guarantees the ambiguity cannot arise.
Go-Back-N's efficiency depends sharply on the loss rate. With no loss, it fully pipelines. With loss, every single lost frame costs an entire window of retransmission — so on a high-BDP link, where the window must be large, a small loss rate is devastating. A window of 2500 frames and a 1 percent loss rate means roughly 25 frames retransmitted for every one actually lost.
| Go-Back-N | Selective Repeat | |
|---|---|---|
| Receiver window | 1 | N |
| Receiver buffering | None | Out-of-order frames buffered |
| ACK type | Cumulative | Individual |
| Retransmission on loss | Entire window | Only the lost frame |
| Max window (k-bit seq) | 2^k − 1 | 2^(k−1) |
| Complexity | Low | Higher |
| Best suited to | Low loss rates | Higher loss, large windows |
Examples
Go-Back-N with N=4: one loss, four retransmissions
sender receiver (expects 0)
|--- 0 ------------------------------>| accept 0, ACK 0 (expects 1)
|--- 1 ------------X (lost) |
|--- 2 ------------------------------>| expects 1, got 2 -> DISCARD, re-ACK 0
|--- 3 ------------------------------>| expects 1, got 3 -> DISCARD, re-ACK 0
|<-- ACK 0 ---------------------------|
|<-- ACK 0 ---------------------------| (duplicate ACKs)
| ... timeout on frame 1 ... |
|--- 1 ------------------------------>| accept 1, ACK 1
|--- 2 ------------------------------>| accept 2, ACK 2 <- resent needlessly
|--- 3 ------------------------------>| accept 3, ACK 3 <- resent needlessly
^ frames 2 and 3 crossed the link
TWICE though they arrived fine
Why the window must be <= 2^k - 1 (here k=2, so 4 sequence numbers 0..3):
BROKEN: window = 4
sender sends 0,1,2,3 receiver accepts all, expects 0 (of the NEXT batch)
all four ACKs lost
sender times out, resends 0,1,2,3
receiver sees 0 and accepts it as NEW DATA <-- silent corruption
SAFE: window = 3
sender sends 0,1,2 receiver accepts, expects 3
all ACKs lost, sender resends 0,1,2
receiver expects 3, sees 0 -> recognises it as old, discards. Correct.
class GoBackN:
def __init__(self, window, seq_bits=3):
self.N = window
self.mod = 2 ** seq_bits
assert window <= self.mod - 1, "window must be <= 2^k - 1"
self.base = 0 # oldest unacknowledged
self.next = 0 # next to send
self.expected = 0 # receiver side
self.transmissions = 0
def send_window(self):
"""Emit every frame currently permitted by the window."""
out = []
while (self.next - self.base) % self.mod < self.N:
out.append(self.next)
self.next = (self.next + 1) % self.mod
self.transmissions += 1
return out
def receive(self, seq):
if seq == self.expected:
self.expected = (self.expected + 1) % self.mod
return ("accept", (seq) % self.mod) # cumulative ACK
# Out of order: discard, and re-ACK the last good frame.
return ("discard", (self.expected - 1) % self.mod)
def timeout(self):
"""Go back: rewind next_seq to base and resend the whole window."""
self.next = self.base
return self.send_window()
gbn = GoBackN(window=4)
sent = gbn.send_window()
print("sent window:", sent) # sent window: [0, 1, 2, 3]
results = []
for seq in sent:
if seq == 1:
results.append((seq, "LOST IN TRANSIT"))
continue
results.append((seq, gbn.receive(seq)))
for seq, r in results:
print(f" frame {seq}: {r}")
# frame 0: ('accept', 0)
# frame 1: LOST IN TRANSIT
# frame 2: ('discard', 0) <- arrived intact, thrown away
# frame 3: ('discard', 0) <- arrived intact, thrown away
print("timeout -> resending:", gbn.timeout())
print(f"total transmissions for 4 frames: {gbn.transmissions}")
# timeout -> resending: [1, 2, 3, 0]
# total transmissions for 4 frames: 8
# Efficiency collapse on high-BDP links:
def gbn_efficiency(loss_rate, window):
"""Each loss costs roughly a whole window of retransmission."""
wasted = loss_rate * window
return max(0.0, 1 - wasted)
print()
for w in (4, 50, 500, 2500):
for p in (0.001, 0.01):
e = gbn_efficiency(p, w)
print(f"window {w:>4}, loss {p:>5.1%}: efficiency {e:>6.1%}")
# window 4, loss 0.1%: efficiency 99.6%
# window 4, loss 1.0%: efficiency 96.0%
# window 500, loss 0.1%: efficiency 50.0%
# window 500, loss 1.0%: efficiency 0.0%
# window 2500, loss 1.0%: efficiency 0.0%
# Large windows + any loss = Go-Back-N is unusable. Hence Selective Repeat.
Key takeaways
- Go-Back-N gives the receiver a window of 1: out-of-order frames are discarded even when intact, so the receiver needs no buffers.
- Acknowledgements are cumulative — ACK n means everything through n arrived — which makes lost ACKs harmless.
- On timeout the sender retransmits the entire window, wasting every frame that had already arrived successfully.
- The maximum window is 2^k − 1 for k-bit sequence numbers; a full 2^k window allows a retransmission to be mistaken for new data.
- Efficiency degrades sharply as window size grows, since each loss costs a whole window — making Go-Back-N unsuitable for high-BDP links with any loss.
🧪 Practice
- With a 5-frame window and frames 0–4 sent, frame 2 is lost. List exactly which frames the receiver accepts, discards, and which are retransmitted.
- Explain precisely why a window of 2^k breaks, using a 2-bit sequence number and a concrete scenario.
- Interview-style: Go-Back-N discards frames that arrived perfectly intact. Why would anyone design a protocol that way? (Hint: consider what the receiver must store and manage to do otherwise, and what hardware cost that implied in the 1970s.)
Selective Repeat ARQ
Theory
Go-Back-N's waste is unnecessary. If frames 2 and 3 arrived intact, why throw them away? Selective Repeat keeps them: the receiver buffers out-of-order frames and the sender retransmits only what was actually lost.
The changes from Go-Back-N are precisely three:
- The receiver has a window of N, not 1. It accepts any frame within that window, even out of order, and buffers it.
- Acknowledgements are individual, not cumulative. ACK n means "I got frame n specifically" and says nothing about others.
- Each frame has its own timer. When one expires, only that frame is resent.
The receiver delivers to the layer above only when a contiguous run is complete, so ordering is still guaranteed — data is simply held until the gap fills.
The cost is complexity: buffer management, per-frame timers, and a subtler correctness constraint. That constraint is the classic exam question, and it is genuinely counter-intuitive.
Why the window must be at most 2^(k−1). Consider a 2-bit sequence number (0–3) and a window of 3, which Go-Back-N would permit:
- Sender transmits frames 0, 1, 2. All arrive; the receiver delivers them and slides its window to accept 3, 0, 1.
- All three ACKs are lost.
- The sender times out on frame 0 and retransmits it.
- The receiver's window now covers 3, 0, 1 — so sequence number 0 is inside its window. It accepts the retransmitted old frame 0 as a brand-new frame. Silent data corruption.
The problem is that the sender's old window and the receiver's new window overlap in sequence-number space. The fix is to make the window no more than half the sequence space, so the two can never overlap. With k bits, the maximum safe window is 2^(k−1).
This is why Selective Repeat, despite retransmitting less, needs more sequence-number bits for the same window size — a trade that is almost always worth making, because sequence numbers are cheap and bandwidth is not.
Selective Repeat is what modern protocols actually do. TCP's SACK (Selective Acknowledgement) option adds selective-repeat behaviour to TCP's fundamentally cumulative scheme, letting a sender learn exactly which segments are missing. QUIC's acknowledgement format is selective by design. On any link with meaningful loss and a large window, the difference is the difference between working and not working.
Examples
Selective Repeat with N=4: only the lost frame is resent
sender receiver window [0..3]
|--- 0 ------------------------------>| accept 0, deliver, ACK 0
|--- 1 ------------X (lost) |
|--- 2 ------------------------------>| accept 2, BUFFER it, ACK 2
|--- 3 ------------------------------>| accept 3, BUFFER it, ACK 3
|<-- ACK 0, ACK 2, ACK 3 -------------|
| ... only frame 1's timer expires ...|
|--- 1 ------------------------------>| accept 1 -> now deliver 1,2,3 in order
^ 2 and 3 never crossed the link twice
Why the window must be <= 2^(k-1). k=2, sequence space 0..3, window 3:
sender window: [0 1 2] 3 sends 0,1,2
receiver accepts 0,1,2, delivers them, slides:
receiver window: 3 [0 1] ... i.e. now accepting 3,0,1
ALL ACKs LOST.
sender times out on 0, retransmits 0
receiver: "0 is in my window" -> ACCEPTS IT AS NEW DATA <-- CORRUPTION
With window = 2 (= 2^(2-1)):
sender window: [0 1] 2 3 sends 0,1
receiver accepts, slides to [2 3]
ACKs lost; sender resends 0
receiver: "0 is NOT in my window [2,3]" -> discards, re-ACKs. Correct.
class SelectiveRepeat:
def __init__(self, window, seq_bits=3):
self.N = window
self.mod = 2 ** seq_bits
assert window <= self.mod // 2, \
f"window must be <= 2^(k-1) = {self.mod//2} for {seq_bits}-bit sequences"
self.rcv_base = 0
self.buffer = {} # out-of-order frames held here
self.delivered = []
self.transmissions = 0
def in_window(self, seq, base):
return (seq - base) % self.mod < self.N
def receive(self, seq, data):
if not self.in_window(seq, self.rcv_base):
return f"seq {seq} outside window -> discard, re-ACK"
self.buffer[seq] = data # buffer even if out of order
action = f"accept {seq}, ACK {seq}"
# Deliver any contiguous run now available.
moved = []
while self.rcv_base in self.buffer:
moved.append(self.buffer.pop(self.rcv_base))
self.delivered.append(moved[-1])
self.rcv_base = (self.rcv_base + 1) % self.mod
if moved:
action += f" -> deliver {moved}"
else:
action += " -> buffered, waiting for gap to fill"
return action
sr = SelectiveRepeat(window=4, seq_bits=3)
print(sr.receive(0, "A"))
print(" (frame 1 lost in transit)")
print(sr.receive(2, "C"))
print(sr.receive(3, "D"))
print(sr.receive(1, "B")) # the retransmission arrives
print("delivered in order:", sr.delivered)
# accept 0, ACK 0 -> deliver ['A']
# (frame 1 lost in transit)
# accept 2, ACK 2 -> buffered, waiting for gap to fill
# accept 3, ACK 3 -> buffered, waiting for gap to fill
# accept 1, ACK 1 -> deliver ['B', 'C', 'D']
# delivered in order: ['A', 'B', 'C', 'D']
# The window constraint, enforced:
for bits in (2, 3, 4):
safe_sr = 2 ** (bits - 1)
safe_gbn = 2 ** bits - 1
print(f"\n{bits}-bit seq ({2**bits} numbers): "
f"GBN max window {safe_gbn}, SR max window {safe_sr}")
try:
SelectiveRepeat(window=3, seq_bits=2)
except AssertionError as e:
print("rejected:", e)
# rejected: window must be <= 2^(k-1) = 2 for 2-bit sequences
# Retransmission cost compared:
def cost(loss_rate, window, frames=10_000):
losses = loss_rate * frames
return {"Go-Back-N": frames + losses * window, # a whole window per loss
"Selective Repeat": frames + losses} # just the lost frame
print()
for w in (4, 100, 1000):
c = cost(0.01, w)
print(f"window {w:>4}: GBN sends {c['Go-Back-N']:>9,.0f} frames, "
f"SR sends {c['Selective Repeat']:>7,.0f} "
f"({c['Go-Back-N']/c['Selective Repeat']:.1f}x more)")
# window 4: GBN sends 10,400 frames, SR sends 10,100 (1.0x more)
# window 100: GBN sends 20,000 frames, SR sends 10,100 (2.0x more)
# window 1000: GBN sends 110,000 frames, SR sends 10,100 (10.9x more)
Key takeaways
- Selective Repeat buffers out-of-order frames at the receiver and retransmits only the frames actually lost.
- It requires a receiver window of N, individual acknowledgements, and a separate timer per frame.
- The maximum window is 2^(k−1) — half the sequence space — because a larger window lets the sender's old window and the receiver's new window overlap, causing a retransmission to be accepted as new data.
- Selective Repeat needs more sequence-number bits than Go-Back-N for the same window, a cheap price for avoiding redundant retransmission.
- The receiver still delivers in order, holding buffered frames until the gap is filled.
- Modern protocols are selective: TCP SACK and QUIC's acknowledgement design both exist for this reason.
🧪 Practice
- With a 4-frame window and frames 0–3 sent, frames 1 and 3 are lost. List what the receiver buffers, what it ACKs, and what the sender retransmits.
- Compute the maximum safe Selective Repeat window for 4-bit and 5-bit sequence numbers, and compare with Go-Back-N's limit.
- Interview-style: Why does Selective Repeat need a smaller maximum window than Go-Back-N for the same sequence space, when it is the more capable protocol? (Hint: the receiver's window also moves — draw where the sender's and receiver's windows sit after a batch of lost ACKs.)
Sequence Numbers and Timeouts
Theory
Two parameters decide whether a reliable protocol works correctly and whether it performs: how many sequence numbers exist, and how long the sender waits before assuming a frame is lost. Both have failure modes that are subtle and expensive.
Sequence numbers must satisfy two requirements simultaneously.
Large enough to keep the window unambiguous. This is the 2^k − 1 and 2^(k−1) constraint already derived. Violating it silently corrupts data, which is the worst kind of bug — no error is reported.
Large enough that an old duplicate cannot be mistaken for a new frame. This is the harder requirement. Sequence numbers wrap around; if a frame is delayed in the network long enough for the numbering to cycle completely and reach that value again, the delayed frame becomes indistinguishable from a current one. Protocols bound this with a maximum segment lifetime (MSL) — a guarantee that no packet survives longer than some fixed time — and choose a sequence space large enough that wraparound cannot occur within an MSL at the maximum link rate.
TCP's 32-bit sequence number was chosen this way, and it is instructive that it has since become marginal: at 100 Gb/s, 4 GB of sequence space is consumed in under a second, far faster than the 2-minute MSL. TCP's PAWS mechanism (Protect Against Wrapped Sequences) uses timestamps to disambiguate, which is precisely the fix this reasoning predicts.
Timeouts face a different tension:
- Too short — the sender retransmits frames that were merely slow. This wastes bandwidth, and in TCP it also triggers an unnecessary congestion-window collapse, so a premature timeout is doubly expensive.
- Too long — the sender sits idle after a genuine loss, adding latency directly to the application.
The correct value must exceed the round-trip time, but RTT varies constantly with queueing. So protocols measure it and adapt, using an exponentially weighted moving average. Jacobson's algorithm, which TCP uses, tracks both the smoothed mean and the variation:
SRTT = (1 - a) * SRTT + a * measured_RTT a = 1/8
RTTVAR = (1 - b) * RTTVAR + b * |SRTT - measured| b = 1/4
RTO = SRTT + 4 * RTTVAR
Including the variance term is the key insight, and it was a genuine breakthrough. A timeout based on the mean alone fires constantly whenever delay is jittery; adding four standard deviations of headroom makes spurious timeouts rare while keeping the timeout responsive.
Two supporting rules complete the design. Karn's algorithm says never to measure RTT from a retransmitted frame — you cannot tell whether the ACK refers to the original or the retransmission, and guessing wrong corrupts the estimate. And exponential backoff doubles the timeout after each consecutive failure, so a genuinely broken path is probed with decreasing frequency rather than flooded.
Examples
Why the variance term matters
Measured RTTs (ms): 100, 102, 98, 340, 101, 99, 105
^ one queueing spike
Timeout = mean only (100 ms):
the 340 ms sample already timed out -> spurious retransmission
and in TCP, an unnecessary congestion-window collapse
Timeout = SRTT + 4 x RTTVAR:
SRTT ~ 105 ms
RTTVAR ~ 30 ms (the spike raised it)
RTO ~ 225 ms -> absorbs moderate spikes without firing
Karn's ambiguity — why retransmitted frames must not be measured:
send frame 5 -------->|
(timeout) |
resend frame 5 ------->|
<----- ACK 5 |
Did that ACK answer the FIRST or the SECOND transmission?
Measuring from the first gives a huge RTT; from the second, a tiny one.
Both are wrong. Karn's rule: discard the sample entirely.
class RTOEstimator:
"""Jacobson/Karels RTT estimation, as specified for TCP in RFC 6298."""
ALPHA, BETA, K = 1/8, 1/4, 4
def __init__(self, min_rto=0.2, max_rto=60.0):
self.srtt = None
self.rttvar = None
self.min_rto, self.max_rto = min_rto, max_rto
self.backoff = 1
def update(self, measured_rtt, was_retransmitted=False):
if was_retransmitted:
return self.rto() # Karn's algorithm: ignore ambiguous samples
if self.srtt is None:
self.srtt = measured_rtt
self.rttvar = measured_rtt / 2
else:
# Variance FIRST — it uses the previous srtt.
self.rttvar = (1 - self.BETA) * self.rttvar \
+ self.BETA * abs(self.srtt - measured_rtt)
self.srtt = (1 - self.ALPHA) * self.srtt + self.ALPHA * measured_rtt
self.backoff = 1 # a good sample resets backoff
return self.rto()
def rto(self):
raw = self.srtt + self.K * self.rttvar
return min(self.max_rto, max(self.min_rto, raw)) * self.backoff
def on_timeout(self):
self.backoff *= 2 # exponential backoff on repeated failure
return self.rto()
est = RTOEstimator()
samples = [0.100, 0.102, 0.098, 0.340, 0.101, 0.099, 0.105]
print(f"{'sample':>8}{'SRTT':>9}{'RTTVAR':>9}{'RTO':>9} spurious?")
for s in samples:
rto_before = est.rto() if est.srtt else float("inf")
spurious = "YES" if s > rto_before else "no"
est.update(s)
print(f"{s*1000:>7.0f}ms{est.srtt*1000:>8.1f}{est.rttvar*1000:>9.1f}"
f"{est.rto()*1000:>8.1f} {spurious}")
# sample SRTT RTTVAR RTO spurious?
# 100ms 100.0 50.0 300.0 no
# 102ms 100.2 37.6 250.7 no
# 98ms 100.0 28.7 214.8 no
# 340ms 130.0 81.5 456.0 no <- absorbed; mean-only would have fired
# 101ms 126.4 68.4 400.0 no
# 99ms 123.0 58.1 355.5 no
# 105ms 120.8 47.1 309.2 no
# Zero spurious retransmissions despite a 3.4x latency spike.
print()
for n in range(1, 6):
print(f"consecutive timeout {n}: RTO = {est.on_timeout()*1000:>8.0f} ms")
# consecutive timeout 1: RTO = 618 ms
# consecutive timeout 5: RTO = 9895 ms <- backing off from a dead path
# Sequence space adequacy at modern speeds:
MSL_SECONDS = 120
for rate_gbps in (1, 10, 100, 400):
bps = rate_gbps * 1e9
wrap_seconds = (2**32) / (bps / 8) # 32-bit space, counted in bytes
status = "SAFE" if wrap_seconds > MSL_SECONDS else "WRAPS WITHIN MSL"
print(f"{rate_gbps:>4} Gb/s: 32-bit space wraps in {wrap_seconds:>7.2f} s {status}")
# 1 Gb/s: 32-bit space wraps in 34.36 s WRAPS WITHIN MSL
# 100 Gb/s: 32-bit space wraps in 0.34 s WRAPS WITHIN MSL
# This is exactly why TCP needs PAWS timestamps at high speed.
Key takeaways
- Sequence numbers must be large enough to keep the window unambiguous and to prevent a delayed old frame from matching a current number within the maximum segment lifetime.
- TCP's 32-bit space wraps in under a second at 100 Gb/s, which is why PAWS timestamps are needed at high rates.
- A timeout that is too short causes spurious retransmissions (and in TCP an unnecessary congestion-window collapse); too long adds idle latency after real losses.
- Jacobson's algorithm estimates both smoothed RTT and its variation, setting RTO = SRTT + 4·RTTVAR — including variance is what makes it robust to jitter.
- Karn's algorithm: never measure RTT from a retransmitted frame, because the ACK is ambiguous.
- Exponential backoff doubles the timeout after consecutive failures so a broken path is not flooded.
🧪 Practice
- Given SRTT = 80 ms and RTTVAR = 15 ms, compute the RTO. Then update both after a measured RTT of 200 ms.
- Explain what goes wrong if a protocol measures RTT from retransmitted frames, giving both directions of error.
- Interview-style: Why does TCP's RTO formula include four times the variance rather than a simple multiple of the mean? (Hint: think about what happens on a path whose delay is usually 10 ms but occasionally 200 ms.)
Link Utilization Analysis
Theory
This topic consolidates the arithmetic behind every performance question in this subchapter into one framework, because the same calculation answers a surprising range of real problems.
Start with the fundamental quantities:
- T_t = L/R — transmission (serialisation) time: how long to clock the frame onto the wire.
- T_p — one-way propagation delay, distance ÷ signal speed (roughly 200,000 km/s in fibre or copper).
- RTT = 2·T_p (ignoring processing and queueing).
- a = T_p / T_t — the ratio that governs everything.
The parameter a is the key abstraction. It answers: how many frame-times fit in one propagation delay? When a ≪ 1, the link is "short and slow" and a frame occupies the whole wire; pipelining barely matters. When a ≫ 1, the link is "long and fast", many frames fit on the wire simultaneously, and pipelining is everything.
The utilisation formulas follow:
| Protocol | Utilisation |
|---|---|
| Stop-and-wait | U = 1/(1 + 2a) |
| Sliding window (no loss) | U = min(1, N/(1 + 2a)) |
| Go-Back-N with loss p | U ≈ N(1−p) / [(1 + 2a)(1 + (N−1)p)] |
| Selective Repeat with loss p | U ≈ min(1, N/(1+2a)) · (1−p) |
Three practical consequences are worth internalising.
The optimal window is the bandwidth-delay product in frames. Compute BDP = R × RTT in bits, divide by frame size. Any smaller and the link idles; any larger buys nothing but buffer occupancy — and on a congested path, larger windows just fill router queues, adding latency without throughput (the bufferbloat problem of Chapter 12).
Throughput is capped at window ÷ RTT. This single formula explains an enormous fraction of real-world "why is my transfer slow" problems. It contains no term for link speed, which is exactly why upgrading a link often changes nothing.
Reducing RTT beats increasing bandwidth for small transfers. A 100 KB transfer over a 100 ms path takes several round trips regardless of link rate. This is why CDNs exist, and why HTTP/2 and QUIC worked so hard to eliminate round trips.
Examples
The parameter a decides which regime you are in
a << 1 (LAN: 1 Gb/s, 100 m)
|<--------- frame on the wire --------->|
[========================================]---> 0.5 us propagation
The frame is LONGER than the wire. Stop-and-wait is nearly fine.
a >> 1 (transatlantic: 10 Gb/s, 80 ms RTT)
|frame| |frame|
[=]-------------------------------------------------[=]
~66,000 frames fit on the wire at once.
Stop-and-wait uses 1/66,000 of the capacity.
SPEED_IN_FIBRE = 200_000_000 # m/s, about 2/3 of c
def analyse(link_bps, distance_km, frame_bytes=1500, window=1, loss=0.0):
t_t = (frame_bytes * 8) / link_bps
t_p = (distance_km * 1000) / SPEED_IN_FIBRE
a = t_p / t_t
rtt = 2 * t_p
u_sw = 1 / (1 + 2*a)
u_win = min(1.0, window / (1 + 2*a))
u_gbn = (window * (1-loss)) / ((1 + 2*a) * (1 + (window-1)*loss)) if loss else u_win
u_sr = min(1.0, window / (1 + 2*a)) * (1 - loss)
bdp_bits = link_bps * rtt
optimal_window = max(1, -(-int(bdp_bits) // (frame_bytes * 8)))
return {"a": a, "rtt_ms": rtt*1e3, "bdp_kb": bdp_bits/8/1024,
"optimal_window": optimal_window,
"U_stopwait": u_sw, "U_window": u_win,
"U_gbn": min(1.0, u_gbn), "U_sr": u_sr}
scenarios = [
("LAN 1 Gb/s, 0.1 km", 1e9, 0.1),
("Metro 1 Gb/s, 50 km", 1e9, 50),
("National 10 Gb/s, 3000 km", 10e9, 3000),
("Transatl. 10 Gb/s, 6000 km", 10e9, 6000),
]
for name, rate, dist in scenarios:
r = analyse(rate, dist)
print(f"{name}")
print(f" a = {r['a']:>10.2f} RTT = {r['rtt_ms']:>7.2f} ms "
f"BDP = {r['bdp_kb']:>10.1f} KB")
print(f" stop-and-wait utilisation: {r['U_stopwait']:>8.4%} "
f"optimal window: {r['optimal_window']:>6} frames")
# LAN 1 Gb/s, 0.1 km
# a = 0.04 RTT = 0.00 ms BDP = 0.1 KB
# stop-and-wait utilisation: 92.31% optimal window: 1 frames
# Transatl. 10 Gb/s, 6000 km
# a = 5000.00 RTT = 60.00 ms BDP = 73242.2 KB
# stop-and-wait utilisation: 0.0100% optimal window: 50000 frames
# The formula that explains most slow transfers:
print()
def throughput_from_window(window_bytes, rtt_ms):
return window_bytes * 8 / (rtt_ms / 1000) / 1e6 # Mb/s
for win_kb, rtt in [(64, 1), (64, 30), (64, 100), (4096, 100), (16384, 100)]:
t = throughput_from_window(win_kb * 1024, rtt)
print(f"window {win_kb:>6} KB, RTT {rtt:>4} ms -> {t:>9.2f} Mb/s "
f"(note: NO link-speed term appears)")
# window 64 KB, RTT 1 ms -> 524.29 Mb/s
# window 64 KB, RTT 30 ms -> 17.48 Mb/s
# window 64 KB, RTT 100 ms -> 5.24 Mb/s <- on a 10 Gb/s link!
# window 4096 KB, RTT 100 ms -> 335.54 Mb/s
# window 16384 KB, RTT 100 ms -> 1342.18 Mb/s
# Go-Back-N versus Selective Repeat as loss rises on a big window:
print()
for p in (0.0, 0.001, 0.01):
r = analyse(1e9, 3000, window=2500, loss=p)
print(f"loss {p:>6.2%}: GBN U={r['U_gbn']:>7.2%} SR U={r['U_sr']:>7.2%}")
# loss 0.00%: GBN U=100.00% SR U=100.00%
# loss 0.10%: GBN U= 28.56% SR U= 99.90%
# loss 1.00%: GBN U= 3.85% SR U= 99.00%
Key takeaways
- The parameter a = T_p/T_t determines the regime: a ≪ 1 means pipelining hardly matters; a ≫ 1 means it is everything.
- Stop-and-wait achieves 1/(1+2a); a sliding window achieves min(1, N/(1+2a)).
- The optimal window is the bandwidth-delay product in frames — smaller idles the link, larger only fills queues and adds latency.
- Throughput ≤ window ÷ RTT, a formula with no link-speed term, which explains why faster links often change nothing.
- For small transfers, reducing RTT beats adding bandwidth — the reason CDNs and round-trip-minimising protocols exist.
- Under loss with large windows, Go-Back-N collapses while Selective Repeat degrades only in proportion to the loss rate.
🧪 Practice
- Compute a, the BDP, and the optimal window for a 1 Gb/s link spanning 1000 km with 1500-byte frames.
- A transfer achieves 20 Mb/s over a 1 Gb/s link with 25 ms RTT. Infer the effective window size and identify the likely limit.
- Interview-style: A company upgrades its transatlantic link from 1 Gb/s to 10 Gb/s and sees no improvement in file-transfer speed. Explain, and give the fix. (Hint: write down which of the two terms in the throughput formula the upgrade actually changed.)
<a id="44-medium-access-control"></a>
4.4 Medium Access Control
When several stations share one medium, something must decide who transmits when; this subchapter works through the three families of answer — partition the channel, let stations contend, or take turns — and the protocols built from each.
Channel Partitioning: TDMA and FDMA
Theory
The medium access problem: N stations share one channel. If two transmit simultaneously, the signals collide and both are lost. Who gets to transmit, and when?
There are exactly three families of answer, and every MAC protocol ever designed belongs to one of them or combines them:
- Channel partitioning — divide the channel into pieces and give each station its own. No collisions are possible by construction.
- Random access — let stations transmit whenever they like, detect the resulting collisions, and recover. Covered in the next three topics.
- Taking turns — coordinate explicitly so only one station transmits at a time. Covered later in this subchapter.
This topic covers the first. The mechanisms are the multiplexing schemes from Chapter 3, applied now as access protocols — hence the extra "A" for Access:
TDMA (Time Division Multiple Access). Time is divided into frames, each containing N slots, and station i owns slot i in every frame. A station transmits at full channel rate during its slot and stays silent otherwise. Guaranteed access, guaranteed rate, zero collisions, and perfectly predictable latency. Used by GSM, Bluetooth's piconet scheduling, and satellite uplinks.
FDMA (Frequency Division Multiple Access). The channel's bandwidth is divided into N frequency bands and each station gets one permanently. Transmission is continuous rather than bursty. Used by analog cellular, cable upstream channels, and satellite transponders.
Both share the same fundamental virtue and the same fatal flaw.
The virtue is determinism. Each station is guaranteed exactly 1/N of the channel with bounded delay, regardless of what anyone else does. For constant-rate traffic like voice, this is exactly right — and it is why the telephone system was built this way.
The flaw is waste under bursty traffic. If a station has nothing to send, its slot goes out empty (TDMA) or its band sits idle (FDMA), and nobody else can use it. With data traffic, where stations are idle most of the time and then want everything at once, this is catastrophic. A station with data to send is limited to R/N even when all other stations are silent and the channel is 99 percent idle.
This is precisely the circuit-versus-packet argument from Chapter 1, appearing again at the MAC layer — and the resolution is the same. Random access protocols waste capacity on collisions but let an active station use the whole channel; partitioning wastes capacity on idle slots but never collides. Which is better depends entirely on how bursty the traffic is and how many stations are active at once.
| Channel partitioning | Random access | Taking turns | |
|---|---|---|---|
| Collisions | None | Yes | None |
| Efficiency at low load | Poor (idle slots wasted) | Excellent | Good (token overhead) |
| Efficiency at high load | Excellent | Degrades badly | Excellent |
| Delay | Bounded, predictable | Unbounded, variable | Bounded |
| Single active station gets | R/N | Nearly R | Nearly R |
| Example | GSM, satellite | Ethernet, Wi-Fi | Token Ring, DOCSIS |
The modern synthesis is hybrid: reservation protocols use a small contention period to request a slot, then grant collision-free slots for the data. DOCSIS (cable), LTE, and 5G all work this way, getting random access's low-load efficiency with partitioning's high-load determinism.
Examples
TDMA: guaranteed slots, wasted when idle
frame 1 frame 2 frame 3
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+
| A | B | | D | | A | | | | | A | B | C | D |
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+
1 2 3 4 1 2 3 4 1 2 3 4
^ C idle ^^^^^^^ three empty slots
Station A has a full queue but CANNOT use slot 2, 3, or 4.
Utilisation here: 6 useful slots out of 12 = 50%.
Random access, same traffic:
+---+---+---+---+ +---+---+---+---+
| A | B | A | D | | A | A | A | A | A takes every idle slot
+---+---+---+---+ +---+---+---+---+
Utilisation approaches 100% -- at the cost of occasional collisions.
def partitioning_throughput(n_stations, active_stations, link_bps):
"""Each station is capped at R/N whether or not others are using their share."""
per_station = link_bps / n_stations
used = per_station * active_stations
return per_station, used, used / link_bps
def random_access_throughput(n_stations, active_stations, link_bps, efficiency=0.9):
"""Active stations share whatever the contention protocol delivers."""
used = link_bps * efficiency if active_stations else 0
return used / max(active_stations, 1), used, used / link_bps
print(f"{'active/total':<14}{'TDMA per-stn':>15}{'TDMA util':>11}"
f"{'random per-stn':>17}{'random util':>13}")
for active in (1, 2, 5, 10):
p_each, _, p_util = partitioning_throughput(10, active, 100e6)
r_each, _, r_util = random_access_throughput(10, active, 100e6)
print(f"{active:>5}/10 {p_each/1e6:>12.1f} Mb/s{p_util:>10.0%}"
f"{r_each/1e6:>14.1f} Mb/s{r_util:>12.0%}")
# active/total TDMA per-stn TDMA util random per-stn random util
# 1/10 10.0 Mb/s 10% 90.0 Mb/s 90%
# 2/10 10.0 Mb/s 20% 45.0 Mb/s 90%
# 5/10 10.0 Mb/s 50% 18.0 Mb/s 90%
# 10/10 10.0 Mb/s 100% 9.0 Mb/s 90%
# One active station: TDMA gives it 10 Mb/s, random access gives it 90 Mb/s.
# All ten active: TDMA wins, because there are no collisions to pay for.
def tdma_delay(n_stations, slot_ms):
"""Worst-case wait: the slot you want just passed."""
return n_stations * slot_ms
for n in (4, 10, 50):
print(f"\n{n} stations, 1 ms slots: worst-case access delay "
f"{tdma_delay(n, 1):>3} ms, guaranteed share {100/n:>5.1f}%")
# 4 stations, 1 ms slots: worst-case access delay 4 ms, guaranteed share 25.0%
# 50 stations, 1 ms slots: worst-case access delay 50 ms, guaranteed share 2.0%
# The guarantee is real — but it shrinks linearly with the station count.
Key takeaways
- Every MAC protocol is channel partitioning, random access, taking turns, or a hybrid.
- TDMA assigns each station a repeating time slot; FDMA assigns each a frequency band. Both eliminate collisions by construction.
- Both give a deterministic guarantee: exactly 1/N of the channel with bounded delay, ideal for constant-rate traffic like voice.
- Both waste capacity badly under bursty traffic — an idle station's slot or band cannot be used by anyone else.
- A single active station is capped at R/N even when the rest of the channel is idle.
- This is the circuit-versus-packet trade-off from Chapter 1 reappearing at the MAC layer.
- Modern systems (DOCSIS, LTE, 5G) are hybrids: brief contention to request slots, then collision-free grants.
🧪 Practice
- Ten stations share a 100 Mb/s channel via TDMA. One has a 50 MB file to send and all others are idle. How long does the transfer take, and how long would it take on an idle random-access channel?
- Explain why GSM chose TDMA for voice while Ethernet chose random access for data, referring to traffic characteristics.
- Interview-style: DOCSIS uses contention slots for requests and scheduled slots for data. What problem does each half solve? (Hint: consider what happens at low load with pure partitioning, and at high load with pure contention.)
ALOHA and Slotted ALOHA
Theory
ALOHAnet, built at the University of Hawaii in 1971 by Norman Abramson, connected islands by radio and needed to share one channel among many stations that could not hear each other. Its protocol was radical in its simplicity, and it is the ancestor of Ethernet and Wi-Fi.
Pure ALOHA in full: when you have a frame, send it. That is the entire protocol. If an acknowledgement does not arrive, assume a collision occurred, wait a random time, and try again.
Its efficiency is bounded by a vulnerable period. A frame sent at time t is destroyed if any other station starts transmitting between t−T and t+T, where T is the frame transmission time — because a frame started just before yours overlaps your beginning, and one started just after overlaps your end. So the danger window is 2T, twice the frame duration.
Modelling arrivals as a Poisson process with G frame attempts per frame time, the probability of no other transmission in a 2T window is e^(−2G), giving throughput:
S = G · e^(−2G), maximised at G = 0.5 where S = 1/(2e) ≈ 0.184
Pure ALOHA's maximum channel utilisation is 18.4 percent. Over 80 percent of capacity is lost to collisions, even when the stations behave optimally.
Slotted ALOHA improves this with one small change: divide time into slots equal to one frame time, and require stations to begin transmitting only at slot boundaries. Now a frame can only collide with another frame in the same slot — partial overlaps are impossible. The vulnerable period halves from 2T to T:
S = G · e^(−G), maximised at G = 1 where S = 1/e ≈ 0.368
One requirement — synchronised clocks — doubles the throughput to 36.8 percent. That is a remarkable return, and it is a general lesson: constraining when stations may act often beats making them smarter about whether to act.
Both protocols share a serious pathology: instability under load. As offered load G rises past the optimum, throughput decreases — more attempts cause more collisions, causing more retransmissions, causing more attempts. Without careful backoff, the channel can collapse to near-zero throughput while every station transmits continuously. This congestion-collapse dynamic recurs throughout networking.
ALOHA's descendants are everywhere: Ethernet added carrier sensing to it, Wi-Fi added collision avoidance, and slotted ALOHA itself is still used for the random-access request channels in cellular and satellite systems, where its low latency at light load is exactly what a request channel needs.
Examples
Vulnerable periods: why slotting doubles throughput
PURE ALOHA — a frame is destroyed by anything overlapping either end
other frame starts here ----+ +---- or here
v v
time ---[////// my frame //////]--------------->
|<--- T --->|<--- T --->|
|<------- vulnerable period = 2T ------->|
S_max = 1/(2e) = 18.4%
SLOTTED ALOHA — transmissions start only on boundaries
time |--slot 1--|--slot 2--|--slot 3--|--slot 4--|
[/ my frame /]
^ only another frame in THIS SAME slot can collide
|<-- vulnerable period = T -->|
S_max = 1/e = 36.8%
import math
def pure_aloha(G): return G * math.exp(-2*G)
def slotted_aloha(G): return G * math.exp(-G)
print(f"{'offered G':>10}{'pure S':>10}{'slotted S':>12}")
for G in (0.1, 0.25, 0.5, 1.0, 1.5, 2.0, 3.0, 5.0):
print(f"{G:>10.2f}{pure_aloha(G):>10.3f}{slotted_aloha(G):>12.3f}")
# offered G pure S slotted S
# 0.10 0.082 0.090
# 0.50 0.184 0.303 <- pure ALOHA's optimum
# 1.00 0.135 0.368 <- slotted ALOHA's optimum
# 2.00 0.037 0.271 <- past the peak: MORE load, LESS throughput
# 5.00 0.000 0.034 <- congestion collapse
print(f"\npure ALOHA max : {1/(2*math.e):.4f} at G = 0.5")
print(f"slotted ALOHA max : {1/math.e:.4f} at G = 1.0")
print(f"improvement : {(1/math.e)/(1/(2*math.e)):.1f}x from slotting alone")
# pure ALOHA max : 0.1839 at G = 0.5
# slotted ALOHA max : 0.3679 at G = 1.0
# improvement : 2.0x from slotting alone
import random
def simulate_slotted(n_stations, p_transmit, slots=200_000):
"""Each station independently transmits in each slot with probability p."""
successes = collisions = idle = 0
for _ in range(slots):
senders = sum(1 for _ in range(n_stations) if random.random() < p_transmit)
if senders == 1: successes += 1 # exactly one -> success
elif senders == 0: idle += 1 # nobody -> wasted slot
else: collisions += 1 # two or more -> all lost
return successes/slots, collisions/slots, idle/slots
print(f"\n{'N':>4}{'p':>8}{'G':>7}{'success':>10}{'collision':>11}{'idle':>8}")
for n, p in [(10, 0.02), (10, 0.10), (10, 0.30), (50, 0.02), (50, 0.10)]:
s, c, i = simulate_slotted(n, p)
print(f"{n:>4}{p:>8.2f}{n*p:>7.2f}{s:>10.3f}{c:>11.3f}{i:>8.3f}")
# N p G success collision idle
# 10 0.02 0.20 0.166 0.017 0.817 <- mostly idle: wasted capacity
# 10 0.10 1.00 0.388 0.264 0.348 <- near optimum
# 10 0.30 3.00 0.122 0.850 0.028 <- collapse: channel is thrashing
# 50 0.10 5.00 0.029 0.971 0.000 <- almost nothing gets through
# The optimal per-station probability is 1/N — the source of G = 1.
for n in (2, 10, 100):
s, _, _ = simulate_slotted(n, 1/n, slots=100_000)
print(f"N={n:>4}, p=1/N: throughput {s:.3f} (limit is 1/e = 0.368)")
Key takeaways
- Pure ALOHA transmits immediately with no coordination; its vulnerable period is 2T, giving a maximum throughput of 1/(2e) ≈ 18.4 percent.
- Slotted ALOHA requires transmissions to start on slot boundaries, halving the vulnerable period to T and doubling throughput to 1/e ≈ 36.8 percent.
- Optimal offered load is G = 0.5 for pure and G = 1 for slotted; each station should transmit with probability about 1/N.
- Beyond the optimum, throughput decreases with increasing load — a congestion-collapse feedback loop that recurs throughout networking.
- Constraining when stations may transmit doubled performance without making any station smarter — a broadly applicable design lesson.
- ALOHA is the direct ancestor of Ethernet (which added carrier sensing) and Wi-Fi, and slotted ALOHA still serves as the request channel in cellular and satellite systems.
🧪 Practice
- Compute throughput for pure and slotted ALOHA at G = 0.3 and G = 2.0, and explain the difference in trend.
- Fifty stations use slotted ALOHA. What per-station transmission probability maximises throughput, and what throughput results?
- Interview-style: Slotted ALOHA doubles throughput over pure ALOHA by adding only clock synchronisation. Why is the gain exactly a factor of two? (Hint: write down the vulnerable period of each and compare the exponents.)
CSMA and CSMA/CD
Theory
ALOHA transmits blindly. But on most shared media a station can listen first — and it is obviously wasteful to transmit into a channel you can hear is already busy. Adding that one behaviour produces CSMA (Carrier Sense Multiple Access): listen before talking.
The human analogy is exact. ALOHA is a meeting where everyone speaks whenever a thought occurs. CSMA is a meeting where people wait for a pause. The second is dramatically more productive, and for the same reason.
Carrier sensing does not eliminate collisions, because of propagation delay. If station A begins transmitting and station B checks the channel before A's signal has physically reached it, B hears silence and transmits too. The vulnerability window is now the propagation delay rather than the frame time — much smaller, but not zero. The further apart the stations, the worse it gets.
CSMA comes in variants distinguished by what a station does when it finds the channel busy:
| Variant | Behaviour when busy | Behaviour when idle | Trade-off |
|---|---|---|---|
| 1-persistent | Keep listening continuously | Transmit immediately (probability 1) | Low delay; collides badly when several stations are waiting |
| Non-persistent | Wait a random time, then check again | Transmit immediately | Fewer collisions; wastes idle time |
| p-persistent | Keep listening | Transmit with probability p, else defer one slot | Tunable compromise, used on slotted channels |
The 1-persistent flaw is worth understanding: if three stations are waiting for a long frame to finish, all three transmit the instant it ends, and all three collide. Guaranteed. This is why Ethernet's backoff matters so much.
CSMA/CD adds the second improvement: collision detection. A station keeps listening while transmitting; if what it hears differs from what it sent, a collision is in progress. Rather than wasting the remaining frame time, it aborts immediately, sends a 32-bit jam signal so every station registers the collision, and backs off.
The gain is substantial. Under ALOHA a collision wastes an entire frame time; under CSMA/CD it wastes only the time until detection — microseconds rather than milliseconds. This is what made shared Ethernet practical.
Collision detection imposes the constraint that explains Ethernet's most famous magic number. A station must still be transmitting when the collision reaches it; otherwise it would finish, conclude success, and never retransmit. The worst case is a collision at the far end of a maximum-length segment, so the frame must take at least 2τ to transmit, where τ is the one-way propagation delay. For 10 Mb/s Ethernet with a 2500 m maximum diameter, 2τ works out to 512 bit times = 64 bytes — the minimum frame size, which is why short frames are padded.
That constraint is also why CSMA/CD did not scale. Minimum frame size must grow with the bit-rate-times-distance product. Gigabit Ethernet needed "carrier extension" padding frames to 512 bytes to keep half-duplex working, which was so wasteful that the answer became obvious: abandon the shared medium entirely. Full-duplex switched links have no collisions at all, so CSMA/CD is simply disabled. In 10 Gb/s Ethernet and above, half-duplex operation is not even defined.
Examples
CSMA/CD in action
t=0 A senses idle, starts transmitting
t=τ-ε B senses idle (A's signal has NOT arrived yet), starts transmitting
t=τ A's signal reaches B -> B detects collision, jams, aborts
t=2τ B's signal reaches A -> A detects collision, jams, aborts
^ A must STILL be transmitting at t=2τ, or it would never know.
=> minimum frame time >= 2τ => minimum frame size
A |=====transmit=====X jam |
| / \ |
| / \ |
B |------X=transmit=X jam |
^ B starts ^ B detects
|<-τ->|<-τ->|
|<--- 2τ = 512 bit times = 64 bytes --------->|
1-persistent's pathology:
long frame in progress ============================|
A waiting --------------------------------------> |TX
B waiting --------------------------------------> |TX all three fire
C waiting --------------------------------------> |TX at the same instant
COLLISION, guaranteed
SPEED = 200_000_000 # m/s in copper
def min_frame_bytes(link_bps, max_distance_m):
"""A frame must take at least 2 x one-way propagation time to transmit."""
tau = max_distance_m / SPEED
min_bits = link_bps * 2 * tau
return min_bits / 8, tau * 1e6
configs = [
("10BASE5 10 Mb/s, 2500 m", 10e6, 2500),
("100BASE-T 100 Mb/s, 250 m", 100e6, 250),
("1000BASE-T 1 Gb/s, 200 m", 1e9, 200),
("1000BASE-T 1 Gb/s, 2500 m", 1e9, 2500),
]
for name, rate, dist in configs:
b, tau = min_frame_bytes(rate, dist)
print(f"{name:<28} tau={tau:>6.2f} us -> min frame {b:>8.1f} bytes")
# 10BASE5 10 Mb/s, 2500 m tau= 12.50 us -> min frame 31.2 bytes
# 100BASE-T 100 Mb/s, 250 m tau= 1.25 us -> min frame 31.2 bytes
# 1000BASE-T 1 Gb/s, 200 m tau= 1.00 us -> min frame 250.0 bytes
# 1000BASE-T 1 Gb/s, 2500 m tau= 12.50 us -> min frame 3125.0 bytes
# ^ a 3 KB minimum frame is absurd. This is why half-duplex gigabit
# needed carrier extension, and why switching replaced it entirely.
import random
def simulate_csma(n_stations, load, persistent=True, slots=100_000, tau_slots=1):
"""Compare 1-persistent CSMA against ALOHA-style blind transmission."""
busy_until, success, collision = 0, 0, 0
waiting = []
for t in range(slots):
arrivals = [i for i in range(n_stations) if random.random() < load/n_stations]
waiting.extend(arrivals)
if t < busy_until:
continue # channel busy: defer
if not waiting:
continue
if persistent:
senders = len(waiting) # ALL waiting stations fire
waiting = []
else:
senders = sum(1 for _ in waiting if random.random() < 0.3)
waiting = [w for w in waiting if random.random() >= 0.3]
if senders == 1:
success += 1; busy_until = t + 10 # frame occupies 10 slots
elif senders > 1:
collision += 1; busy_until = t + tau_slots # CD aborts quickly
total = success + collision
return success / total if total else 0
print()
for load in (0.2, 0.5, 0.9):
eff = simulate_csma(10, load)
print(f"offered load {load:>4.1f}: 1-persistent CSMA/CD success rate {eff:>6.1%}")
# offered load 0.2: 1-persistent CSMA/CD success rate 92.6%
# offered load 0.5: 1-persistent CSMA/CD success rate 73.1%
# offered load 0.9: 1-persistent CSMA/CD success rate 58.4%
# Far better than ALOHA's 18-37% ceiling — carrier sensing plus early abort.
Key takeaways
- CSMA listens before transmitting, eliminating the collisions ALOHA suffers from transmitting into a busy channel.
- Collisions still occur within the propagation delay window, before a distant station's signal has arrived.
- Variants differ in what to do when busy: 1-persistent (transmit the instant it clears — collides when several wait), non-persistent (random wait), p-persistent (tunable).
- CSMA/CD listens while transmitting, aborts on collision, and sends a jam signal — reducing collision cost from a full frame time to microseconds.
- A station must still be transmitting when the collision returns, requiring a minimum frame time of 2τ — which is Ethernet's 64-byte minimum frame (512 bit times).
- Minimum frame size must grow with bit rate × distance, which is why CSMA/CD did not scale past gigabit and why switched full-duplex links replaced it.
🧪 Practice
- Compute the minimum frame size for a 100 Mb/s CSMA/CD network with a 500 m maximum diameter.
- Explain why 1-persistent CSMA collides reliably when several stations queue behind a long frame, and how binary exponential backoff resolves it.
- Interview-style: Why is CSMA/CD disabled on a full-duplex switched Ethernet link, and what would go wrong if it were left enabled? (Hint: define physically what a collision is, and ask whether that event can occur when each direction has its own dedicated path.)
CSMA/CA and Hidden Terminal Problem
Theory
Wireless cannot use CSMA/CD, for a reason rooted in radio physics: a station cannot detect collisions while transmitting. Its own signal at the antenna is perhaps a million times stronger than any incoming one, so listening while transmitting reveals nothing but itself. The entire "detect and abort" mechanism is unavailable.
Worse, carrier sensing itself becomes unreliable, because in radio not every station can hear every other station. Two distinct pathologies follow.
The hidden terminal problem. Stations A and C are both within range of access point B but out of range of each other. A transmits to B. C senses the channel, hears nothing (A is hidden from it), and transmits too. The signals collide at B, though neither A nor C can detect it. Carrier sensing has failed completely — the stations sensed the wrong location. What matters is whether the channel is busy at the receiver, and the sender cannot observe that.
The exposed terminal problem. The mirror image: B is transmitting to A, and C wants to transmit to D. C hears B and defers — but C's transmission to D would not have interfered with A at all. Carrier sensing causes an unnecessary loss of capacity.
802.11's response is CSMA/CA (Collision Avoidance), built from several mechanisms:
- Sense the channel, and if busy, defer — as in CSMA.
- Random backoff even when the channel is idle. Unlike 1-persistent CSMA, a station that finds the channel free still waits a random number of slots. This prevents the guaranteed collision when several stations are queued behind a transmission.
- Acknowledge every frame. Since collisions cannot be detected, the only evidence of success is a returning ACK. A missing ACK means retransmit.
- Interframe spaces (IFS) to create priority. SIFS (shortest) is used for ACKs, so an acknowledgement always wins the channel over new data. DIFS (longer) is for ordinary transmissions. The different waiting times form a simple priority system.
- Optional RTS/CTS to solve hidden terminals. The sender transmits a short Request To Send; the AP replies with a Clear To Send that every station in the AP's range hears — including hidden ones. Both frames carry a duration field that sets each listener's NAV (Network Allocation Vector), a countdown during which it will not transmit. This is virtual carrier sensing: stations defer based on announced duration rather than on what they can hear.
RTS/CTS costs two extra frame exchanges, so it is typically enabled only above a size threshold, where the cost of a collision exceeds the cost of the handshake.
These mechanisms are why Wi-Fi's efficiency is markedly lower than Ethernet's — a significant fraction of airtime goes to backoff, interframe spaces, acknowledgements, and control frames rather than data.
Examples
Hidden terminal: carrier sensing senses the WRONG place
A ((( -------> [B] <------- ))) C
|<-- A's range -->|<-- C's range -->|
A and C cannot hear each other.
A senses idle -> transmits to B
C senses idle (truly cannot hear A) -> transmits to B
BOTH signals arrive at B and collide. Neither sender can tell.
RTS/CTS fixes it by having the RECEIVER announce the reservation:
A --RTS(duration=2ms)--> B
B --CTS(duration=2ms)--> everyone in B's range, INCLUDING C
^ C hears the CTS even though it cannot hear A
C sets NAV = 2 ms and stays silent. No collision.
Exposed terminal: carrier sensing is TOO conservative
A <------ ((( B ))) ------> C ------> D
B transmits to A. C hears B and defers.
But C -> D would not have disturbed A at all. Capacity wasted.
The IFS priority ladder:
|<-SIFS->| ACKs, CTS — shortest wait, always wins
|<--PIFS-->| contention-free polling
|<---DIFS--->| ordinary data — longest wait, lowest priority
Shorter wait = higher priority, with no explicit negotiation.
import random
SLOT_US, SIFS_US, DIFS_US = 9, 16, 34
def csma_ca_backoff(collision_count, cw_min=15, cw_max=1023):
"""Contention window doubles on each failure, exactly like Ethernet's."""
cw = min(cw_max, (cw_min + 1) * (2 ** collision_count) - 1)
return random.randint(0, cw), cw
print(f"{'attempt':>8}{'CW':>7}{'backoff slots':>15}{'wait (us)':>12}")
for n in range(6):
slots, cw = csma_ca_backoff(n)
print(f"{n:>8}{cw:>7}{slots:>15}{slots*SLOT_US:>12}")
# attempt CW backoff slots wait (us)
# 0 15 7 63
# 1 31 22 198
# 2 63 48 432
# 5 511 308 2772
# The window doubles, spreading retries further apart as contention rises.
def airtime_us(payload_bytes, rate_mbps, use_rts=False):
"""Total channel time for one successful frame exchange."""
data_us = (payload_bytes + 36) * 8 / rate_mbps # + 802.11 headers
ack_us = 14 * 8 / 24 # ACK at a basic rate
avg_backoff = 7.5 * SLOT_US # mean of CW_min = 15
total = DIFS_US + avg_backoff + data_us + SIFS_US + ack_us
if use_rts:
rts_us, cts_us = 20 * 8 / 24, 14 * 8 / 24
total += rts_us + SIFS_US + cts_us + SIFS_US # the handshake's cost
return total
print()
for size in (100, 500, 1500):
for rts in (False, True):
t = airtime_us(size, 100)
eff = (size * 8 / 100) / t
label = "with RTS/CTS" if rts else "no RTS/CTS "
t2 = airtime_us(size, 100, rts)
eff2 = (size * 8 / 100) / t2
if rts:
print(f"{size:>5} B {label}: {t2:>7.1f} us, efficiency {eff2:>5.1%}")
else:
print(f"{size:>5} B {label}: {t:>7.1f} us, efficiency {eff:>5.1%}")
print()
# 100 B no RTS/CTS : 131.5 us, efficiency 6.1%
# 100 B with RTS/CTS: 174.8 us, efficiency 4.6%
# 1500 B no RTS/CTS : 243.5 us, efficiency 49.3%
# 1500 B with RTS/CTS: 286.8 us, efficiency 41.8%
# RTS/CTS overhead is fixed, so it hurts small frames most — hence the
# size threshold. For large frames threatened by hidden terminals, it pays.
Key takeaways
- Radios cannot detect collisions while transmitting, because their own signal overwhelms the receiver — so CSMA/CD is impossible on wireless.
- The hidden terminal problem: two stations out of range of each other collide at a receiver both can reach; carrier sensing measures the wrong location.
- The exposed terminal problem: a station defers unnecessarily because it hears a transmission that would not have interfered with its own destination.
- CSMA/CA adds random backoff even on an idle channel, mandatory acknowledgements, and interframe spaces that create implicit priority (SIFS for ACKs beats DIFS for data).
- RTS/CTS solves hidden terminals by having the receiver broadcast a CTS that hidden stations can hear, setting their NAV for virtual carrier sensing.
- RTS/CTS costs two extra exchanges, so it is enabled only above a frame-size threshold.
- These overheads are why Wi-Fi's usable throughput is well below its nominal rate.
🧪 Practice
- Draw a four-station topology exhibiting both a hidden terminal pair and an exposed terminal pair, and label which station suffers what.
- Explain why SIFS is shorter than DIFS, and what would break if acknowledgements had to wait DIFS.
- Interview-style: Wi-Fi advertises 1.2 Gb/s but a file transfer reaches 600 Mb/s on a clean, close link. Where did the rest go? (Hint: list everything that occupies airtime but carries no user data.)
Token Passing and Polling
Theory
Random access is efficient at low load and degrades under contention. Channel partitioning is efficient at high load and wasteful when idle. The third family — taking turns — attempts to get both: coordinate explicitly so collisions never occur, but grant the channel only to stations that actually want it.
Token passing. A special short frame, the token, circulates among stations in a logical ring. Only the station holding the token may transmit. When it finishes — or when its token holding time expires — it passes the token to the next station. No collisions are possible, because permission is explicit and unique.
The properties are genuinely attractive:
- Deterministic, bounded delay. The worst-case wait is one full token rotation. A station can compute exactly how long it might wait, which matters enormously for industrial control and real-time systems.
- Efficient at high load. No capacity is lost to collisions; overhead is just the token itself.
- Fair by construction. Every station gets a turn in strict order.
The drawbacks are equally real:
- Overhead at low load. With one active station and 50 idle ones, the token still circulates through all 50.
- Token loss is catastrophic. If the holder crashes mid-transmission, the token vanishes and the network stops. Recovery requires a monitor station that detects the absence and regenerates it — added complexity and a single point of failure.
- Token duplication is equally damaging and must also be detected.
- Ring maintenance: stations joining and leaving must be handled without disrupting circulation.
IEEE 802.5 Token Ring and FDDI were the major implementations. Token Ring was technically superior to contemporary Ethernet in several respects — deterministic latency, better high-load efficiency, priority support — and lost comprehensively anyway. The reasons are worth noting because they recur: Ethernet was simpler, cheaper, and improved faster, and once switching removed Ethernet's collision problem, Token Ring's main advantage evaporated. Being technically better is not sufficient.
Polling. A designated controller asks each station in turn whether it has data. The station replies with data or a negative response. This centralises the coordination that token passing distributes.
Polling is simpler for the stations — they need no ring-maintenance logic — but introduces polling overhead (the round trip to ask) and a single point of failure in the controller. It suits star topologies with a natural master: Bluetooth's piconet, USB, legacy mainframe terminals, and — importantly — modern cellular and DOCSIS, where the base station or cable head-end schedules every upstream transmission.
| Token passing | Polling | |
|---|---|---|
| Coordination | Distributed | Centralised |
| Single point of failure | Monitor station | Controller |
| Overhead | Token circulation | Poll messages |
| Failure mode | Token loss/duplication | Controller failure |
| Example | Token Ring, FDDI, PROFIBUS | Bluetooth, USB, DOCSIS, LTE |
The modern relevance is significant even though Token Ring is dead: scheduled access has returned. LTE, 5G, DOCSIS, and Wi-Fi 6's OFDMA all have a central scheduler granting transmission opportunities — polling by another name. The reason is the same one that motivated token passing: at high load with many stations, contention wastes too much, and deterministic scheduling wins.
Examples
Token passing: permission circulates explicitly
+---> [A] ---> [B] ---> [C] ---> [D] ---+
| has |
+------token----------------------------+
A holds the token -> A may transmit (up to its holding time)
A finishes -> passes token to B
B has nothing -> passes immediately to C
C transmits, then passes to D ...
Worst-case wait for any station = one full rotation.
NO collisions are possible: permission is unique and explicit.
Token loss and recovery:
A holds token -> A crashes mid-frame
... silence ...
Monitor station's timer expires -> "no token has passed in N ms"
Monitor purges the ring and issues a NEW token.
Correct, but it is extra machinery and a dependency on one station.
Polling:
[Controller] --"A, anything?"--> [A] <--"yes, here"-- data
--"B, anything?"--> [B] <--"nothing"---- NAK (wasted round trip)
--"C, anything?"--> [C] <--"yes, here"-- data
def token_ring_delay(n_stations, frame_ms, token_pass_ms, active_fraction):
"""Worst-case wait is one full rotation: all active frames plus all token hops."""
active = max(1, int(n_stations * active_fraction))
rotation = active * frame_ms + n_stations * token_pass_ms
efficiency = (active * frame_ms) / rotation
return rotation, efficiency
print(f"{'stations':>9}{'active':>8}{'rotation ms':>13}{'efficiency':>12}")
for n in (10, 50, 100):
for frac in (0.05, 1.0):
rot, eff = token_ring_delay(n, frame_ms=1.2, token_pass_ms=0.01,
active_fraction=frac)
print(f"{n:>9}{frac:>8.0%}{rot:>13.2f}{eff:>12.1%}")
# stations active rotation ms efficiency
# 10 5% 2.50 48.0% <- token overhead dominates
# 10 100% 12.10 99.2% <- excellent at high load
# 100 5% 7.00 85.7%
# 100 100% 121.00 99.2%
# Token passing is the mirror image of random access: it shines under load.
def polling_efficiency(n_stations, frame_ms, poll_overhead_ms, active_fraction):
active = max(1, int(n_stations * active_fraction))
# The controller pays the poll cost for EVERY station, active or not.
cycle = n_stations * poll_overhead_ms + active * frame_ms
return (active * frame_ms) / cycle
print()
for n in (10, 100):
for frac in (0.1, 1.0):
e = polling_efficiency(n, 1.2, 0.05, frac)
print(f"polling {n:>4} stations, {frac:>4.0%} active: efficiency {e:>6.1%}")
# polling 10 stations, 10% active: efficiency 70.6%
# polling 10 stations, 100% active: efficiency 96.0%
# polling 100 stations, 10% active: efficiency 70.6%
# polling 100 stations, 100% active: efficiency 96.0%
# Comparing all three families at varying load:
import math
def aloha(G): return G * math.exp(-G)
print(f"\n{'load':>6}{'slotted ALOHA':>15}{'CSMA/CD':>10}{'token ring':>12}")
for load in (0.1, 0.3, 0.6, 0.9):
a = aloha(load)
c = min(0.95, 0.95 - 0.4 * max(0, load - 0.5)) # rough CSMA/CD behaviour
_, t = token_ring_delay(20, 1.2, 0.01, load)
print(f"{load:>6.1f}{a:>15.2f}{c:>10.2f}{t:>12.2f}")
# load slotted ALOHA CSMA/CD token ring
# 0.1 0.09 0.95 0.86
# 0.3 0.22 0.95 0.95
# 0.6 0.33 0.91 0.97
# 0.9 0.37 0.79 0.98
# Random access wins at low load; taking turns wins at high load.
Key takeaways
- Token passing circulates an explicit permission frame; only the holder may transmit, so collisions are impossible.
- It provides deterministic bounded delay (one token rotation) and high efficiency under load, making it attractive for industrial and real-time use.
- Its weaknesses are token-circulation overhead at low load, and the need for a monitor station to recover from token loss or duplication.
- Polling centralises the same idea: a controller asks each station in turn. Simpler stations, but poll overhead and a single point of failure.
- Token Ring was technically superior to early Ethernet and still lost — Ethernet was simpler, cheaper, and switching removed its main weakness.
- Scheduled access has returned in LTE, 5G, DOCSIS, and Wi-Fi 6 OFDMA, because central scheduling beats contention at high load with many stations.
🧪 Practice
- A 20-station token ring has 2 ms frames and 0.1 ms token passing. Compute worst-case access delay when all stations are active.
- Explain what happens if the token-holding station fails mid-transmission, and what mechanism recovers the ring.
- Interview-style: Token Ring offered deterministic latency that Ethernet could not match, yet it disappeared. Why? (Hint: consider cost, complexity, rate of improvement, and what switching did to Ethernet's collision problem.)
Binary Exponential Backoff
Theory
When a collision occurs, both stations must retry — but if they retry immediately, they collide again, and again, forever. They need to retry at different times, and since they cannot communicate to negotiate, the only option is randomness. That is the first half of the idea.
The second half is subtler and more important. How wide should the random range be? If it is too narrow, collisions recur because there are too few slots to spread across. If it is too wide, stations wait needlessly when contention is actually light. And the protocol has no way to know how many stations are competing.
Binary exponential backoff solves this by learning from failure. After the nth consecutive collision, the station waits a random number of slot times chosen uniformly from 0 to 2ⁿ−1:
| Collision | Range (slots) | Possible waits |
|---|---|---|
| 1st | 0–1 | 2 |
| 2nd | 0–3 | 4 |
| 3rd | 0–7 | 8 |
| 10th | 0–1023 | 1024 |
| 11th–16th | 0–1023 (capped) | 1024 |
After 16 attempts Ethernet gives up and reports failure upward.
The elegance is that the algorithm estimates contention implicitly. Repeated collisions are evidence that many stations are competing, so the window widens automatically. Success resets it, so light load returns to fast retry. No station ever needs to know how many others exist — the collision history encodes it.
Two practical details matter. The cap at 1023 prevents unbounded delay, and the abort at 16 stops a station retrying forever on a broken link. Ethernet's slot time is 512 bit times — the same 2τ value that sets the minimum frame size, so the backoff quantum is exactly the collision-detection window.
Binary exponential backoff has one well-known unfairness, the capture effect. A station that transmits successfully resets its backoff counter to zero, while a station that has collided several times is drawing from a wide window. The successful station therefore wins subsequent contests too, and can monopolise the channel while an unlucky one starves. This is a known flaw of shared Ethernet and is one more reason switching was such an improvement.
The pattern generalises far beyond Ethernet. Wi-Fi uses the same algorithm with a contention window from 15 to 1023. TCP doubles its retransmission timeout on consecutive losses. API clients retry with exponential backoff and added jitter. In every case the logic is identical: repeated failure is evidence of contention, so back off geometrically — and randomness is what prevents synchronised retries.
Examples
Two stations colliding repeatedly, then diverging
collision 1: A picks from {0,1} -> 1 B picks from {0,1} -> 1 COLLIDE again
collision 2: A picks from {0..3} -> 3 B picks from {0..3} -> 0
B waits 0 slots, transmits, SUCCEEDS
A waits 3 slots, finds the channel busy, defers
A's next attempt succeeds; A's counter resets to 0.
The window doubling means the chance of picking the same value
halves with every collision:
after 1 collision: P(same) = 1/2
after 2: P(same) = 1/4
after 3: P(same) = 1/8
after n: P(same) = 1/2^n -> convergence is guaranteed
The capture effect:
A succeeds -> A's counter = 0, draws from {0,1}
B has collided 4 times -> draws from {0..15}
A's expected wait 0.5 slots; B's expected wait 7.5 slots
A wins again, resets again... B may starve.
import random
SLOT_TIME_US = 51.2 # 512 bit times at 10 Mb/s
def backoff_slots(collision_count):
"""802.3: uniform over 0..2^n - 1, capped at n = 10, abort after 16."""
if collision_count > 16:
raise RuntimeError("excessive collisions: frame discarded")
n = min(collision_count, 10)
return random.randint(0, 2**n - 1)
print(f"{'collision':>10}{'range':>12}{'sampled':>9}{'wait (us)':>12}")
for n in range(1, 12):
s = backoff_slots(n)
print(f"{n:>10}{'0-' + str(2**min(n,10)-1):>12}{s:>9}{s*SLOT_TIME_US:>12.1f}")
# collision range sampled wait (us)
# 1 0-1 1 51.2
# 3 0-7 5 256.0
# 10 0-1023 718 36761.6
# 11 0-1023 402 20582.4 <- capped; range stops growing
def simulate_contention(n_stations, trials=20_000):
"""How many collision rounds before every station has transmitted once?"""
rounds_needed = []
for _ in range(trials):
waiting, rounds, collisions = set(range(n_stations)), 0, {i: 0 for i in range(n_stations)}
while waiting:
rounds += 1
picks = {s: backoff_slots(collisions[s] + 1) for s in waiting}
earliest = min(picks.values())
winners = [s for s, p in picks.items() if p == earliest]
if len(winners) == 1:
waiting.discard(winners[0]) # transmitted successfully
for s in winners:
if len(winners) > 1:
collisions[s] += 1 # collided: widen the window
if rounds > 200:
break
rounds_needed.append(rounds)
return sum(rounds_needed) / len(rounds_needed)
print()
for n in (2, 5, 10, 25):
print(f"{n:>3} contending stations: {simulate_contention(n):>6.1f} rounds "
f"on average to clear the backlog")
# 2 contending stations: 3.0 rounds on average to clear the backlog
# 5 contending stations: 8.4 rounds on average to clear the backlog
# 10 contending stations: 18.6 rounds on average to clear the backlog
# 25 contending stations: 50.3 rounds on average to clear the backlog
# Probability two stations collide again, by collision count:
print()
for n in range(1, 8):
window = 2 ** n
print(f"after {n} collisions: window {window:>4}, "
f"P(both pick the same slot) = {1/window:>7.4%}")
# after 1 collisions: window 2, P(both pick the same slot) = 50.0000%
# after 5 collisions: window 32, P(both pick the same slot) = 3.1250%
# after 7 collisions: window 128, P(both pick the same slot) = 0.7812%
Key takeaways
- After a collision, stations must retry at different times; with no way to negotiate, randomness is the only option.
- Binary exponential backoff draws a wait uniformly from 0 to 2ⁿ−1 slots after the nth consecutive collision.
- The window doubling implicitly estimates contention: repeated collisions widen the window, success resets it, and no station needs to know how many others exist.
- Ethernet caps the window at 1023 slots and abandons the frame after 16 attempts; the slot time is 512 bit times, the same 2τ as the minimum frame.
- The probability of a repeat collision halves each round, guaranteeing convergence.
- The capture effect is its known unfairness: a recently successful station draws from a narrow window and can monopolise the channel.
- The same pattern appears in Wi-Fi's contention window, TCP's RTO doubling, and retry logic in distributed systems generally.
🧪 Practice
- After the 4th collision, what is the range of slot times a station may wait, and what is the maximum delay in microseconds at 10 Mb/s?
- Compute the probability that two contending stations collide a third consecutive time, showing your reasoning.
- Interview-style: Explain the capture effect and why it makes shared Ethernet unfair. (Hint: compare the contention windows of a station that just succeeded and one that has collided five times.)
<a id="45-ethernet"></a>
4.5 Ethernet
Ethernet won the local network entirely; this subchapter covers its frame format, its addressing, how it scaled across five orders of magnitude in speed, and the operational details that generate most real-world faults.
Ethernet Frame Format
Theory
Ethernet's frame has barely changed since 1980, which is remarkable for a technology that has gone from 10 Mb/s to 400 Gb/s — a 40,000-fold increase. That stability is the single biggest reason Ethernet won: every speed upgrade preserved the frame, so software, protocols, and analysis tools carried forward unchanged.
The fields, in order:
| Field | Bytes | Purpose |
|---|---|---|
| Preamble | 7 | 10101010 repeated — lets the receiver's PLL lock onto the clock |
| SFD | 1 | 10101011 — the final 11 marks where the frame proper begins |
| Destination MAC | 6 | Who the frame is for |
| Source MAC | 6 | Who sent it |
| Type/Length | 2 | EtherType (≥ 1536) or length (≤ 1500), as covered earlier |
| Payload | 46–1500 | The encapsulated packet; padded if shorter than 46 |
| FCS | 4 | CRC-32 over everything from destination MAC onward |
Plus a mandatory interframe gap of 12 byte-times of silence between frames, giving receivers time to process and re-arm.
Several details reward attention.
The preamble is not part of the frame. It is physical-layer machinery — 64 bits of alternating signal that let the receiver recover the clock, exactly as Chapter 3 described. It is stripped before anything else looks at the frame and does not count toward the frame's length. Notice it also uses the "distinguishable marker" framing technique: the SFD's terminal 11 breaks the alternating pattern unambiguously.
The 46-byte minimum payload is a consequence of CSMA/CD. Header (14) + payload (46) + FCS (4) = 64 bytes, the minimum frame size derived earlier from the 2τ collision-detection requirement. Payloads shorter than 46 bytes are padded with zeros. This is why a 1-byte TCP acknowledgement still occupies 64 bytes on the wire, and it means the receiver must use the IP header's length field — not the frame size — to find where real data ends.
The 1500-byte maximum was chosen when memory was expensive; it has constrained the Internet ever since, as the MTU discussion showed.
The FCS is recomputed at every hop. Each switch verifies it, strips it, and generates a fresh one. This protects the frame on the wire but not inside the switch — the gap the end-to-end checksum covers.
Adding a 802.1Q VLAN tag inserts 4 bytes after the source MAC, making the maximum frame 1522 bytes. Devices that do not expect tagged frames may report these as "baby giants".
Two error counters follow directly from these rules and are diagnostically valuable: a runt is a frame under 64 bytes (usually a collision fragment or a duplex mismatch), and a giant exceeds 1518 bytes (usually an MTU mismatch or an unexpected VLAN tag).
Examples
Complete Ethernet II frame on the wire
|<------------------------- 84 to 1538 bytes -------------------------->|
+--------+-----+--------+--------+------+----------------+-----+--------+
|preamble| SFD |dst MAC |src MAC | type | payload | FCS | IFG |
| 7 | 1 | 6 | 6 | 2 | 46 - 1500 | 4 | 12 |
+--------+-----+--------+--------+------+----------------+-----+--------+
|<-- physical -->|<--------- the FRAME (64-1518) --------->|<- silence ->|
|<------ covered by the FCS ------->|
Preamble bit pattern:
10101010 10101010 ... 10101010 10101011
|<------- 7 bytes of alternating ------>|^^ SFD ends with 11,
gives the PLL 56 transitions to lock breaking the pattern
Minimum-size frame carrying a 1-byte payload:
| dst 6 | src 6 | type 2 | 1 byte data + 45 bytes of ZERO PAD | FCS 4 |
^ 64-byte minimum enforced by padding
Efficiency: 1 useful byte in 84 bytes of wire time = 1.2%
import zlib
def build_frame(dst: str, src: str, ethertype: int, payload: bytes, vlan=None):
d = bytes.fromhex(dst.replace(":", ""))
s = bytes.fromhex(src.replace(":", ""))
body = d + s
if vlan is not None:
# 802.1Q: TPID 0x8100, then PCP(3) DEI(1) VID(12)
body += (0x8100).to_bytes(2, "big") + vlan.to_bytes(2, "big")
body += ethertype.to_bytes(2, "big")
if len(payload) < 46:
payload = payload + b"\x00" * (46 - len(payload)) # mandatory zero pad
body += payload
fcs = zlib.crc32(body) & 0xFFFFFFFF
return body + fcs.to_bytes(4, "little") # FCS is little-endian
def describe(frame: bytes):
size = len(frame)
kind = ("RUNT" if size < 64 else
"giant/baby-giant" if size > 1518 else "valid")
wire = size + 8 + 12 # + preamble/SFD + IFG
return (f"{size:>5} B frame ({kind:<16}) -> {wire:>5} B of wire time, "
f"{'' if size >= 64 else 'INVALID'}")
print(describe(build_frame("aabbccddeeff", "112233445566", 0x0800, b"X")))
print(describe(build_frame("aabbccddeeff", "112233445566", 0x0800, b"X" * 1500)))
print(describe(build_frame("aabbccddeeff", "112233445566", 0x0800, b"X" * 1500, vlan=100)))
# 64 B frame (valid ) -> 84 B of wire time,
# 1518 B frame (valid ) -> 1538 B of wire time,
# 1522 B frame (giant/baby-giant) -> 1542 B of wire time,
# ^ a VLAN-tagged full-size frame: legitimate, but counted as a
# "baby giant" by devices not configured to expect 802.1Q
# Efficiency across payload sizes — the padding penalty is severe:
print()
for p in (1, 18, 46, 100, 500, 1500):
f = build_frame("aabbccddeeff", "112233445566", 0x0800, b"X" * p)
wire = len(f) + 20
print(f"payload {p:>5} B -> wire {wire:>5} B, efficiency {p/wire:>6.1%}")
# payload 1 B -> wire 84 B, efficiency 1.2% <- 45 bytes of pure padding
# payload 18 B -> wire 84 B, efficiency 21.4%
# payload 46 B -> wire 84 B, efficiency 54.8% <- first size needing no pad
# payload 1500 B -> wire 1538 B, efficiency 97.5%
# Below 46 bytes, extra data is FREE — the frame is padded to 64 regardless.
# Interface counters map directly onto these rules:
COUNTERS = {
"runts": "< 64 bytes — collision fragment or duplex mismatch",
"giants": "> 1518 bytes — MTU mismatch or unexpected VLAN tag",
"FCS errors": "CRC failed — cabling, noise, or duplex mismatch",
"alignment": "not a whole number of bytes AND bad FCS — physical fault",
}
print()
for k, v in COUNTERS.items():
print(f"{k:<14}{v}")
Key takeaways
- The Ethernet frame has been stable since 1980 across a 40,000-fold speed increase, which is the main reason Ethernet displaced every competitor.
- Preamble (7) + SFD (1) are physical-layer clock-recovery machinery, stripped before the frame is parsed and not counted in its length.
- Frame size is 64–1518 bytes (1522 with a VLAN tag); the 46-byte minimum payload exists to satisfy CSMA/CD's 2τ requirement and is zero-padded when necessary.
- Padding means the IP header's length field — not the frame size — determines where real data ends.
- The FCS is CRC-32 over the frame from destination MAC onward, and is recomputed at every hop.
- A mandatory 12-byte interframe gap separates frames.
- Runts (<64 B) suggest collisions or duplex mismatch; giants (>1518 B) suggest MTU or VLAN misconfiguration.
🧪 Practice
- Compute the total wire time in bytes for a frame carrying a 40-byte TCP acknowledgement, including preamble and interframe gap.
- Explain why sending 20 bytes of data costs exactly the same wire time as sending 46 bytes.
- Interview-style: A switch port reports thousands of "giants" after a VLAN change. What happened, and is the traffic actually invalid? (Hint: compute how many bytes an 802.1Q tag adds and compare with the untagged maximum.)
MAC Addresses and OUI Structure
Theory
A MAC address is the link layer's identifier: 48 bits, conventionally written as six hex bytes. Its defining property — and the source of both its virtues and its limits — is that it is flat. There is no hierarchy, no network portion, no way to deduce location. 00:1A:2B:3C:4D:5E tells you who manufactured the interface and nothing whatsoever about where it is.
The structure has two halves:
- OUI (Organisationally Unique Identifier) — the first 24 bits, assigned by the IEEE to a manufacturer for a fee.
00:1B:63is Apple,00:50:56is VMware,08:00:27is VirtualBox. - Device identifier — the last 24 bits, assigned by the manufacturer, giving 16.7 million addresses per OUI.
Two bits inside the first byte carry special meaning, and knowing them lets you read an address at a glance:
| Bit | Name | Value 0 | Value 1 |
|---|---|---|---|
| Least significant bit of byte 0 | I/G (Individual/Group) | Unicast | Multicast |
| Second-least significant bit of byte 0 | U/L (Universal/Local) | Globally unique (from an OUI) | Locally administered |
So an address whose first byte is even is unicast, and odd is multicast. The all-ones address FF:FF:FF:FF:FF:FF is broadcast (a special case of multicast). The U/L bit explains why virtual machines and containers often have addresses starting 02: — they are locally administered and not drawn from any vendor's OUI.
Two multicast mappings are worth memorising because they appear constantly in packet captures:
- IPv4 multicast maps to
01:00:5Eplus the low 23 bits of the IP address. Since IPv4 multicast addresses have 28 significant bits, 32 different IP groups share each MAC — an imperfect but workable mapping. - IPv6 multicast maps to
33:33plus the low 32 bits of the IPv6 address.
The deeper architectural point is why MAC addresses cannot be used for global routing. Flat addresses cannot be aggregated: a router could not say "everything starting 00:1B:63 is that way", because Apple devices are everywhere. Routing on MAC addresses would need one table entry per device on Earth. Hierarchical IP addressing exists precisely to allow aggregation, and this is the clearest illustration of why layers 2 and 3 use different address schemes.
A practical note on MAC randomisation: because MAC addresses are globally unique and broadcast constantly, they enable tracking — a shop's Wi-Fi can recognise a returning phone. Modern iOS, Android, and Windows therefore randomise the MAC per network, setting the locally-administered bit. This breaks MAC-based access control lists and DHCP reservations, which is a common source of support tickets.
Examples
Reading a MAC address
00 : 1B : 63 : 84 : 45 : E6
^^^^^^^^^^^^ ^^^^^^^^^^^^
OUI (Apple) device-specific (16.7M per OUI)
First byte 0x00 = 00000000 binary
^^
||-- I/G bit = 0 -> UNICAST
|--- U/L bit = 0 -> globally unique
Special addresses:
FF:FF:FF:FF:FF:FF broadcast (all bits set)
01:00:5E:xx:xx:xx IPv4 multicast (I/G = 1)
33:33:xx:xx:xx:xx IPv6 multicast
01:80:C2:00:00:00 Spanning Tree BPDU
02:42:ac:11:00:02 locally administered (U/L = 1) — a Docker container
IPv4 multicast mapping: 224.0.0.251 (mDNS) -> MAC
224. 0. 0.251
low 23 bits: 0000000 00000000 11111011
01:00:5E | 0 + those 23 bits
= 01:00:5E:00:00:FB
^ the top bit of the 4th byte is always 0, so 32 IP groups
collide onto each MAC address. Hosts filter the rest in software.
def analyse_mac(mac: str) -> dict:
b = [int(x, 16) for x in mac.split(":")]
first = b[0]
return {
"address": mac.lower(),
"oui": ":".join(f"{x:02x}" for x in b[:3]).upper(),
"multicast": bool(first & 0b01), # I/G bit
"local": bool(first & 0b10), # U/L bit
"broadcast": all(x == 0xFF for x in b),
}
KNOWN_OUI = {"00:1B:63": "Apple", "00:50:56": "VMware",
"08:00:27": "VirtualBox", "01:00:5E": "IPv4 multicast",
"33:33:00": "IPv6 multicast"}
for mac in ["00:1b:63:84:45:e6", "ff:ff:ff:ff:ff:ff", "01:00:5e:00:00:fb",
"02:42:ac:11:00:02", "33:33:00:00:00:01", "08:00:27:9a:1f:cc"]:
a = analyse_mac(mac)
kind = ("broadcast" if a["broadcast"] else
"multicast" if a["multicast"] else "unicast")
scope = "local" if a["local"] else "global"
vendor = KNOWN_OUI.get(a["oui"], "unknown vendor")
print(f"{mac} {kind:<9} {scope:<7} {a['oui']} {vendor}")
# 00:1b:63:84:45:e6 unicast global 00:1B:63 Apple
# ff:ff:ff:ff:ff:ff broadcast local FF:FF:FF unknown vendor
# 01:00:5e:00:00:fb multicast global 01:00:5E IPv4 multicast
# 02:42:ac:11:00:02 unicast local 02:42:AC unknown vendor
# 33:33:00:00:00:01 multicast global 33:33:00 IPv6 multicast
def ipv4_multicast_to_mac(ip: str) -> str:
octets = [int(o) for o in ip.split(".")]
ip_int = int.from_bytes(bytes(octets), "big")
low23 = ip_int & 0x7FFFFF # only the low 23 bits survive
return f"01:00:5e:{(low23>>16)&0xFF:02x}:{(low23>>8)&0xFF:02x}:{low23&0xFF:02x}"
print()
for ip in ["224.0.0.1", "224.0.0.251", "239.255.255.250", "225.0.0.251"]:
print(f"{ip:<16} -> {ipv4_multicast_to_mac(ip)}")
# 224.0.0.1 -> 01:00:5e:00:00:01
# 224.0.0.251 -> 01:00:5e:00:00:fb
# 239.255.255.250 -> 01:00:5e:7f:ff:fa
# 225.0.0.251 -> 01:00:5e:00:00:fb <- COLLIDES with 224.0.0.251
# Why flat addresses cannot be routed globally:
print()
print(f"MAC address space : 2^48 = {2**48:,} addresses, NO hierarchy")
print(f"routing on MACs : would need ~1 entry per device on Earth")
print(f"IPv4 with CIDR : ~1,000,000 prefixes cover 4.3 billion addresses")
print("Aggregation is only possible because IP addresses are HIERARCHICAL.")
Key takeaways
- MAC addresses are 48 bits: a 24-bit OUI assigned by the IEEE to a vendor, plus 24 vendor-assigned bits.
- The I/G bit (least significant bit of byte 0) marks multicast; the U/L bit (next bit) marks locally administered addresses — so
02:prefixes indicate VMs and containers. FF:FF:FF:FF:FF:FFis broadcast;01:00:5E+ low 23 bits carries IPv4 multicast (32 IP groups per MAC);33:33+ low 32 bits carries IPv6 multicast.- MAC addresses are flat and encode no location, so they cannot be aggregated and cannot be used for global routing — the reason hierarchical IP addressing exists.
- Modern devices randomise MAC addresses per network for privacy, which breaks MAC-based ACLs and DHCP reservations.
🧪 Practice
- For
0A:1B:2C:3D:4E:5F, determine whether it is unicast or multicast and whether it is globally or locally administered.- Compute the Ethernet multicast MAC for IPv4 group
239.192.0.100, then find another IPv4 group that maps to the same MAC.- Interview-style: Why can the Internet not simply route on MAC addresses and dispense with IP entirely? (Hint: consider how a core router's table size would grow, and what property of IP addresses keeps it bounded.)
Ethernet Standards from 10BASE-T to 400GbE
Theory
Ethernet has scaled from 10 Mb/s to 400 Gb/s — a factor of 40,000 — while keeping the same frame format, the same addressing, and the same service model. Understanding how explains why it displaced every competitor.
The naming convention encodes the specification, as introduced in Chapter 2: speed + BASE (baseband) + medium/encoding. 1000BASE-T is 1000 Mb/s baseband over twisted pair; 10GBASE-LR is 10 Gb/s over long-reach single-mode fibre.
The generations and what each had to solve:
| Standard | Year | Speed | Medium | Key change |
|---|---|---|---|---|
| 10BASE5 / 10BASE2 | 1980s | 10 Mb/s | Coax bus | Shared medium, CSMA/CD |
| 10BASE-T | 1990 | 10 Mb/s | Cat3 UTP | Star topology — the decisive shift |
| 100BASE-TX | 1995 | 100 Mb/s | Cat5 UTP | 4B/5B + MLT-3 to fit 100 MHz cable |
| 1000BASE-T | 1999 | 1 Gb/s | Cat5e UTP | All 4 pairs, PAM-5, echo cancellation, full duplex |
| 10GBASE-T | 2006 | 10 Gb/s | Cat6a | PAM-16, heavy DSP, LDPC |
| 25/40/100GbE | 2010s | 25–100 Gb/s | Fibre/DAC | Parallel lanes, QSFP form factors |
| 400GbE / 800GbE | 2017+ | 400–800 Gb/s | Fibre | PAM-4, coherent optics |
Three transitions did the real work.
Star topology (10BASE-T). Replacing the shared coax bus with a hub and dedicated cables per station seemed minor but changed everything: a single cable fault no longer killed the segment, structured cabling became possible, and — crucially — it created the physical arrangement that switching would later exploit.
Switching plus full duplex (mid-1990s). Replacing hubs with switches gave each port its own collision domain. With a dedicated path in each direction, collisions became impossible, CSMA/CD was switched off, and Ethernet's shared-medium heritage became irrelevant. This is the single most important event in Ethernet's history: it removed the scaling limit that would otherwise have killed it, as the CSMA/CD topic showed.
Signal processing (1000BASE-T onward). Gigabit over Cat5e required transmitting on all four pairs simultaneously in both directions, using echo cancellation to subtract each transceiver's own signal from what it receives. 10GBASE-T pushed further with PAM-16 and LDPC coding. The cable did not improve much; the silicon did.
Two structural observations explain the modern landscape. Above 10 Gb/s, copper largely gives way to fibre and direct-attach copper, because twisted pair's bandwidth and crosstalk limits become prohibitive. And high-speed Ethernet is built from parallel lanes — 100GbE as 4 × 25 Gb/s, 400GbE as 8 × 50 Gb/s — which is why QSFP modules can be broken out into several independent lower-speed links.
The intermediate speeds 2.5GBASE-T and 5GBASE-T deserve a mention: created specifically so existing Cat5e/Cat6 building cabling could support Wi-Fi 6 access points needing more than 1 Gb/s without recabling. They are a good example of standards following deployment reality rather than leading it.
Examples
How each generation fitted more bits into the same cable
10BASE-T Manchester, 1 pair, half duplex
20 Mbaud for 10 Mb/s (100% coding overhead)
100BASE-TX 4B/5B + MLT-3, 1 pair each way
125 Mbaud -> MLT-3 folds the fundamental to 31.25 MHz
so it fits inside Cat5's 100 MHz
1000BASE-T PAM-5 on ALL FOUR pairs, BOTH directions at once
125 Mbaud x 2 bits x 4 pairs = 1000 Mb/s
requires echo cancellation: each transceiver subtracts
its own transmission from what it hears
pair 1 <===> |
pair 2 <===> | all four bidirectional simultaneously
pair 3 <===> |
pair 4 <===> |
10GBASE-T PAM-16 + LDPC + massive DSP
800 Mbaud x 4 bits x 4 pairs, needs Cat6a to 100 m
The cable barely changed; the silicon did all the work.
STANDARDS = {
# name: (Mb/s, medium, max_metres, pairs/lanes, encoding)
"10BASE-T": (10, "Cat3 UTP", 100, 2, "Manchester"),
"100BASE-TX": (100, "Cat5 UTP", 100, 2, "4B/5B + MLT-3"),
"1000BASE-T": (1000, "Cat5e UTP", 100, 4, "PAM-5, echo cancelled"),
"2.5GBASE-T": (2500, "Cat5e UTP", 100, 4, "PAM-16 (reduced rate)"),
"10GBASE-T": (10000, "Cat6a UTP", 100, 4, "PAM-16 + LDPC"),
"10GBASE-SR": (10000, "OM4 MMF", 400, 1, "64B/66B"),
"10GBASE-LR": (10000, "OS2 SMF", 10000, 1, "64B/66B"),
"100GBASE-SR4":(100000, "OM4 MMF", 100, 4, "64B/66B x 4 lanes"),
"400GBASE-DR4":(400000, "OS2 SMF", 500, 4, "PAM-4 x 4 lanes"),
}
print(f"{'standard':<15}{'speed':>10}{'medium':<12}{'reach':>8}{'lanes':>7} encoding")
for name, (mbps, medium, reach, lanes, enc) in STANDARDS.items():
speed = f"{mbps/1000:.1f}G" if mbps >= 1000 else f"{mbps}M"
print(f"{name:<15}{speed:>10} {medium:<12}{reach:>6}m{lanes:>7} {enc}")
def per_lane_rate(total_mbps, lanes):
return total_mbps / lanes
print()
for name in ("10GBASE-SR", "100GBASE-SR4", "400GBASE-DR4"):
mbps, _, _, lanes, _ = STANDARDS[name]
print(f"{name:<15} {mbps/1000:>6.0f} Gb/s = {lanes} lanes x "
f"{per_lane_rate(mbps, lanes)/1000:>5.1f} Gb/s each")
# 10GBASE-SR 10 Gb/s = 1 lanes x 10.0 Gb/s each
# 100GBASE-SR4 100 Gb/s = 4 lanes x 25.0 Gb/s each
# 400GBASE-DR4 400 Gb/s = 4 lanes x 100.0 Gb/s each
# Parallel lanes are why a 100G QSFP28 port breaks out into 4 x 25G links.
# What changed and what did not, across 40,000x:
print()
CONSTANT = ["frame format", "48-bit MAC addressing", "1500-byte MTU",
"64-byte minimum frame", "best-effort unacknowledged service"]
CHANGED = ["line coding", "medium", "duplex mode", "collision handling",
"number of lanes", "signal processing"]
print("UNCHANGED since 1980:", *[f"\n - {c}" for c in CONSTANT], sep="")
print("\nCHANGED every generation:", *[f"\n - {c}" for c in CHANGED], sep="")
# The stable interface at the top is exactly what let everything below it
# be replaced — the layering argument from Chapter 2, demonstrated over 40 years.
Key takeaways
- Ethernet naming encodes the spec: speed +
BASE+ medium/encoding, as in1000BASE-Tor10GBASE-LR. - Three transitions carried it: star topology (10BASE-T), switching plus full duplex (which eliminated collisions and removed the CSMA/CD scaling limit), and advanced signal processing (PAM encodings, echo cancellation, LDPC).
- Gigabit over Cat5e works by using all four pairs bidirectionally with echo cancellation; 10GBASE-T adds PAM-16 and heavy DSP.
- Above 10 Gb/s, links move to fibre and direct-attach copper, and are built from parallel lanes (100GbE = 4 × 25 Gb/s), enabling breakout cables.
- 2.5GBASE-T and 5GBASE-T exist to serve Wi-Fi 6 access points over already-installed Cat5e/Cat6.
- The frame format, addressing, MTU, and service model have been unchanged since 1980 — the stable interface that allowed everything beneath it to be replaced.
🧪 Practice
- Decode
40GBASE-SR4and2.5GBASE-Tinto speed, medium, and lane count.- Explain why 1000BASE-T needs all four pairs while 100BASE-TX needs only two, and what echo cancellation is for.
- Interview-style: Ethernet increased in speed 40,000-fold while its frame format never changed. Why did that matter? (Hint: think about every piece of software, hardware, and tooling that parses a frame, and what a format change would have required of each.)
Collision and Broadcast Domains
Theory
These two terms are constantly confused and the distinction is one of the most reliably tested ideas in networking. They describe different scopes with different boundaries.
A collision domain is the set of interfaces whose transmissions can physically interfere — the layer 1 concept developed in Chapter 3. A broadcast domain is the set of interfaces that will receive a frame sent to FF:FF:FF:FF:FF:FF — a layer 2 concept about forwarding, not physics.
The boundaries differ because different devices bound them:
| Device | Collision domains | Broadcast domains |
|---|---|---|
| Hub / repeater | Extends the existing one | Extends the existing one |
| Switch / bridge | One per port | Extends the existing one |
| Router | One per interface | One per interface |
| VLAN on a switch | One per port | One per VLAN |
The crucial line: switches break up collision domains but not broadcast domains. A switch floods broadcast frames out every port. Connect a hundred switches together and you still have one broadcast domain — every broadcast reaches every device.
Collision domains are now largely historical. A full-duplex switch port serving one device has a dedicated path in each direction, so no collision is possible and CSMA/CD is disabled. The concept survives only for hubs, half-duplex links, and Wi-Fi.
Broadcast domains, by contrast, matter more than ever. An oversized broadcast domain causes real problems:
- Broadcast traffic scales with host count, and every host must interrupt its CPU to inspect every broadcast, even to discard it. ARP, DHCP, mDNS, NetBIOS, and various discovery protocols all broadcast continuously.
- A broadcast storm can saturate the network. A switching loop without spanning tree multiplies broadcasts without limit, and because Ethernet frames have no TTL field, nothing stops them circulating forever. The network collapses in seconds.
- Security and isolation: any host in a broadcast domain can attempt ARP spoofing against any other, as the final subchapter covers.
Practical guidance limits a broadcast domain to a few hundred hosts, commonly a /24 subnet. VLANs are the standard tool for subdividing without buying more hardware: one physical switch can host many broadcast domains, with traffic between them passing through a router that applies policy.
Note the tidy correspondence: one broadcast domain = one IP subnet. This is not coincidence. A subnet is defined as the set of hosts reachable without a router, and a broadcast domain is the set reachable by a layer 2 broadcast — the same set by construction, which is why ARP works.
Examples
Counting both domain types in one topology
[ROUTER]
/ \
[SWITCH A] [SWITCH B]
/ | \ | \
PC PC [HUB] PC PC
/ \
PC PC
COLLISION DOMAINS (layer 1 — who can physically interfere):
SWITCH A ports to PCs .................. 2
SWITCH A port to HUB + the hub segment . 1 (shared by both hub PCs)
SWITCH B ports to PCs .................. 2
router-to-switch links ................. 2
= 9
BROADCAST DOMAINS (layer 2 — who receives a broadcast):
everything on SWITCH A's side .......... 1
everything on SWITCH B's side .......... 1
= 2
The ROUTER is the only boundary. Switches and hubs are not.
Why a loop is fatal — Ethernet frames have NO TTL:
[SW1]======[SW2]
|| || a broadcast enters...
[SW3]======[SW4]
SW1 floods -> SW2 and SW3 flood -> SW4 floods -> back to SW1 -> ...
Each pass MULTIPLIES the frame. No hop count ever decrements.
Within seconds the CPU and links are saturated: a BROADCAST STORM.
This is exactly why Spanning Tree exists.
def count_domains(topology):
"""Collision domains: per switch/router port + per hub segment.
Broadcast domains: bounded only by routers and VLANs."""
collision = (topology["switch_ports"] + topology["router_ports"]
+ topology["hub_segments"])
broadcast = topology["router_interfaces"] if not topology.get("vlans") \
else topology["vlans"]
return collision, broadcast
net = {"switch_ports": 6, "router_ports": 2, "hub_segments": 1,
"router_interfaces": 2}
c, b = count_domains(net)
print(f"collision domains: {c}, broadcast domains: {b}")
# collision domains: 9, broadcast domains: 2
def broadcast_load(hosts, broadcasts_per_host_per_sec=5, frame_bytes=84):
"""Every broadcast is processed by EVERY host in the domain."""
total_bps = hosts * broadcasts_per_host_per_sec * frame_bytes * 8
interrupts_per_host = hosts * broadcasts_per_host_per_sec
return total_bps, interrupts_per_host
print(f"\n{'hosts':>7}{'broadcast traffic':>20}{'interrupts/host/s':>20}")
for h in (50, 250, 1000, 4000):
bps, ints = broadcast_load(h)
print(f"{h:>7}{bps/1e6:>17.2f} Mb/s{ints:>20,}")
# hosts broadcast traffic interrupts/host/s
# 50 0.17 Mb/s 250
# 250 0.84 Mb/s 1,250
# 1000 3.36 Mb/s 5,000
# 4000 13.44 Mb/s 20,000
# Broadcast load grows as O(n) in traffic but every host pays it —
# so the CPU cost across the domain grows as O(n^2).
def storm_growth(initial_frames, switches_in_loop, seconds, pps_capacity=1_000_000):
frames = initial_frames
for t in range(1, seconds + 1):
frames *= switches_in_loop # each pass multiplies
if frames > pps_capacity:
return t, frames
return seconds, frames
t, f = storm_growth(1, switches_in_loop=3, seconds=20)
print(f"\nbroadcast storm saturates the network after {t} propagation rounds "
f"({f:,} frames)")
# broadcast storm saturates the network after 13 propagation rounds (1,594,323 frames)
# With microsecond-scale propagation, this is well under a second.
Key takeaways
- A collision domain is the set of interfaces that can physically interfere (layer 1); a broadcast domain is the set that receives a broadcast frame (layer 2).
- Switches create one collision domain per port but do not divide broadcast domains — they flood broadcasts everywhere.
- Only routers and VLANs bound a broadcast domain.
- Collision domains are largely obsolete on full-duplex switched links; broadcast domains matter more than ever.
- Broadcast traffic scales with host count and every host must process every broadcast, so CPU cost across a domain grows quadratically.
- Ethernet frames have no TTL, so a switching loop multiplies broadcasts without limit — a broadcast storm that collapses the network in seconds, which is why Spanning Tree exists.
- One broadcast domain = one IP subnet, by construction — which is what makes ARP viable.
🧪 Practice
- Count collision and broadcast domains for a router with three interfaces, each connected to a switch with 12 used ports, one of which feeds a 4-port hub.
- Explain why adding switches never reduces broadcast traffic, and what device or feature does.
- Interview-style: Why is a broadcast storm more dangerous on Ethernet than a routing loop is on IP? (Hint: compare what happens to a frame's header versus a packet's header on each pass through the loop.)
Auto-Negotiation and Duplex Mismatch
Theory
Ethernet spans many speeds and two duplex modes, and a link only works if both ends agree on both. Auto-negotiation (IEEE 802.3u, now clause 28) is the mechanism by which they agree without human configuration.
It works below the data layer, before any frame can be sent. Each end transmits FLP (Fast Link Pulse) bursts — a sequence of link pulses encoding a 16-bit link code word advertising its capabilities: which speeds it supports, which duplex modes, whether it can do flow control. Both ends read the other's advertisement and independently select the highest common capability using a fixed priority order:
10GBASE-T > 1000BASE-T full > 1000BASE-T half > 100BASE-TX full
> 100BASE-T4 > 100BASE-TX half > 10BASE-T full > 10BASE-T half
Because both ends run the same deterministic algorithm on the same data, they reach the same conclusion without negotiating back and forth.
Auto-negotiation also carries Auto-MDI-X, which detects whether the cable is straight-through or crossover and swaps the transmit and receive pairs internally as needed. This is why crossover cables became unnecessary.
Duplex mismatch is the classic failure, and it arises from one specific rule. If one end has auto-negotiation disabled and is hard-set, it transmits no FLP bursts. The auto-negotiating end falls back to parallel detection: it can sense the speed from the signalling, but the signalling carries no duplex information. The standard requires it to assume half duplex — the safe choice, since half-duplex is what an old device would use.
So hard-setting one end to 100/full and leaving the other on auto produces:
- One end at 100 Mb/s full duplex — transmits whenever it wants.
- The other at 100 Mb/s half duplex — believes it must wait for a clear channel.
The link comes up. Speed matches. Pings succeed. And under load it collapses.
The mechanism of collapse: the full-duplex end transmits while receiving. The half-duplex end sees incoming signal while it is transmitting and — correctly, by its own rules — declares a collision. Because this happens after the first 64 bytes, it is a late collision. It aborts, backs off, and retransmits. Meanwhile the full-duplex end receives a truncated frame and logs an FCS error or a runt.
The signature is unmistakable once you know it:
| Symptom | Where |
|---|---|
| Late collisions, collisions, deferred transmissions | The half-duplex end |
| FCS/CRC errors, runts | The full-duplex end |
| Link up, pings fine, throughput catastrophic under load | Both |
| Performance degrades in both directions simultaneously | The giveaway |
The rule that prevents it: auto-negotiate on both ends, or hard-set both ends — never one of each. Gigabit and faster mandate auto-negotiation, so the fault is confined to 10/100 equipment, but it remains a standard interview question because diagnosing it requires reasoning about what each end believes.
Examples
The four configuration combinations
Local Remote Result
------------ ------------ --------------------------------------------
auto auto negotiated correctly -> 100/full CORRECT
100/full 100/full both hard-set and agree -> 100/full CORRECT
auto 100/full local parallel-detects speed, assumes HALF
-> MISMATCH: 100/half vs 100/full BROKEN
100/full auto mirror image -> MISMATCH BROKEN
Why the mismatch destroys throughput:
FULL end HALF end
|---- frame A -------------->| (HALF is mid-transmission)
|<--- frame B ---------------| HALF sees incoming signal while sending
| -> declares LATE COLLISION
| -> aborts, jams, backs off
| receives a truncated frame
| -> logs FCS ERROR / RUNT
Each end blames the other. Pings (small, infrequent) survive;
bulk transfer (continuous, bidirectional) collapses.
# Diagnosing a duplex mismatch from both sides.
$ ethtool eth0
# Speed: 100Mb/s
# Duplex: Half <- expected Full: the first clue
# Auto-negotiation: on <- this end negotiated; the peer did not
# Link detected: yes
$ ethtool -S eth0 | grep -iE 'collision|crc|runt|deferred'
# tx_deferred: 29104
# tx_late_collisions: 18442 <- LATE collisions: the signature
# tx_collisions: 31877
# rx_crc_errors: 0 <- note: errors are on the OTHER side
# The switch's view of the very same link:
$ show interface FastEthernet0/7
# Full-duplex, 100Mb/s
# 0 runts, 0 giants, 90213 CRC, 0 frame, 0 overrun
# ^ CRC errors here pair with late collisions there
# -> together these two counters DIAGNOSE the mismatch
# The fix: make both ends agree. Auto on both is the standard choice.
$ sudo ethtool -s eth0 autoneg on
# switch:
# interface FastEthernet0/7
# duplex auto
# speed auto
# Verify what was actually negotiated, and what each side advertised:
$ ethtool eth0 | grep -A4 'Advertised link modes'
# Advertised link modes: 10baseT/Half 10baseT/Full
# 100baseT/Half 100baseT/Full
# 1000baseT/Full
# Link partner advertised link modes: Not reported
# ^^^^^^^^^^^^ the peer sent NO FLP bursts:
# it is hard-set. This is the root cause.
PRIORITY = [ # highest common capability wins
("1000BASE-T", "full"), ("1000BASE-T", "half"),
("100BASE-TX", "full"), ("100BASE-TX", "half"),
("10BASE-T", "full"), ("10BASE-T", "half"),
]
def negotiate(local_caps, remote_caps, remote_autoneg=True):
if not remote_autoneg:
# Parallel detection: speed is detectable, duplex is NOT.
# The standard mandates falling back to HALF duplex.
speed = next((s for s, d in PRIORITY
if any(s == ls for ls, _ in local_caps)), None)
return (speed, "half"), "PARALLEL DETECTION — duplex assumed half"
common = [c for c in PRIORITY if c in local_caps and c in remote_caps]
return (common[0] if common else None), "negotiated"
full_caps = [("1000BASE-T","full"), ("100BASE-TX","full"), ("100BASE-TX","half"),
("10BASE-T","full"), ("10BASE-T","half")]
cases = [
("auto <-> auto", full_caps, full_caps, True, "full"),
("auto <-> 100/full", full_caps, [("100BASE-TX","full")], False, "full"),
]
for name, local, remote, autoneg, remote_actual in cases:
result, how = negotiate(local, remote, autoneg)
mismatch = result[1] != remote_actual
print(f"{name:<20} -> local runs {result[0]} {result[1]:<5} "
f"({how})")
if mismatch:
print(f"{'':<20} remote runs {remote_actual} "
f"=> DUPLEX MISMATCH")
# auto <-> auto -> local runs 1000BASE-T full (negotiated)
# auto <-> 100/full -> local runs 1000BASE-T half (PARALLEL DETECTION — duplex assumed half)
# remote runs full => DUPLEX MISMATCH
def throughput_under_mismatch(line_mbps, collision_rate):
"""Collisions force backoff and retransmission, compounding losses."""
return line_mbps * (1 - collision_rate) ** 3
print()
for cr in (0.0, 0.2, 0.5, 0.75):
print(f"collision rate {cr:>4.0%}: "
f"{throughput_under_mismatch(100, cr):>6.2f} Mb/s of 100 Mb/s")
# collision rate 0%: 100.00 Mb/s of 100 Mb/s
# collision rate 20%: 51.20 Mb/s of 100 Mb/s
# collision rate 50%: 12.50 Mb/s of 100 Mb/s
# collision rate 75%: 1.56 Mb/s of 100 Mb/s
# Small, infrequent packets (ping) still get through — which is precisely
# why the fault is so often misdiagnosed as an application problem.
Key takeaways
- Auto-negotiation exchanges FLP bursts carrying a link code word of capabilities; both ends independently pick the highest common one using a fixed priority order.
- It also provides Auto-MDI-X, making crossover cables unnecessary.
- A hard-set end sends no FLP bursts, so the auto end uses parallel detection — which can sense speed but not duplex, and by standard must assume half.
- The resulting duplex mismatch produces a link that comes up, passes pings, and collapses under load.
- Signature counters: late collisions on the half-duplex end, FCS errors and runts on the full-duplex end, with degradation in both directions at once.
- Rule: auto-negotiate on both ends or hard-set both ends, never one of each.
- Gigabit and faster require auto-negotiation, confining this fault to 10/100 equipment.
🧪 Practice
- For each combination — both auto, both hard-set to 100/full, one auto and one 100/full — state the resulting speed and duplex on each end.
- Explain why a duplex mismatch shows CRC errors on one side and late collisions on the other rather than the same counter on both.
- Interview-style: A link passes pings perfectly but transfers files at 2 Mb/s. Counters show late collisions on the server and CRC errors on the switch. Diagnose and explain why ping succeeded. (Hint: compare what ping puts on the wire with what a bulk transfer does, particularly regarding simultaneous bidirectional traffic.)
Jumbo Frames
Theory
Ethernet's 1500-byte MTU was chosen when memory cost a fortune. It imposes a fixed per-frame cost — 18 bytes of Ethernet header and FCS, 20 bytes of IP, 20 bytes of TCP, plus preamble and interframe gap — that is paid on every frame regardless of payload.
Jumbo frames raise the payload to around 9000 bytes, cutting the number of frames for a given transfer by six. Three distinct benefits follow, and the third is the one that matters most in practice:
- Better wire efficiency. Header overhead falls from about 5 percent to under 1 percent.
- Fewer interrupts and less CPU. A host processing 10 Gb/s of 1500-byte frames handles roughly 800,000 frames per second; at 9000 bytes it handles 140,000. Per-frame processing cost — interrupts, context switches, header parsing, checksum verification — dominates at high speed, so this is usually the larger win.
- Better throughput per CPU cycle, which matters enormously for storage protocols (iSCSI, NFS, NVMe over Fabrics) and for anything driving 10 Gb/s or more.
The critical caveat: jumbo frames are not an IEEE standard. IEEE 802.3 defines the maximum frame as 1518 bytes and has consistently declined to raise it. Jumbo support is a vendor convention, and 9000 is only a common choice — some devices support 9216, others 9004, others different values.
The consequences of non-standardisation are serious:
- Every device in the broadcast domain must agree. If one switch in the path has a 1500-byte MTU, it silently drops jumbo frames. There is no negotiation mechanism and no error.
- The symptom is a PMTUD black hole — small packets work, large ones vanish — exactly as the MTU topic described.
- Mismatched jumbo sizes are worse than none. A host at 9000 talking through a switch at 9216 works; the reverse silently fails.
The practical guidance that follows: enable jumbo frames on isolated, fully controlled networks — a storage VLAN, a cluster interconnect, a backup network — where every device is known and configured. Do not enable them on general-purpose LANs that reach the Internet, because the path beyond your control is 1500 bytes and PMTUD failures will follow.
One more consideration: a corrupted jumbo frame discards six times as much data, so on a link with meaningful error rates the retransmission cost rises. On clean fibre this is irrelevant; on a marginal link it is not.
Modern alternatives often deliver most of the benefit without the configuration risk. TSO/LRO (TCP Segmentation Offload / Large Receive Offload) let the OS hand the NIC a 64 KB buffer that the NIC splits into standard 1500-byte frames — the host sees jumbo-sized units and the wire sees standard frames. This captures the CPU benefit, which is usually the dominant one, with no interoperability risk at all.
Examples
Where the frame count goes
Transferring 1 GB:
1500-byte MTU (1448-byte MSS): 690,608 frames
9000-byte MTU (8948-byte MSS): 111,757 frames 6.2x fewer
Per-frame fixed cost on the wire:
preamble 8 + eth hdr 14 + FCS 4 + IFG 12 = 38 bytes of framing
+ IP 20 + TCP 20 = 78 bytes total overhead per frame
standard: 78 / 1538 = 5.1% overhead
jumbo: 78 / 9038 = 0.9% overhead
The MTU mismatch failure, which has no error message:
[Host 9000]---[SW 9000]---[SW 1500]---[SW 9000]---[Host 9000]
^
silently drops every frame over 1518 bytes
ping (small) -> works
TCP handshake (small) -> works, session ESTABLISHED
bulk transfer (9000) -> every frame vanishes, no ICMP, no log entry
def transfer_profile(bytes_total, mtu, cpu_us_per_frame=2.0):
mss = mtu - 40 # IP + TCP headers
frames = -(-bytes_total // mss) # ceiling division
overhead_per_frame = 38 + 40 # framing + IP/TCP headers
wire_bytes = frames * (mss + overhead_per_frame)
efficiency = bytes_total / wire_bytes
cpu_seconds = frames * cpu_us_per_frame / 1e6
return frames, efficiency, cpu_seconds
print(f"{'MTU':>6}{'frames for 1 GB':>18}{'wire efficiency':>18}{'CPU seconds':>14}")
for mtu in (1500, 4000, 9000, 9216):
f, e, c = transfer_profile(1_000_000_000, mtu)
print(f"{mtu:>6}{f:>18,}{e:>17.2%}{c:>14.2f}")
# MTU frames for 1 GB wire efficiency CPU seconds
# 1500 684,932 94.93% 1.37
# 4000 252,526 98.03% 0.51
# 9000 111,608 99.14% 0.22
# 9216 109,015 99.16% 0.22
# Efficiency saturates quickly; the CPU saving is the bigger and more
# durable benefit.
def frames_per_second(link_gbps, mtu):
mss = mtu - 40
return (link_gbps * 1e9 / 8) / (mss + 78)
print()
for rate in (1, 10, 40, 100):
std = frames_per_second(rate, 1500)
jum = frames_per_second(rate, 9000)
print(f"{rate:>4} Gb/s: {std:>12,.0f} fps standard vs {jum:>10,.0f} fps jumbo "
f"({std/jum:.1f}x fewer)")
# 1 Gb/s: 81,352 fps standard vs 13,830 fps jumbo (5.9x fewer)
# 10 Gb/s: 813,545 fps standard vs 138,303 fps jumbo (5.9x fewer)
# 100 Gb/s: 8,135,449 fps standard vs 1,383,027 fps jumbo (5.9x fewer)
# At 100 Gb/s, 8 million interrupts per second is not survivable without
# offload — hence TSO/LRO even when jumbo frames are not used.
# Safety check before enabling jumbo frames anywhere:
def jumbo_safe(path_mtus):
lowest = min(path_mtus.values())
consistent = len(set(path_mtus.values())) == 1
return consistent, lowest, {d: m for d, m in path_mtus.items() if m == lowest}
path = {"host-a": 9000, "switch-1": 9000, "switch-2": 1500, "host-b": 9000}
ok, lowest, culprits = jumbo_safe(path)
print(f"\nconsistent: {ok}, effective path MTU: {lowest}")
print(f"limiting device(s): {culprits}")
# consistent: False, effective path MTU: 1500
# limiting device(s): {'switch-2': 1500}
# Enabling and verifying jumbo frames end to end.
$ sudo ip link set eth0 mtu 9000
$ ip link show eth0 | head -1
# 2: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 9000 qdisc fq state UP
# Verify the WHOLE PATH, not just the local interface. DF-set ping is the test:
$ ping -M do -s 8972 -c 3 10.0.5.20 # 8972 + 8 ICMP + 20 IP = 9000
# 8980 bytes from 10.0.5.20: icmp_seq=1 ttl=64 time=0.412 ms
# -> the path genuinely supports 9000 end to end
$ ping -M do -s 8972 -c 3 10.0.9.40
# (no replies — 100% packet loss, and NO error message)
# -> some device in this path is silently dropping jumbo frames
$ ping -c 3 10.0.9.40 # small packets still fine
# 3 packets transmitted, 3 received, 0% packet loss
# -> the classic small-works / large-fails MTU signature
Key takeaways
- Jumbo frames raise the payload to about 9000 bytes, cutting frame count roughly sixfold for a given transfer.
- Benefits: wire efficiency rises from ~95 to ~99 percent, and — more importantly — per-frame CPU and interrupt load falls by the same factor.
- Jumbo frames are not an IEEE standard; 9000 is a convention, and devices vary (9216, 9004, others).
- Every device in the path must agree. A single 1500-byte device silently drops jumbo frames, producing a PMTUD black hole with no error message.
- Enable them only on isolated, fully controlled networks — storage, cluster, and backup VLANs — never on general LANs reaching the Internet.
- A corrupted jumbo frame loses six times as much data, which matters on error-prone links.
- TSO/LRO offload captures most of the CPU benefit with standard frames on the wire and no interoperability risk.
🧪 Practice
- Compute the number of frames and the wire efficiency for a 500 MB transfer at MTU 1500 versus MTU 9000.
- Explain why an MTU mismatch produces no error message, and give the diagnostic command that reveals it.
- Interview-style: A storage team enables jumbo frames and reports that NFS mounts succeed but large file reads hang. What happened? (Hint: consider which operations use small packets, which use full-size ones, and what a single 1500-byte device in the path does to each.)
<a id="46-switching-and-bridging"></a>
4.6 Switching and Bridging
Switches are the devices that made Ethernet scale; this subchapter covers how they learn where hosts are, how they avoid destroying the network with loops, how links are bundled, and how one physical switch is divided into many virtual ones.
Transparent Bridging and MAC Learning
Theory
A switch's job is to forward each frame only where it needs to go. To do that it must know which port leads to which MAC address — and the elegant part of the design is that nobody tells it. It figures this out by watching traffic, which is why the mechanism is called transparent bridging: hosts are completely unaware the switch exists, and no configuration is required.
The algorithm has four rules, defined in IEEE 802.1D:
- Learning. For every arriving frame, record its source MAC address against the port it arrived on. This is the key insight: if a frame came from MAC X on port 3, then X must be reachable through port 3.
- Forwarding. Look up the frame's destination MAC. If it is in the table, send the frame out that port only.
- Flooding. If the destination is unknown, or is broadcast or multicast, send the frame out every port except the one it arrived on. This guarantees delivery even before learning is complete, at the cost of temporary inefficiency.
- Filtering. If the destination is on the same port the frame arrived on, discard it — the two hosts can reach each other directly and the switch must not interfere.
Entries age out, typically after 300 seconds of inactivity, so the table adapts when devices move or disappear.
Notice what this gives you: a self-configuring device that starts knowing nothing and converges to correct behaviour purely by observation, while remaining invisible to the hosts. That combination is why switches replaced hubs universally and why no protocol had to change to accommodate them.
Two operational consequences follow directly from the algorithm.
Unknown-unicast flooding is normal but should be rare. Sustained flooding usually indicates asymmetric routing, an aging timer shorter than the host's ARP cache timer, or a MAC table overflowing.
MAC table overflow is a security problem. The table is finite — perhaps 8,000 to 128,000 entries. The MAC flooding attack sends frames with thousands of forged source addresses, filling the table so that legitimate entries are evicted. The switch then floods all traffic, effectively turning itself into a hub and letting the attacker capture traffic between other hosts. The defence is port security, limiting how many MAC addresses may be learned per port.
A note on terminology: "bridge" and "switch" describe the same function. Historically a bridge had few ports and forwarded in software; a switch has many ports and forwards in hardware. The standards still say "bridge", which is why you see bridge commands and 802.1D in documentation.
Examples
Learning by observation, starting from an empty table
Topology: A(p1) B(p2) C(p3) D(p4) all on one switch
MAC table: empty
1) A -> B learn A on p1. B unknown -> FLOOD to p2, p3, p4
table: { A: p1 }
B, C, D all receive it; only B keeps it.
2) B -> A learn B on p2. A is known -> forward ONLY to p1
table: { A: p1, B: p2 }
C and D see nothing. The switch is already doing its job.
3) C -> A learn C on p3. A known -> forward only to p1
table: { A: p1, B: p2, C: p3 }
4) A -> B again both known -> forward only to p2
Meanwhile C <-> D can transmit SIMULTANEOUSLY on their own ports.
This is the whole point: one collision domain per port, parallel traffic.
MAC flooding attack:
attacker sends 100,000 frames with random source MACs
-> table fills, legitimate entries evicted
-> switch floods EVERYTHING
-> attacker sees traffic between all other hosts (a hub, effectively)
Defence: port security (limit MACs learned per port).
import time
class Switch:
def __init__(self, ports, table_size=8, aging_seconds=300):
self.ports = ports
self.table = {} # mac -> (port, last_seen)
self.table_size = table_size
self.aging = aging_seconds
self.stats = {"forwarded": 0, "flooded": 0, "filtered": 0}
def _age_out(self, now):
self.table = {m: v for m, v in self.table.items()
if now - v[1] < self.aging}
def receive(self, frame_src, frame_dst, in_port, now=None):
now = now if now is not None else time.time()
self._age_out(now)
# RULE 1: LEARN the source address against the arrival port.
if frame_src not in self.table and len(self.table) >= self.table_size:
oldest = min(self.table, key=lambda m: self.table[m][1])
del self.table[oldest] # eviction: the flooding attack's lever
self.table[frame_src] = (in_port, now)
# Broadcast and multicast are always flooded.
if frame_dst == "ff:ff:ff:ff:ff:ff" or int(frame_dst.split(":")[0], 16) & 1:
self.stats["flooded"] += 1
return ("FLOOD", [p for p in self.ports if p != in_port])
entry = self.table.get(frame_dst)
if entry is None: # RULE 3: unknown -> FLOOD
self.stats["flooded"] += 1
return ("FLOOD (unknown unicast)", [p for p in self.ports if p != in_port])
out_port = entry[0]
if out_port == in_port: # RULE 4: FILTER
self.stats["filtered"] += 1
return ("FILTER (same port)", [])
self.stats["forwarded"] += 1 # RULE 2: FORWARD
return ("FORWARD", [out_port])
sw = Switch(ports=["p1", "p2", "p3", "p4"])
traffic = [("aa:00:00:00:00:01", "aa:00:00:00:00:02", "p1"),
("aa:00:00:00:00:02", "aa:00:00:00:00:01", "p2"),
("aa:00:00:00:00:03", "aa:00:00:00:00:01", "p3"),
("aa:00:00:00:00:01", "aa:00:00:00:00:02", "p1"),
("aa:00:00:00:00:01", "ff:ff:ff:ff:ff:ff", "p1")]
for src, dst, port in traffic:
action, out = sw.receive(src, dst, port, now=1000)
print(f"{src[-2:]} -> {dst[-2:] if dst[0]!='f' else 'BCAST'} on {port}: "
f"{action:<24} out={out}")
# 01 -> 02 on p1: FLOOD (unknown unicast) out=['p2', 'p3', 'p4']
# 02 -> 01 on p2: FORWARD out=['p1']
# 03 -> 01 on p3: FORWARD out=['p1']
# 01 -> 02 on p1: FORWARD out=['p2']
# 01 -> BCAST on p1: FLOOD out=['p2', 'p3', 'p4']
print("\nMAC table:", {m: v[0] for m, v in sw.table.items()})
print("stats:", sw.stats)
# The MAC flooding attack, demonstrated:
print("\n--- MAC flooding attack ---")
victim = Switch(ports=["p1", "p2", "p3"], table_size=8)
victim.receive("aa:00:00:00:00:01", "aa:00:00:00:00:02", "p1", now=1000)
victim.receive("aa:00:00:00:00:02", "aa:00:00:00:00:01", "p2", now=1000)
print("legitimate entries learned:", len(victim.table))
for i in range(20): # flood with forged sources
victim.receive(f"de:ad:00:00:{i//256:02x}:{i%256:02x}",
"aa:00:00:00:00:99", "p3", now=1000)
action, out = victim.receive("aa:00:00:00:00:02", "aa:00:00:00:00:01", "p2", now=1000)
print(f"after attack, legit lookup: {action} -> {out}")
# after attack, legit lookup: FLOOD (unknown unicast) -> ['p1', 'p3']
# ^ the attacker on p3 now receives traffic meant for another host
# The MAC table on a real switch.
$ show mac address-table
# Vlan Mac Address Type Ports
# 10 001a.2b3c.4d5e DYNAMIC Gi1/0/1 <- learned by observation
# 10 00e0.4c68.01aa DYNAMIC Gi1/0/2
# 10 0050.5689.1f2c STATIC Gi1/0/24 <- manually pinned
# Total Mac Addresses for this criterion: 3
$ show mac address-table aging-time
# Global Aging Time: 300 <- entries expire after 5 min
# Port security: the defence against MAC flooding.
# interface GigabitEthernet1/0/5
# switchport port-security
# switchport port-security maximum 2 <- at most 2 MACs on this port
# switchport port-security violation restrict <- drop and log on violation
Key takeaways
- Transparent bridging requires no configuration and is invisible to hosts: the switch learns entirely by observing traffic.
- Four rules: learn the source MAC against the arrival port, forward to a known destination port, flood unknown unicast and all broadcast/multicast, filter frames whose destination is on the arrival port.
- Learning uses the source address; forwarding uses the destination address.
- Entries age out after about 300 seconds, letting the table adapt when hosts move.
- Sustained unknown-unicast flooding suggests asymmetric routing, aging-timer mismatch, or table overflow.
- MAC flooding attacks overflow the finite table to force flooding and enable eavesdropping; port security is the defence.
- "Bridge" and "switch" name the same function — the standards still say bridge.
🧪 Practice
- Starting with an empty table on a 4-port switch, trace the table contents and the forwarding action for: A→B, B→A, C→broadcast, A→C.
- Explain why a switch learns from the source address rather than the destination, and what would break if it tried the reverse.
- Interview-style: An attacker plugs into a switch port and begins receiving traffic between two other hosts. No port mirroring is configured. What happened? (Hint: consider what a switch does when its forwarding table can no longer hold the entries it needs.)
Switch Forwarding Modes
Theory
Once a switch knows which port to use, a second question arises: when should it start forwarding? Two answers trade latency against error containment.
Store-and-forward. Receive the entire frame into a buffer, verify the FCS, then forward. Corrupted frames are discarded and never propagate.
- Latency: the whole frame must be clocked in first — at 1 Gb/s, a 1500-byte frame takes about 12 microseconds.
- Benefit: no bad frame is ever forwarded, and the switch can connect ports of different speeds (a 1 Gb/s port to a 100 Mb/s port) because it has the entire frame buffered.
- This is the default on virtually all modern switches.
Cut-through. Begin forwarding as soon as the destination MAC has been read — just 6 bytes after the frame header begins. The rest of the frame streams through while still arriving.
- Latency: constant and tiny, typically well under a microsecond, and — importantly — independent of frame size.
- Cost: the FCS has not been seen yet, so corrupted frames are forwarded. Errors propagate through the network and are only detected at the destination.
- Cannot bridge different speeds, because there is nowhere to buffer the rate difference.
Fragment-free is the compromise: wait for the first 64 bytes before forwarding. Since collisions in a properly designed Ethernet occur within the first 64 bytes (the slot time from the CSMA/CD topic), this catches collision fragments while keeping latency low. It is largely historical now that collisions are gone.
Adaptive cut-through is what good switches actually do: run in cut-through mode, monitor the error rate, and automatically fall back to store-and-forward when errors exceed a threshold — getting low latency on healthy links and containment on bad ones.
| Mode | Forwards after | Latency (1 Gb/s, 1500 B) | Forwards bad frames | Speed change |
|---|---|---|---|---|
| Store-and-forward | Entire frame + FCS check | ~12 µs | No | Yes |
| Cut-through | 6 bytes (destination MAC) | ~0.1 µs | Yes | No |
| Fragment-free | 64 bytes | ~0.6 µs | Some | No |
| Adaptive | Switches automatically | Varies | Only until threshold | Partially |
The practical question is when this matters. For ordinary traffic it does not — 12 microseconds is negligible against millisecond-scale network delays, and store-and-forward's error containment is worth far more. It matters intensely in high-frequency trading, where microseconds carry monetary value, and in HPC and low-latency cluster interconnects, where thousands of hops of accumulated latency affect job completion time.
Note also that any switch doing something to the frame beyond forwarding — inspecting a VLAN tag deeply, applying an ACL, rewriting a header, doing quality-of-service classification — generally needs store-and-forward regardless of configuration.
Examples
When forwarding begins
Frame arriving:
|preamble|SFD| dst MAC | src MAC |type| ........ payload ........ |FCS|
|<- 8 ->| |<-- 6 -->|<-- 6 -->|<2>| |<4>|
^ ^
| |
CUT-THROUGH starts here STORE-AND-FORWARD
(destination known; FCS starts here (whole
not yet seen, so a corrupt frame verified, bad
frame WILL be forwarded) frames dropped)
^
FRAGMENT-FREE starts at 64 bytes
(catches collision fragments)
Latency accumulation across 5 switches, 1 Gb/s, 1500-byte frames:
store-and-forward: 5 x 12.0 us = 60.0 us
cut-through : 5 x 0.1 us = 0.5 us
difference : 59.5 us — irrelevant for web traffic,
decisive for trading systems
def forwarding_latency(frame_bytes, link_gbps, mode):
bits = frame_bytes * 8
serialise_us = bits / (link_gbps * 1000) # us to clock in the frame
fixed_us = 0.05 # switch fabric processing
if mode == "store-and-forward":
return serialise_us + fixed_us # must receive it ALL
if mode == "cut-through":
return (14 * 8) / (link_gbps * 1000) + fixed_us # header only
if mode == "fragment-free":
return (64 * 8) / (link_gbps * 1000) + fixed_us
raise ValueError(mode)
print(f"{'frame':>7}{'store-fwd':>12}{'cut-thru':>11}{'frag-free':>12}")
for size in (64, 512, 1500, 9000):
sf = forwarding_latency(size, 1, "store-and-forward")
ct = forwarding_latency(size, 1, "cut-through")
ff = forwarding_latency(size, 1, "fragment-free")
print(f"{size:>7}{sf:>10.2f}us{ct:>9.2f}us{ff:>10.2f}us")
# frame store-fwd cut-thru frag-free
# 64 0.56us 0.16us 0.56us
# 512 4.15us 0.16us 0.56us
# 1500 12.05us 0.16us 0.56us
# 9000 72.05us 0.16us 0.56us
# Cut-through latency is CONSTANT; store-and-forward grows with frame size.
def path_latency(hops, frame_bytes, link_gbps, mode):
return hops * forwarding_latency(frame_bytes, link_gbps, mode)
print()
for hops in (1, 5, 12):
sf = path_latency(hops, 1500, 10, "store-and-forward")
ct = path_latency(hops, 1500, 10, "cut-through")
print(f"{hops:>3} hops @10G: store-and-forward {sf:>7.2f} us, "
f"cut-through {ct:>5.2f} us (saving {sf-ct:>6.2f} us)")
# 1 hops @10G: store-and-forward 1.25 us, cut-through 0.06 us (saving 1.19 us)
# 12 hops @10G: store-and-forward 14.95 us, cut-through 0.68 us (saving 14.27 us)
# Error propagation: the real cost of cut-through.
def errors_forwarded(frames, error_rate, mode, hops=5):
bad = frames * error_rate
if mode == "store-and-forward":
return 0, bad # dropped at the first switch
return bad * hops, 0 # carried across every hop
for mode in ("store-and-forward", "cut-through"):
propagated, contained = errors_forwarded(1_000_000, 0.0001, mode)
print(f"\n{mode:<20}: {propagated:>8.0f} bad frames forwarded onward, "
f"{contained:>6.0f} contained at the first switch")
# store-and-forward : 0 bad frames forwarded onward, 100 contained at the first switch
# cut-through : 500 bad frames forwarded onward, 0 contained at the first switch
# ^ corrupt frames consume bandwidth on every subsequent link before
# finally being discarded by the destination host.
Key takeaways
- Store-and-forward buffers the whole frame and verifies the FCS before forwarding: higher latency, but corrupted frames never propagate, and it can bridge different port speeds. It is the modern default.
- Cut-through forwards after reading just the 6-byte destination MAC: latency is tiny and independent of frame size, but bad frames are forwarded and speed changes are impossible.
- Fragment-free waits 64 bytes to catch collision fragments — a now-historical compromise.
- Adaptive cut-through starts in cut-through and falls back to store-and-forward when errors exceed a threshold.
- The latency difference is negligible for ordinary traffic and decisive for high-frequency trading and HPC interconnects.
- Any switch performing ACLs, QoS classification, or header rewriting generally requires store-and-forward regardless of setting.
🧪 Practice
- Compute store-and-forward and cut-through latency for a 9000-byte frame on a 10 Gb/s link, and explain why the gap is so much larger than for a 64-byte frame.
- Explain why cut-through cannot connect a 10 Gb/s port to a 1 Gb/s port.
- Interview-style: A trading firm insists on cut-through switching. What risk are they accepting, and how would you mitigate it? (Hint: consider what reaches the destination when a frame is corrupted mid-path, and what adaptive mode does about it.)
Spanning Tree Protocol
Theory
Redundant links are essential — a network with a single path between switches fails completely when that path fails. But redundancy in a switched Ethernet creates loops, and loops in Ethernet are catastrophic in a way they are not in IP.
The reason is the absence of a TTL. An IP packet caught in a routing loop has its TTL decremented at each hop and is discarded after at most 255. An Ethernet frame has no such field. A broadcast frame that enters a loop circulates forever, and worse, each switch duplicates it out every port, so the frame count grows exponentially. Three consequences arrive within seconds:
- Broadcast storm — links saturate, CPUs peg, the network stops.
- MAC table instability — the same source address arrives on different ports as copies circulate, so switches rewrite their tables continuously ("MAC flapping").
- Multiple frame delivery — hosts receive many copies of each frame.
STP (Spanning Tree Protocol, IEEE 802.1D), designed by Radia Perlman in 1985, solves this by computing a spanning tree: a subgraph that connects every switch with exactly one active path between any pair, disabling the remaining links. The redundant links are not removed — they are placed in a blocking state, ready to be activated if the active topology breaks.
The algorithm has three stages, and the ordering is what makes it converge:
1. Elect a root bridge. Every switch has a bridge ID = 2-byte priority (default 32768) + its MAC address. The lowest bridge ID wins. Since the MAC address breaks ties, an election always resolves — but it also means that with default priorities the oldest switch (lowest MAC) usually becomes root, which is rarely the topologically sensible choice. Setting priority deliberately is standard practice.
2. Each non-root switch selects one root port — the port with the lowest cumulative path cost to the root. Costs are inversely related to bandwidth:
| Link speed | STP cost (802.1D-1998) | RSTP cost (802.1D-2004) |
|---|---|---|
| 10 Mb/s | 100 | 2,000,000 |
| 100 Mb/s | 19 | 200,000 |
| 1 Gb/s | 4 | 20,000 |
| 10 Gb/s | 2 | 2,000 |
3. Each network segment selects one designated port — the port on that segment with the lowest cost to the root, which will forward traffic for it. Every remaining port is blocked.
Switches exchange BPDUs (Bridge Protocol Data Units) every 2 seconds to maintain this. Classic STP's weakness is its timer-based convergence: a port moves through blocking → listening (15 s) → learning (15 s) → forwarding, so recovering from a failure takes 30 to 50 seconds — an eternity for modern applications, and precisely why RSTP replaced it.
Two protection features are near-mandatory in practice. PortFast (edge port) moves an access port straight to forwarding, since a port with a single host cannot create a loop. BPDU Guard shuts down a PortFast port that unexpectedly receives a BPDU — because that means someone plugged a switch into an access port, which is exactly how accidental loops happen.
Examples
STP converting a looped topology into a tree
Physical (contains a loop): After STP:
[SW1]------[SW2] [SW1 = ROOT]
| | | |
| | | |
[SW3]------[SW4] [SW3] [SW2]
| |
every link active | (blocked)
-> broadcast storm [SW4]--X--+
Root election: lowest bridge ID = priority.MAC
SW1: 32768.0011.1111.1111 <- LOWEST -> ROOT
SW2: 32768.0022.2222.2222
SW3: 32768.0033.3333.3333
SW4: 32768.0044.4444.4444
SW4's root port: compare paths to SW1
via SW3: cost 4 + 4 = 8 <- lower, becomes ROOT PORT
via SW2: cost 4 + 4 = 8 tie -> broken by lowest sender bridge ID
SW3 (0033..) < SW2's path? -> deterministic
The remaining port is BLOCKED, removing the loop.
Port state progression in classic STP (the 50-second problem):
blocking --(20s max-age)--> listening --(15s)--> learning --(15s)--> forwarding
^ no data ^ BPDUs only ^ learns MACs ^ passes data
Total worst case: 50 seconds of outage after a topology change.
STP_COST = {10: 100, 100: 19, 1000: 4, 10000: 2}
class Bridge:
def __init__(self, name, priority, mac):
self.name, self.priority, self.mac = name, priority, mac
self.bridge_id = (priority, mac)
self.root_id = self.bridge_id # initially each believes it is root
self.root_cost = 0
self.root_port = None
def elect_root(bridges):
"""The lowest bridge ID (priority first, then MAC) wins."""
return min(bridges, key=lambda b: b.bridge_id)
def compute_tree(bridges, links):
"""Dijkstra from the root using STP path costs."""
root = elect_root(bridges)
by_name = {b.name: b for b in bridges}
for b in bridges:
b.root_id = root.bridge_id
b.root_cost = 0 if b is root else float("inf")
# Relax edges until costs stabilise.
for _ in range(len(bridges)):
for a, z, speed in links:
cost = STP_COST[speed]
for src, dst in ((a, z), (z, a)):
if by_name[src].root_cost + cost < by_name[dst].root_cost:
by_name[dst].root_cost = by_name[src].root_cost + cost
by_name[dst].root_port = src
return root
bridges = [Bridge("SW1", 32768, "0011.1111.1111"),
Bridge("SW2", 32768, "0022.2222.2222"),
Bridge("SW3", 32768, "0033.3333.3333"),
Bridge("SW4", 32768, "0044.4444.4444")]
links = [("SW1","SW2",1000), ("SW1","SW3",1000),
("SW2","SW4",1000), ("SW3","SW4",1000)]
root = compute_tree(bridges, links)
print(f"ROOT BRIDGE: {root.name} (id {root.priority}.{root.mac})\n")
for b in bridges:
rp = f"via {b.root_port}" if b.root_port else "(is root)"
print(f"{b.name}: cost to root = {b.root_cost:>3} root port {rp}")
# ROOT BRIDGE: SW1 (id 32768.0011.1111.1111)
# SW1: cost to root = 0 root port (is root)
# SW2: cost to root = 4 root port via SW1
# SW3: cost to root = 4 root port via SW1
# SW4: cost to root = 8 root port via SW2
# Influencing the election deliberately — the standard practice:
print("\n--- setting SW3 priority to 4096 ---")
bridges[2].priority = 4096
bridges[2].bridge_id = (4096, bridges[2].mac)
root = compute_tree(bridges, links)
print(f"ROOT BRIDGE is now: {root.name}")
# ROOT BRIDGE is now: SW3
# Convergence timing: why RSTP was necessary.
STATES = [("blocking -> listening", 20), ("listening", 15), ("learning", 15)]
total = sum(t for _, t in STATES)
print(f"\nclassic STP convergence:")
for state, t in STATES:
print(f" {state:<24} {t:>3} s")
print(f" {'TOTAL OUTAGE':<24} {total:>3} s <- unacceptable for modern apps")
# classic STP convergence:
# blocking -> listening 20 s
# listening 15 s
# learning 15 s
# TOTAL OUTAGE 50 s <- unacceptable for modern apps
Key takeaways
- Ethernet frames have no TTL, so a switching loop causes exponentially multiplying broadcast storms, MAC table flapping, and duplicate delivery — collapsing the network in seconds.
- STP computes a loop-free spanning tree, putting redundant links in a blocking state rather than removing them, so they can take over on failure.
- Three stages: elect the root bridge (lowest priority.MAC bridge ID), choose each switch's root port (lowest cumulative path cost), and choose one designated port per segment; block everything else.
- Path costs are inversely related to bandwidth, and the cost values differ between the 1998 and 2004 standards.
- Default priorities mean the oldest switch often becomes root by accident — set the priority deliberately.
- Classic STP converges in 30–50 seconds because of its timer-based port states, which is why RSTP replaced it.
- PortFast skips the delay on access ports; BPDU Guard disables such a port if a BPDU appears, catching accidental switch connections.
🧪 Practice
- Four switches have bridge IDs 32768.AAAA, 32768.BBBB, 4096.CCCC, and 32768.DDDD. Which becomes root, and why does priority outrank the MAC address?
- Compute the STP path cost from a switch to the root across two 100 Mb/s links versus one 10 Mb/s link, and state which path wins.
- Interview-style: Why is a switching loop more damaging than a routing loop? (Hint: compare what each protocol's header does on every pass through the loop, and what a switch does with a broadcast frame versus what a router does with a packet.)
RSTP and MSTP
Theory
Classic STP's 30-to-50-second convergence was tolerable in 1990 and is not now. Two successors address different limitations.
RSTP (Rapid Spanning Tree Protocol, 802.1w), folded into 802.1D-2004, achieves sub-second convergence through several changes:
Simplified port states. Five states collapse into three: discarding (merging blocking, listening, and disabled), learning, and forwarding.
Explicit port roles. RSTP names roles separately from states, and adds two that STP lacked:
| Role | Meaning |
|---|---|
| Root port | Best path toward the root |
| Designated port | Forwards for this segment |
| Alternate port | A backup path to the root via a different switch — can take over immediately |
| Backup port | A redundant path to the same segment, via the same switch |
The alternate port is the crucial addition. Because RSTP has already computed and stored the next-best path, failure of the root port promotes the alternate immediately, with no timer wait. Classic STP had to recompute from scratch.
Proposal/agreement handshake. Rather than waiting out timers to be sure it is safe to forward, adjacent switches negotiate explicitly: one proposes to forward, the other blocks its non-edge ports and agrees. This synchronised handshake propagates outward from the root, converging in milliseconds.
Edge ports. RSTP standardises PortFast: a port declared as an edge port forwards immediately, and reverts to normal operation if a BPDU ever arrives.
Every switch originates BPDUs every hello interval, rather than only relaying the root's. Losing three consecutive BPDUs (6 seconds) signals failure, replacing the 20-second max-age timer.
MSTP (Multiple Spanning Tree Protocol, 802.1s) solves a completely different problem: a single spanning tree wastes links. With one tree for all VLANs, blocked links carry nothing for anyone, so half the network's capacity may sit idle.
MSTP maps groups of VLANs to instances, each with its own independently computed tree. VLANs 1–10 might use instance 1 with SW1 as root, while VLANs 11–20 use instance 2 with SW2 as root. The link blocked in instance 1 forwards in instance 2 — so all links carry traffic while each instance remains loop-free.
| STP (802.1D) | RSTP (802.1w) | MSTP (802.1s) | |
|---|---|---|---|
| Convergence | 30–50 s | < 1 s typically | < 1 s |
| Port states | 5 | 3 | 3 |
| Trees | 1 | 1 | Multiple instances |
| Link utilisation | Blocked links idle | Blocked links idle | All links used |
| Backwards compatible | — | Yes, with STP | Yes, with both |
Cisco's PVST+/Rapid-PVST+ runs one tree per VLAN — simpler to reason about but consuming CPU proportional to VLAN count, which is why MSTP's instance grouping scales better in large deployments.
Examples
Why the alternate port makes convergence instant
CLASSIC STP: the backup path is not pre-computed
root port fails -> switch has NO stored alternative
-> wait max-age (20 s), re-run the algorithm,
then listening (15 s) + learning (15 s) = 50 s outage
RSTP: the alternate port is already known and ready
root port fails -> promote the ALTERNATE port immediately
-> forwarding in milliseconds
[ROOT]
/ \
cost4 cost4
/ \
[SW2]---------[SW3]
^root port ^root port
^ALTERNATE port toward root via SW2 — pre-computed,
held in discarding state, promoted instantly on failure
MSTP: two instances, two trees, every link carrying traffic
Instance 1 (VLANs 1-10), root = SW1 Instance 2 (VLANs 11-20), root = SW2
[SW1]=====[SW2] [SW1]--X--[SW2]
| X blocked | |
| | | |
[SW3]-----[SW4] [SW3]=====[SW4]
The SW2-SW4 link is blocked for VLANs 1-10 but FORWARDING for VLANs 11-20.
Total utilisation: 100% of links, versus 75% with a single tree.
RSTP_ROLES = {
"root": "best path toward the root bridge — forwarding",
"designated": "forwards for this segment — forwarding",
"alternate": "backup path to root via ANOTHER switch — discarding, instant promote",
"backup": "redundant path to the same segment — discarding",
}
STATE_OF = {"root": "forwarding", "designated": "forwarding",
"alternate": "discarding", "backup": "discarding"}
print(f"{'role':<12}{'state':<13}purpose")
for role, purpose in RSTP_ROLES.items():
print(f"{role:<12}{STATE_OF[role]:<13}{purpose}")
def convergence_time(protocol, has_alternate=True):
if protocol == "STP":
return 20 + 15 + 15 # max-age + listening + learning
if protocol == "RSTP":
return 0.001 if has_alternate else 0.9 # instant promote, or handshake
return 0.001
print()
for proto in ("STP", "RSTP"):
t = convergence_time(proto)
print(f"{proto:<6} convergence after root-port failure: {t:>8.3f} s")
# STP convergence after root-port failure: 50.000 s
# RSTP convergence after root-port failure: 0.001 s
def mstp_utilisation(total_links, blocked_per_instance, instances):
"""With N instances, a link blocked in one may forward in another."""
if instances == 1:
return (total_links - blocked_per_instance) / total_links
# Distinct roots spread the blocked links across different instances.
effectively_unused = max(0, blocked_per_instance - (instances - 1))
return (total_links - effectively_unused) / total_links
print()
for inst in (1, 2, 4):
u = mstp_utilisation(total_links=8, blocked_per_instance=2, instances=inst)
label = "single tree (STP/RSTP)" if inst == 1 else f"MSTP, {inst} instances"
print(f"{label:<24}: link utilisation {u:>6.1%}")
# single tree (STP/RSTP) : link utilisation 75.0%
# MSTP, 2 instances : link utilisation 87.5%
# MSTP, 4 instances : link utilisation 100.0%
# CPU cost: why MSTP scales better than per-VLAN trees.
print()
for vlans in (10, 100, 1000):
print(f"{vlans:>5} VLANs -> PVST+: {vlans:>5} tree computations, "
f"MSTP (4 instances): {4:>2} computations")
# 10 VLANs -> PVST+: 10 tree computations, MSTP (4 instances): 4 computations
# 1000 VLANs -> PVST+: 1000 tree computations, MSTP (4 instances): 4 computations
Key takeaways
- RSTP (802.1w) converges in under a second by collapsing five port states into three (discarding, learning, forwarding) and adding explicit port roles.
- The alternate port — a pre-computed backup path to the root — is the key change: failure promotes it instantly instead of re-running the algorithm.
- The proposal/agreement handshake lets adjacent switches confirm it is safe to forward rather than waiting out timers.
- Every RSTP switch originates BPDUs; three missed hellos (6 s) signal failure, replacing STP's 20-second max-age.
- MSTP (802.1s) maps VLAN groups to independent spanning-tree instances, so a link blocked in one instance forwards in another and all links carry traffic.
- Cisco's PVST+ runs one tree per VLAN, which is simpler but scales poorly in CPU compared with MSTP's instance grouping.
🧪 Practice
- List RSTP's three port states and four port roles, and state which states each role occupies.
- Explain how MSTP allows every physical link to carry traffic while keeping each VLAN's topology loop-free.
- Interview-style: RSTP converges in milliseconds where STP took 50 seconds. What specific change accounts for most of that improvement? (Hint: ask what STP had to do after a failure that RSTP had already done in advance.)
Link Aggregation and LACP
Theory
Spanning tree's weakness is that it wastes redundant links — a blocked port carries nothing. Link aggregation takes a different approach: rather than blocking parallel links, combine several physical links into one logical link that spanning tree sees as a single connection. No loop exists to block, so all member links carry traffic.
The benefits are both capacity and resilience:
- Aggregate bandwidth. Four 10 Gb/s links become one 40 Gb/s logical link.
- Resilience without reconvergence. If one member fails, traffic redistributes across the remainder in milliseconds. Spanning tree never even notices, because the logical link stays up.
- No blocked capacity. Unlike STP's redundancy, every link is productive.
The names vary: LAG (Link Aggregation Group), port channel, EtherChannel, bond, team. The standard is IEEE 802.1AX (originally 802.3ad).
The mechanism that makes this work correctly is the crucial part. A naive implementation would round-robin frames across members — and that would reorder packets, because links have slightly different queueing delays. Out-of-order delivery makes TCP interpret the gaps as loss, triggering spurious fast retransmits and collapsing throughput.
So aggregation instead uses a hash. Selected header fields are hashed, and the result picks a member link. Because every frame of a given flow hashes identically, all frames of a flow take the same link and order is preserved.
| Hash input | Granularity | Best for |
|---|---|---|
| Source MAC | Coarse | Rarely useful |
| Source + destination MAC | Coarse | Layer 2 only |
| Source + destination IP | Medium | Router-to-router |
| Source + dest IP + ports | Fine | General use, the common default |
The consequence follows directly and is one of the most misunderstood points in networking: a single flow can never exceed the speed of one member link. Four bonded 10 Gb/s links give 40 Gb/s of aggregate capacity, but one TCP connection is capped at 10 Gb/s. Someone testing a new 4×10 G bond with a single iperf stream will measure 10 Gb/s and conclude it is broken. It is working exactly as designed.
Aggregation also distributes unevenly when flow count is low or hashes collide — with two large flows on a four-link bond, two links may be saturated while two sit idle.
LACP (Link Aggregation Control Protocol) is the negotiation protocol. Instead of configuring both ends statically and hoping, LACP exchanges LACPDUs to verify that both ends agree on membership before bringing the bundle up.
- Active mode initiates negotiation; passive mode only responds. At least one end must be active.
- Static (on) mode skips negotiation entirely — and is dangerous, because a miscabled static bundle creates a loop with nothing to detect it. LACP would catch that mismatch.
Requirements for members: matching speed, duplex, and VLAN configuration, and all connecting to the same peer device — unless the peer supports MLAG/vPC/stacking, which lets one bundle span two physical switches for device-level redundancy.
Examples
Aggregation versus spanning tree for the same redundancy
WITH STP: WITH LAG:
[SW1]====[SW2] [SW1]====[SW2]
4 links, 3 BLOCKED 4 links, ALL forwarding
usable: 10 Gb/s usable: 40 Gb/s
failover: ~1 s (RSTP) failover: milliseconds, STP unaware
Why hashing, not round-robin:
ROUND-ROBIN (broken):
frame 1 -> link A (queue depth 2) arrives at t=10
frame 2 -> link B (queue depth 0) arrives at t=8 <- ARRIVES FIRST
frame 3 -> link C arrives at t=9
Receiver sees 2, 3, 1 -> TCP infers loss -> spurious fast retransmit
-> congestion window collapses -> throughput far WORSE than one link
HASH (correct):
hash(srcIP, dstIP, srcPort, dstPort) -> always the same link for a flow
flow X -> link A always order preserved
flow Y -> link C always order preserved
The single-flow limit, which surprises everyone:
4 x 10 Gb/s bond = 40 Gb/s aggregate
one iperf stream = 10 Gb/s MAXIMUM <- not a fault; by design
40 parallel streams = ~40 Gb/s <- this is the correct test
import hashlib, random
from collections import Counter
def hash_to_link(flow, n_links, policy="l4"):
"""Select a member link from flow identifiers. Same flow -> same link."""
if policy == "l2":
key = f"{flow['src_mac']}{flow['dst_mac']}"
# Coarse: every flow between the same two hosts lands on ONE link.
elif policy == "l3":
key = f"{flow['src_ip']}{flow['dst_ip']}"
else: # l4: finest granularity
key = f"{flow['src_ip']}{flow['dst_ip']}{flow['src_port']}{flow['dst_port']}"
digest = hashlib.md5(key.encode()).digest()
return int.from_bytes(digest[:4], "big") % n_links
def make_flows(n, hosts=4):
return [{"src_mac": f"aa:00:00:00:00:{i%hosts:02x}",
"dst_mac": "bb:00:00:00:00:01",
"src_ip": f"10.0.0.{i%hosts + 1}",
"dst_ip": "10.0.1.100",
"src_port": 40000 + i,
"dst_port": 443} for i in range(n)]
N_LINKS = 4
for policy in ("l2", "l3", "l4"):
dist = Counter(hash_to_link(f, N_LINKS, policy) for f in make_flows(200))
spread = [dist.get(i, 0) for i in range(N_LINKS)]
print(f"policy {policy}: distribution across 4 links = {spread}")
# policy l2: distribution across 4 links = [50, 0, 100, 50]
# ^ only 4 distinct MAC pairs exist, so balancing is poor
# policy l3: distribution across 4 links = [50, 50, 0, 100]
# policy l4: distribution across 4 links = [46, 57, 50, 47]
# ^ port numbers give many distinct keys -> even distribution
def aggregate_throughput(n_links, link_gbps, n_flows):
"""Hash collisions mean utilisation is imperfect with few flows."""
if n_flows == 0:
return 0.0
used = set(hash_to_link(f, n_links) for f in make_flows(n_flows, hosts=n_flows))
per_flow_cap = link_gbps
total = min(n_flows * per_flow_cap, len(used) * link_gbps)
return total, len(used)
print(f"\n4 x 10 Gb/s bond (40 Gb/s aggregate):")
for flows in (1, 2, 4, 8, 40):
total, used = aggregate_throughput(4, 10, flows)
print(f" {flows:>3} flow(s): {total:>5.1f} Gb/s achieved, "
f"{used}/4 links carrying traffic")
# 1 flow(s): 10.0 Gb/s achieved, 1/4 links carrying traffic <- the surprise
# 2 flow(s): 20.0 Gb/s achieved, 2/4 links carrying traffic
# 4 flow(s): 30.0 Gb/s achieved, 3/4 links carrying traffic <- hash collision
# 40 flow(s): 40.0 Gb/s achieved, 4/4 links carrying traffic
# Failover behaviour: capacity degrades, the logical link stays up.
print()
for failed in range(4):
remaining = 4 - failed
print(f"{failed} link(s) failed: {remaining*10:>2} Gb/s capacity, "
f"logical link {'UP' if remaining else 'DOWN'} "
f"({'STP unaware' if remaining else 'STP reconverges'})")
# 0 link(s) failed: 40 Gb/s capacity, logical link UP (STP unaware)
# 3 link(s) failed: 10 Gb/s capacity, logical link UP (STP unaware)
# Configuring and verifying a bond on Linux.
$ cat /proc/net/bonding/bond0
# Bonding Mode: IEEE 802.3ad Dynamic link aggregation
# Transmit Hash Policy: layer3+4 (1) <- the hash input; layer3+4 balances best
# 802.3ad info
# LACP rate: fast <- LACPDUs every 1 s, not 30 s
# Aggregator ID: 1
# Number of ports: 4
# Slave Interface: eth1
# MII Status: up
# Aggregator ID: 1 <- all slaves MUST share this ID
# Slave Interface: eth2
# MII Status: up
# Aggregator ID: 1
# A mismatch shows as different aggregator IDs — the bundle silently splits:
# Slave eth3: Aggregator ID: 2 <- NOT bundled; peer disagrees
# Switch side:
$ show etherchannel summary
# Flags: D - down P - bundled in port-channel I - stand-alone
# Group Port-channel Protocol Ports
# 1 Po1(SU) LACP Gi1/0/1(P) Gi1/0/2(P) Gi1/0/3(P) Gi1/0/4(P)
# ^^^^ S=layer2, U=in use ^^^ (P) = bundled correctly
# (I) would mean stand-alone: a problem
Key takeaways
- Link aggregation combines several physical links into one logical link, so spanning tree sees no loop and all members carry traffic.
- It provides aggregate bandwidth plus millisecond failover without STP reconvergence.
- Frames are distributed by hashing header fields — never round-robin — because reordering would make TCP infer loss and collapse throughput.
- Therefore a single flow cannot exceed one member link's speed; a 4×10 G bond gives 40 Gb/s aggregate but 10 Gb/s per connection.
- Hash policies range from source/destination MAC (coarse) to source/destination IP plus ports (fine, the usual default).
- LACP negotiates membership via LACPDUs and catches misconfiguration; static bundles skip this and can silently create loops.
- Members must match in speed, duplex, and VLAN config, and terminate on the same peer unless MLAG/vPC/stacking is used.
🧪 Practice
- A 4×10 Gb/s bond is tested with a single
iperfstream and reaches 9.4 Gb/s. Is the bond faulty? Explain and give the correct test.- Explain why round-robin distribution would reduce TCP throughput below that of a single link.
- Interview-style: Why is LACP preferable to a statically configured bundle? (Hint: consider what happens when someone patches one member cable into the wrong switch, and which mode would detect it.)
VLANs and 802.1Q Tagging
Theory
A switch creates one broadcast domain across all its ports. Often you want several — separating finance from engineering, isolating guest Wi-Fi, keeping VoIP phones on their own network. The historical answer was to buy a separate switch per group, which is expensive, inflexible, and wastes ports.
A VLAN (Virtual LAN) creates multiple logical broadcast domains on shared physical hardware. Ports 1–8 belong to VLAN 10, ports 9–16 to VLAN 20, and the switch forwards frames only among ports in the same VLAN. Two devices plugged into adjacent ports of the same switch cannot communicate at all unless a router connects their VLANs.
The benefits are the reason VLANs are universal:
- Segmentation without hardware. One switch serves many isolated networks.
- Location independence. A user's VLAN follows their port assignment, not their physical location — the finance VLAN can span three floors.
- Broadcast containment. Broadcast traffic stays within its VLAN, so domains stay small.
- Security boundaries. Inter-VLAN traffic must pass through a router, where policy can be applied.
The problem VLANs create: when a frame leaves one switch for another, the receiving switch must know which VLAN it belongs to. The Ethernet header has no field for this.
IEEE 802.1Q solves it by inserting a 4-byte tag after the source MAC:
| Field | Bits | Purpose |
|---|---|---|
| TPID | 16 | 0x8100 — identifies the frame as tagged |
| PCP | 3 | Priority Code Point — 8 QoS classes (802.1p) |
| DEI | 1 | Drop Eligible Indicator |
| VID | 12 | VLAN ID: 0–4095, of which 1–4094 are usable |
Two numbers follow: the 12-bit VID gives 4094 usable VLANs (0 and 4095 are reserved), a limit that drove VXLAN's development for cloud scale; and the tag makes the maximum frame 1522 bytes, which devices not expecting tags report as "baby giants".
Ports come in two kinds:
- Access ports carry exactly one VLAN and send untagged frames. Hosts connect here and are entirely unaware VLANs exist.
- Trunk ports carry many VLANs and tag frames so the receiver can sort them. Switch-to-switch and switch-to-router links are trunks.
The native VLAN is a trunk's untagged VLAN — frames belonging to it traverse the trunk with no tag, for backwards compatibility. It is also a security liability: a VLAN hopping attack sends double-tagged frames, where the switch strips the outer native-VLAN tag and forwards the frame into the inner VLAN. The defences are to never use VLAN 1 as native, to use a dedicated unused native VLAN, and ideally to tag the native VLAN explicitly.
Examples
802.1Q tag insertion
Untagged frame:
| dst MAC 6 | src MAC 6 | EtherType 2 | payload | FCS 4 | max 1518
Tagged frame:
| dst MAC 6 | src MAC 6 | 802.1Q 4 | EtherType 2 | payload | FCS 4 | max 1522
^^^^^^^^^^ inserted here
|TPID 0x8100|PCP|DEI| VID |
|<-- 16 --->| 3 | 1 | 12 |
Access ports versus trunk ports:
[PC-A]--access VLAN 10--[SW1]===trunk===[SW2]--access VLAN 10--[PC-B]
untagged tagged untagged
frames
PC-A and PC-B never see a tag. SW1 adds it on the trunk,
SW2 strips it before delivery. The hosts are unaware.
VLAN hopping via double tagging:
attacker (native VLAN 1) sends: |VLAN 1 tag|VLAN 20 tag| payload |
SW1: "native VLAN — strip the outer tag", forwards on the trunk
SW2: sees the VLAN 20 tag, delivers into VLAN 20 <-- ATTACK SUCCEEDS
Defence: dedicated unused native VLAN, or tag the native VLAN.
def build_tag(vid, pcp=0, dei=0):
"""802.1Q TCI: 3-bit priority, 1-bit DEI, 12-bit VLAN ID."""
assert 1 <= vid <= 4094, "VLAN 0 and 4095 are reserved"
tci = (pcp << 13) | (dei << 12) | vid
return (0x8100).to_bytes(2, "big") + tci.to_bytes(2, "big")
def parse_tag(tag: bytes):
tpid = int.from_bytes(tag[0:2], "big")
tci = int.from_bytes(tag[2:4], "big")
return {"tpid": hex(tpid), "pcp": (tci >> 13) & 0x7,
"dei": (tci >> 12) & 0x1, "vid": tci & 0xFFF}
for vid, pcp in [(10, 0), (20, 3), (100, 5), (4094, 7)]:
t = build_tag(vid, pcp)
print(f"VLAN {vid:>4} pcp {pcp}: tag = {t.hex(' ')} -> {parse_tag(t)}")
# VLAN 10 pcp 0: tag = 81 00 00 0a -> {'tpid': '0x8100', 'pcp': 0, 'dei': 0, 'vid': 10}
# VLAN 20 pcp 3: tag = 81 00 60 14 -> {'tpid': '0x8100', 'pcp': 3, 'dei': 0, 'vid': 20}
# VLAN 4094 pcp 7: tag = 81 00 ff fe -> {'tpid': '0x8100', 'pcp': 7, 'dei': 0, 'vid': 4094}
class VlanSwitch:
def __init__(self):
self.ports = {} # port -> ("access", vid) or ("trunk", {vids}, native)
def access(self, port, vid): self.ports[port] = ("access", vid, None)
def trunk(self, port, vids, native=1): self.ports[port] = ("trunk", vids, native)
def egress(self, port, vid):
"""Decide how a frame in `vid` leaves this port."""
kind, cfg, native = self.ports[port]
if kind == "access":
return "send UNTAGGED" if cfg == vid else "DROP (wrong VLAN)"
if vid not in cfg:
return "DROP (VLAN not allowed on trunk)"
if vid == native:
return f"send UNTAGGED (native VLAN {native})"
return f"send TAGGED vid={vid}"
sw = VlanSwitch()
sw.access("Gi1/0/1", 10)
sw.access("Gi1/0/5", 20)
sw.trunk("Gi1/0/24", {10, 20, 30}, native=99)
print()
for port in ("Gi1/0/1", "Gi1/0/5", "Gi1/0/24"):
for vid in (10, 20, 99):
print(f"frame in VLAN {vid:>2} out {port:<9}: {sw.egress(port, vid)}")
print()
# frame in VLAN 10 out Gi1/0/1 : send UNTAGGED
# frame in VLAN 20 out Gi1/0/1 : DROP (wrong VLAN)
# frame in VLAN 99 out Gi1/0/1 : DROP (wrong VLAN)
#
# frame in VLAN 10 out Gi1/0/24 : send TAGGED vid=10
# frame in VLAN 99 out Gi1/0/24 : send UNTAGGED (native VLAN 99)
print(f"usable VLAN IDs: 1-4094 ({4094:,}) — 0 and 4095 reserved")
print("this 4094 ceiling is why cloud providers moved to VXLAN (24-bit VNI,")
print(f"giving {2**24:,} segments)")
Key takeaways
- A VLAN creates multiple logical broadcast domains on one physical switch; ports in different VLANs cannot communicate without a router.
- 802.1Q inserts a 4-byte tag after the source MAC: TPID
0x8100, 3-bit PCP priority, 1-bit DEI, and a 12-bit VID. - The 12-bit VID allows 4094 usable VLANs (0 and 4095 reserved) — the limit that motivated VXLAN's 24-bit VNI.
- A tagged frame can reach 1522 bytes, reported as a "baby giant" by devices not expecting tags.
- Access ports carry one VLAN untagged (hosts are unaware); trunk ports carry many VLANs tagged.
- The native VLAN traverses a trunk untagged and enables double-tagging VLAN hopping — use a dedicated unused native VLAN or tag it explicitly.
🧪 Practice
- Build the 802.1Q tag bytes for VLAN 250 with priority 5, showing the TCI bit layout.
- Explain why a host on an access port never sees a VLAN tag, and which device adds and removes it.
- Interview-style: Explain a double-tagging VLAN hopping attack and how to prevent it. (Hint: trace what the first switch does with the outer tag when it matches the native VLAN.)
Trunking and Inter-VLAN Routing
Theory
VLANs deliberately isolate traffic — but complete isolation is rarely what anyone wants. Finance and engineering still need the same file server, everyone needs the Internet, and VoIP phones need to reach the call manager. Since VLANs are separate broadcast domains, and by construction separate IP subnets, moving traffic between them requires a router. This is inter-VLAN routing.
First, the carrying mechanism. A trunk is a link that carries multiple VLANs by tagging frames. Two design points matter in practice:
- Allowed VLAN lists. A trunk should carry only the VLANs it needs. Permitting all VLANs everywhere spreads broadcast traffic unnecessarily and widens the blast radius of a misconfiguration.
- Dynamic trunking is a liability. Cisco's DTP negotiates trunk formation automatically, which means an attacker's device can negotiate itself a trunk port and gain access to every VLAN. Best practice is to hard-configure ports as access or trunk and disable negotiation.
There are three ways to route between VLANs.
1. Router with one interface per VLAN. Physically obvious: one router port per VLAN, each an access port. It does not scale — twenty VLANs need twenty router interfaces and twenty switch ports — and it is now purely historical.
2. Router-on-a-stick. A single physical link, configured as a trunk, carrying all VLANs. The router creates a subinterface per VLAN, each with the VLAN's gateway IP address and configured to expect that VLAN's tag. A frame from VLAN 10 to VLAN 20 travels up the trunk tagged 10, is routed internally, and returns tagged 20.
Cheap, but the single link carries all inter-VLAN traffic in both directions — every routed packet crosses it twice — so it is a bandwidth bottleneck and a single point of failure.
3. Layer 3 switch with SVIs. The modern answer. A layer 3 switch routes in the same ASIC that switches, at line rate. Each VLAN gets an SVI (Switched Virtual Interface) — a virtual layer 3 interface holding that VLAN's gateway address. Routing happens inside the switch with no external link involved.
| Approach | Inter-VLAN bandwidth | Scalability | Cost | Use |
|---|---|---|---|---|
| Router per VLAN | Full per interface | Very poor | High | Obsolete |
| Router-on-a-stick | Shared one link | Poor | Low | Small sites, labs |
| L3 switch with SVIs | Line rate in ASIC | Excellent | Moderate | Standard practice |
The essential conceptual point, which ties this subchapter to the next chapter: a VLAN is a broadcast domain, and a broadcast domain is an IP subnet. VLAN 10 might be 10.1.10.0/24 with gateway 10.1.10.1 on the SVI. A host in VLAN 10 sending to 10.1.20.50 consults its routing table, sees the destination is not local, and ARPs for its default gateway — the SVI. The switch then routes the packet into VLAN 20. Every inter-VLAN packet is a layer 3 forwarding decision, exactly as Chapter 5 will describe.
Examples
Router-on-a-stick: one link carries everything
[PC VLAN 10]---+
|
[PC VLAN 20]---+--[SWITCH]===trunk===[ROUTER]
| Gi0/0.10 ip 10.1.10.1 VLAN 10
[PC VLAN 30]---+ Gi0/0.20 ip 10.1.20.1 VLAN 20
Gi0/0.30 ip 10.1.30.1 VLAN 30
VLAN 10 host -> VLAN 20 host:
1. host sees 10.1.20.50 is not local -> sends to gateway 10.1.10.1
2. frame goes up the trunk TAGGED VLAN 10
3. router receives on Gi0/0.10, routes to Gi0/0.20
4. frame returns down the trunk TAGGED VLAN 20
^ the same physical link carried it BOTH WAYS: the bottleneck
Layer 3 switch with SVIs: routing happens inside
[PC VLAN 10]---+
| +---------------------------+
[PC VLAN 20]---+---| L3 SWITCH |
| | SVI vlan10: 10.1.10.1 |
[PC VLAN 30]---+ | SVI vlan20: 10.1.20.1 |
| SVI vlan30: 10.1.30.1 |
| routing done in the ASIC |
+---------------------------+
No external link is involved. Line-rate forwarding, no bottleneck.
import ipaddress
class L3Switch:
def __init__(self):
self.svis = {} # vlan -> (gateway_ip, network)
self.access_ports = {} # port -> vlan
def add_svi(self, vlan, cidr):
net = ipaddress.ip_network(cidr, strict=False)
gateway = list(net.hosts())[0] # convention: .1 is the gateway
self.svis[vlan] = (gateway, net)
def vlan_of_ip(self, ip):
addr = ipaddress.ip_address(ip)
for vlan, (_, net) in self.svis.items():
if addr in net:
return vlan
return None
def forward(self, src_ip, dst_ip):
src_vlan, dst_vlan = self.vlan_of_ip(src_ip), self.vlan_of_ip(dst_ip)
if src_vlan is None:
return "source not in any configured VLAN"
if dst_vlan is None:
gw, _ = self.svis[src_vlan]
return f"L3 ROUTE via default gateway (off-switch); host ARPs for {gw}"
if src_vlan == dst_vlan:
# Same broadcast domain: pure layer 2, no routing involved.
return f"L2 SWITCH within VLAN {src_vlan} (no routing, host ARPs for the destination)"
gw, _ = self.svis[src_vlan]
return (f"L3 ROUTE VLAN {src_vlan} -> VLAN {dst_vlan} "
f"(host ARPs for gateway {gw}, switch routes in ASIC)")
sw = L3Switch()
sw.add_svi(10, "10.1.10.0/24")
sw.add_svi(20, "10.1.20.0/24")
sw.add_svi(30, "10.1.30.0/24")
print("SVI configuration:")
for vlan, (gw, net) in sw.svis.items():
print(f" interface Vlan{vlan:<4} ip address {gw}/{net.prefixlen}")
print()
for src, dst in [("10.1.10.50", "10.1.10.60"),
("10.1.10.50", "10.1.20.50"),
("10.1.20.10", "10.1.30.99"),
("10.1.10.50", "93.184.216.34")]:
print(f"{src:<14} -> {dst:<14}: {sw.forward(src, dst)}")
# 10.1.10.50 -> 10.1.10.60 : L2 SWITCH within VLAN 10 (no routing, host ARPs for the destination)
# 10.1.10.50 -> 10.1.20.50 : L3 ROUTE VLAN 10 -> VLAN 20 (host ARPs for gateway 10.1.10.1, ...)
# 10.1.10.50 -> 93.184.216.34 : L3 ROUTE via default gateway (off-switch); host ARPs for 10.1.10.1
# Bandwidth comparison: where inter-VLAN traffic actually flows.
def inter_vlan_capacity(design, trunk_gbps=1, backplane_gbps=176):
if design == "router-on-a-stick":
# Every packet crosses the single trunk TWICE (in and back out).
return trunk_gbps / 2, "single trunk, traversed twice per packet"
return backplane_gbps, "switch backplane, line rate"
print()
for d in ("router-on-a-stick", "L3 switch with SVIs"):
cap, why = inter_vlan_capacity(d)
print(f"{d:<22}: {cap:>6.1f} Gb/s usable ({why})")
# router-on-a-stick : 0.5 Gb/s usable (single trunk, traversed twice per packet)
# L3 switch with SVIs : 176.0 Gb/s usable (switch backplane, line rate)
# Router-on-a-stick configuration:
# interface GigabitEthernet0/0.10
# encapsulation dot1Q 10 <- expect VLAN 10 tags on this subinterface
# ip address 10.1.10.1 255.255.255.0
# interface GigabitEthernet0/0.20
# encapsulation dot1Q 20
# ip address 10.1.20.1 255.255.255.0
# Layer 3 switch with SVIs — the modern equivalent:
# ip routing <- must be enabled explicitly
# interface Vlan10
# ip address 10.1.10.1 255.255.255.0
# interface Vlan20
# ip address 10.1.20.1 255.255.255.0
# Trunk hardening: never rely on dynamic negotiation.
# interface GigabitEthernet1/0/24
# switchport mode trunk <- hard-set, not "dynamic auto"
# switchport trunk allowed vlan 10,20,30 <- explicit list, not "all"
# switchport trunk native vlan 999 <- dedicated unused native VLAN
# switchport nonegotiate <- disable DTP entirely
$ show interfaces trunk
# Port Mode Encapsulation Status Native vlan
# Gi1/0/24 on 802.1q trunking 999
# Port Vlans allowed on trunk
# Gi1/0/24 10,20,30 <- only what is needed
Key takeaways
- VLANs isolate by design, so inter-VLAN communication requires a router — each VLAN is a separate broadcast domain and a separate IP subnet.
- Trunks should carry an explicit allowed-VLAN list, and dynamic trunk negotiation (DTP) should be disabled to prevent an attacker negotiating trunk access.
- Router-on-a-stick uses one trunk with a subinterface per VLAN: cheap, but all inter-VLAN traffic crosses the same link twice.
- A layer 3 switch with SVIs routes in the switching ASIC at line rate and is standard practice.
- An SVI is a virtual layer 3 interface holding a VLAN's gateway address.
- Every inter-VLAN packet is a layer 3 forwarding decision: the host ARPs for its default gateway, and the router or SVI forwards into the destination VLAN.
🧪 Practice
- Write the subinterface configuration for router-on-a-stick serving VLANs 5, 15, and 25 with gateways at
192.168.x.1.- Explain why router-on-a-stick halves effective inter-VLAN bandwidth, tracing one packet's path.
- Interview-style: Two hosts on the same switch, in different VLANs, cannot ping each other. Everything looks correctly configured at layer 2. What is missing? (Hint: ask which device makes the forwarding decision between two different IP subnets, and whether it exists in this topology.)
<a id="47-address-resolution"></a>
4.7 Address Resolution
IP addresses identify hosts globally, but frames are delivered by MAC address; this closing subchapter covers the protocols that bridge the two, and the attacks that exploit their trust.
ARP Request and Reply Operation
Theory
A host wants to send an IP packet to 192.168.1.50 on its local network. It has the IP address. But the link layer delivers frames by MAC address, and the host has no idea what MAC belongs to that IP. Something must translate between the two, and that something is ARP (Address Resolution Protocol, RFC 826).
The method is a broadcast question. The host sends an ARP request to the broadcast address FF:FF:FF:FF:FF:FF, which every station in the broadcast domain receives. The request asks, in effect, "Who has 192.168.1.50? Tell 192.168.1.10." Every host examines it; the one that owns that address sends a unicast ARP reply containing its MAC. Everyone else discards the request.
Two details reward attention.
The request is broadcast; the reply is unicast. The requester's own MAC and IP are inside the request, so the responder already knows where to send the answer directly — no second broadcast is needed.
ARP is not carried inside IP. It rides directly in Ethernet frames with EtherType 0x0806. This is why its layer placement is genuinely ambiguous, as Chapter 2 discussed: it serves IP but is not encapsulated by it.
The ARP packet's fields:
| Field | Bytes | Typical value |
|---|---|---|
| Hardware type | 2 | 1 = Ethernet |
| Protocol type | 2 | 0x0800 = IPv4 |
| Hardware length | 1 | 6 |
| Protocol length | 1 | 4 |
| Operation | 2 | 1 = request, 2 = reply |
| Sender hardware address | 6 | Sender's MAC |
| Sender protocol address | 4 | Sender's IP |
| Target hardware address | 6 | Zeros in a request |
| Target protocol address | 4 | The IP being resolved |
The most important behaviour to internalise is when ARP is used for the destination and when for the gateway. The sending host first compares the destination IP against its own subnet mask:
- Destination on the same subnet — ARP for the destination's own IP.
- Destination on another subnet — ARP for the default gateway's IP.
In the second case the frame's destination MAC is the router's, while the IP header's destination remains the far-away server. This is the layering point from Chapter 2 made concrete: layer 2 addresses the next hop; layer 3 addresses the true endpoint. A host never learns, and never needs to learn, the MAC address of a remote server.
Examples
Same-subnet resolution
Host A (192.168.1.10, aa:aa:aa:aa:aa:aa) wants 192.168.1.50
1. BROADCAST request
eth dst FF:FF:FF:FF:FF:FF src aa:aa... type 0x0806
ARP: op=1 (request)
sender 192.168.1.10 / aa:aa:aa:aa:aa:aa
target 192.168.1.50 / 00:00:00:00:00:00 <- unknown, hence zeros
Every host in the broadcast domain receives and inspects this.
.20, .30, .40 discard it. Only .50 responds.
2. UNICAST reply
eth dst aa:aa:aa:aa:aa:aa src bb:bb... type 0x0806
ARP: op=2 (reply)
sender 192.168.1.50 / bb:bb:bb:bb:bb:bb
target 192.168.1.10 / aa:aa:aa:aa:aa:aa
Sent directly — the responder already knows A's MAC from the request.
Off-subnet: ARP asks for the GATEWAY, never the remote server
Host A (192.168.1.10/24) wants 93.184.216.34
Is 93.184.216.34 inside 192.168.1.0/24? NO
-> ARP for the DEFAULT GATEWAY 192.168.1.1
resulting frame:
eth dst = router's MAC <- next hop, layer 2
ip dst = 93.184.216.34 <- true endpoint, layer 3, unchanged end to end
A never learns the server's MAC, and never needs to.
import ipaddress, struct
def build_arp(op, sender_mac, sender_ip, target_mac, target_ip):
return struct.pack(
"!HHBBH6s4s6s4s",
1, # hardware type: Ethernet
0x0800, # protocol type: IPv4
6, 4, # hardware len, protocol len
op, # 1 = request, 2 = reply
bytes.fromhex(sender_mac.replace(":", "")),
ipaddress.ip_address(sender_ip).packed,
bytes.fromhex(target_mac.replace(":", "")),
ipaddress.ip_address(target_ip).packed)
def parse_arp(pkt):
(_, _, _, _, op, sha, spa, tha, tpa) = struct.unpack("!HHBBH6s4s6s4s", pkt)
return {"op": "request" if op == 1 else "reply",
"sender": f"{ipaddress.ip_address(spa)} / {sha.hex(':')}",
"target": f"{ipaddress.ip_address(tpa)} / {tha.hex(':')}"}
req = build_arp(1, "aa:aa:aa:aa:aa:aa", "192.168.1.10",
"00:00:00:00:00:00", "192.168.1.50")
rep = build_arp(2, "bb:bb:bb:bb:bb:bb", "192.168.1.50",
"aa:aa:aa:aa:aa:aa", "192.168.1.10")
print("request:", parse_arp(req))
print("reply :", parse_arp(rep))
# request: {'op': 'request', 'sender': '192.168.1.10 / aa:aa:aa:aa:aa:aa',
# 'target': '192.168.1.50 / 00:00:00:00:00:00'}
# reply : {'op': 'reply', 'sender': '192.168.1.50 / bb:bb:bb:bb:bb:bb',
# 'target': '192.168.1.10 / aa:aa:aa:aa:aa:aa'}
def who_to_arp_for(src_ip, src_prefix, dst_ip, gateway):
"""The single most important decision a sending host makes."""
local_net = ipaddress.ip_network(f"{src_ip}/{src_prefix}", strict=False)
if ipaddress.ip_address(dst_ip) in local_net:
return dst_ip, "destination is LOCAL -> ARP for it directly"
return gateway, "destination is REMOTE -> ARP for the default gateway"
print()
for dst in ["192.168.1.50", "192.168.1.254", "10.0.0.5", "93.184.216.34"]:
target, why = who_to_arp_for("192.168.1.10", 24, dst, "192.168.1.1")
print(f"sending to {dst:<16} -> ARP for {target:<14} ({why})")
# sending to 192.168.1.50 -> ARP for 192.168.1.50 (destination is LOCAL -> ARP for it directly)
# sending to 10.0.0.5 -> ARP for 192.168.1.1 (destination is REMOTE -> ARP for the default gateway)
# sending to 93.184.216.34 -> ARP for 192.168.1.1 (destination is REMOTE -> ARP for the default gateway)
# Watching ARP happen.
$ sudo tcpdump -i eth0 -n arp
# 14:02:11.418 ARP, Request who-has 192.168.1.50 tell 192.168.1.10, length 28
# 14:02:11.419 ARP, Reply 192.168.1.50 is-at bb:bb:bb:bb:bb:bb, length 46
# ^ request is broadcast, reply is unicast, ~1 ms apart
# Confirming that off-subnet traffic resolves the GATEWAY, not the server:
$ ip neigh flush all && curl -s -o /dev/null https://example.com && ip neigh
# 192.168.1.1 dev eth0 lladdr 4c:ed:fb:11:22:33 REACHABLE
# ^ only the gateway was resolved. 93.184.216.34 appears NOWHERE in this table,
# because the host never needs the remote server's MAC address.
Key takeaways
- ARP maps a known IPv4 address to the MAC address needed to build a frame.
- The request is broadcast to
FF:FF:FF:FF:FF:FF; the reply is unicast, since the requester's MAC was inside the request. - ARP rides directly in Ethernet with EtherType
0x0806— it is not carried inside IP, which is why its layer placement is debated. - The sending host compares the destination against its subnet mask: local destinations are ARPed for directly, remote ones cause an ARP for the default gateway.
- Consequently a frame's destination MAC is the next hop's, while the IP header keeps the true endpoint — layer 2 addresses the hop, layer 3 the destination.
- A host never learns a remote server's MAC address and has no need to.
🧪 Practice
- A host
10.0.5.20/24with gateway10.0.5.1sends to10.0.5.99and then to172.16.8.4. State which IP it ARPs for in each case.- Explain why the ARP reply is unicast rather than broadcast, and what information makes that possible.
- Interview-style: A host's ARP table contains its gateway but never any Internet servers, no matter how many sites it visits. Why? (Hint: identify which addresses appear in the Ethernet header versus the IP header for an off-subnet packet.)
ARP Cache and Gratuitous ARP
Theory
Broadcasting a request before every packet would be absurd, so every host keeps an ARP cache: a table of recently resolved IP-to-MAC mappings. The cache is consulted first, and only a miss triggers a broadcast.
Entries expire, and the timeout is a deliberate trade-off. Too long and the host keeps using a stale mapping after a device is replaced or fails over; too short and ARP traffic rises. Linux uses an adaptive scheme with a base of about 60 seconds; Windows uses a randomised 15–45 seconds; Cisco routers traditionally default to four hours, which is why a router can keep sending to a decommissioned server's MAC long after everyone else has noticed.
Linux tracks entry states, which are genuinely useful when diagnosing:
| State | Meaning |
|---|---|
REACHABLE | Confirmed recently; usable |
STALE | Timed out but retained; will be revalidated on next use |
DELAY | Waiting briefly for upper-layer confirmation before probing |
PROBE | Actively re-sending ARP requests |
FAILED | No response; resolution failed |
PERMANENT | Manually configured static entry, never expires |
A neat efficiency: because an ARP request carries the sender's IP and MAC, every host that receives the broadcast can update its own cache for the sender — even hosts that never reply. One broadcast informs the whole segment.
Gratuitous ARP is an ARP message a host sends when nobody asked. It is formatted with the sender and target IP set to the same value — the sender's own address. It can be sent as a request (the common form) or a reply, and it serves three distinct purposes:
1. Duplicate address detection. On acquiring an address, a host gratuitously ARPs for it. Any reply means someone else already has it, and the host reports a conflict rather than causing an outage.
2. Cache updating after a MAC change. If a server's NIC is replaced, or a VM migrates to another host, the IP stays but the MAC changes. A gratuitous ARP tells every listener immediately instead of waiting for caches to expire.
3. Failover announcement. This is the operationally critical one. Protocols like VRRP, HSRP, and clustered services move a virtual IP between physical machines. When the standby takes over, it broadcasts gratuitous ARPs so every host and switch updates its mapping to the new MAC. Without this, traffic would continue to the dead machine until caches expired — potentially minutes.
Gratuitous ARP also updates switch MAC tables, since the frame's source address is learned normally. That matters as much as updating host caches.
The security consequence is severe and is the subject of a later topic: ARP has no authentication whatsoever. Any host may send a gratuitous ARP claiming any IP address, and receivers believe it.
Examples
Cache lookup flow
Application sends to 192.168.1.50
|
v
Check ARP cache
|
+-- HIT (REACHABLE) --> build frame immediately, send
|
+-- HIT (STALE) ------> send using it, but probe to revalidate
|
+-- MISS -------------> queue the packet
broadcast ARP request
on reply: cache it, send the queued packet
on timeout (3 tries): report host unreachable
Gratuitous ARP during a VRRP failover:
Before: VIP 192.168.1.1 -> aa:aa (router A, active)
every host caches 192.168.1.1 = aa:aa
Router A fails. Router B takes the VIP and broadcasts:
ARP request: who-has 192.168.1.1 tell 192.168.1.1
^^^^^^^^^^^ ^^^^^^^^^^^
sender IP == target IP -> GRATUITOUS
sender MAC = bb:bb
Every host updates: 192.168.1.1 -> bb:bb
Every switch relearns the VIP's MAC on router B's port.
Failover completes in milliseconds instead of waiting out cache timers.
import time
class ArpCache:
def __init__(self, base_timeout=60):
self.entries = {} # ip -> (mac, timestamp, state)
self.base_timeout = base_timeout
self.stats = {"hits": 0, "misses": 0, "broadcasts": 0}
def lookup(self, ip, now):
e = self.entries.get(ip)
if e is None:
self.stats["misses"] += 1
self.stats["broadcasts"] += 1
return None, "MISS -> broadcast ARP request"
mac, ts, state = e
age = now - ts
if state == "PERMANENT":
self.stats["hits"] += 1
return mac, "HIT (PERMANENT)"
if age > self.base_timeout * 2:
del self.entries[ip]
self.stats["misses"] += 1
self.stats["broadcasts"] += 1
return None, "EXPIRED -> broadcast ARP request"
if age > self.base_timeout:
self.entries[ip] = (mac, ts, "STALE")
self.stats["hits"] += 1
return mac, "HIT (STALE) -> use it, then revalidate"
self.stats["hits"] += 1
return mac, "HIT (REACHABLE)"
def learn(self, ip, mac, now, source="reply"):
old = self.entries.get(ip)
self.entries[ip] = (mac, now, "REACHABLE")
if old and old[0] != mac:
return f"UPDATED {ip}: {old[0]} -> {mac} (via {source})"
return f"learned {ip} = {mac} (via {source})"
def gratuitous(self, ip, mac, now):
"""Sender IP == target IP. Everyone updates, asked or not."""
return self.learn(ip, mac, now, source="gratuitous ARP")
cache = ArpCache(base_timeout=60)
t = 1000
print(cache.learn("192.168.1.1", "aa:aa:aa:aa:aa:aa", t))
print(cache.lookup("192.168.1.1", t + 10)[1])
print(cache.lookup("192.168.1.1", t + 90)[1])
print(cache.lookup("192.168.1.1", t + 200)[1])
# learned 192.168.1.1 = aa:aa:aa:aa:aa:aa (via reply)
# HIT (REACHABLE)
# HIT (STALE) -> use it, then revalidate
# EXPIRED -> broadcast ARP request
print("\n--- VRRP failover ---")
cache.learn("192.168.1.1", "aa:aa:aa:aa:aa:aa", t)
print("router A active:", cache.lookup("192.168.1.1", t + 5)[0])
print(cache.gratuitous("192.168.1.1", "bb:bb:bb:bb:bb:bb", t + 30))
print("router B active:", cache.lookup("192.168.1.1", t + 35)[0])
# router A active: aa:aa:aa:aa:aa:aa
# UPDATED 192.168.1.1: aa:aa:aa:aa:aa:aa -> bb:bb:bb:bb:bb:bb (via gratuitous ARP)
# router B active: bb:bb:bb:bb:bb:bb
# ^ no reboot, no timeout wait, no packet loss beyond the failover itself
# Why cache timeout choice matters:
print()
for device, timeout in [("Linux", 60), ("Windows", 30), ("Cisco router", 14400)]:
print(f"{device:<14} timeout {timeout:>6} s -> worst-case staleness after a "
f"silent MAC change: {timeout/60:>6.1f} min")
# Linux timeout 60 s -> worst-case staleness ...: 1.0 min
# Cisco router timeout 14400 s -> worst-case staleness ...: 240.0 min
# ^ four hours of blackholing if a device is replaced without a gratuitous ARP
# Inspecting and manipulating the cache.
$ ip neigh show
# 192.168.1.1 dev eth0 lladdr 4c:ed:fb:11:22:33 REACHABLE
# 192.168.1.50 dev eth0 lladdr bb:bb:bb:bb:bb:bb STALE
# 192.168.1.77 dev eth0 FAILED <- host did not answer
$ sudo ip neigh flush dev eth0 # force re-resolution of everything
$ sudo arping -U -I eth0 192.168.1.1 # send a gratuitous ARP (-U = update)
$ sudo ip neigh add 192.168.1.5 lladdr aa:bb:cc:dd:ee:ff dev eth0 nud permanent
# ^ a static entry: immune to spoofing, but must be maintained by hand
Key takeaways
- The ARP cache avoids broadcasting before every packet; only a miss triggers a request.
- Timeouts vary widely — roughly 60 s on Linux, 15–45 s on Windows, but four hours on many routers, which can prolong blackholing after a hardware change.
- Linux entry states (
REACHABLE,STALE,DELAY,PROBE,FAILED,PERMANENT) are directly useful for diagnosis. - Because a request carries the sender's IP and MAC, every host on the segment can update its cache from one broadcast.
- Gratuitous ARP has sender IP equal to target IP and serves duplicate address detection, MAC-change notification, and — most importantly — failover announcement for VRRP/HSRP virtual IPs.
- It updates switch MAC tables as well as host caches.
- ARP has no authentication: any host can claim any address, which is the basis of ARP spoofing.
🧪 Practice
- Explain what a gratuitous ARP looks like on the wire and how it differs structurally from an ordinary request.
- A server's NIC is replaced and some clients keep failing for hours while others recover in a minute. Explain the difference.
- Interview-style: A VRRP failover completes but clients take four hours to recover. What went wrong? (Hint: consider which device has the longest ARP timeout and what message should have reached it at failover time.)
Proxy ARP
Theory
ARP normally works only within a broadcast domain, because the request is a broadcast that routers do not forward. Proxy ARP deliberately breaks that rule: a router answers an ARP request for an IP address that is not its own, supplying its own MAC address so that traffic for that destination is sent to it, and it then forwards the traffic onward.
The router is effectively saying "I am not that host, but send it to me and I will see it gets there." The requesting host is entirely unaware anything unusual happened — it caches the router's MAC against the remote host's IP and proceeds normally.
The original motivation was hosts with a broken or absent notion of subnetting. Early systems configured with a classful /8 mask believed every address in 10.0.0.0/8 was on their local link, so they would ARP for hosts that were actually several routers away. Proxy ARP let such hosts work without reconfiguration — the router answered, and connectivity happened.
Legitimate modern uses remain, though they are narrow:
- Dial-up and VPN concentrators, where remote clients are assigned addresses from the LAN's subnet but are not physically on that segment. The concentrator proxies for them.
- Transparent firewalls inserted into a segment without renumbering.
- Mobile IP home agents proxying for a device that has roamed away.
The problems, however, are why Proxy ARP is disabled by default on most modern equipment:
- It hides topology. Hosts believe everything is local, so troubleshooting becomes confusing —
tracerouteand subnet reasoning stop reflecting reality. - It inflates ARP caches. Every remote host gets its own cache entry, all mapping to the same router MAC.
- It masks misconfiguration. A host with a wrong subnet mask works, so the error goes undetected until Proxy ARP is turned off somewhere and a mysterious outage follows.
- It is a security weakness. A malicious host can proxy-ARP for addresses it does not own — which is simply ARP spoofing with a respectable name.
- It can create forwarding loops when several routers proxy for the same range.
The correct modern practice is to configure hosts with accurate subnet masks and default gateways, so they ARP only for genuinely local addresses. Proxy ARP is a compatibility mechanism for situations you should be trying to eliminate.
A related but distinct mechanism is Local Proxy ARP, used with private VLANs: it makes a router answer ARP for hosts on the same subnet, forcing all traffic through the router so policy can be applied even between hosts that would otherwise talk directly.
Examples
Proxy ARP in action
Host A Router Host B
10.0.0.10/8 10.0.0.1 | 10.1.0.1 10.1.0.50/16
(wrongly believes the aa:aa |
whole /8 is local) |
A wants 10.1.0.50. With a /8 mask it thinks that is LOCAL, so:
A broadcasts: who-has 10.1.0.50 tell 10.0.0.10
B never hears it — it is on a different segment.
WITHOUT Proxy ARP: no reply, A concludes the host is unreachable.
WITH Proxy ARP: the router replies
"10.1.0.50 is-at aa:aa" <- the ROUTER's own MAC, not B's
A caches: 10.1.0.50 -> aa:aa
A sends frames to aa:aa; the router forwards them to B. It works.
A's ARP cache after talking to 200 remote hosts:
10.1.0.50 -> aa:aa
10.1.0.51 -> aa:aa
10.2.7.19 -> aa:aa 200 entries, ALL the same MAC.
... Compare with a correctly configured host:
one entry for the gateway.
import ipaddress
class Router:
def __init__(self, mac, interfaces, proxy_arp=False):
self.mac = mac
self.interfaces = {ipaddress.ip_network(n, strict=False): ip
for n, ip in interfaces.items()}
self.proxy_arp = proxy_arp
def has_route_to(self, ip):
addr = ipaddress.ip_address(ip)
return any(addr in net for net in self.interfaces)
def on_arp_request(self, target_ip, arriving_on):
addr = ipaddress.ip_address(target_ip)
own = [ip for net, ip in self.interfaces.items() if str(ip) == target_ip]
if own:
return f"REPLY (my own address) {target_ip} is-at {self.mac}"
if not self.proxy_arp:
return "SILENT — not my address, proxy ARP disabled"
# Proxy ARP: answer for someone else, if a route exists elsewhere.
local_net = ipaddress.ip_network(arriving_on, strict=False)
if addr in local_net:
return "SILENT — target is on the same segment; let it answer"
if self.has_route_to(target_ip):
return f"PROXY REPLY: {target_ip} is-at {self.mac} <- MY mac, not theirs"
return "SILENT — no route to target"
r = Router("aa:aa:aa:aa:aa:aa",
{"10.0.0.0/16": "10.0.0.1", "10.1.0.0/16": "10.1.0.1"})
print("--- proxy ARP DISABLED (modern default) ---")
for target in ("10.0.0.1", "10.0.0.99", "10.1.0.50"):
print(f" who-has {target:<12}: {r.on_arp_request(target, '10.0.0.0/16')}")
# who-has 10.0.0.1 : REPLY (my own address) 10.0.0.1 is-at aa:aa:aa:aa:aa:aa
# who-has 10.1.0.50 : SILENT — not my address, proxy ARP disabled
r.proxy_arp = True
print("\n--- proxy ARP ENABLED ---")
for target in ("10.0.0.99", "10.1.0.50", "192.168.5.1"):
print(f" who-has {target:<12}: {r.on_arp_request(target, '10.0.0.0/16')}")
# who-has 10.0.0.99 : SILENT — target is on the same segment; let it answer
# who-has 10.1.0.50 : PROXY REPLY: 10.1.0.50 is-at aa:aa:aa:aa:aa:aa <- MY mac, not theirs
# who-has 192.168.5.1 : SILENT — no route to target
# Cache bloat: the diagnostic fingerprint of proxy ARP.
def cache_size(remote_hosts, proxy_arp):
return remote_hosts + 1 if proxy_arp else 1 # +1 for the gateway itself
print()
for hosts in (10, 100, 1000):
print(f"talking to {hosts:>5} remote hosts: "
f"{cache_size(hosts, True):>5} cache entries with proxy ARP, "
f"{cache_size(hosts, False):>2} without")
# talking to 10 remote hosts: 11 cache entries with proxy ARP, 1 without
# talking to 1000 remote hosts: 1001 cache entries with proxy ARP, 1 without
# An ARP cache full of different IPs mapping to ONE MAC is the telltale sign.
# Checking and disabling proxy ARP.
$ cat /proc/sys/net/ipv4/conf/eth0/proxy_arp
# 0 <- disabled, the correct modern default
$ sudo sysctl -w net.ipv4.conf.eth0.proxy_arp=0
# On Cisco, proxy ARP is historically ON by default per interface:
# interface GigabitEthernet0/0
# no ip proxy-arp <- disable it explicitly
# The fingerprint: many different IPs, one MAC address.
$ ip neigh show | awk '{print $5}' | sort | uniq -c | sort -rn
# 247 aa:aa:aa:aa:aa:aa <- 247 distinct IPs behind one MAC
# 1 4c:ed:fb:11:22:33
# -> either proxy ARP is active, or something is spoofing at scale
Key takeaways
- Proxy ARP has a router answer ARP requests for addresses it does not own, supplying its own MAC so traffic is sent to it for forwarding.
- Its original purpose was supporting hosts with incorrect or absent subnet configuration.
- Legitimate modern uses are narrow: VPN and dial-up concentrators, transparent firewalls, and Mobile IP home agents.
- It hides topology, bloats ARP caches, masks host misconfiguration, and can create forwarding loops.
- It is effectively sanctioned ARP spoofing, so it is disabled by default on modern equipment.
- The diagnostic fingerprint is an ARP cache with many distinct IP addresses all mapping to a single MAC.
- The correct alternative is accurate subnet masks and default gateways on hosts.
🧪 Practice
- Explain how Proxy ARP allows a host with a
/8mask to reach a host three routers away, tracing the ARP exchange.- Describe two ways Proxy ARP makes troubleshooting harder, with a concrete symptom for each.
- Interview-style: An ARP cache shows 200 different IP addresses all resolving to the same MAC. Give two possible explanations and say how you would distinguish them. (Hint: one is a configured router behaviour, the other is an attack — consider whether that MAC belongs to the legitimate gateway.)
IPv6 Neighbor Discovery Protocol
Theory
IPv6 has no ARP. Its replacement, NDP (Neighbor Discovery Protocol, RFC 4861), does everything ARP did and considerably more — and it fixes ARP's architectural awkwardness by running inside ICMPv6, which runs inside IP. NDP is unambiguously a layer 3 protocol, unlike ARP.
NDP uses five ICMPv6 message types:
| Type | Message | Purpose |
|---|---|---|
| 133 | Router Solicitation (RS) | "Are there any routers here?" |
| 134 | Router Advertisement (RA) | Routers announce themselves, the prefix, and configuration flags |
| 135 | Neighbor Solicitation (NS) | ARP request's equivalent: resolve an address |
| 136 | Neighbor Advertisement (NA) | ARP reply's equivalent |
| 137 | Redirect | "There is a better first hop for that destination" |
The single most important improvement is that NDP does not broadcast — IPv6 has no broadcast address at all. Instead it uses the solicited-node multicast address: ff02::1:ff followed by the last 24 bits of the target's address. A host joins the solicited-node group corresponding to each of its own addresses, so a neighbor solicitation reaches only the few hosts whose addresses share those 24 bits, rather than every machine on the segment.
The improvement is real: on a segment of 1000 hosts, an ARP request interrupts all 1000, while a neighbor solicitation typically interrupts one. Every other host's NIC filters it out in hardware, with no CPU cost at all.
NDP absorbs several functions that IPv4 spread across separate protocols:
- Address resolution (ARP's job) via NS/NA.
- Router discovery (IPv4 needs DHCP or static config) via RS/RA.
- Prefix discovery and SLAAC, letting a host configure its own global address from the RA's prefix plus an interface identifier — stateless address autoconfiguration, with no DHCP server required.
- DAD (Duplicate Address Detection), where a host sends an NS for its own tentative address before using it; any reply means the address is taken.
- NUD (Neighbor Unreachability Detection), actively tracking whether a neighbour is still reachable — something ARP never did properly.
- Redirect, informing a host of a better first hop.
The RA flags determine how hosts configure themselves: the M (Managed) flag directs hosts to use DHCPv6 for addresses, and the O (Other) flag directs them to use DHCPv6 only for other information such as DNS servers.
NDP inherits ARP's core weakness — it is unauthenticated by default, so NDP spoofing and rogue RA attacks mirror ARP spoofing. SEND (SEcure Neighbor Discovery, RFC 3971) adds cryptographic protection but is barely deployed; in practice the defence is RA Guard and ND Inspection on switches, the direct analogues of the IPv4 protections in the next topic.
Examples
Solicited-node multicast: why NDP interrupts one host instead of a thousand
Target address: 2001:db8::a1b2:c3d4:e5f6:7890
^^^^^^^^ last 24 bits: f6:78:90
Solicited-node group: ff02::1:fff6:7890
Ethernet multicast MAC: 33:33:ff:f6:78:90
^^^^^ IPv6 multicast prefix
ARP (IPv4): broadcast -> ALL 1000 hosts interrupt their CPU to inspect
NDP (IPv6): multicast -> NICs filter in hardware; typically 1 host wakes up
Address resolution exchange:
Host A --NS--> ff02::1:fff6:7890 "who has 2001:db8::...:7890?"
(carries A's own link-layer address)
Host B --NA--> Host A (unicast) "that is me, at bb:bb:bb:bb:bb:bb"
SLAAC — a host configures itself with no DHCP server:
Host --RS--> ff02::2 (all-routers)
Router --RA--> ff02::1 (all-nodes)
prefix 2001:db8:1::/64, flags M=0 O=0, lifetime 1800
Host builds: 2001:db8:1:: + its own interface identifier
Host runs DAD on the result, then starts using it.
No DHCP server was involved at any point.
import ipaddress
def solicited_node(ipv6_addr: str) -> tuple:
"""ff02::1:ff + the low 24 bits of the target address."""
addr = ipaddress.IPv6Address(ipv6_addr)
low24 = int(addr) & 0xFFFFFF
group = ipaddress.IPv6Address(int(ipaddress.IPv6Address("ff02::1:ff00:0")) | low24)
mac = (f"33:33:ff:{(low24 >> 16) & 0xFF:02x}:"
f"{(low24 >> 8) & 0xFF:02x}:{low24 & 0xFF:02x}")
return str(group), mac
for addr in ["2001:db8::a1b2:c3d4:e5f6:7890",
"2001:db8::1",
"fe80::20c:29ff:fe1f:2c3b"]:
grp, mac = solicited_node(addr)
print(f"{addr:<32} -> {grp:<24} MAC {mac}")
# 2001:db8::a1b2:c3d4:e5f6:7890 -> ff02::1:fff6:7890 MAC 33:33:ff:f6:78:90
# 2001:db8::1 -> ff02::1:ff00:1 MAC 33:33:ff:00:00:01
# fe80::20c:29ff:fe1f:2c3b -> ff02::1:ff1f:2c3b MAC 33:33:ff:1f:2c:3b
def hosts_interrupted(total_hosts, protocol):
if protocol == "ARP":
return total_hosts # broadcast: everyone
# Solicited-node: collision only if the low 24 bits match.
expected = 1 + (total_hosts - 1) / (2 ** 24)
return expected
print()
for n in (50, 1000, 10000):
a, n6 = hosts_interrupted(n, "ARP"), hosts_interrupted(n, "NDP")
print(f"{n:>6} hosts: ARP interrupts {a:>6}, NDP interrupts {n6:>8.4f} "
f"({a/n6:>9,.0f}x fewer)")
# 50 hosts: ARP interrupts 50, NDP interrupts 1.0000 ( 50x fewer)
# 10000 hosts: ARP interrupts 10000, NDP interrupts 1.0006 ( 9994x fewer)
NDP_TYPES = {133: ("Router Solicitation", "host asks: any routers here?"),
134: ("Router Advertisement", "router announces prefix + flags"),
135: ("Neighbor Solicitation", "resolve address / DAD / NUD"),
136: ("Neighbor Advertisement", "here is my link-layer address"),
137: ("Redirect", "use a better first hop for that destination")}
print()
for t, (name, purpose) in NDP_TYPES.items():
print(f"ICMPv6 type {t}: {name:<24} {purpose}")
def slaac_flags(m, o):
if m: return "DHCPv6 for addresses AND other config (stateful)"
if o: return "SLAAC for addresses, DHCPv6 for DNS etc (stateless DHCPv6)"
return "pure SLAAC — no DHCP server needed at all"
print()
for m, o in [(0,0), (0,1), (1,0)]:
print(f"RA flags M={m} O={o}: {slaac_flags(m, o)}")
# NDP on a live system.
$ ip -6 neigh show
# fe80::4ced:fbff:fe11:2233 dev eth0 lladdr 4c:ed:fb:11:22:33 router REACHABLE
# ^^^^^^ NDP records
# that this IS a router
$ sudo tcpdump -i eth0 -n icmp6 and 'ip6[40] >= 133 and ip6[40] <= 137'
# IP6 fe80::a1b2 > ff02::1:fff6:7890: ICMP6, neighbor solicitation,
# ^^^^^^^^^^^^^^^^^^ solicited-node multicast, NOT broadcast
# who has 2001:db8::a1b2:c3d4:e5f6:7890, length 32
# IP6 2001:db8::...:7890 > fe80::a1b2: ICMP6, neighbor advertisement,
# tgt is 2001:db8::a1b2:c3d4:e5f6:7890, length 32
# Protecting against rogue router advertisements (the IPv6 analogue of
# rogue DHCP): RA Guard on access ports.
# interface GigabitEthernet1/0/5
# ipv6 nd raguard attach-policy HOST_PORTS <- drop RAs from a host port
Key takeaways
- IPv6 replaces ARP with NDP, carried inside ICMPv6 — so unlike ARP, it is unambiguously a layer 3 protocol.
- Five message types: RS (133), RA (134), NS (135), NA (136), and Redirect (137).
- NDP uses solicited-node multicast (
ff02::1:ff+ the target's low 24 bits) instead of broadcast, so typically one host is interrupted instead of every host on the segment. - NDP absorbs functions IPv4 spread across protocols: address resolution, router discovery, prefix discovery and SLAAC, DAD, NUD, and redirects.
- SLAAC lets a host build its own global address from the RA's prefix with no DHCP server; the RA's M and O flags control whether DHCPv6 is used.
- NDP is unauthenticated by default, so rogue RA and NDP spoofing attacks mirror ARP spoofing; RA Guard and ND Inspection are the practical defences.
🧪 Practice
- Compute the solicited-node multicast address and Ethernet MAC for
2001:db8:abcd::9f8e:7d6c.- Explain how SLAAC lets a host obtain a routable global address with no DHCP server, listing the messages exchanged.
- Interview-style: Why is NDP's use of multicast rather than broadcast a meaningful improvement on a large segment? (Hint: consider what every host's NIC and CPU must do with a broadcast frame versus a multicast frame it is not subscribed to.)
ARP Spoofing Fundamentals
Theory
ARP was designed in 1982 for a cooperative research network, and it contains no authentication of any kind. A host receiving an ARP reply has no way to verify that the sender actually owns the claimed IP address. Worse, most implementations accept unsolicited replies and use them to update the cache — so an attacker need not even wait to be asked.
ARP spoofing (also called ARP cache poisoning) exploits this directly. The attacker broadcasts forged ARP replies claiming that some IP address — typically the default gateway — is at the attacker's MAC address. Every host that believes it now sends its off-subnet traffic to the attacker.
To become a full man-in-the-middle, the attacker poisons both directions:
- Tell the victim that the gateway's IP is at the attacker's MAC.
- Tell the gateway that the victim's IP is at the attacker's MAC.
- Enable IP forwarding so traffic continues to flow, and both parties observe nothing wrong.
The attacker now sits transparently in the path and can read, record, modify, or drop traffic. Note that this requires the attacker to be inside the same broadcast domain — which is precisely why broadcast domain size is a security concern, as the domains topic noted, and why VLAN segmentation has security value beyond performance.
What an attacker gains depends heavily on what protects the traffic above:
| Traffic | Exposure under ARP spoofing |
|---|---|
| Plaintext HTTP, FTP, Telnet | Fully readable and modifiable |
| DNS (unencrypted) | Answers can be forged, redirecting the victim anywhere |
| HTTPS/TLS | Encrypted; interception triggers a certificate warning |
| SSH | Protected, with a host-key-changed warning |
| Traffic metadata | Always visible: who talks to whom, when, how much |
This is exactly the end-to-end argument applied to security: link-layer trust cannot be established, so protection must come from the endpoints. TLS is what actually defends the traffic, and certificate validation is the mechanism — which is why training users to click through certificate warnings is genuinely dangerous.
The layered defences, in order of effectiveness:
- Dynamic ARP Inspection (DAI) — the primary control. The switch validates every ARP packet against a trusted DHCP snooping binding table of legitimate IP-to-MAC-to-port mappings, and drops any that do not match. This stops spoofing at the switch port, before it reaches any victim.
- DHCP snooping — builds the binding table DAI depends on, and independently blocks rogue DHCP servers.
- Port security — limits MAC addresses per port, constraining related attacks.
- Static ARP entries — immune to poisoning, but unmanageable at scale; reserved for critical servers.
- Network segmentation — smaller broadcast domains mean fewer reachable victims.
- Encryption everywhere — TLS, SSH, VPNs. This does not prevent the attack but removes most of its value.
- Detection tools —
arpwatchand similar alert on IP-to-MAC mapping changes.
The IPv6 equivalents are NDP spoofing and rogue RA attacks, countered by RA Guard and ND Inspection — the same problem and the same shape of solution.
Examples
Man-in-the-middle via bidirectional poisoning
NORMAL:
[Victim 192.168.1.10] <-----------> [Gateway 192.168.1.1]
cache: .1 = gw_mac cache: .10 = victim_mac
ATTACK — the attacker sends two streams of forged replies:
to victim: "192.168.1.1 is-at attacker_mac"
to gateway: "192.168.1.10 is-at attacker_mac"
RESULT:
[Victim] ---> [ATTACKER] ---> [Gateway] ---> Internet
<--- <---
victim cache: .1 = attacker_mac <- poisoned
gateway cache: .10 = attacker_mac <- poisoned
attacker forwards traffic, so BOTH SIDES SEE NORMAL CONNECTIVITY.
Detection fingerprint — two IPs sharing one MAC:
$ ip neigh
192.168.1.1 lladdr 00:de:ad:be:ef:00 REACHABLE
192.168.1.99 lladdr 00:de:ad:be:ef:00 REACHABLE
^^^^^^^^^^^^^^^^^ the gateway and some host,
same MAC = poisoning
How Dynamic ARP Inspection stops it:
DHCP snooping builds the trusted binding table:
192.168.1.10 -> aa:aa:aa:aa:aa:aa on Gi1/0/5
Attacker on Gi1/0/9 sends "192.168.1.1 is-at attacker_mac"
DAI checks: does Gi1/0/9 have a binding for 192.168.1.1? NO
-> DROP the packet, log, optionally err-disable the port.
The forged ARP never reaches any victim.
class Host:
def __init__(self, name, ip, mac):
self.name, self.ip, self.mac = name, ip, mac
self.arp_cache = {}
def receive_arp_reply(self, claimed_ip, claimed_mac, validate=False,
trusted_bindings=None, arriving_port=None):
if validate:
# Dynamic ARP Inspection: check against the DHCP snooping table.
expected = trusted_bindings.get(claimed_ip)
if expected != (claimed_mac, arriving_port):
return f"DAI: DROPPED forged reply ({claimed_ip} -> {claimed_mac})"
old = self.arp_cache.get(claimed_ip)
self.arp_cache[claimed_ip] = claimed_mac
if old and old != claimed_mac:
return f"cache OVERWRITTEN: {claimed_ip} {old} -> {claimed_mac}"
return f"cached {claimed_ip} = {claimed_mac}"
def detect_anomaly(self):
"""Two IPs sharing one MAC is the classic spoofing fingerprint."""
by_mac = {}
for ip, mac in self.arp_cache.items():
by_mac.setdefault(mac, []).append(ip)
return {m: ips for m, ips in by_mac.items() if len(ips) > 1}
victim = Host("victim", "192.168.1.10", "aa:aa:aa:aa:aa:aa")
GATEWAY_MAC, ATTACKER_MAC = "4c:ed:fb:11:22:33", "00:de:ad:be:ef:00"
print("--- WITHOUT protection ---")
print(victim.receive_arp_reply("192.168.1.1", GATEWAY_MAC))
print(victim.receive_arp_reply("192.168.1.99", ATTACKER_MAC))
print(victim.receive_arp_reply("192.168.1.1", ATTACKER_MAC)) # the attack
print("anomaly detected:", victim.detect_anomaly())
# cached 192.168.1.1 = 4c:ed:fb:11:22:33
# cached 192.168.1.99 = 00:de:ad:be:ef:00
# cache OVERWRITTEN: 192.168.1.1 4c:ed:fb:11:22:33 -> 00:de:ad:be:ef:00
# anomaly detected: {'00:de:ad:be:ef:00': ['192.168.1.99', '192.168.1.1']}
print("\n--- WITH Dynamic ARP Inspection ---")
bindings = {"192.168.1.1": (GATEWAY_MAC, "Gi1/0/1"), # from DHCP snooping
"192.168.1.99": (ATTACKER_MAC, "Gi1/0/9")}
v2 = Host("victim", "192.168.1.10", "aa:aa:aa:aa:aa:aa")
print(v2.receive_arp_reply("192.168.1.1", GATEWAY_MAC, True, bindings, "Gi1/0/1"))
print(v2.receive_arp_reply("192.168.1.1", ATTACKER_MAC, True, bindings, "Gi1/0/9"))
print("cache:", v2.arp_cache)
# cached 192.168.1.1 = 4c:ed:fb:11:22:33
# DAI: DROPPED forged reply (192.168.1.1 -> 00:de:ad:be:ef:00)
# cache: {'192.168.1.1': '4c:ed:fb:11:22:33'} <- attack never landed
# What the attacker actually gains, by protocol:
print()
EXPOSURE = {
"HTTP": ("full content + modification", "none"),
"FTP/Telnet":("credentials in cleartext", "none"),
"DNS": ("answers forgeable", "DNSSEC / DoH / DoT"),
"HTTPS/TLS": ("metadata only", "certificate validation"),
"SSH": ("metadata only", "host key verification"),
}
print(f"{'protocol':<12}{'attacker gains':<32}protected by")
for proto, (gain, prot) in EXPOSURE.items():
print(f"{proto:<12}{gain:<32}{prot}")
# HTTPS/TLS metadata only certificate validation
# ^ the end-to-end argument: link-layer trust is impossible,
# so the endpoints must protect themselves.
# Detection: watch for IP-to-MAC mapping changes.
$ sudo arpwatch -i eth0
# arpwatch: flip flop 192.168.1.1 00:de:ad:be:ef:00 (4c:ed:fb:11:22:33)
# ^^^^^^^^^ the gateway's MAC changed — investigate immediately
$ ip neigh | awk '{print $5}' | sort | uniq -d
# 00:de:ad:be:ef:00 <- one MAC claiming multiple IPs
# The primary defence, configured on the switch:
# ip dhcp snooping <- builds the trusted binding table
# ip dhcp snooping vlan 10,20
# interface GigabitEthernet1/0/24
# ip dhcp snooping trust <- the uplink toward the real DHCP server
#
# ip arp inspection vlan 10,20 <- validate ARP against those bindings
# interface GigabitEthernet1/0/24
# ip arp inspection trust
#
$ show ip arp inspection statistics vlan 10
# Vlan Forwarded Dropped DHCP Drops ACL Drops
# 10 48291 147 147 0
# ^^^ 147 forged ARP packets dropped at the port
Key takeaways
- ARP has no authentication, and most implementations accept unsolicited replies — so any host can claim any IP address.
- ARP spoofing poisons caches by forging replies, typically claiming the default gateway's IP.
- Poisoning both the victim and the gateway, with IP forwarding enabled, creates a transparent man-in-the-middle that neither side detects.
- The attacker must be inside the same broadcast domain, which is why segmentation has security value.
- TLS and SSH still protect content; interception produces certificate or host-key warnings, which is why those warnings must never be dismissed casually.
- Dynamic ARP Inspection backed by DHCP snooping is the primary defence, validating every ARP packet against a trusted binding table at the switch port.
- Supporting defences: port security, static entries for critical hosts, segmentation, ubiquitous encryption, and
arpwatch-style detection. - IPv6's equivalents are NDP spoofing and rogue RAs, countered by RA Guard and ND Inspection.
🧪 Practice
- Describe the exact sequence of forged messages needed to place an attacker between a victim and its gateway, and state what must also be enabled on the attacker's machine.
- Explain why HTTPS limits the damage of ARP spoofing but does not prevent the attack, and state what the attacker can still learn.
- Interview-style: Explain how Dynamic ARP Inspection stops ARP spoofing, and why it depends on DHCP snooping. (Hint: consider where the switch gets its notion of which IP legitimately belongs on which port.)
<a id="5-the-network-layer-and-ip-addressing"></a>