sivaramaiah  
 
  LinkStateRouting 09/20/2017 9:48pm (UTC)
   
 

 

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    |

LINK STATE PACKET FOR 2

|-------------|

|   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

 

 

 

 

 
  Menu Items
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

  add
HOT TOPICS
MCA PROJECT DETAILS ------------------------------------- Jntu all Lab manuals ------------------------------------- Jntu Syllabus Books ------------------------------------- Paper presentations ------------------------------------- Seminars ------------------------------------- Campus Papers ------------------------------------- Competetive Exams GATE ------------------------------------- GRE ------------------------------------- TOEFL ------------------------------------- IELTS ------------------------------------- CAT ------------------------------------- GMAT ------------------------------------- Templates ------------------------------------- Students Resume Preparation tips ------------------------------------- Job zone(Interview questions) ------------------------------------- Google Adsence html code ------------------------------------- Web sites --------x--------------x-----------
  Advertisement
  Advertisement

 


-----------------------------
  Offline Messages
  Adds
  Visitors Information
Today, there have been 66440 visitors (187983 hits) on this page!
=> Do you also want a homepage for free? Then click here! <= --------------------------------------------------