Routing — forwarding table, routing table: Exercises

Before we start, one picture nails down every word we lean on.

Figure — Routing — forwarding table, routing table

Recall Reminder of the two rules we test all page

Matching rule: a destination address $D$ matches a prefix $P / L$ when the top $L$ bits agree. In symbols, with mask $M = L 1 \dots 1 32 - L 0 \dots 0$ , $(D \land M) = (P \land M) .$ Here $\land$ means bitwise AND (compare bit-by-bit; $1 \land 1 = 1$ , everything else $0$ ). ANDing with $M$ erases the host bits and keeps only the network bits. Selection rule: among ALL matching prefixes, pick the one with the ==largest $L$ — the longest prefix match (LPM)==. Table order does not matter.

Level 1 — Recognition

Exercise 1.1 (L1)

Which of these two lives in the data plane and is consulted for every packet: the routing table, or the forwarding table (FIB)?

Recall Solution 1.1

The forwarding table (FIB) lives in the data plane and is consulted per packet. Why: the routing table is the "planning book" (control plane), rebuilt by protocols when topology changes — far too slow to consult per packet. The router bakes the best paths into the lean FIB so hardware can look them up at line rate. See Control Plane vs Data Plane.

Exercise 1.2 (L1)

An address that matches 0.0.0.0/0 — how many leading bits did it have to agree on?

Recall Solution 1.2

Zero bits. Prefix length $L = 0$ means the mask is all zeros, so $(D \land M) = (P \land M) = 0$ for any $D$ . That is why 0.0.0.0/0 matches every address, yet (being the shortest) wins only when nothing more specific matches. See Default Gateway and 0.0.0.0/0.

Exercise 1.3 (L1)

True or false: "A /25 network is bigger than a /24 network because 25 > 24."

Recall Solution 1.3

False. More prefix bits = fewer host bits = a smaller network. /24 leaves $32 - 24 = 8$ host bits $\Rightarrow 2^{8} = 256$ addresses. /25 leaves $32 - 25 = 7$ host bits $\Rightarrow 2^{7} = 128$ addresses. So /24 (256) is bigger than /25 (128).

Level 2 — Application

Exercise 2.1 (L2)

Write the subnet mask (dotted-decimal) for /20.

Recall Solution 2.1

/20 = 20 ones then 12 zeros: $11111111.11111111.11110000.00000000$ Byte by byte: 11111111=255, 11111111=255, 11110000= $128 + 64 + 32 + 16 = 240$ , 00000000=0. Answer: 255.255.240.0. The third byte is the interesting one — only its top 4 bits are network bits, and $2^{7} + 2^{6} + 2^{5} + 2^{4} = 240$ .

Exercise 2.2 (L2)

Does 172.16.5.10 match the prefix 172.16.0.0/16? Show the AND.

Recall Solution 2.2

Mask for /16 = 255.255.0.0. AND erases the last two bytes: $172.16.5.10 \land 255.255.0.0 = 172.16.0.0.$ That equals the prefix 172.16.0.0, so yes, it matches. Why the AND: the mask keeps the top 16 bits (172.16) and zeros the host part (5.10). If what's left equals $P$ , the address lives in that network.

Exercise 2.3 (L2)

Basic LPM. Forwarding table:

Prefix	Out interface
`0.0.0.0/0`	eth0
`172.16.0.0/12`	eth1
`172.16.0.0/16`	eth2

Packet to 172.16.200.9. Which interface?

Recall Solution 2.3

0.0.0.0/0 matches (length 0) → candidate.
172.16.0.0/12: mask 255.240.0.0. $172.16.200.9 \land 255.240.0.0 = 172.16.0.0$ ? The second byte 16 = 00010000; top 4 bits 0001 AND 1111 gives 0001 = 16. So the result is 172.16.0.0 ✓ (length 12).
172.16.0.0/16: top 16 bits 172.16 match ✓ (length 16). Lengths $0, 12, 16$ . Longest = 16 → eth2.

Level 3 — Analysis

Exercise 3.1 (L3) — the split-at-128 case

