Distance Vector Routing Program In C
Introduction:
- One of the two main classes of routing protocols in the theory of computer communication pertaining to packet-switched networks is the distance-vector routing protocol. The other major class is the link-state routing protocol.
- The Bellman-Ford algorithm is used to determine pathways in a distance-vector routing system.
- According to a distance-vector routing protocol, a router must notify its neighbours of topology changes on a regular basis and, in some situations, as soon as a change in a network's topology is discovered.
- Distance-vector routing systems have less computational complexity and message overhead as compared to link-state protocols, which demand that a router notify every node in a network of topology changes.
- In contrast to link-nation protocols, which demand that a router notify all network nodes of topology changes, distance-vector routing techniques offer less message overhead and computational complexity.
- The firm Distance Vector provides routers as "vectors of distance and route". As opposed to distance, which is indicated by metrics like hop count, direction is expressed by the deal with of the subsequent hop and the go out interface.
Routers that utilise the distance vector protocol are not aware of the whole route to a destination. Rather, DV incorporates two techniques:
1. Which interface or in which direction a packet should be transmitted.
2. How far it is from the final destination.
Examples for Distance Vector Routing Program:
- Routing Information Protocol Version 1 & 2 (RIPv1 & RIPv2), IGRP, and RIPv1 & RIPv2 are some examples of distance-vector routing protocols.
- A distance-vector protocol creates routes based purely on link costs, whereas in EGP and BGP, for example, the local route priority value takes precedence over the link cost. This is why EGP and BGP are not real distance-vector routing protocols.
- All distance-vector routing protocols, including IGRP and the Routing Information Protocol Versions 1 and a pair, use distance matrices.
- In BGP, for instance, the local direction choosing price takes priority over the hyperlink cost, hence EGP and BGP aren't always distance-vector routing systems.
- Distance-vector protocols only take into consideration link costs when determining routes, therefore they aren't really distance-vector routing methods.
Distance Vector Algorithm:
Information stored by the DV router:
- Every router has a unique ID.
- A link cost (static or dynamic) is related to each link that is connected to a router.
- A middle level of hops
Initialization of the distance vector table:
- Distance from itself to itself is equal to 0.
- Distance from itself to EVERY other router is an infinite integer.
- A router sends a routing packet with its distance vector to each and every one of its neighbours.
- The most recent distance vector that a router has received from each of its neighbours is received and saved by each router.
- A router updates its distance vector if:
- It gets a new distance vector with different information from a neighbour.
- It finds that a connection to a nearby property has broken.
DV Calculation can be obtained as:
Dx(y) = Calculation of the least expensive route from x to y
C(x,v) = Each neighbor's cost is known by Node x.
Dx = [Dx(y): y ∈ N ] = Node x stores the distance vector.
Node x also keeps track of the distance vectors between its neighbours.
For each neighbour v, x keeps track of Dv = [Dv(y): y N]
NOTE:
A node x saves the distance vector of any neighbour v it receives new DV estimates from and it uses the B-F equation to update its own DV:
Dx(y) = min { C(x,v) + Dv(y), Dx(y) } for each and every node y ∈ N
Example for calculating the DV:
As seen in the figure, three routes are X, Y, and Z. Routing tables are unique to each router. Distances to the destination nodes are listed in each routing table.
![Distance Vector Routing Program In C](https://static.tutorialandexample.com/c/distance-vector-routing-program-in-c1.png)
Consider router X. X will share its routing table with neighbours, and neighbours will share their routing tables with X. The bellmen-ford equation will be used to determine the distance from node X to the destination.
Dx(y) = min { C(x,v) + Dv(y), Dx(y) } for each node y ∈ N
As we can see, when Y serves as an intermediate node (hop), the distance between X and Z will be reduced, causing the routing table X to be updated.
![Distance Vector Routing Program In C](https://static.tutorialandexample.com/c/distance-vector-routing-program-in-c2.png)
Similarly, Z also
![Distance Vector Routing Program In C](https://static.tutorialandexample.com/c/distance-vector-routing-program-in-c3.png)
The routing table for all is
![Distance Vector Routing Program In C](https://static.tutorialandexample.com/c/distance-vector-routing-program-in-c4.png)
C Program for implementing the Distance Vector Algorithm
#include<stdio.h>
struct node {
unsigned distance[20];
unsigned from[20];
}rt[10];
int main()
{
int dist_mat[20][20],n,i,j,k,count=0;
printf("\nEnter the number of nodes required: ");
scanf("%d",&n);
printf("\nEnter the cost matrix :\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++ )
{
scanf("%d",&dist_mat[i][j]);
dist_mat[i][i]=0;
rt[i].distance[j]=dist_mat[i][j];
rt[i].from[j]=j;
}
do
{
count=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
for(k=0;k<n;k++)
if(rt[i].distance[j]>dist_mat[i][k]+rt[k].distance[j])
{
rt[i].distance[j]=rt[i].distance[k]+rt[k].distance[j];
rt[i].from[j]=k;
count++;
}
}while(count!=0);
for(i=0;i<n;i++)
{
printf("\n\nState value for router %d is \n",i+1);
for(j=0;j<n;j++)
{
printf("\t\nnode %d via %d Distance%d",j+1,rt[i].from[j]+1,rt[i].distance[j]);
}
}
printf("\n\n");
}
OUTPUT:
![Distance Vector Routing Program In C](https://static.tutorialandexample.com/c/distance-vector-routing-program-in-c5.png)
Advantages of Distance Vector Routing:
It is less complicated to establish and maintain than link-state routing.
Disadvantages of Distance Vector Routing:
- Slower convergence compared to link-state routing.
- Changes to the hop count require more traffic to propagate to and process across all routers than changes to the link status.
- Hop counts are often updated even while the network topology does not, resulting in the continued occurrence of bandwidth-wasting broadcasts.
- Given that distance vector routing demands that every router be aware of every other router, a big network's routing table will be greater than its link state.
- Additionally, it could clog WAN connections.
Conclusion:
- A dynamic protocol is a distance vector routing.
- The distant vector routing algorithm finds the shortest path through the network. It is also referred to as the Ford Fulkerson or Bellman-Ford algorithms.
- The router distributes the data across the nearby nodes with direct links.
- The router uses algorithms to choose the most efficient path between the source and the destination.
- Each router in the network periodically exchanges its topology with the router next to it.