Routing Algorithms

When a router receives a packet, it looks at the destination IP address and forwards the packet out of the correct physical port. But how does the router know which port leads to the correct destination? It consults its Routing Table.

The process of building and maintaining this routing table dynamically as the network changes (links go down, new routers are added) is governed by Routing Algorithms.

1. Distance Vector Routing (RIP)

In Distance Vector routing, each router maintains a table containing the best known distance (cost) to every other destination in the network, and which link to use to get there.

How it works (The Bellman-Ford Algorithm):

1. Initially, a router only knows the cost to its directly connected neighbors.
2. Periodically (e.g., every 30 seconds), every router sends its entire routing table to its immediate neighbors.
3. When a router receives a table from a neighbor, it calculates: "If I route through this neighbor, what is the total cost to reach destination X?"
4. If the new cost is cheaper than its current known route, it updates its routing table.

Pros: Very simple to configure and requires minimal memory and CPU. Cons:

• Slow Convergence: It takes a long time for a change (like a broken link) to propagate across the entire network.
• Count-to-Infinity Problem: If a link goes down, routers can get caught in a routing loop, falsely advertising increasing distances to each other in an infinite loop.

Protocol Implementation: RIP (Routing Information Protocol).

2. Link State Routing (OSPF)

Link State routing is vastly superior and is the standard for modern internal networks. Instead of blindly trusting its neighbors' routing tables, every router independently maps out the entire network topology.

How it works (Dijkstra's Algorithm):

1. Discovery: Each router figures out the identity and cost of its directly connected neighbors.
2. Flooding: Each router constructs a "Link State Packet" (LSP) containing its neighbor information and floods it to absolutely every other router in the entire network.
3. Database: Every router collects these LSPs and builds an identical, complete map (graph) of the entire network topology.
4. Shortest Path: Every router runs Dijkstra's Shortest Path Algorithm locally on its own map to compute the mathematically optimal route to every possible destination.

Pros: Fast convergence. Because every router has a complete map of the network, routing loops are impossible. Cons: Requires significant CPU processing to run Dijkstra's algorithm, and requires more memory to store the topological database.

Protocol Implementation: OSPF (Open Shortest Path First).

3. Path Vector Routing (BGP)

While OSPF is used inside an organization's network (Intra-Domain Routing), it cannot scale to the size of the global Internet. For routing between massive autonomous networks (like AT&T routing to Comcast), Path Vector Routing is used.

How it works: Instead of tracking the exact cost (distance) to a destination, BGP tracks the exact path (a list of Autonomous Systems) the packet must travel through.

• If AT&T receives a route advertisement that says "To reach destination X, the path is [Verizon $\to$ Sprint $\to$ AT&T]", AT&T sees its own name in the path and instantly drops the route, completely preventing global routing loops.

Protocol Implementation: BGP (Border Gateway Protocol). BGP is the duct tape that holds the global Internet together. If BGP fails (as happened to Facebook in 2021), the entire company disappears from the Internet.