Table: 192.168.10.0/24 → A, 192.168.10.128/25 → B. Route each packet: (a) 192.168.10.100, (b) 192.168.10.200.

Recall Solution 3.1

A /25 splits the last byte at 128: the top bit of that byte decides which half. Look at the last octet in binary. (a) 192.168.10.100: $100 = 01100100$ — top bit is 0 ⇒ lower half (0–127).

/24 matches ✓ (length 24).
/25: mask last byte = 10000000 = 128. $100 \land 128 = 0 \neq = 128$ ⇒ does not match .128.
Only /24 matches → interface A. (b) 192.168.10.200: $200 = 11001000$ — top bit is 1 ⇒ upper half (128–255).
/24 matches ✓ (24).
/25: $200 \land 128 = 128$ = the prefix's last byte ✓ (length 25).
Lengths 24, 25 → longest = 25 → interface B.

Exercise 3.2 (L3) — why two tables, in your own words

A friend says: "Just make the routing table fast and delete the forwarding table — one book is simpler." Give the two-part reason this is wrong.

Recall Solution 3.2

Correctness comes from the routing table; speed comes from the forwarding table — you need both.

Richness/slowness: the routing table (RIB) holds many candidate routes per prefix, metrics, administrative distances, and protocol info, and it is rewritten whenever OSPF and Link-State Routing or Distance Vector — RIP converge. Searching all that per packet is too slow.
Line-rate lookup: the FIB is a distilled one-entry-per-prefix table placed in fast hardware (TCAM and Line-rate Forwarding) so millions of packets/second get an interface in one lookup. The router "thinks once" (control plane), then "ships fast" (data plane). See Control Plane vs Data Plane.

Exercise 3.3 (L3) — administrative distance tie-break

OSPF offers 10.1.0.0/16 via next-hop A with cost 20; RIP offers the same 10.1.0.0/16 via next-hop B with cost 5. OSPF's administrative distance is 110, RIP's is 120. Which route is installed into the FIB, and why is the smaller cost (5) ignored?

Recall Solution 3.3

The OSPF route (next-hop A) is installed. Why: administrative distance is compared first, and it ranks how much you trust the protocol, lower = more trusted. OSPF (110) beats RIP (120), so the router never even reaches the metric comparison. Metric (cost) only breaks ties within the same protocol. RIP's cost 5 is on a different, less-trusted yardstick — you cannot compare a RIP hop-count to an OSPF cost. So exactly one entry, 10.1.0.0/16 → A, is pushed to the FIB.

Level 4 — Synthesis

Exercise 4.1 (L4) — build a FIB

You must forward for these directly-known facts. Directly connected: eth0 on 10.0.0.0/8; a learned route 10.5.0.0/16 via next-hop 10.0.0.9; a learned route 10.5.5.0/24 via next-hop 10.0.0.9; and a gateway of last resort 0.0.0.0/0 via 10.0.0.1. All next-hops resolve out eth0. Write the FIB (prefix → out-interface), then route 10.5.5.77 and 10.5.9.4.

Recall Solution 4.1

Resolved FIB (every next-hop resolves to eth0, so we bake in the interface):

Prefix	Next-hop	Out interface
`0.0.0.0/0`	`10.0.0.1`	eth0
`10.0.0.0/8`	direct	eth0
`10.5.0.0/16`	`10.0.0.9`	eth0
`10.5.5.0/24`	`10.0.0.9`	eth0

Route 10.5.5.77: matches /0(0), /8(8), /16(16), /24(24). Longest = 24 → 10.5.5.0/24, eth0. Route 10.5.9.4: matches /0(0), /8(8), /16(16). The /24 needs top 24 bits 10.5.5, but this address has 10.5.9 — no match. Longest of the matches = 16 → 10.5.0.0/16, eth0. (All go out eth0 here, but the chosen prefix entry differs — that entry is what carries the next-hop and, in real life, the MAC via ARP — Address Resolution Protocol.)

Exercise 4.2 (L4) — supernet / aggregation

A router has four contiguous entries all pointing out eth3: 10.8.0.0/16, 10.9.0.0/16, 10.10.0.0/16, 10.11.0.0/16. Find the single aggregate prefix that covers exactly these four and no more.

