Distance Vector Algorithm
Distance Vector Algorithm is a decentralized routing algorithm that requires that each
router simply inform its neighbors of its routing table. For each network path, the receiving
routers pick the neighbor advertising the lowest cost, then add this entry into its routing table for
re-advertisement. To find the shortest path, Distance Vector Algorithm is based on one of two
basic algorithms: the Bellman-Ford and the Dijkstra algorithms.
Routers that use this algorithm have to maintain the distance tables (which is a one-
dimension array -- "a vector"), which tell the distances and shortest path to sending packets to
each node in the network. The information in the distance table is always updated by exchanging
information with the neighboring nodes. The number of data in the table equals to that of all
nodes in networks (excluded itself). The columns of table represent the directly attached
neighbors whereas the rows represent all destinations in the network. Each data contains the path
for sending packets to each destination in the network and distance/or time to transmit on that
path (we call this as "cost"). The measurements in this algorithm are the number of hops, latency,
the number of outgoing packets, etc.
The starting assumption for distance-vector routing is each node knows the cost of the
link of each of its directly connected neighbors. Next, every node sends a configured message to
its directly connected neighbors containing its own distance table. Now, every node can learn
and update its distance table with cost and next hops for all nodes network. Repeat exchanging
until no more information between the neighbors.
Consider a node A that is interested in routing to destination H via a directly attached
neighbor J. Node A's distance table entry, Dx(Y,Z) is the sum of the cost of the direct-one hop
link between A and J, c(A,J), plus neighboring J's currently known minimum-cost path (shortest
path) from itself(J) to H. That is
Dx(H,J) = c(A,J) + minw{Dj(H,w)} The minw is taken over all the J's
This equation suggests that the form of neighbor-to-neighbor communication that will take place
in the DV algorithm - each node must know the cost of each of its neighbors' minimum-cost path
to each destination. Hence, whenever a node computes a new minimum cost to some destination,
it must inform its neighbors of this new minimum cost.
Figure (a) A subnet. (b) Input from A, I, H, K, and the new routing table for J.
Implementation Algorithm:
1. send my routing table to all my neighbors whenever my
link table changes
2. when I get a routing table from a neighbor on port P with
link metric M:
a. add L to each of the neighbor's metrics
b. for each entry (D, P', M') in the updated neighbor's
table:
i. if I do not have an entry for D, add (D, P, M') to
my routing table
ii. if I have an entry for D with metric M", add (D,
P, M') to my routing table if M' < M"
3. if my routing table has changed, send all the new entries
to all my neighbors.
4. Write a program for distance vector algorithm to find suitable path for
transmission
#include<stdio.h>
#include<stdlib.h>
int d[10][10],via[10][10];
int main()
{
int i,c,j,k,n,m,cost,g[10][10],temp[10][10],ch,count;
system("c");
printf("\n enter the number of nodes:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\n enter the record for router %c:\n",i+97);
for(j=0;j<n;j++)
{
printf("(%c:%c)::",i+97,j+97);
scanf("%d",&g[i][j]);
if(g[i][j]!=999)
d[i][j]=1;
}
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
temp[i][j]=g[i][j];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
for(k=0;k<n;k++)
via[i][k]=i;
do
{
count=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
for(k=0;k<n;k++)
if(g[i][j]+g[j][k]<g[i][k])
{
g[i][k]=g[i][j]+g[j][k];
via[i][k]=j;
count++;
}
}while(count!=0);
for(i=0;i<n;i++)
{
printf("cost table of router %c:\n",i+97);
for(j=0;j<n;j++)
printf("%c:%d via %c \n",j+97,g[i][j],via[i][j]+97);
}
}
OUTPUT:
Enter the number of nodes: 4
Enter the record for router a:
(a:a)::0
(a:b)::2
(a:c)::3
(a:d)::8
Enter the record for router b:
(b:a)::2
(b:b)::0
(b:c)::999
(b:d)::5
Enter the record for router c:
(c:a)::3
(c:b)::999
(c:c)::0
(c:d)::4
Enter the record for router d:
(d:a)::8
(d:b)::5
(d:c)::4
(d:d)::0
cost table of router a:
a:0 via a
b:2 via a
c:3 via a
d:7 via b
cost table of router b:
a:2 via b
b:0 via b
c:5 via a
d:5 via b
cost table of router c:
a:3 via c
b:5 via a
c:0 via c
d:4 via c
cost table of router d:
a:7 via b
b:5 via d
c:4 via d
d:0 via d
