Routing
Introduced
Vocabulary
| English | Meaning |
|---|---|
| routing table/ˈraʊtɪŋ ˈteɪbl/ | Stored information a router uses to choose where to forward packets for different network destinations. |
| longest prefix match | Choosing the routing-table entry whose matching destination prefix is longest. |
Tables and prefixes
- A router's routing table maps destination prefixes to next hops; the longest prefix match rule picks the most specific route, and the default catches what nothing else does.
- Table
10.0.0.0/8 → X,10.1.0.0/16 → Y,10.1.2.0/24 → Z, default → W:10.1.2.200goes to Z,10.9.9.9to X,192.168.1.1to W.
{exercise:uni-cs0903-table}
Practice
Destination 10.1.2.200 with /8, /16 and /24 entries present goes to —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Longest prefix match: three match, the /24 is most specific.
Dijkstra, in numbers
- Course weights: A–B 4, A–C 2, B–C 1, B–D 5, C–D 8, C–E 10, D–E 2, E–F 3, D–F 6. From A the settle order is C, B, D, E, F at distances 2, 3, 8, 10, 13.
- F's best path is A C B D E F at $2+1+5+2+3 = 13$ — via E ($10 + 3$) beats D's direct $8 + 6 = 14$. Settled nodes are final: never relax through them again.
{exercise:uni-cs0903-dijkstra}
Practice
On the course graph, node F settles at —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
A C B D E F: 2 + 1 + 5 + 2 + 3 = 13 - via E beats D direct (14).
Why hierarchy}
- Flat tables would hold one entry per host: $4 \times 10^9$ IPv4 rows. Prefix aggregation announces one /12 covering $2^{20}$ addresses, keeping the table near $10^5$ entries.
- Aggregation throws away the host bits on purpose — the table stays human-sized because nobody needs to know hosts.
{exercise:uni-cs0903-aggregate}
Practice
A /12 announcement covers — addresses
Difficulty 1/5 · 100 coins + a small bonus on first completion today
32 - 12 = 20 host bits: 2^20 addresses aggregated away.