Routing Algorithms

Why This Matters

Routing algorithms are the decision-making engines that determine how data travels across networks. Understanding them means understanding why the internet actually works. The fundamental trade-offs here are local knowledge vs. global knowledge, convergence speed vs. computational overhead, and scalability vs. optimality. These concepts appear throughout Networked Life, from social network information spread to game-theoretic equilibria.

Don't just memorize which protocol uses which algorithm. Know why distance vector approaches struggle with convergence, how link state methods achieve faster updates at the cost of more overhead, and when hierarchical structures become necessary. Exam questions will ask you to reason about trade-offs, compare approaches, and apply algorithmic thinking to novel scenarios.

---

Local Knowledge Approaches: Distance Vector Routing

These algorithms operate on a simple principle: each node only knows about its immediate neighbors and shares what it learns. This distributed approach requires minimal coordination but comes with real trade-offs in convergence behavior.

Distance Vector Routing

• Routers share routing tables only with immediate neighbors. No node ever sees the complete network topology.
• The Bellman-Ford algorithm calculates best paths by iteratively updating distance estimates based on what neighbors report.
• Periodic updates (rather than triggered updates) cause slow convergence and leave the protocol vulnerable to routing loops, most notably the count-to-infinity problem. In count-to-infinity, two routers keep incrementing a route's cost back and forth because neither realizes the destination is unreachable, and the cost slowly "counts" up to the protocol's defined infinity value.

Bellman-Ford Algorithm

• Computes shortest paths from a single source to all other nodes through iterative edge relaxation. It runs $|V| - 1$ iterations for a graph with $|V|$ vertices, because the longest possible shortest path visits every vertex once.
• Handles negative edge weights, unlike Dijkstra's algorithm, making it more flexible for certain cost models.
• Its runtime of $O(VE)$ is slower than Dijkstra's, but its structure maps naturally onto distributed systems: each router only needs information from its neighbors to run its update step. That's why it's the basis for distance vector protocols.

Routing Information Protocol (RIP)

• Uses hop count as its sole metric. This is simple but completely ignores bandwidth, latency, and link quality differences. A path through two high-speed links and a path through two congested links look identical to RIP.
• Maximum of 15 hops limits network diameter, making RIP suitable only for smaller networks.
• 30-second update intervals create slow convergence. RIP has been largely replaced by OSPF in modern networks.

---

Global Knowledge Approaches: Link State Routing

Link state methods flip the approach: every router builds a complete map of the network. This requires more communication overhead upfront but enables faster, more informed routing decisions.

Link State Routing

• Each router maintains complete network topology. This is a fundamental shift from the local-only knowledge of distance vector.
• Link State Advertisements (LSAs) are flooded across the network so all routers converge on the same global view. "Flooding" means each router forwards the LSA to all its neighbors except the one it received it from, guaranteeing every router gets the update.
• Faster convergence results because changes propagate immediately through flooding rather than rippling through neighbor-by-neighbor periodic updates.

Dijkstra's Algorithm

• Finds shortest paths from a source to all nodes using a greedy approach: it always expands the lowest-cost unexplored node next, and once a node is finalized, its shortest path is guaranteed.
• With a priority queue (min-heap) implementation, runtime is $O((V + E) \log V)$, significantly faster than Bellman-Ford for typical network graphs.
• Requires non-negative edge weights. The greedy strategy breaks if a later edge could reduce an already-finalized path cost. This is the key constraint that determines when you can and cannot use it.

Open Shortest Path First (OSPF)

• A link-state protocol using Dijkstra's algorithm internally. It's the dominant interior gateway protocol in enterprise networks.
• Hierarchical area structure reduces LSA flooding by summarizing routes at area boundaries. Routers within an area share full topology with each other, but only summarized reachability information crosses area borders.
• Triggered updates (not periodic) mean changes propagate immediately, directly solving RIP's slow convergence problem.

---

Inter-Domain Routing: Crossing Autonomous Systems

When data crosses organizational boundaries, routing becomes a policy problem, not just an optimization problem. These protocols handle the political and economic realities of the internet's structure.

Border Gateway Protocol (BGP)

• The protocol connecting autonomous systems (ASes). Virtually all inter-domain routing on the internet runs BGP.
• Path vector routing maintains full AS-path information, naturally preventing loops: if a router sees its own AS number in an advertised path, it rejects that path.
• Policy-based decisions allow network operators to prefer certain routes based on business relationships (customer, peer, provider), not just shortest paths. For example, an AS might prefer a longer path through a customer (who pays it) over a shorter path through a provider (whom it pays).

Path Vector Routing

• Stores the complete path to each destination, not just a distance. This enables both loop detection and policy enforcement.
• Each router advertises the full AS-path, allowing downstream routers to make informed decisions about which routes to accept or prefer.
• The trade-off is larger routing tables in exchange for richer decision-making information.

---

Scalability and Optimization Strategies

As networks grow, naive approaches break down. These techniques address the fundamental challenge of managing complexity at scale.

Hierarchical Routing

• Organizes routers into levels (areas, regions, domains) to prevent routing table size from exploding. Without hierarchy, every router would need an entry for every destination in the entire network.
• Route summarization at each level reduces table entries. Instead of knowing the path to every individual destination, a router knows how to reach an aggregate block. For example, a backbone router might have one entry for an entire regional network rather than thousands of entries for individual subnets.
• Trade-off: suboptimal paths are possible since detailed topology is hidden at higher levels. But the scalability gains almost always outweigh this cost.

Hot Potato Routing

• Hand off packets as quickly as possible to the next autonomous system. The goal is to minimize your own internal costs by pushing traffic to the nearest exit point.
• Reduces internal resource usage for the AS doing the routing, since traffic spends less time traversing its infrastructure.
• Selfish but rational: each AS optimizes for itself. This can lead to globally suboptimal paths (the packet might enter the destination AS far from the actual destination), but it's locally efficient for the sending AS.

---

Quick Reference Table

---

Self-Check Questions

1. Both RIP and OSPF route traffic within an autonomous system. What fundamental difference in their approach to network knowledge explains why OSPF converges faster after a link failure?

2. You're designing a routing system for a network where some links have negative costs (representing payments or incentives). Which shortest-path algorithm must you use, and why does the alternative fail?

3. Compare BGP and OSPF: why does BGP use path vector routing while OSPF uses link state, given that both need to find efficient routes?

4. A network operator wants to minimize the resources their AS spends on transit traffic. Which routing strategy would they employ, and what's the potential downside for end-to-end path quality?

5. If you had to explain why the internet uses hierarchical routing rather than flat routing tables, what two scalability problems would you cite, and how does hierarchy address each?