Computer Networks: Distance-vector routing protocol

A distance-vector routing protocol in data networks determines the best route for data packets based on distance. Distance-vector routing protocols measure the distance by the number of routers a packet has to pass, one router counts as one hop.

Some distance-vector protocols also take into account network latency and other factors that influence traffic on a given route.

To determine the best route across a network, routers, on which a distance-vector protocol is implemented, exchange information with one another, usually routing tables plus hop counts for destination networks and possibly other traffic information.

Distance-vector routing protocols also require that a router informs its neighbors of network topology changes periodically.

The Distance vector algorithm is iterative, asynchronous and distributed.

Distributed: It is distributed in that each node receives information from one or more of its directly attached neighbors performs calculation and then distributes the result back to its neighbors.
Iterative: It is iterative in that its process continues until no more information is available to be exchanged between neighbors.
Asynchronous: It does not require that all of its nodes operate in the lock step with each other.

Three Keys to understand the working of Distance Vector Routing Algorithm:

Knowledge about the whole network: Each router shares its knowledge through the entire network. The Router sends its collected knowledge about the network to its neighbors.
Routing only to neighbors: The router sends its knowledge about the network to only those routers which have direct links. The router sends whatever it has about the network through the ports. The information is received by the router and uses the information to update its own routing table.
Information sharing at regular intervals: Within 30 seconds, the router sends the information to the neighboring routers.

Let d_x(y) be the cost of the least-cost path from node x to node y. The least costs are related by Bellman-Ford equation,

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

Where the min_v is the equation taken for all x neighbors. After traveling from x to v, if we consider the least-cost path from v to y, the path cost will be c(x,v)+d_v(y). The least cost from x to y is the minimum of c(x,v)+d_v(y) taken over all neighbors.

With the Distance Vector Routing algorithm, the node x contains the following routing information:

For each neighbor v, the cost c(x,v) is the path cost from x to directly attached neighbor, v.
The distance vector x, i.e., D_x = [ D_x(y) : y in N ], containing its cost to all destinations, y, in N.
The distance vector of each of its neighbors, i.e., D_v = [ D_v(y) : y in N ] for each neighbor v of x.

Distance vector routing is an asynchronous algorithm in which node x sends the copy of its distance vector to all its neighbors. When node x receives the new distance vector from one of its neighboring vector, v, it saves the distance vector of v and uses the Bellman-Ford equation to update its own distance vector. The equation is given below:

d_x(y) = min_v{ c(x,v) + d_v(y)} for each node y in N

The node x has updated its own distance vector table by using the above equation and sends its updated table to all its neighbors so that they can update their own distance vectors.

In distance vector routing, the least-cost route between any two nodes is the route with minimum distance. In this protocol, as the name implies, each node maintains a vector (table) of minimum distances to every node.

Initialization:

At the beginning, each node can know only the distance between itself and its immediate neighbors, those directly connected to it.

Assume that each node can send a message to the immediate neighbors and find the distance between itself and these neighbors. The distance for any entry that is not a neighbor is marked as infinite (unreachable).

In distance vector routing, each node shares its routing table with its immediate neighbors periodically and when there is a change.

Updating:

When a node receives a two-column(next column is not necessary) table from a neighbor, it needs to update its routing table.

Updating takes three steps:

1. The receiving node needs to add the cost between itself and the sending node to each value in the second column.

The logic is clear. If node C claims that its distance to a destination is x , and the distance between A and C is y , then the distance between A and that destination, via C, is x + y.

2. The receiving node needs to add the name of the sending node to each row as the third column if the receiving node uses information from any row. The sending node is the next node in the route.

3. The receiving node needs to compare each row of its old table with the corresponding row of the modified version of the received table.

a. If the next-node entry is different, the receiving node chooses the row with the smaller cost. If there is a tie, the old one is kept.

b. If the next-node entry is the same, the receiving node chooses the new row.

For example, suppose node C has previously advertised a route to node X with distance 3. Suppose that now there is no path between C and X; node C now advertises this route with a distance of infinity. Node A must not ignore this value even though its old entry is smaller. The old route does not exist anymore. The new route has a distance of infinity.

When D sends table to E: