Visual walkthrough — Routing — forwarding table, routing table

We are deep-diving the central mechanic of the parent note: the forwarding table and Longest Prefix Match (LPM).

---

Step 1 — An IP address is just 32 light switches

WHAT. An IPv4 address like 10.20.30.40 is written as four numbers 0–255 joined by dots. But the router does not see decimals — it sees 32 bits, a row of 32 tiny switches, each either on (1) or off (0).

WHY. Each of the four decimal chunks is one byte = 8 switches. Eight switches can count from 0 (all off) to 255 (all on). So 10 = 00001010, 20 = 00010100, and so on. We switch to bits because matching — the whole job of forwarding — happens bit by bit, not decimal by decimal.

PICTURE. Look at the figure: the top strip is the address 10.20.30.40 spelled out as 32 switches, grouped in four bytes. The magenta bits are the ones that are on.

---

Step 2 — A prefix says "only the first L switches matter"

WHAT. A prefix is written P/L, e.g. 10.20.0.0/16. The number after the slash, $L$, is the prefix length: it means "to belong to this network, an address must agree with $P$ on its first $L$ bits — the rest can be anything."

WHY. A network is a group of addresses. Instead of listing every member, we fix the leading bits (the network part) and let the trailing bits (the host part) roam free. 10.20.0.0/16 fixes the first 16 bits (10.20) and frees the last 16 — that is a group of $2^{16}=65536$ addresses.

