DV Algorithms

DV algorithms are also known as Bellman-Ford routing algorithms and Ford-Fulkerson routing algorithms. In these algorithms, every router has a routing table that shows it the best route for any destination. A typical graph and routing table for router J is shown below.


Destination
Weight
Line
A
8
A
B
20
A
C
28
I
D
20
H
E
17
I
F
30
I
G
18
H
H
12
H
I
10
I
J
0
---
K
6
K
L
15
K

A typical network graph and routing table for router J

As the table shows, if router J wants to get packets to router D, it should send them to router H. When packets arrive at router H, it checks its own table and decides how to send the packets to D.

In DV algorithms, each router has to follow these steps:

  1. It counts the weight of the links directly connected to it and saves the information to its table.
  2. In a specific period of time, it send its table to its neighbor routers (not to all routers) and receive the routing table of each of its neighbors.
  3. Based on the information in its neighbors' routing tables, it updates its own.
One of the most important problems with DV algorithms is called "count to infinity." Let's examine this problem with an example:

Imagine a network with a graph as shown below. As you see in this graph, there is only one link between A and the other parts of the network. Here you can see the graph and routing table of all nodes:


A
B
C
D
A
0,-
1,A
2,B
3,C
B
1,B
0,-
2,C
3,D
C
2,B
1,C
0,-
1,C
D
3,B
2,C
1,D
0,-

Network graph and routing tables

Now imagine that the link between A and B is cut. At this time, B corrects its table. After a specific amount of time, routers exchange their tables, and so B receives C's routing table. Since C doesn't know what has happened to the link between A and B, it says that it has a link to A with the weight of 2 (1 for C to B, and 1 for B to A -- it doesn't know B has no link to A). B receives this table and thinks there is a separate link between C and A, so it corrects its table and changes infinity to 3 (1 for B to C, and 2 for C to A, as C said). Once again, routers exchange their tables. When C receives B's routing table, it sees that B has changed the weight of its link to A from 1 to 3, so C updates its table and changes the weight of the link to A to 4 (1 for C to B, and 3 for B to A, as B said).

This process loops until all nodes find out that the weight of link to A is infinity. This situation is shown in the table below. In this way, experts say DV algorithms have a slow convergence rate.

B
C
D
Sum of weight to A after link cut
,A
2,B
3,C
Sum of weight to B after 1st updating
3,C
2,B
3,C
Sum of weight to A after 2nd updating
3,C
4,B
3,C
Sum of weight to A after 3rd updating
5,C
4,B
5,C
Sum of weight to A after 4th updating
5,C
6,B
5,C
Sum of weight to A after 5th updating
7,C
6,B
7,C
Sum of weight to A after nth updating
...
...
...

The "count to infinity" problem

One way to solve this problem is for routers to send information only to the neighbors that are not exclusive links to the destination. For example, in this case, C shouldn't send any information to B about A, because B is the only way to A.