Routing: Distance Vector vs Link State
Scenario
Imagine driving across the country. Distance Vector is like asking the gas station attendant, 'Which way to New York and how far?' Link State is like having a complete drone map of the entire country's road system to plot your own route.
Overview
These are the two main types of dynamic routing protocols used by routers to map network paths.
They dictate how routers share information and calculate the fastest path for data to travel.
Where used: Networking, System Design, Cloud Infrastructure
Why learn this
- Understanding these protocols is key to understanding how data robustly routes across the global internet without loops.
- It comes up in System Design when discussing network topology and convergence.
Mental model
Distance Vector relies on rumors from neighbors to build a map. Link State shares a complete map of the network so everyone calculates their own best path.
Routing protocols decide how data travels. Distance Vector (like RIP) works by having routers blindly trust their neighbors' estimates of how far away a destination is (routing by rumor). Link State (like OSPF) works by having every router broadcast the exact status of its direct connections to everyone, allowing each router to build an identical, complete mathematical map of the entire network.
Explanation
To move data across the internet, routers must build 'routing tables' that tell them which way to forward a packet. They do this dynamically using routing protocols. The two fundamental families of dynamic routing protocols are Distance Vector and Link State. They solve the exact same problem—finding the shortest path to a destination—but they take completely different approaches to gathering information.
In a Distance Vector protocol, a router only knows two things: the distance (hop count or cost) to a destination, and the vector (which specific neighbor to send it to). It learns this by periodically receiving a copy of its neighbors' routing tables. If Router A tells Router B 'I can reach the destination in 2 hops', Router B adds 1 hop for itself, and records 'I can reach it in 3 hops via A'. The glaring flaw is that Router B has no idea what the actual path looks like; it just blindly trusts Router A. This 'routing by rumor' can cause disastrous routing loops if a link goes down and routers start feeding each other outdated rumors.
Link State protocols fix the 'blind trust' problem by giving every router a complete map of the entire network. Instead of sharing their entire routing table, a Link State router only shares information about its direct links (e.g., 'I am connected to Router C and the cost is 5'). Crucially, this 'Link State Advertisement' (LSA) is flooded to every single router in the network, not just neighbors.
Because every router receives the exact same puzzle pieces (the LSAs), every router can build an identical, complete graph of the network topology in its memory. Once the map is built, each router independently runs Dijkstra's Shortest Path First algorithm to calculate the best route to every possible destination.
While Link State is far more robust, converges faster, and doesn't suffer from routing loops, it is much more CPU and memory intensive. It requires powerful routers to store the entire network graph and constantly run Dijkstra's algorithm. Distance Vector is much lighter, making it suitable for smaller, simpler networks where the memory overhead of a full map isn't justified.
Key points
- Distance Vector (e.g., RIP, BGP): Shares full routing tables, but only with direct neighbors. 'Routing by rumor.' Slower to converge when changes happen.
- Link State (e.g., OSPF, IS-IS): Shares only direct connection status, but with everyone in the network. Uses Dijkstra's algorithm to calculate paths.
- Convergence: The time it takes for all routers to agree on the network topology after a change. Link State converges much faster.
- Routing Loops: A severe issue in Distance Vector where packets bounce back and forth infinitely. Prevented by techniques like 'Split Horizon' or 'Poison Reverse'.
Common mistakes
- Assuming Link State uses less bandwidth because it doesn't send the full routing table: While it's true they don't send full tables, Link State protocols flood link state updates to the entire network whenever a link changes, which can cause significant burst traffic in large, unstable networks.
- Confusing the algorithms they use: Distance Vector protocols generally rely on the Bellman-Ford algorithm. Link State protocols rely on Dijkstra's algorithm.
Glossary
- routing protocol
- A set of rules that routers use to communicate with each other so they can figure out the best paths to send data across the internet.
- distance vector
- A routing method where each router just tells its immediate neighbors how far away it thinks everything is, learning the network through second-hand rumors.
- link-state
- A routing method where every router maps out the entire network by telling everyone else exactly who it is directly connected to.
Recall questions
- What is meant by 'routing by rumor' in a Distance Vector protocol?
- Which algorithm do Link State routing protocols use to calculate the shortest path?
- Why is Link State more resistant to routing loops than Distance Vector?
Questions & answers
A network architect is designing a massive enterprise network with hundreds of routers. They need the network to react instantly to down links without creating routing loops. Which protocol type should they use and why?
A Link State protocol (like OSPF).
Approach: Distance Vector protocols are slow to converge in large networks and are highly susceptible to routing loops during topology changes. Link State protocols flood link updates immediately and recalculate paths independently, providing the fast convergence and loop-free routing required for large enterprise networks.
What is the 'Count to Infinity' problem?
A routing loop in Distance Vector protocols where two routers continuously increment the hop count to a destination that has actually gone offline.
Approach: Explain that if Router A loses its connection to destination X, but Router B still advertises 'I can reach X in 2 hops' (because B was secretly routing through A), A will think 'Oh, I can use B to reach X in 3 hops'. B then updates to 4, A to 5, counting to infinity.