Introduction: The Network's GPS

Imagine the internet as a gigantic, sprawling city with billions of addresses. When you send an email or visit a website, you are essentially mailing a letter (a data packet) from your address to another. How does this letter find its way through a maze of intersections, highways, and byways to reach its destination halfway across the world in milliseconds? The answer lies with special-purpose computers that act as the city's postal workers and traffic controllers: routers.

A router sits at the junction of two or more networks and makes the critical decision of where to send each passing packet. But to make this decision, it needs a map. This "map" is called a routing table, which contains a list of directions: "To reach network X, send the packet to the next router Y."

But where does this map come from? A network is not static; links can fail, new routers can be added, and traffic conditions can change. Routers cannot rely on a pre-printed map. Instead, they must continuously learn about the network's layout and update their own maps. The method they use to learn and build these tables is defined by a routing algorithm. This page explores the fundamental "philosophies" behind how routers build their view of the world.

The Goal of a Routing Algorithm: Finding the "Best" Path

At its core, a routing algorithm is a set of rules and procedures used by routers to learn about the network's topology, share this information with other routers, and calculate the best path(s) to all reachable destinations. The ultimate goal is to populate the routing table with high-quality, loop-free routes.

What Makes a Path "Best"? The Metric

The concept of the "best" path is not universal. It is determined by a metric. A metric is a numerical value assigned to a path that the algorithm seeks to minimize. It's the "cost" of using that path. Common metrics include:

• Hop Count: The number of routers a packet must cross. Simple, but doesn't account for link speed.
• Bandwidth: The data-carrying capacity of the links. Higher bandwidth is better, so the metric is often calculated as $1/\text{bandwidth}$.
• Delay (Latency): The time it takes for a packet to traverse the links.
• Load: How busy the links are.
• Cost: An administratively defined value, often based on a combination of factors or monetary cost.

Distance Vector: Routing by Rumor

The first major family of routing algorithms is Distance Vector. The best analogy for this is "routing by rumor" or following signposts. Each router initially knows very little: only its own identity and how to reach its immediate, directly connected neighbors (the "distance" to them is one hop, or the cost of the link). It doesn't have a map of the entire network.

How It Works: Sharing What You Know

The core principle of a Distance Vector algorithm is simple and decentralized, based on the $\text{Bellman-Ford}$ algorithm:

1. Each router maintains a routing table that lists all known destinations, the distance (metric) to that destination, and the next router (next-hop) on the path.
2. On a regular basis (e.g., every 30 seconds), each router broadcasts its entire routing table to its directly connected neighbors.
3. When a router receives a table from a neighbor, it compares the received information with its own. For each destination in the neighbor's table, it calculates a new potential distance: $d_{\text{new}} = d_{\text{neighbor}} + c_{\text{link}}$, where $d_{\text{neighbor}}$ is the neighbor's distance to the destination and $c_{\text{link}}$ is the cost of the link to that neighbor.
4. If this newly calculated distance is better (lower) than the one it currently has in its table, it updates its entry, setting the new, lower distance and listing the neighbor who sent the update as the next-hop.

Through this process of sharing rumors with neighbors, knowledge about the network topology gradually propagates from router to router until all routers have learned the best paths to all destinations. This final stable state is known as convergence.

Example: The Problem of "Counting to Infinity"

The "routing by rumor" approach has a famous and significant drawback. While it works well when links are added or metrics improve, it reacts very slowly and problematically to link failures. This is known as the Counting to Infinity problem.

Consider a simple network: Router A is connected to Router B, which is connected to Network X. The hop count is the metric.

1. Stable State: B advertises it can reach X with a metric of $1$ (directly connected). A receives this, adds its own cost of $1$ to get to B, and installs a route to X via B with a metric of $2$.
2. Link Failure: The link between B and X goes down. B now has no route to X.
3. Bad Rumor Spreads: Before B can tell A about the failure, A's periodic update arrives at B. A's table says, "I can get to Network X in $2$ hops."
4. Routing Loop: B hears this rumor from A. B thinks, "Wow, A has a path to X! I can get to A in $1$ hop, so my new path to X is via A with a cost of $2+1=3$." B updates its table to point to A.
5. The Count Begins: On the next update, A tells B its route (cost $2$). B updates its cost to $3$. Then A hears from B (cost $3$) and updates its cost to $4$. Then B hears from A (cost $4$) and updates to $5$. The packets destined for X are now trapped in a loop, bouncing between A and B while the metric slowly increments toward infinity.