PICTURE. The figure draws a vertical violet wall at position $L$. Left of the wall = frozen network bits (must match). Right of the wall = free host bits (don't care).

---

Step 3 — The mask is a wall made of 1s and 0s

WHAT. To check a match we need a tool that erases the host bits and keeps only the network bits. That tool is the subnet mask $M$: exactly $L$ ones, then $32-L$ zeros.

$M=\underset{L\text{ ones (network)}}{\underbrace{11\dots 1}}\underset{32-L\text{ zeros (host)}}{\underbrace{00\dots 0}}$

Here every $1$ marks a bit we care about, and every $0$ marks a bit we throw away. For /16 that is 11111111.11111111.00000000.00000000 = 255.255.0.0.

WHY this tool and not another? We need a single operation that can simultaneously keep some bits and discard others. The bitwise AND does exactly that, and the mask is the pattern that tells AND which bits to keep — see the next step. We build the mask from $L$ because $L$ is the definition of how many bits are frozen.

PICTURE. The figure stacks three masks (/8, /16, /24). Notice the orange "1-wall" grows to the right as $L$ grows — a longer prefix is a taller wall of ones.

---

Step 4 — AND erases the host bits

WHAT. The bitwise AND ($\wedge$) compares two bits and outputs $1$ only if both are $1$. Otherwise it outputs $0$.

$0\wedge 0=0,0\wedge 1=0,1\wedge 0=0,1\wedge 1=1$

WHY AND? Look at what happens when we AND an address bit with a mask bit:

• Mask bit $=1$ (a keep bit): $x\wedge 1=x$ — the address bit survives unchanged.
• Mask bit $=0$ (a throw-away bit): $x\wedge 0=0$ — the address bit is forced to zero.

So $D\wedge M$ passes the network bits through untouched and flattens all host bits to $0$. That is precisely "erase the host part, keep the network part." No other basic operation does this cleanly, which is why forwarding hardware uses AND.

PICTURE. Watch the address 10.20.30.40 meet the /16 mask. The first 16 bits pour straight through (magenta stays magenta); the last 16 are flattened to grey zeros. The result is 10.20.0.0.

---

Step 5 — Try it: does 10.20.30.40 fall in 10.20.0.0/16?

WHAT. Apply Step 4 concretely.

WHY. This is the atomic operation the router repeats for every prefix in the table. Master it once here.

PICTURE / computation. With $M=$ 255.255.0.0 (/16):

$D\wedge M=\underset{\text{kept}}{\underbrace{10.20}}.\underset{\text{erased}}{\underbrace{0.0}}=\text{10.20.0.0}$ $P\wedge M=\text{10.20.0.0}\wedge \text{255.255.0.0}=\text{10.20.0.0}$

Both sides equal 10.20.0.0 → MATCH. Each term: $D=$ 10.20.30.40 (the packet), $M=$ mask that keeps 16 bits, $P=$ 10.20.0.0 (the network). The figure shows the two erased results landing on the same value — a green "equals" bridge.

---

Step 6 — Many prefixes match at once — now which one?

WHAT. In a real table several prefixes overlap. Our packet 10.20.30.40 matches all three of:

Prefix	$L$	Does 10.20.30.40 match?	Out
0.0.0.0/0	0	yes (everything matches $L=0$)	eth0
10.0.0.0/8	8	yes (top 8 bits 10)	eth1
10.20.0.0/16	16	yes (top 16 bits 10.20)	eth2

WHY a tie-break is needed. Three answers is one too many — a packet leaves by exactly one door. We must choose. The rule is Longest Prefix Match: pick the matching prefix with the largest $L$.

WHY longest? A larger $L$ freezes more bits, so it describes a smaller, more precise region of address space (fewer host bits). The most specific route is the most trustworthy statement about where the destination actually is — it was learned by someone who knows that exact neighbourhood. So $L=16$ (eth2) wins over $L=8$ and $L=0$.

PICTURE. Three nested boxes: /0 is the whole address space, /8 a smaller box inside it, /16 the smallest, tightest box around our dot. The dot sits inside all three; LPM tucks it into the innermost box → eth2.

---

Step 7 — The edge cases you must never trip on

WHAT. Four boundary situations that break naive intuition. Each gets its own panel in the figure.

(a) The default route 0.0.0.0/0 ($L=0$). Zero frozen bits means the mask is all zeros, so $D\wedge M=0$ and $P\wedge M=0$ for every $D$. It always matches — but because $L=0$ is the smallest length, LPM uses it only when nothing more specific matches. It is the fallback, not the favourite. See Default Gateway and 0.0.0.0/0.

(b) The half-byte split /25. Mask 255.255.255.128: the last byte's top bit is frozen. For 192.168.5.200, the last byte 200 = 11001000 has its top bit $=1$, so it falls in the 128–255 half → matches 192.168.5.128/25, not 192.168.5.0/25.

(c) A host route /32. All 32 bits frozen — the "network" is a single address. It is the longest possible prefix, so if it matches, it always wins.

(d) No match at all. If not even 0.0.0.0/0 is present and nothing matches, the router has no door to use → the packet is dropped (and often an ICMP "unreachable" is sent). This is why most tables carry a default route.

PICTURE. Four mini-panels, one per case, each showing the mask wall and the resulting match/no-match.

---

The one-picture summary

The whole pipeline on one canvas: the packet's address enters, gets AND-ed against each prefix's mask, the matches are collected, and the tallest wall (largest $L$) wins the packet's outgoing door.

Recall Feynman: the whole walkthrough in plain words

Picture 32 light switches — that's the address. A network says "I only care about the first few switches; freeze those, ignore the rest." To test membership we lay a mask over the switches — ones where we care, zeros where we don't — and we AND them: caring bits pass through, don't-care bits get squashed to zero. If the squashed address equals the network's own squashed value, the packet belongs. Usually several networks all claim the packet — a big loose one and a small tight one nested inside it. We always trust the tightest one, the one that froze the most switches, because it knows the neighbourhood best. That is Longest Prefix Match. Special cases: /0 freezes nothing and always matches (the fallback), /32 freezes everything (a single-host bullseye), and if nothing matches, the packet is dropped.

---

Related: IP Addressing and Subnetting · TCAM and Line-rate Forwarding · Control Plane vs Data Plane · OSPF and Link-State Routing · Distance Vector — RIP · ARP — Address Resolution Protocol