Distance Vector Protocols: The Bellman-Ford Algorithm
The goal of Distance vector protocols is to build the shortest path from one vertex to all the other vertices, just like the Link State protocols.
The basic concept of a distance vector protocol is to build a distance vector that contains the shortest path from the source Vertex to each destination Cd (d from 1 to n, the number of destinations ). It’s a set of distances from a router to all the other routers in the topology.
The best path to each destination is called least cost path. We will use the terms “metric” and “cost” interchangeably. We also refer to “least cost path” or “shortest path” interchangeably”
Also we define “neighbors” as routers directly connected to each other.
Routing information is exchanged locally, i.e. between neighbors. Each router starts by learning about its neighbors, then the neighbors of its neighbors, etc.
The most common distance vector algorithm used in Distance Vector protocols is Bellman-Ford. The Bellman-Ford algorithm is a distributed algorithm that belongs to the family of Shortest Path routing algorithms. It requires few computations on routers.
How the Bellman-Ford protocol algorithm works
Initially, it is assumed that each router knows the cost of its connected links.
Each router builds the distance vector. For his neighbors, the least cost path to them equals the link cost. For non-neighboring routers, the path is initially set to the infinity ∞.
Each router sends its distance vector to its neighbors only. Whenever a router receives from its neighbor a new least path cost to a destination Y, it updates its route to Y with the advertised cost, plus the local link cost. Notice here that a router does not compare the cost of the path received against the path it already has in its distance vector. What this means is, even if router A has a “better” route to Y and still receives an update from its neighbor to Y, it updates its distance vector anyway.
Whenever a connected link fails, the router updates its least cost paths that involve that link and send the updated distance vector to its neighbors.
The algorithm is iterated many times before the network converges. Convergence -in the case of the RIP protocol- occurs when the longest loop-free path to the destination is explored (the longest loop-free path is the path with the most number of hops without forming a loop). But the maximum number of iterations -in normal conditions- is equal to the number of vertices -or routers- participating in the algorithm, minus 1. At this number of iterations we are sure that the algorithm converges:
Max_iter = nb_vertices – 1
A more mathematical approach to how the Bellman-ford algorithm works can be found in the videos below.
Problems with the Bellman-Ford algorithm
The Bellman-Ford algorithm is not as fancy as it seems to be. Have a failure at one link and problems could appear.
Remember what I said ealier about the maximum number of iterations? the Max_iter value is true under normal conditions, which means when there is no link failure.
Let’s say we have three routers R1, R2 and R3 linked in a linear fashion.
Let’s suppose the protocol has converged. All routers are regularly exchanging their distance vectors. This can be either synchronous or asynchronous. When the Bellman Ford algorithm works in a synchronous fashion, all routers send their distance vectors at the same time. And when it works in an asynchronous fashion, the sending of the distance vectors occurs at different times.
Back to the topology. Let’s suppose the link between R2 and R3 fails. R2 no longer can reach R3 through that link. At the next iteration of the Bellman Ford algorithm, R1 sends to R2 its distance vector containing a route to R3 through R2. R2 receives it and installs the route to R3 through R1.
At the next iteration of the algorithm, R1 will learn a new route to R3 through R2 but with a higher cost. It simply installs the routing update. The cost of the route to R3 is then the metric of the R1-R2 link plus the metric of the route received from R2.
Now R2 learns from R1 that R3 is still reachable. So at R2, the cost to reach R3 is the metric of the R2-R1 link plus the metric of the route received from R1.
And the cycle continues.
We see that the Count-to-Infinity problem has nothing to do with the physical topology. In fact, we don’t have a physical loop here and yet a Count-to-Infinity problem rose.
This will lead to:
- a routing loop between R1 and R2: to reach R3, R1 must go through R2, and to reach R3 R2 must go through R1
- R1 and R2 having routes to R3 with an ever increasing metric value, until the IP TTL value expires.
This is called the count-to-infinity problem.
Here is another example where removing a link could cause the count-to-infinity problem. Initially all links are up. The network is as follows:
And the routing table at each router
Let’s suppose that link R2-R3 goes down:
A new iteration of the algorithm gives the following:
- the router has a direct link to R2. Nothing happens.
- R1 has a high-cost link to R3 (100), which it never chooses. So R1 preserves the previous route to R3 (a route of cost 2).
- the router has a direct link to R1 –> nothing changes for the cost of the route to R1.
- Since R2-R3 link is down, R2 needs to learn a new route to R3. R2 receives an update from R1 which knows how to reach R3.
- The cost for R2 to reach R1 is 1,
- The cost for R1 to reach R3 is 2
–> The cost for R2 to reach R3 is 1+2 = 3.
- R3 has a direct high-cost link to R1, which it never chooses
- R3 link to R2 is broken. So it needs another route to reach R2. R3 receives an update from R1 stating that, in order to reach R2 we can go through R1. So
- cost from R3 to R1: 2
- cost form R1 to R2: 1
- –> The cost from R3 to R2 is 2 + 1 = 3
- R1 used to reach R3 with a cost of 2. Now that R2-R3 link is down, R1 must go through R2.
- R1 recieves an update from R2. In this update, it is mentioned that the cost to reach R3 through R2 is 3. So:
- cost from R1 to R2: 1
- cost from R2 to R3: 3
- –> cost from R1 to R3 = 1 + 3 = 4. The path has a higher cost than before, but still it is cheaper than the direct link from R1 to R3. So it takes it.
- Similarly, R3-R1 link has a high cost. R3 looks for a better path from itself to R1. It has a route to R1 through R2:
- cost from R3 to R2: 3
- cost from R2 to R1: 1
- –> cost from R3 to R1: 3 + 1 = 4
This process continues until we have an alternate path that has a cost equal or greater to 100.
If we increase the cost of the R1-R3 link this will enhance the issue. The algorithm will converge only when the cost of an alternate path between R1 and R3 (through R2) is equal or greater to the cost of the direct link. However, reducing it helps the algorithm converge a little earlier.
Solutions to the Count-to-Infinity problem
There are many possible solutions.
Defining the infinity
One solution is to define the infinity as a small integer, such as 16. So whenever a route has a metric of 16, it will be discarded
The purpose of Split Horizon is to prevent the propagation of reverse routes. A reverse route is when a router A receives an update about network X from router B over an interface i, and router A sends back an update about network X to router B over the same interface i.
What Split Horizon does is when a router A receives an update about a route X from a router B over an interface i, router A will not send back an update about the same route over the interface i. So Split Horizon works by suppressing selected updates.
Split Horizon does not completely solve the problem because there still can be routing loops. Look at this figure:
Let’s assume, for some reason, router B did not learn about network 10.1.1.0 from router A, but learned it from router C. However, router C has a route to 10.1.1.0 via router B. This leads to a routing loop.
Split Horizon with Poison Reverse
Split Horizon with Poison Reverse builds on Split Horizon, but in addition it marks the network as unreachable (∞).
Example of the Count-to-infinity problem in RIP
The following video demonstrates the result of deactivating Split Horizon in a RIP environment, to see the count-to-infinity problem.
RIP, Carnegie Mellon University
Routing And Addressing I, North Western University
Routing TCP/IP Volume 1