Routing Algorithms Explained: Beyond the Basics

The most surprising thing about routing algorithms is that the "shortest" path isn’t always the best path, and sometimes, the best path is actively avoided.

Let’s see what happens when we actually do routing. Imagine a simple network: three routers, A, B, and C.

A --(1)--> B --(1)--> C
^           |
|           | (1)
|           |
+-----------+

Here, the numbers represent the "cost" or "metric" of a link.

Dijkstra’s Algorithm: The Greedy Shortest Path

Dijkstra is like a meticulous scout. It starts at one point (say, router A) and explores outward, always taking the cheapest step first.

1. Start at A. Current known shortest paths: A to A is 0.
2. Explore neighbors of A: B is 1 hop away (cost 1). C is directly connected (cost 5).
   • Known shortest paths: A to A (0), A to B (1), A to C (5).
3. From the closest known node (B): Explore its neighbors.
   • From B, we can reach A (cost 1 + 1 = 2). But we already know A to A is 0, so this doesn’t improve anything.
   • From B, we can reach C (cost 1 + 1 = 2). This is better than the direct A to C path (cost 5).
   • Known shortest paths: A to A (0), A to B (1), A to C (2).
4. No more unvisited nodes or better paths found. Dijkstra declares: A to B is cost 1, A to C is cost 2.

Dijkstra finds the path with the lowest cumulative cost. It’s fast and great for finding the absolute cheapest route.

Bellman-Ford Algorithm: The Pessimistic Path Checker

Bellman-Ford is like a cautious auditor. It’s slower but can handle some tricky situations Dijkstra can’t, like negative costs (though we don’t have those here) and detecting routing loops. It works by repeatedly "relaxing" all edges.

Let’s say we want to find the shortest path from A to all other nodes. Initially, costs are infinite except for A to itself (0).

• Initialization:

  • dist(A,A) = 0
  • dist(A,B) = ∞
  • dist(A,C) = ∞

• Pass 1 (Relax all edges):

  • Edge A->B: dist(A,B) = min(∞, dist(A,A) + cost(A,B)) = min(∞, 0 + 1) = 1
  • Edge B->A: dist(A,A) = min(0, dist(A,B) + cost(B,A)) = min(0, 1 + 1) = 0 (no change)
  • Edge B->C: dist(A,C) = min(∞, dist(A,B) + cost(B,C)) = min(∞, 1 + 1) = 2
  • Edge C->B: dist(A,B) = min(1, dist(A,C) + cost(C,B)) = min(1, 2 + 1) = 1 (no change)
  • Edge A->C: dist(A,C) = min(2, dist(A,A) + cost(A,C)) = min(2, 0 + 5) = 2 (no change)

• Pass 2 (Relax all edges again):

  • A->B: dist(A,B) = min(1, dist(A,A) + 1) = 1
  • B->A: dist(A,A) = min(0, dist(A,B) + 1) = 0
  • B->C: dist(A,C) = min(2, dist(A,B) + 1) = 2
  • C->B: dist(A,B) = min(1, dist(A,C) + 1) = 1
  • A->C: dist(A,C) = min(2, dist(A,A) + 5) = 2

After |V|-1 passes (where |V| is the number of vertices, 3 in this case, so 2 passes), Bellman-Ford has converged. It finds the same paths as Dijkstra: A to B is 1, A to C is 2. Bellman-Ford is more computationally expensive but is the foundation for protocols like RIP (Routing Information Protocol).

BGP: The Inter-Network Diplomat

Now, let’s talk about the real world: the internet. Dijkstra and Bellman-Ford work within an autonomous system (AS) – a group of routers managed by a single organization. But how do different ASes talk to each other? That’s BGP (Border Gateway Protocol).

BGP doesn’t just care about "cost." It cares about policies and reachability. An AS might have multiple paths to another AS, but it might prefer one based on business agreements, peering arrangements, or security.

Consider AS1 (our A, B, C network) and AS2.

AS1 <-----> AS2
  (eBGP)

AS1 has internal routers (iBGP) and border routers (eBGP) that connect to AS2. BGP routers exchange prefixes (blocks of IP addresses) and path attributes.

Path attributes are key:

• AS_PATH: A list of AS numbers the prefix has traversed. This is crucial for loop detection. If AS1 sees a prefix with its own AS number in the AS_PATH, it knows it’s a loop and discards it.
• NEXT_HOP: The IP address of the next router to send traffic to.
• LOCAL_PREF: An attribute used within an AS to prefer one exit point over another. Higher is better.
• MED (Multi-Exit Discriminator): Used between two ASes to suggest which path is preferred for inbound traffic. Lower is better.

When AS1’s router receives a prefix from AS2, it looks at the path attributes. It might have multiple paths to AS2’s prefixes. It will pick the "best" path based on a complex decision tree:

1. Prefer the path with the highest LOCAL_PREF.
2. If LOCAL_PREFs are equal, prefer the path where the prefix originated from your AS (if it’s an iBGP route).
3. Prefer the path with the shortest AS_PATH.
4. Prefer the path with the lowest Origin Type (IGP < EGP < Incomplete).
5. Prefer the path with the lowest MED.
6. Prefer eBGP paths over iBGP paths.
7. Prefer the path to the closest IGP neighbor.
8. Prefer the path with the lowest Router ID (if all else fails).

This decision tree is why BGP is often called a "path vector" protocol. It exchanges entire paths, not just metrics, allowing for sophisticated policy enforcement.

The one thing most people don’t realize about BGP is that a router’s decision about which path to use for outgoing traffic is heavily influenced by attributes that other ASes can set, like MED, to try and influence how traffic enters their network. It’s a constant negotiation and sometimes a subtle war of influence between network operators.

The next rabbit hole you’ll fall down is understanding how these AS paths interact with internal routing protocols like OSPF or IS-IS within an AS, and the complex interplay of route redistribution.