Routing Algorithms (Distance Vector, Link State)
Routing algorithms are the methods routers use to choose the best path for forwarding a packet. In distance vector routing, each router shares its distance table with neighbors and learns routes secondhand, while in link state routing every router builds a complete map of the network and computes shortest paths itself, converging faster.
A routing algorithm is the method a router uses to decide which path a packet should take toward its destination when there are multiple possible routes. The two foundational approaches, distance vector and link state, take genuinely different strategies to solve the same problem.
Distance vector routing
Each router maintains a table of the distance (usually measured in hops, the number of routers a packet must pass through) to every known destination, along with which neighbor to send traffic to for that destination. Routers periodically share their entire distance table with their directly connected neighbors, who use that information to update their own tables ("routing by rumor": a router doesn't know the full network topology, only what its neighbors tell it about distances).
The classic distance vector algorithm is based on the Bellman-Ford algorithm. Its main real weakness is slow convergence after a network change, and a specific failure mode called the "count to infinity" problem, where a route to a now-unreachable destination can bounce between routers being repeatedly (and incorrectly) reported as reachable through each other before the routers eventually realize it's actually gone.
Link state routing
Each router instead builds a complete map of the entire network's topology (which routers connect to which, and the cost of each link), by having every router broadcast information about its direct connections to all other routers in the network (flooding). Once every router has the same complete map, each one independently runs a shortest-path algorithm (commonly Dijkstra's algorithm) to compute the best route to every destination.
Link state routing converges faster and more reliably than distance vector after a network change, because every router has full visibility into the topology rather than relying on secondhand information from neighbors, but it requires more processing power and memory to store and compute over the full network map.
A worked example
Picture four routers, A, B, C, D, connected in a line: A-B-C-D.
With distance vector: A knows it's 1 hop from B, and learns from B that B is 1 hop from C, so A concludes it's 2 hops from C. A learns about D the same way, secondhand, through B's own secondhand knowledge from C.
With link state: every router floods its direct connections (A knows it connects to B; B knows it connects to A and C; and so on) to every other router. A ends up with the complete picture (A-B-C-D) directly, and runs Dijkstra's algorithm on that full map to compute that D is 3 hops away, without ever relying on another router's calculated distance, only on raw topology facts.
Where this matters in real systems
RIP (Routing Information Protocol) is a real, if largely legacy, distance vector protocol; OSPF (Open Shortest Path First) is a widely used real link state protocol, and its faster convergence and more reliable behavior after topology changes are exactly why OSPF is far more common in serious enterprise and ISP networks today than RIP is.
What interviewers actually ask about routing algorithms
- "What's the difference between distance vector and link state routing?" Distance vector routers only know distances reported by direct neighbors ("routing by rumor"); link state routers build a complete map of the network topology and independently compute shortest paths from it.
- "What is the count-to-infinity problem?" A failure mode in distance vector routing where a route to an unreachable destination gets repeatedly, incorrectly reported as reachable through neighboring routers, delaying the network's realization that the destination is actually gone.
- "Why does link state routing generally converge faster after a topology change?" Every router has full visibility into the real network topology directly, rather than relying on secondhand, potentially stale information from neighbors.
- "Name a real protocol using each approach." RIP is a classic distance vector protocol; OSPF is a widely used link state protocol.
Key takeaways
- Distance vector routing shares distance tables between neighbors and has each router calculate routes based on secondhand information.
- Link state routing floods full topology information to every router, which then independently computes shortest paths using the complete map.
- Distance vector is simpler but converges slower and can suffer the count-to-infinity problem; link state converges faster but needs more processing and memory.
- RIP is a real distance vector protocol; OSPF is a real, more widely used link state protocol.
More in Network Layer
Browse all Computer Networks topics
Log in to save which topics you've read across every subject.
Frequently asked questions
What's the difference between distance vector and link state routing?
Distance vector routers only know distances reported by direct neighbors ("routing by rumor"); link state routers build a complete map of the network topology and independently compute shortest paths from it.
What is the count-to-infinity problem?
A failure mode in distance vector routing where a route to an unreachable destination gets repeatedly, incorrectly reported as reachable through neighboring routers, delaying the network's realization that the destination is actually gone.
Why does link state routing generally converge faster after a topology change?
Every router has full visibility into the real network topology directly, rather than relying on secondhand, potentially stale information from neighbors.
Name a real protocol using each approach.
RIP is a classic distance vector protocol; OSPF is a widely used link state protocol.