Distributed Asynchronous Distance Vector Routing


Table of Contents
1. Introduction
2. General Idea
3. rtupdate
4. References
5. Source Code
6. Sample Output


1. Introduction
The purpose of this document is to document my design choices when implementing the Distributed Asynchronous Distance Vector Routing program. The discussion will be split five two parts. The first part will summarize the general idea of the program, the second part will discuss the rtinit() method, the third part with discuss rtupdate(), the fourth part will describe tests administered to ensure that the program was producing the right output, and finally the last part will display references. Within Part 2 and Part 3, I also will explain my design choices, the design alternatives and possible improvements. The source code and sample outputs are at the very end.

2. General Idea
There are four nodes in this system. Each node has a method called rtinit() that initialized their distance table. After the distance table is initialized, a packet is created and its mincost is set. The packet is then sent to the corresponding node's directly connected neighbors. When a node receives a packet, the node's rtupdate routine is called. The packet it receives contains the shortest paths to all other network nodes from the packet's sourceID. These values are used to update the current node's values. If the current node's values changes, then the node will create a packet with the current min costs set, and send the packet to its directly connected neighbors.

Since node0, node1, node2, and node3 have similar codes, for simplicity, I will talk in terms of node0.
Part 2: rtinit()
I first create a new pointer, lets call it node0, to the distance_table to be used later on in the method. I then set the cost of the distance table to its default value-- infinity also known as 999 in this program-- within two for loops. Packet0's, a global object that is create, mincost is also set 999. In another loop, I updated the distance table with the distances from the current node to each of its directly connected neighbors (the distances to its neighbors are taken from the graph displayed on the assignment page and it is stored in an array in each node class called node0_dist). After this is done, the cost of the distance table is compared to the mincost of the packet. If the cost in the distance table is smaller (which it should be since all mincost of the packet is set to infinity), then we update the packet's mincost at the current index we are looking at to the value of the distance table at the current index. The updated packet is then sent to all directly connected neighbors.


3. rtupdate
Like in rtinit(), I create a pointer to the distance_table object in the beginning of this method. I also initialized a boolean called update that will be used later to determine if the distance table have been updated or not. Next, I create a new int that is equal to the received packet's (from the parameter) sourceID. The clock time is then printed out. Next, I create a new int array of size 4, which is called dist0 in node0.c (dist1 in node1.c, dist2 in node2.c etc..). Each entry is set to be 999 (infinity). I then equal the value of the distance table to the sum the mincost of the packet0 (which was globally created) at the index of the sourceID with the mincost of the received packet at the current index (line 92). I update the new int I created previously with the updated cost in the distance table. Next I compare the value of the int array (dist0) with the mincost of packet0. If the value in the value of the int array is less than the mincost at the same index, then the min cost is set to equal the value at dist0. I then set the boolean I created in the beginning of the method to true. Finally, if the boolean is set to true, then packet0 is sent out to the current node's directly connected neighbors.

Improvements:
This method runs slowly-- this is because it uses several for loops. Therefore, on a much larger system, the program will not run very efficiently. Other techniques will have to be devised to reduce computational time of this method. One technique that might work is to make the node class an object/struct that takes in parameters. Therefore, when we create node0, node1, node2, and node3, we can simply create a new node struct and pass in the node's corresponding intial distance distance values (i.e the array node_dist). This will greatly reduce the number of code.

Design Choices:
In this method, I chose to create a new integer array, dist0[4], to copy and store the minimum path from the distance table. I did this so I can compare dist0 to packet0 later on to set packet0's mincost and to determine if there is an update in the distance table. I could have simply just compared the values from the distance table with packet0, but since packet0.mincost is a 1D array, I decided for my understanding, I will compare packet0 to another 1D array.


4. References: 
Booleans in C: http://cboard.cprogramming.com/c-programming/109520-bool-c.html


5. Source Code:*
* only the source for node0 and node1 will be show since node2 and node4 are very similar.
** Starter Code

node0.c

#include 
#include 

extern struct rtpkt {
  int sourceid;       /* id of sending router sending this pkt */
  int destid;         /* id of router to which pkt being sent 
                         (must be an immediate neighbor) */
  int mincost[4];    /* min cost to node 0 ... 3 */
  };

extern int TRACE;
extern int YES;
extern int NO;

struct distance_table 
{
  int costs[4][4];
} dt0;

/* students to write the following two routines, and maybe some others */

struct distance_table dt0; //initilize table 

struct rtpkt packet0; //initilize packet
int node0_dist[]={0,1,3,7}; //initial distance values of the system
int id0=0; //ID value of the node. node0 = 0

