Routing Algorithms

The GPS Analogy

A GPS app does not just find a route from A to B — it finds the best route based on distance, traffic, and road conditions. It recalculates when a road is closed. When you take a wrong turn, it adapts instantly.

Routers do exactly the same thing for network packets. Every packet arriving at a router carries a destination IP address, and the router must decide: Which interface do I forward this out of? The answer comes from a routing table, built and maintained by routing algorithms.

The Routing Table

Every router holds a routing table — a structured list of destinations and instructions for reaching them.

On Windows, run route print to see your machine's routing table. On Linux, use ip route show.

Static vs Dynamic Routing

Static routing means an administrator manually enters routes. The router does not adapt — if a link fails, packets are dropped until a human updates the table.

• Best for: small networks, stub networks, security-sensitive paths
• Advantage: predictable, zero protocol overhead
• Disadvantage: does not scale, manual updates required

Dynamic routing means routers exchange information with neighbors and automatically build their tables. When topology changes, they converge on new paths.

• Best for: medium to large networks, multi-path environments
• Advantage: automatic failover, scalable
• Disadvantage: consumes bandwidth and CPU for protocol messages

Distance Vector Routing: RIP and Bellman-Ford

Distance Vector protocols work on a simple principle: each router tells its neighbors "I can reach destination X at cost Y." Routers collect these advertisements and pick the lowest-cost path.

The underlying algorithm is Bellman-Ford:

For each destination D:
  best_cost[D] = min over all neighbors N of (cost_to_N + neighbor_cost_to_D)

RIP (Routing Information Protocol) is the classic distance vector protocol:

• Metric: hop count (max 15 hops; 16 = unreachable)
• Updates: broadcast full table every 30 seconds
• Version: RIPv2 supports CIDR and authentication

The Count-to-Infinity Problem

When a link fails, routers can enter a loop where they keep incrementing the hop count believing a route exists through each other.

Router A thinks: "I can reach X through B (cost 2)"
Router B thinks: "I can reach X through A (cost 3)"
→ Both increment indefinitely until 16

Fix — Split Horizon: Never advertise a route back to the router you learned it from. This eliminates most routing loops in simple topologies.

Link State Routing: OSPF and Dijkstra

Link State protocols take a fundamentally different approach: every router floods the network with information about its own directly connected links. Each router collects this information into a Link State Database (LSDB) — a complete map of the entire network.

With the full map, each router independently runs Dijkstra's Shortest Path First (SPF) algorithm to compute the optimal path to every destination.

OSPF (Open Shortest Path First):

• Metric: cost based on interface bandwidth (higher bandwidth = lower cost)
• Updates: triggered by topology changes (not periodic full broadcasts)
• Scales well: uses areas to limit LSDB size in large networks
• Area 0 is the backbone; all other areas connect to it

Why Link State Converges Faster

Distance vector routers only know their neighbors' claims about the world. Link state routers have the actual map. When a link fails:

• RIP: must wait up to 180 seconds for routes to time out
• OSPF: detects failure within seconds via Hello packet timeouts and floods updated LSAs immediately

BGP: The Internet's Backbone Protocol

All the protocols above work within a single organization's network (an Autonomous System, or AS). But the internet connects thousands of autonomous systems — ISPs, universities, companies — each with their own routing policies.

BGP (Border Gateway Protocol) is the protocol that routes between autonomous systems.

• Type: Path Vector (an extension of distance vector)
• Metric: AS path length + policy attributes (not just hop count)
• Scale: Handles 900,000+ routes in the global routing table
• Policy-driven: ISPs can prefer certain paths for business reasons, not just technical ones

BGP is what makes the internet's routing resilient and policy-aware. When a major ISP announces or withdraws routes, BGP propagates those changes globally — sometimes causing brief outages visible worldwide.

Protocol Comparison Table

Reading Routing Tables in Practice

Windows:

route print

Look for the IPv4 Route Table section. The default route is 0.0.0.0 with mask 0.0.0.0 — this is where packets go when no more specific route matches.

Linux:

ip route show

or the older:

netstat -rn

Key entry to understand:

0.0.0.0/0 via 192.168.1.1 dev eth0

Translation: For any destination not matched by a more specific route, forward to 192.168.1.1 on interface eth0 (your gateway/router).

How Routers Choose Between Routes

When multiple routing protocols provide routes to the same destination, routers use Administrative Distance (AD) to break the tie:

Lower AD wins. A static route always beats OSPF. A directly connected network always wins.

Key Takeaways

• Every router maintains a table mapping destinations to next-hop instructions
• Static routes are manual and simple; dynamic protocols adapt automatically
• RIP uses hop count and Bellman-Ford; simple but slow to converge
• OSPF gives every router a full topology map; fast convergence via Dijkstra
• BGP connects autonomous systems and is the protocol that holds the internet together
• Use route print (Windows) or ip route show (Linux) to inspect routing decisions on any machine