Routing Algorithms

Why This Matters

Routing algorithms are the decision-making engines that determine how data travels across networks—and understanding them means understanding why the internet actually works. You're being tested on the fundamental trade-offs in distributed systems: 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. The real exam questions will ask you to reason about trade-offs, compare approaches, and apply algorithmic thinking to novel scenarios—so focus on the underlying mechanisms, not just the acronyms.

---

Local Knowledge Approaches: Distance Vector Routing

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

Distance Vector Routing

• Routers share routing tables only with immediate neighbors—no node ever sees the complete network topology
• Bellman-Ford algorithm calculates best paths by iteratively updating distance estimates based on neighbor reports
• Periodic updates (rather than triggered updates) cause slow convergence and vulnerability to routing loops like the count-to-infinity problem

Bellman-Ford Algorithm

• Computes shortest paths from a single source to all other nodes through iterative edge relaxation—runs $|V| - 1$ iterations for $|V|$ vertices
• Handles negative edge weights, unlike Dijkstra's algorithm, making it more flexible for certain cost models
• Slower runtime of $O(VE)$ compared to Dijkstra's, but its distributed nature makes it ideal for distance vector protocols

Routing Information Protocol (RIP)

• Uses hop count as its sole metric—simple but ignores bandwidth, latency, and link quality differences
• Maximum of 15 hops limits network diameter, making RIP suitable only for smaller networks
• 30-second update intervals create slow convergence; largely replaced by OSPF in modern networks

---

Global Knowledge Approaches: Link State Routing

Link state methods flip the script: 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—a fundamental shift from the local-only knowledge of distance vector
• Link State Advertisements (LSAs) flood the network so all routers share the same global view
• Faster convergence because changes propagate immediately rather than rippling through neighbor-by-neighbor updates

Dijkstra's Algorithm

• Finds shortest paths from source to all nodes using a greedy approach that always expands the lowest-cost unexplored node
• Priority queue implementation yields $O((V + E) \log V)$ runtime—significantly faster than Bellman-Ford for dense graphs
• Requires non-negative edge weights—a critical limitation that determines when you can and cannot apply it

Open Shortest Path First (OSPF)

• Link-state protocol using Dijkstra's algorithm internally—the dominant interior gateway protocol in enterprise networks
• Hierarchical area structure reduces LSA flooding by summarizing routes at area boundaries
• Triggered updates (not periodic) mean changes propagate immediately, 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—literally the glue holding the internet together
• Path vector routing maintains full AS-path information, naturally preventing loops by rejecting paths containing your own AS
• Policy-based decisions allow network operators to prefer certain routes based on business relationships, not just shortest paths

Path Vector Routing

• Stores complete path to each destination, not just distance—enables loop detection and policy enforcement
• Each router advertises full AS-path, allowing downstream routers to make informed policy decisions
• Foundation of BGP's design—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 manage large networks without explosion of routing table size
• Route summarization at each level reduces table entries—instead of knowing every destination, know the aggregate
• Trade-off: suboptimal paths are possible since detailed topology is hidden, but scalability gains usually outweigh this cost

Hot Potato Routing

• Hand off packets as quickly as possible to the next autonomous system—minimize your own costs
• Reduces internal latency and resource usage by pushing traffic to exit points immediately
• Selfish but rational—each AS optimizes for itself, which can lead to globally suboptimal but locally efficient routing

---

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 can't you use the alternative?

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 an FRQ asks you 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?