void rtinit0() {

  //a pointer to the address of the distance table
  struct distance_table *node0 = &dt0;

  //filling up tables with default mincost: inifinity 
  int x, y;
  for(x=0; x<4; x++){
    for(y=0; y<4; y++)
      node0->costs[x][y]=999; //default min value
  }

  //filling in table with inital distances
  int i;
  for (i=0; i<4; i++){
    node0->costs[i][i]= node0_dist[i];
    packet0.mincost[i]=999; //set to default value
  }

  //set packet.min cost to the values in distance table
  int j,k;
  for(j=0; j<4; j++){
    for (k=0; k<4; k++){
      //compares the cost in the table with packet0.mincost
      //only set the values of packet if the values in table is less
      if(node0->costs[j][k]costs[j][k]; 
    }
  }

  //notifying directly connected neighbors
  int z;
  for (z=1; z<4; z++){ //to node 1, 2, 3
    packet0.sourceid=id0; //defines source ID
    packet0.destid = z; //defines destination ID
    tolayer2(packet0); //sends
  }
  printdt0(node0); //prints table
}

void rtupdate0(rcvdpkt)
  struct rtpkt *rcvdpkt;
{ 
  bool update=false; //boolean that determines if the distance table has been updated
  struct distance_table *node0 = &dt0; //pointer to distance table

  //Node that sent packet
  int packet_from = rcvdpkt->sourceid; //get source ID of received packet
  printf("Node %d Received a packet from Node %d \n", id0, packet_from);

  //clocktime
  extern float clocktime; //prints out clocktime
  printf("Clocktime rtupdate0: %f\n node %d\n", clocktime, packet_from);
  printf("\n");printdt0(&dt0); //prints table

  //Update min cost for node that sent packet
  int dist0[4]; //create new integer array 
  int i;
  for (i=0; i<4; i++){
    dist0[i]=999; //set interger array to default mincost value "999"
    
    /*Sums the min cost from packet0 at the index of the received packet with 
    the mincost at the current index of the received packet*/
    int sum=packet0.mincost[packet_from]+rcvdpkt->mincost[i];
    if(sum<=999) //just in case-- not necessary
      node0->costs[i][packet_from]= sum; //update the distance table with value
  }

  //finding minimum path
  int j,k;
  for(j=0; j<4; j++)
    for(k=0; k<4; k++)
      if(node0->costs[j][k]costs[j][k]; //we update dist0's values
        printf("\nNew minimum path from node %d to %d through %d with value %d",id0,j,packet_from,dist0[j]);
      }
      printf("\n");
      printdt0(node0); //print table

  int a;
  for (a=0; a<4; a++)
    if(dist0[a]costs[1][1],
	 dtptr->costs[1][2],dtptr->costs[1][3]);
  printf("dest 2|  %3d   %3d   %3d\n",dtptr->costs[2][1],
	 dtptr->costs[2][2],dtptr->costs[2][3]);
  printf("     3|  %3d   %3d   %3d\n",dtptr->costs[3][1],
	 dtptr->costs[3][2],dtptr->costs[3][3]);
}

linkhandler0(linkid, newcost)   
  int linkid, newcost;

/* called when cost from 0 to linkid changes from current value to newcost*/
/* You can leave this routine empty if you're an undergrad. If you want */
/* to use this routine, you'll need to change the value of the LINKCHANGE */
/* constant definition in prog3.c from 0 to 1 */
	
{
}


node1.c

#include 
#include 
#include 

extern struct rtpkt {
  int sourceid;       /* id of sending router sending this pkt */
  int destid;         /* id of router to which pkt being sent 
                         (must be an immediate neighbor) */
  int mincost[4];    /* min cost to node 0 ... 3 */
  };

extern int TRACE;
extern int YES;
extern int NO;

int node1_dist[]= { 1,  0,  1, 999 };

struct distance_table 
{
  int costs[4][4];
} dt1;


/* students to write the following two routines, and maybe some others */
struct distance_table dt1; //initilize table 

struct rtpkt packet1; //initilize packet

int id1=1;

rtinit1() {
  struct distance_table *node1 = &dt1;

  int x, y;
  for(x=0; x<4; x++){
    for(y=0; y<4; y++)
      node1->costs[x][y]=999;
  }

  int i;
  for (i=0; i<4; i++){
    node1->costs[i][i]= node1_dist[i];
    packet1.mincost[i]=999; 
  }

  int j, k;
  for(j=0; j<4; j++){
    for (k=0; k<4; k++){
      //finds min cost
      if(node1->costs[j][k]costs[j][k];
    }
  }

  int z;
  for (z=1; z<4; z++){ //to 1, 2, 3
    packet1.sourceid=id1;
    packet1.destid = z;
    tolayer2(packet1);
  }
  printdt1(node1);
}


rtupdate1(rcvdpkt)
  struct rtpkt *rcvdpkt;
  
{
  bool update=false;
  struct distance_table *node1 = &dt1;

  int packet_from = rcvdpkt->sourceid;
  printf("Node %d Received a packet from Node %d \n", id1, packet_from);

  //clocktime
  extern float clocktime;
  printf("Clocktime rtupdate0: %f\n node %d\n", clocktime, packet_from);
  printf("\n");printdt1(&dt1);

  int dist1[4];
  int i;
  for (i=0; i<4; i++){
    int sum=packet1.mincost[packet_from]+rcvdpkt->mincost[i];
    if(sum<=999){
      node1->costs[i][packet_from]= packet1.mincost[packet_from]+rcvdpkt->mincost[i];
      dist1[i]=999; 
    }
    else {
      node1->costs[i][packet_from]= 999;
      dist1[i]=999; 
    }
  }

  int j,k;
  for(j=0; j<4; j++)
    for(k=0; k<4; k++)
      if(node1->costs[j][k]costs[j][k];
        printf("\nNew minimum path from node %d to %d through %d with value %d",id1,j,packet_from,dist1[j]);
      }
      printf("\n");
      printdt1(node1);

  int a;
  for (a=0; a<4; a++)
    if(dist1[a]costs[0][0], dtptr->costs[0][2]);
  printf("dest 2|  %3d   %3d\n",dtptr->costs[2][0], dtptr->costs[2][2]);
  printf("     3|  %3d   %3d\n",dtptr->costs[3][0], dtptr->costs[3][2]);

}

linkhandler1(linkid, newcost)   
int linkid, newcost; 
	
{
}