12.2 Distance Vector Routing

Distance Vector Routing

Distance vector routing is a method routers use to figure out the best paths through a network. Each router shares its routing table with its neighbors, and everyone uses that shared information to calculate shortest paths via the Bellman-Ford algorithm.

The approach is simple and fully distributed, but it comes with real trade-offs: slow convergence, routing loops, and the count-to-infinity problem can all cause issues, especially as networks grow.

Principles of Distance Vector Routing

In distance vector routing, no single router knows the full network topology. Instead, each router only knows two things: the cost to reach its direct neighbors, and what those neighbors have told it about their best paths. From that limited view, every router builds its own routing table.

• Each router maintains a routing table containing the best known distance to every destination (measured in a metric like hop count) and the next-hop router to get there.
• Routers periodically share their entire routing table with directly connected neighbors (e.g., every 30 seconds in RIP).
• When a router receives a neighbor's table, it checks whether any of those advertised paths offer a shorter route than what it currently has. If so, it updates its own table.
• This process repeats until all routers converge on consistent shortest-path information.

The "distance vector" name comes from exactly this: each router advertises a vector (a list) of distances to all known destinations.

Exchange of Routing Information

Routing updates are the mechanism that makes distance vector work. Here's how the exchange typically plays out:

1. A router packages its entire routing table into an update message.
2. It sends that message to all directly connected neighbors, usually via a protocol like RIP (Routing Information Protocol).
3. Each neighbor receives the update and compares every entry against its own table. For each destination, it asks: "Is this neighbor offering a shorter path than what I currently have?"
4. If a shorter path exists, the router updates its table with the new distance and sets that neighbor as the next hop.
5. This cycle repeats at regular intervals (every 30 seconds in RIP).

Beyond periodic updates, triggered updates are sent immediately when something changes, such as a link going down or a new router joining the network. Triggered updates help the network react faster than waiting for the next scheduled exchange.

Bellman-Ford Algorithm in Routing

The Bellman-Ford algorithm is the mathematical core of distance vector routing. Each router maintains a distance vector, which is simply a list of the shortest known distance to every destination in the network.

The key equation is:

$d_x(y) = \min_v \{ c(x,v) + d_v(y) \}$

• $d_x(y)$: the least-cost path from router $x$ to destination $y$
• $c(x,v)$: the cost of the direct link from $x$ to neighbor $v$
• $d_v(y)$: the shortest distance that neighbor $v$ has reported to destination $y$

In plain terms: to find the best path to $y$, router $x$ looks at each neighbor $v$ and adds the cost to reach $v$ plus whatever $v$ says its own best cost to $y$ is. The minimum across all neighbors wins.

How it converges step by step:

1. Each router initializes its distance vector: cost 0 to itself, infinity to all other destinations (unless directly connected).
2. Routers exchange distance vectors with their neighbors.
3. Upon receiving a neighbor's vector, each router recalculates its own distances using the equation above.
4. If any entry changes, the router sends its updated vector to its neighbors.
5. Steps 2-4 repeat until no router has anything new to report. At that point, the algorithm has converged.

Limitations of Distance Vector Routing

Distance vector routing's simplicity comes at a cost. These are the main problems you need to know:

Slow convergence. Because updates are periodic (e.g., every 30 seconds), changes in network topology can take multiple update cycles to propagate across the entire network. During this window, routers may have inconsistent views and forward packets along stale paths.

Routing loops. When topology changes, two or more routers can end up pointing at each other as the next hop for a destination, causing packets to bounce back and forth indefinitely until their TTL expires.

Count-to-infinity problem. This is the most well-known distance vector failure mode. When a destination becomes unreachable (say a link fails), routers don't immediately realize it. Instead, they keep advertising incrementally higher costs to each other, slowly "counting up" toward infinity. In RIP, infinity is defined as 16 hops, so the process eventually terminates, but it can take a long time and cause prolonged outages.

Scalability issues. Every router sends its entire routing table in each update. As the network grows, these tables get larger, consuming more memory and more bandwidth, even during periods when nothing has changed.

Limited metrics. Basic distance vector protocols like RIP use only hop count. A path with 2 hops through slow, congested links would be preferred over a 3-hop path through high-bandwidth links. More sophisticated metrics (bandwidth, delay, reliability) aren't considered unless the protocol is specifically designed for them.