To combat this, mechanisms like Split Horizon (not advertising a route back out of the interface it was learned on), Route Poisoning, and Hold-Down Timers were developed. The classic protocol that uses this algorithm is $\text{RIP}$ ($\text{Routing Information Protocol}$).

Link-State: Everyone Gets a Complete Map

The second major family of algorithms, Link-State, takes a fundamentally different approach. Instead of relying on second-hand information from neighbors, the goal is for every single router to have a complete and identical map of the entire network topology. Each router then acts as its own GPS, independently calculating the best route from its own perspective to every possible destination.

How It Works: Building the Map and Finding the Shortest Path

The Link-State process can be broken down into a few key steps, based on $\text{Dijkstra's}$ $\text{Shortest Path First}$ ($\text{SPF}$) algorithm:

1. Discover Neighbors and Link Costs: Each router first discovers its directly connected neighbors and determines the cost (metric) of the link to each of them.
2. Create a Link-State Packet (LSP): Each router packages this information: its ID, its list of neighbors, and the cost to each neighbor, into a small message called a Link-State Packet (LSP).
3. Flood the LSP to All Routers: The router then sends its LSP to all of its neighbors. Each neighbor that receives the LSP saves a copy, updates its own map, and forwards the LSP to all of its neighbors (except the one it came from). This process, known as flooding, ensures that every router in the area quickly receives a copy of every other router's LSP.
4. Build a Complete Topology Database: By collecting all the LSPs, each router builds an identical database which represents a complete map of the network.
5. Run the Shortest Path First ($\text{SPF}$) Algorithm: With the complete map, each router runs the $\text{SPF}$ ($\text{Dijkstra's}$) algorithm, placing itself at the root of a tree and calculating the shortest path to every other node and network. The result is a complete tree of the best routes.
6. Populate the Routing Table: From the calculated shortest-path tree, the router extracts the best paths and installs them into its routing table.

When a network change occurs (e.g., a link fails), only the routers directly affected by the change create and flood a new LSP. All other routers receive the update, modify their maps, and rerun the $\text{SPF}$ algorithm. This results in much faster convergence than with Distance Vector. Prominent protocols using this algorithm are $\text{OSPF}$ ($\text{Open Shortest Path First}$) and $\text{IS-IS}$.

Path Vector: Routing by Policy

The third major algorithm family, Path Vector, is designed for a completely different scale: the entire global internet. When routing between massive, independently managed networks called Autonomous Systems (AS), the "best" path is often defined not by the lowest metric, but by business relationships, security concerns, and political policies.

How It Works: Advertising the Full Path

The Path Vector algorithm is a modification of Distance Vector, but with a critical enhancement:

• Instead of just advertising a destination and a distance metric, routers advertise the destination network along with the entire path of AS numbers that the route traverses.
• For example, a router in AS 1 might advertise to its neighbor in AS 2: "I can reach Network Z via the path (AS 1)."
• AS 2 then advertises to its neighbor in AS 3: "I can reach Network Z via the path (AS 2, AS 1)."

Built-in Loop Prevention and Policy Control

This simple mechanism provides two powerful features:

1. Robust Loop Prevention: Loop detection is trivial. If a router receives a route update and sees its own AS number already in the path list, it knows the route is a loop and immediately discards it. This completely avoids the "counting to infinity" problem.
2. Policy-Based Routing: Because the full path is known, administrators can apply rules (policies) to influence routing decisions based on business logic rather than just a simple metric. For instance:
   • "Do not accept routes that pass through my competitor's AS."
   • "Prefer routes learned from my primary transit provider over my backup."
   • "Do not announce my internal customer networks to other transit providers."

Decision-making is based on a complex set of path attributes, not just a single cost value. The only protocol that uses this algorithm is $\text{BGP}$ ($\text{Border Gateway Protocol}$), the routing protocol of the Internet.