Routing Algorithms: Distance Vector and Link State

Routing algorithms decide the path each data packet takes across a network. Two classic families solve this problem differently. Distance vector algorithms have each router learn routes from its neighbors' claims about distances ("I can reach X in 3 hops"), while link state algorithms give every router a complete map of the network so each one can compute the shortest paths itself.

This matters because the internet is thousands of interconnected networks, and packets must find efficient paths without any central controller. The choice of algorithm affects how fast the network recovers from a failed cable, how much control traffic routers exchange, and whether routing loops can form. Real protocols — RIP and OSPF — are built directly on these two ideas.

Key Concepts

• Router: a device forwarding packets toward destinations using a routing table.
• Metric: the cost of a path — hop count, delay, or bandwidth-based; algorithms minimize it.
• Distance vector: each router keeps a vector of (destination, distance) pairs and shares it with neighbors; based on the Bellman-Ford equation.
• Link state: each router floods its local link costs to everyone, builds an identical map, and runs Dijkstra's algorithm.
• Convergence: the time for all routers to agree on correct routes after a change.
• Count to infinity: the distance-vector failure mode where routers keep incrementing a dead route's cost, converging very slowly.
• Autonomous system: a network under one administration; RIP and OSPF run inside one, BGP connects them together.

Formulas

• Bellman-Ford update: D_x(y) = min over neighbors v of { cost(x, v) + D_v(y) } — router x's best distance to y is the cheapest neighbor's advertised distance plus the link cost to that neighbor.
• Dijkstra relaxation: when considering edge u→v with cost c, if dist[u] + c < dist[v], set dist[v] = dist[u] + c.
• RIP uses hop count as its metric with infinity = 16 (any route costing 16 or more is unreachable); OSPF cost = reference_bandwidth ÷ link_bandwidth.

Worked Example

Four routers with link costs: A–B = 2, A–C = 5, B–C = 1, B–D = 3, C–D = 2. Trace A's distance vector (initially A = 0, B = 2, C = 5, D = ∞):

1. A receives B's vector (B = 0, C = 1, D = 3). Candidate routes via B: to C = 2 + 1 = 3, better than A's direct 5 — update C = 3. To D = 2 + 3 = 5, better than ∞ — update D = 5. A's vector is now (A = 0, B = 2, C = 3, D = 5).
2. A receives C's vector (C = 0, B = 1, D = 2). Via C: to D = 5 + 2 = 7, worse than 5 — no change. To B = 5 + 1 = 6, worse than 2 — no change.
3. Verify optimality by hand: A→D options are A-B-D = 2 + 3 = 5, A-B-C-D = 2 + 1 + 2 = 5, A-C-D = 5 + 2 = 7. True shortest = 5, matching A's table.

After exchanging vectors, every router converges to true shortest paths — that is distance vector in action.

Common Misconceptions

• "Routers know the whole internet." Each router knows only its own table; packets hop router to router, each making a local best decision.
• "Distance vector and link state give different routes." Both compute shortest paths; they differ in how routers learn the information, not in the final answer for the same costs.
• "More hops always means slower." A 5-hop fiber path can beat a 2-hop congested path — metrics, not hop counts, decide in link state protocols.

Real-World Applications

• RIP in small networks, OSPF in enterprises, IS-IS in ISP backbones.
• BGP connecting ISPs and companies worldwide.
• Data-center fabrics running link-state variants for fast convergence.

Distance vector routers learn from neighbors via the Bellman-Ford update; link state routers flood link costs and each runs Dijkstra. The four-router trace shows tables converging to true shortest paths. Both families still run the internet's core.