Computer Networks · free preview
Routing
Routing is the distributed computation that fills forwarding tables, the network is a graph and the goal is least-cost paths, distance-vector routing has each node tell its neighbors its vector of distances to everywhere and suffers the count-to-infinity pathology that split horizon only partly cures, link-state routing instead floods every node's neighborhood map reliably so all nodes build the same complete graph and run Dijkstra's shortest-path algorithm locally, metrics that feed either algorithm must capture latency, capacity and load without oscillation, and hierarchy through areas and autonomous systems keeps the whole enterprise within bounds.
1. The Routing Problem
The Routing Problem
2. Counting to Infinity
Counting to Infinity
3. Link State
Link State
4. Metrics and Hierarchy
Metrics and Hierarchy
5. What neighbors hear
What fundamentally distinguishes what a distance-vector node tells its neighbors from what a link-state node tells them?
6. Counting to infinity
A link fails, and two nearby routers begin advertising the lost destination to each other with ever-increasing costs. What is happening?
7. Split horizon
What does the split-horizon rule forbid, and what loop does it eliminate?
8. Reliable flooding
In link-state routing, how does every node end up with the same map, and how do stale copies of link-state packets get discarded?
9. The metric trap
Why did measuring link cost by instantaneous queue length fail in the early ARPANET?
10. Why hierarchy
Why does OSPF divide a large network into areas?
11. Infinity in RIP
In the Routing Information Protocol, what hop count is defined to represent infinity, bounding the count-to-infinity pathology?
12. The shortest-path algorithm
Each link-state node computes least-cost paths on the shared map using which classic shortest-path algorithm?
13. Poison reverse
Which technique strengthens split horizon by advertising a route back to its teacher at infinite cost rather than staying silent?
14. The sequence number's job
In reliable flooding, which field of a link-state packet lets a node discard an older copy in favor of the freshest one?
Practice this interactively
Free account · instant grading · spaced review that schedules itself.
Start this course for free