LINK STATE ROUTING ALGORITHM
#include<stdio.h>
#include<conio.h>
#define LIMIT 10
#define INFINITY 10000
int m,n,k,i,j,dist[LIMIT][LIMIT],sn,dn,min=0;
struct node
{
int hello[LIMIT],from,adj[LIMIT];
}node[LIMIT];
main()
{
clrscr();
printf("Enter how many nodes do u want::");
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
dist[i][j]=-1;
for(i=1;i<=n;i++)
{
printf("\nEnter distance for %d node:",i);
for(j=1;j<=n;j++)
if(dist[i][j]==-1)
if(i==j)
{
dist[i][j]=0;
printf(" 0");
}
else
{
scanf("%d",&m);
dist[i][j]=dist[j][i]=m;
}
else
printf(" %d",dist[i][j]);
}
printf("\nDistance matrix is:");
for(i=1;i<=n;i++)
{
printf("\n");
node[i].from=0;
for(j=1;j<=n;j++)
printf("\t%d",dist[i][j]);
}
printf("\nSENDING HELLO PACKETS");
for(i=1;i<=n;i++)
{
k=1;
for(j=1;j<=n;j++)
{
if(dist[i][j]>0)
node[i].from++;
if(dist[j][i]>0)
node[i].hello[k++]=j;
}
}
for(i=1;i<=n;i++)
{
printf("\nHello packets to node %d:",i);
for(j=1;j<=node[i].from;j++)
printf("\n%d",node[i].hello[j]);
}
printf("\nSENDING ECHO PACKETS");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
if(dist[i][j]>0)
printf("\nfrom %d to %d, the distance is:%d",i,j,dist[i][j]);
}
printf("\n CONSTRUCTION LINKSTATE PACKETS");
for(i=1;i<=n;i++)
{
printf("\nLINK STATE PACKET FOR %d",i);
printf("\n|-------------|");
printf("\n| %d |",i);
printf("\n|-------------|");
printf("\n| seq |");
printf("\n|-------------|");
printf("\n| Age |");
printf("\n|-------------|");
for(j=1;j<=n;j++)
if(dist[i][j]>0)
{
printf("\n| %d | %d |",j,dist[i][j]);
printf("\n|-------------|");
}
}
printf("\nDISTRIBUTING THE LINK STATE PACKETS");
for(i=1;i<=n;i++)
{
printf("\nNeighbours for %d node are:",i);
for(j=1;j<=n;j++)
{
if(dist[i][j]>0)
printf("%d",j);
}
for(j=1;j<=node[i].from;j++)
{
printf("\n the distance from %d to ",i);
printf("%d is %d",node[i].hello[j],dist[i][node[i].hello[j]]);
}
}
printf("\nCOMPUTING THE SHORTEST PATH");
printf("\nEnter source and destination:");
scanf("%d%d",&sn,&dn);
min=spath(sn,dn,min);
printf("\n minimum distance:%d",min);
getch();
}
int spath(int s,int t,int min)
{
struct state
{
int pred;
int len;
enum{permanent,tentative}label;
}state[LIMIT];
int i=1,k;
struct state *p;
for(p=&state[i];p<=&state[n];p++)
{
p->pred=0;
p->len=INFINITY;
p->label=tentative;
}
state[t].len=0;
state[t].label=permanent;
k=t;
do
{
for(i=1;i<=n;i++)
if(dist[k][i]!=0 && state[i].label==tentative)
{
if(state[k].len+dist[k][i]<state[i].len)
{
state[i].pred=k;
state[i].len=state[k].len+dist[k][i];
}
}
k=0;
min=INFINITY;
for(i=1;i<=n;i++)
if(state[i].label==tentative && state[i].len<min)
{
min=state[i].len;
k=i;
}
state[k].label=permanent;
} while(k!=s);
return(min);
}
output
Enter how many nodes do u want::4
Enter distance for 1 node: 0 2 3 4
Enter distance for 2 node: 2 0 7 8
Enter distance for 3 node: 3 7 0 6
Enter distance for 4 node: 4 8 6 0
Distance matrix is:
0 2 3 4
2 0 7 8
3 7 0 6
4 8 6 0
SENDING HELLO PACKETS
Hello packets to node 1:
2 3 4
Hello packets to node 2:
1 3 4
Hello packets to node 3:
1 2 4
Hello packets to node 4:
1 2 3
SENDING ECHO PACKETS
from 1 to 2, the distance is:2
from 1 to 3, the distance is:3
from 1 to 4, the distance is:4
from 2 to 1, the distance is:2
from 2 to 3, the distance is:7
from 2 to 4, the distance is:8
from 3 to 1, the distance is:3
from 3 to 2, the distance is:7
from 3 to 4, the distance is:6
from 4 to 1, the distance is:4
from 4 to 2, the distance is:8
from 4 to 3, the distance is:6
CONSTRUCTION LINKSTATE PACKETS
LINK STATE PACKET FOR 1
|-------------|
| 1 |
|-------------|
| seq |
|-------------|
| Age |
|-------------|
| 2 | 2 |
|-------------|
| 3 | 3 |
|-------------|
| 4 | 4 |
|-------------|
| seq |
|-------------|
| Age |
|-------------|
| 1 | 2 |
|-------------|
| 3 | 7 |
|-------------|
| 4 | 8 |
|-------------|
LINK STATE PACKET FOR 3
|-------------|
| 3 |
|-------------|
| seq |
|-------------|
| Age |
|-------------|
| 1 | 3 |
|-------------|
| 2 | 7 |
|-------------|
| 4 | 6 |
LINK STATE PACKET FOR 4
|-------------|
| 4 |
|-------------|
| seq |
|-------------|
| Age |
|-------------|
| 1 | 4 |
|-------------|
| 2 | 8 |
|-------------|
| 3 | 6 |
|---------------| | 2 | 8 |
|-------------|
| 3 | 6 |
|-------------|
DISTRIBUTING THE LINK STATE PACKETS
Neighbours for 1 node are:234
the distance from 1 to 2 is 2
the distance from 1 to 3 is 3
the distance from 1 to 4 is 4
Neighbours for 2 node are:134
the distance from 2 to 1 is 2
the distance from 2 to 3 is 7
the distance from 2 to 4 is 8
Neighbours for 3 node are:124
the distance from 3 to 1 is 3
the distance from 3 to 2 is 7
the distance from 3 to 4 is 6
Neighbours for 4 node are:123
the distance from 4 to 1 is 4
the distance from 4 to 2 is 8
the distance from 4 to 3 is 6
COMPUTING THE SHORTEST PATH
Enter source and destination:2 3
minimum distance:5
This website was created for free with Own-Free-Website.com. Would you also like to have your own website?
