Router City.
Every packet needs a plan —
and a push.
You've just joined Router City's Network Operations team. Six routers, one misbehaving forwarding table, and a delivery deadline. Before you touch a single packet, you need to understand the two jobs every router does — and the algorithms that make the whole city work at scale. Six modules. One final exam. No hand-holding at the end.
Forwarding vs. Routing
Two jobs, two very different speeds. Kurose & Ross's own analogy is a road trip: routing is planning the whole trip from source to destination. Forwarding is just getting through a single interchange — a local, split-second decision.
A letter (packet) leaves host h1 for host h6 across three switches. Two different questions get answered by two different planes:
Data Plane
Local, per-router. Looks only at the packet sitting in front of it right now, and decides which output port to use. Runs in hardware, per-packet, at line rate.
Control Plane
Network-wide logic. Decides the paths that datagrams follow end-to-end, and installs the forwarding tables that the data plane blindly obeys.
Router R3 receives a packet and instantly sends it out interface 2 because its forwarding table says so. Which plane made this specific decision, and which plane decided that route existed in the first place?
A
Data plane made the decision, control plane built the table.
B
Control plane made the decision, data plane built the table.
C
Both are the same plane — routers don't separate the two.
Longest Prefix Matching
A router's forwarding table doesn't store every destination — it stores prefix ranges. When a destination address could match more than one row, the router always takes the longest matching prefix, because longer prefixes describe more specific — and therefore more authoritative — ranges.
| Destination address range (prefix) | Prefix length | Interface |
|---|---|---|
| 11001000 00010111 00010* | 21 bits | 0 |
| 11001000 00010111 00011000 | 24 bits | 1 |
| 11001000 00010111 00011* | 21 bits | 2 |
| otherwise | — | 3 |
Pick a destination address arriving at R7. Watch the bit-by-bit match against every row, then choose the interface before revealing the router's answer.
Link-State Routing — Dijkstra
In link-state routing (OSPF, IS-IS), every router floods its link costs so everyone knows the whole map. Each router then runs Dijkstra's algorithm locally to compute shortest paths to every destination. Step through it below — and predict each move before the algorithm does it.
| Node | Tentative distance from A | Via |
|---|
Distance Vector — Bellman-Ford
Distance vector (RIP, EIGRP) never sees the whole map. Every router only knows its own neighbors, and periodically gossips its own distance vector to them. Over several rounds, the estimates converge to the true shortest distances — the same answer Dijkstra reaches globally.
Each round, every node updates its distance to F using: D(node) = min over neighbors [ cost(node,neighbor) + D(neighbor) ].
| Link-State | Distance Vector | |
|---|---|---|
| Topology knowledge | Global — everyone sees the full map | Local — only direct neighbors |
| Message cost | O(N·E) flooding messages | Only exchanges with neighbors, but rounds can be many |
| Convergence risk | Possible oscillation if costs depend on load | Routing loops, "count-to-infinity" |
| Fault blast radius | A lying router mostly hurts itself (each router computes its own table) | A lying router's bad vector propagates to everyone downstream |
Scaling It Up — Autonomous Systems & BGP
The internet isn't one flat network — it's a network of networks. Routers are grouped into Autonomous Systems (AS): a university, an ISP, a datacenter. Inside an AS, routers agree on one intra-domain protocol (OSPF, EIGRP, RIP). Between AS's, everyone speaks one common language: BGP.
The Router City Certification Exam
No more guided walkthroughs. Three tasks, real computation required, wrong answers just get a nudge — not the solution. Solve all three to get certified.
Same forwarding table as Module 2. A new packet arrives at R7:
Which output interface does R7 use?
00011011. Its first 5 bits are 00011. Which 21-bit prefix has last-5-bits 00011?00011000. It isn't — so that longer prefix is disqualified. The winner is the next-longest row that still matches.A new link-cost map (not the one from Module 3). Compute the total shortest-path cost from A to F and type it in.
Router R1 sits inside AS 100 (a university network). It needs to deliver a packet to a server inside AS 200 (a datacenter on the other side of the country), reachable through gateway router R9.
Which protocol determines the path between AS 100 and AS 200?