Recall Solution 4.2

Look at the second byte in binary: $8 = 00001000, 9 = 00001001, 10 = 00001010, 11 = 00001011$ . They agree on the top 6 bits (000010) and differ only in the last 2 bits (00,01,10,11). Four values = $2^{2}$ , exactly one full block of the low 2 bits. Common bits = 8 (first byte) + 6 (second byte) = 14 bits. Aggregate = 10.8.0.0/14. Check: /14 mask second byte = 11111100 = 252, so it covers second-byte values $8$ through $11$ — precisely the four, nothing more. See IP Addressing and Subnetting.

Level 5 — Mastery

Exercise 5.1 (L5) — no specific match, default saves the day

Table: 10.0.0.0/8 → eth1, 192.168.0.0/16 → eth2, 0.0.0.0/0 → eth0. Route 8.8.8.8.

Recall Solution 5.1

10.0.0.0/8: first byte 8 = 00001000 vs 10 = 00001010. AND with 255.0.0.0 gives 8.0.0.0 ≠ 10.0.0.0 ⇒ no match.
192.168.0.0/16: first byte 8 ≠ 192 ⇒ no match.
0.0.0.0/0: matches (length 0). Only the default matches → eth0. This is the "gateway of last resort" doing its job: it is always a match but the shortest, so it wins only when nothing more specific does. See Default Gateway and 0.0.0.0/0.

Exercise 5.2 (L5) — the deceptive overlap at a bit boundary

Table: 172.16.0.0/16 → A, 172.16.128.0/17 → B, 172.16.128.0/18 → C. Route (a) 172.16.130.5, (b) 172.16.64.9.

Recall Solution 5.2

The action is entirely in the third byte. Write it in binary and test the top bits. (a) 172.16.130.5: third byte $130 = 10000010$ .

/16 matches (top 16 bits 172.16) — length 16.
/17: prefix third byte 128 = 10000000; mask third byte = 10000000. $130 \land 128 = 128$ ✓ — length 17.
/18: mask third byte = 11000000 = 192; prefix third byte 128 = 10000000. $130 \land 192$ : $130 = 10000010$ , AND 11000000 = 10000000 = 128 = prefix ✓ — length 18.
Lengths 16, 17, 18 → longest = 18 → interface C. (b) 172.16.64.9: third byte $64 = 01000000$ .
/16 matches — length 16.
/17: $64 \land 128 = 0 \neq = 128$ ⇒ no match.
/18: $64 \land 192 = 64 \neq = 128$ ⇒ no match.
Only /16 matches → interface A.

Exercise 5.3 (L5) — degenerate: identical prefix, different lengths, host on the boundary

Table: 203.0.113.0/24 → X, 203.0.113.0/26 → Y, 203.0.113.0/25 → Z. Route (a) 203.0.113.0 (the network address itself), (b) 203.0.113.63, (c) 203.0.113.64.

Recall Solution 5.3

Last byte splits: /25 at 128, /26 at 64. Relevant boundaries: /26 covers 0–63, /25 covers 0–127, /24 covers 0–255. (a) 203.0.113.0: last byte 0. Matches /24(24), /25(25) — since $0 \land 128 = 0$ , /26(26) — since $0 \land 192 = 0$ . All three match! Longest = 26 → Y. (The all-zero host address still matches; LPM does not care that it's the "network address".) (b) 203.0.113.63: $63 = 00111111$ .

/24 ✓ (24).
/25: $63 \land 128 = 0$ = prefix last byte ✓ (25).
/26: $63 \land 192 = 0$ = prefix ✓ (26) — 63 is still in the 0–63 block.
Longest = 26 → Y. (c) 203.0.113.64: $64 = 01000000$ .
/24 ✓ (24).
/25: $64 \land 128 = 0$ = prefix ✓ (25) — 64 is still in the 0–127 half.
/26: $64 \land 192 = 64 \neq = 0$ ⇒ no match (64 crossed into the next /26 block, 64–127, which is not in the table).
Longest of matches = 25 → Z.

See also: Hinglish version of the parent.