in C or c++ Implement distributed Distance Vector and Link State routing algorit
ID: 3709737 • Letter: I
Question
in C or c++ Implement distributed Distance Vector and Link State routing algorithms. Randomly generate a connected weighted graph and then apply the distributed Distance Vector and Link State algorithms to find the shortest path between any two nodes. If there is a tie, you can randomly choose one path. We assume there are at most 10 nodes and the weight on each edge is randomly chosen between 1 and 10. The inputs are the weighted graph and a source and a destination. And the outputs are the source, intermediate nodes, the destiantion, and the shorted path length. You will get extra 10 points if your weighted graph is automatically generated. Also, print out all the shortest paths when multiple shortest paths exist from a source to a destination. Distance Vector Algorithm Each node maintains a vector of distances and next hops to all destinations 1. Initialize vector with 0 cost to self, infinity to other destinations 2. Periodically send vector to neighbors 3. Update vector for each destination by selecting the shorted distance heard, after adding cost of neighbor link 4. Use the best neighbor for forwarding Link State Algorithm 1. Nodes flood topology with link state packets Each node learns full topology 2. Each node computes its own forwarding table By running Dijkstra algorithm
Explanation / Answer
Distance vector algorithm:
#include<stdio.h>
#include<iostream>
using namespace std;
struct node
{
unsigned dist[6];
unsigned from[6];
}DVR[10];
int main()
{
cout<<" DISTANCE VECTOR ROUTING ALGORITHM ";
int costmat[6][6]; // Assuming there are maximum 6 nodes
int nodes, i, j, k;
cout<<" Enter the number of nodes : ";
cin>>nodes; //Enter the nodes
cout<<" Enter the cost matrix : " ;
for(i = 0; i < nodes; i++)
{
for(j = 0; j < nodes; j++)
{
cin>>costmat[i][j];
costmat[i][i] = 0;
DVR[i].dist[j] = costmat[i][j]; //initialise the distance equal to cost matrix
DVR[i].from[j] = j;
}
}
for(i = 0; i < nodes; i++) //We choose arbitary vertex k and we calculate the
//direct distance from the node i to k using the cost matrix and add the distance from k to node j
for(j = i+1; j < nodes; j++)
for(k = 0; k < nodes; k++)
if(DVR[i].dist[j] > costmat[i][k] + DVR[k].dist[j])
{ //We calculate the minimum distance
DVR[i].dist[j] = DVR[i].dist[k] + DVR[k].dist[j];
DVR[j].dist[i] = DVR[i].dist[j];
DVR[i].from[j] = k;
DVR[j].from[i] = k;
}
for(i = 0; i < nodes; i++)
{
cout<<" For router: "<<i+1;
for(j = 0; j < nodes; j++)
cout<<" node "<<j+1<<" via "<<DVR[i].from[j]+1<<" Distance "<<DVR[i].dist[j];
}
cout<<" ";
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.