About a decade ago I wrote some code for a computer communications project while at Uni. I thought I'd share the code with anyone out there who might need some reference for writing a program that emulates how routers discover neighbours using either - 1. Flooding Algorithm or 2. Link State. The network simulation program is CNet. The code was written in C.
Please do not forget to reference this page :) Thanks.
------------------------
FLOODING CODE
-------------------------
#include <cnet.h>
#include <stdlib.h>
#include <string.h>
/* The source code below demonstrate flooding and is
implemented according to the flooding routing
algorithm described in the textbook titled
"Computer Networks" 4th edition 2003, written by A. S.
Tanenbaum. The control mechanism used is source host
sequencing.
*/
typedef enum { PK_DATA, PK_ACK } PACKETKIND;
typedef enum { DST_PERTH=100, DST_SYDNEY=200 } DESTINAION;
const int SOURCE_NODE = 21;
const int DEST_NODE = 32;
int numOfMsgToTrsmt = 0;
unsigned long timeTransmitMsg = 0;
unsigned long timeReceiveAck = 0;
typedef struct {
char data[MAX_MESSAGE_SIZE];
} MSG;
typedef struct {
CnetAddr src_addr;
CnetAddr dest_addr;
PACKETKIND type;
int id_seq;
int id_ackSeq;
int msgLen;
MSG msgData;
} PACKET;
static int nextMsgSeq_id = 0;
static int nextAckSeq_id = 0;
/* ----------------------------------------------------------------------- */
/*******************forward declarations*/
/* functions to use for application layer to transmit a message */
static void application_down_to_network(int link, MSG *msg, int *length, CnetAddr dest_address);
static void network_down_to_datalink(int link, PACKET *pkt, int *length);
/* event handler function for physical layer*/
static void pkt_arrived(CnetEvent ev, CnetTimer timer, CnetData data);
/* the functions used to send arriving stream of data bytes upward in the network hiearchry */
static void network_up_to_application(MSG *data, int* len, int* msgSeq, PACKETKIND pktype);
static void datalink_up_to_network(char* frame, int* link);
static void application_ready(CnetEvent ev, CnetTimer timer, CnetData data)
{
MSG appMsg;
int length;
CnetAddr destaddr;
length = sizeof(MSG);
CNET_read_application(&destaddr, (char*)&appMsg, &length);
CNET_disable_application(ALLNODES);
application_down_to_network(1, &appMsg, &length, destaddr);
}
static void application_down_to_network(int link, MSG *msg, int *length, CnetAddr dest_address)
{
PACKET newMsgPkt;
int msg_pk_size = sizeof(PACKET);
/*intialize packet header informtion*/
newMsgPkt.src_addr = nodeinfo.address;
newMsgPkt.dest_addr = dest_address;
newMsgPkt.msgLen = *length;
newMsgPkt.type = PK_DATA;
memcpy(&newMsgPkt.msgData, (char *)msg, *length);
newMsgPkt.id_seq = nextMsgSeq_id++; /*assign and increment for next message*/
network_down_to_datalink(link, &newMsgPkt, &msg_pk_size);
}
static void network_down_to_datalink(int link, PACKET *pkt, int *length)
{
timeTransmitMsg = nodeinfo.time_of_day.sec;
CNET_write_physical_reliable(link, (char*)pkt, length);
}
static void pkt_arrived(CnetEvent ev, CnetTimer timer, CnetData data)
{
timeReceiveAck = nodeinfo.time_of_day.sec;
char new_msgFrame[sizeof(PACKET)]; /*array for holding arriving stream of bytes*/
int link, length;
length = sizeof(new_msgFrame);
CNET_read_physical(&link, new_msgFrame, &length);
datalink_up_to_network(new_msgFrame, &link);
}
static void datalink_up_to_network(char* frame, int* link)
{
int length;
PACKET *new_msg_pkt;
int msg_pk_size = sizeof(PACKET);
new_msg_pkt = (PACKET*)frame; /*convert to packet format*/
if (nodeinfo.nodetype == NT_HOST && nodeinfo.address == new_msg_pkt->dest_addr)
{
if (new_msg_pkt->type == PK_DATA && new_msg_pkt->id_seq == nextMsgSeq_id)
{
length = new_msg_pkt->msgLen;
network_up_to_application(&new_msg_pkt->msgData, &length, &nextMsgSeq_id, PK_DATA);
nextMsgSeq_id++;
printf("Sending acknowledgment for packet sequence number %d\n\n", (nextMsgSeq_id-1));
/*re-use packet as acknowledgement packet*/
CnetAddr oldDest = new_msg_pkt->dest_addr;
new_msg_pkt->dest_addr = new_msg_pkt->src_addr;
new_msg_pkt->src_addr = oldDest;
new_msg_pkt->msgLen = 0;
new_msg_pkt->type = PK_ACK;
new_msg_pkt->id_ackSeq = nextAckSeq_id++;
network_down_to_datalink(1, new_msg_pkt, &msg_pk_size);
}
else if(new_msg_pkt->type == PK_ACK &&
new_msg_pkt->dest_addr == nodeinfo.address &&
new_msg_pkt->id_ackSeq == nextAckSeq_id) /*check if its an acknowledegment for previous msg*/
{
network_up_to_application(&new_msg_pkt->msgData, &length, &nextAckSeq_id, PK_ACK);
nextAckSeq_id++;
}
}
else if ( /*nodeinfo.nodetype == NT_ROUTER && */
( (new_msg_pkt->type == PK_DATA && nextMsgSeq_id == new_msg_pkt->id_seq) ||
(new_msg_pkt->type == PK_ACK && nextAckSeq_id == new_msg_pkt->id_ackSeq) )
)
{
/*only increment packet sequence counter if packet if of type PK_DATA*/
if (new_msg_pkt->type == PK_DATA)
{
nextMsgSeq_id++;
printf("Packet arrived. Sequence number %d. Forwarding to all non-receiving link\n\n", new_msg_pkt->id_seq);
}
else if (new_msg_pkt->type == PK_ACK)
{
nextAckSeq_id++;
printf("Acknowledgment arrived. Sequence number %d. Forwarding to all non-receiving link\n\n", new_msg_pkt->id_ackSeq);
}
/*flood al non-receiving links connected to this router in that case*/
length = sizeof(PACKET);
int i=1;
while (i <= nodeinfo.nlinks)
{
if(i != (*link)) /*check that current link is not the link paket arrived on. If so then skip it*/
network_down_to_datalink(i, new_msg_pkt, &length);
i++; /*move on to next link*/
}
}
}
static void network_up_to_application(MSG *data, int* len, int* msgSeq, PACKETKIND pktype)
{
if (pktype == PK_DATA)
{
printf("Data arrived. Sequence no: %d Writing to Application Layer\n", *msgSeq);
CNET_write_application((char*)data, len);
}
else if (pktype == PK_ACK)
{
printf("Acknowledgement arrived for message sequence no: %d\n", *msgSeq);
printf("Time taken for ack to arrive is: %ld", timeReceiveAck-timeTransmitMsg);
if(nodeinfo.nodenumber == SOURCE_NODE && numOfMsgToTrsmt < 0)
{
CNET_enable_application(DEST_NODE);
numOfMsgToTrsmt++;
}
}
}
void reboot_node(CnetEvent ev, CnetTimer timer, CnetData data)
{
printf("Propagation Delay %d\n", (unsigned int)linkinfo[1].propagationdelay);
CNET_set_handler(EV_APPLICATIONREADY, application_ready, 0);
CNET_set_handler(EV_PHYSICALREADY, pkt_arrived, 0);
if(nodeinfo.nodenumber == SOURCE_NODE)
CNET_enable_application(DEST_NODE);
}
---------------------------
LINK STATE CODE
---------------------------
#include <cnet.h>
#include <stdlib.h>
#include <string.h>
/* The source code below implements the link state routing
algorithm protocol based on the description as
described by A.S Tanenbaum in his textbook titled
"Computer Networks" 4th edition 2003.
*/
/*values for packet kind*/
typedef enum {PK_DATA, PK_ACK, PK_HELLO, PK_HELLO_REPLY,
PK_ECHO, PK_ECHO_REPLY, PK_LINKSTATE, PK_NBR_INFO} PACKETKIND;
typedef enum {DST_PERTH =100, DST_SYDNEY=200} DESTINAION;
typedef enum {LINK_UP, LINK_DOWN} LINKSTATE_TYPE;
typedef enum {permanent, tentative, unknown} STATE;
typedef enum {TRUE, FALSE} BOOLEAN;
/*constant values that affect the opertion of the link state routing protocol*/
const unsigned int MAX_NODES = 50;
const unsigned int HELLO_TIMEOUT = 3000000; /*in nanoseconds*/
const unsigned int WAIT_LINKSTATE_TIMEOUT = 5000000; /*in nanoseconds*/
const unsigned int INFINITY = 1000000000; /*REALLY REALLY LARGE VALUE USED in minimum spanning tree processing*/
const unsigned int SOURCE_NODE = 0;
const unsigned int DEST_NODE = 11;
unsigned int numOfMsgGen = 0;
unsigned long timeTransmitMsg = 0;
unsigned long timeReceiveAck = 0;
/*structures to represent all kinds of packet*/
typedef struct {
char data[MAX_MESSAGE_SIZE];
} MSG;
typedef struct {
unsigned int seq_no;
CnetAddr src_addr;
CnetAddr adjNode_addr;
} HELLO_PACKET;
typedef struct {
unsigned int srcTimeSent;
unsigned int destTimeRec;
unsigned int srcTimeRec;
} ECHO_PACKET;
typedef struct {
CnetAddr src_addr;
CnetAddr dest_addr;
int id_seq;
int id_ackSeq; /*piggy backing?*/
int msgLen;
MSG msgData;
} DATA_PACKET;
typedef struct {
CnetAddr nodeAddress;
unsigned int linkNo;
LINKSTATE_TYPE stateOfLink;
unsigned int delay;
} NBR_INFO;
typedef struct {
CnetAddr nodeAddress;
unsigned int seq;
unsigned int noOfNbrs;
NBR_INFO* neighbours;
} LINKSTATE_PACKET;
typedef struct {
PACKETKIND type;
DATA_PACKET pktData;
HELLO_PACKET pktHello;
ECHO_PACKET pktEcho;
LINKSTATE_PACKET theLinkState;
} PACKET;
typedef struct {
LINKSTATE_PACKET* LSPackets;
unsigned int currNoOfNodes;
} LINKSTATE_BUFFER;
typedef struct {
unsigned int parent;
unsigned int length; /*length of path from source node to this node*/
STATE status;
} DIJKSTRAS_NODE;
static int nextMsgSeq_id = 0;
static int nextAckSeq_id = 0;
static unsigned int nextHelloSeq_id =0;
/*objects to hold information adjacent nodes*/
unsigned int currLinkState_id = 1; /*start count from 1*/
/*The only database to hold all node information.
The address is used as the index into the array ie
the position of a linkstate packet represents the
address of the node it belongs to.*/
LINKSTATE_BUFFER LSPktsBuffer;
NBR_INFO* neighbours = NULL;
int nbrsHello_ackd = 0; /*Keep track of number of replies to hello packets*/
CnetTimer timerIDBuildLS; /*Keep track of the wait time for hello packets*/
CnetTimer timerIDReceiveLS; /*Keep track of the wait time for receiving link state packets*/
CnetInt64 waitLSTimeout;
BOOLEAN firstTime = TRUE; /*1 if when applicaton_ready layer first executes*/
BOOLEAN aFirstLinkState = TRUE;
DIJKSTRAS_NODE* allNodes = NULL;
int* routing_table = NULL;
/* ----------------------------------------------------------------------- */
/*******************forward declarations*/
/* functions to use for application layer to transmit a message */
static void application_down_to_network(MSG *msg, int *length, CnetAddr dest_address);
static void network_down_to_datalink(int link, PACKET *pkt, int *length);
/* event handler function for physical layer*/
static void physical_ready(CnetEvent ev, CnetTimer timer, CnetData data);
/* the functions used to send arriving stream of data bytes upward in the network hiearchry */
static void network_up_to_application(char *data, int* len, int* msgSeq, PACKETKIND pktype);
static void datalink_up_to_network(char* frame, int* link, unsigned int* actual_size);
/* functions for cleaning up*/
static void shutdown(CnetEvent ev, CnetTimer timer, CnetData data);
/* functions for the link state routing protocol*/
static void determine_neighbours();
static void init_build_linkstate_update(CnetEvent ev, CnetTimer timer, CnetData data);
static void create_linkstate_update(unsigned int no_Of_Nbrs, NBR_INFO* neighbours);
/*static void increase_LSBuffer();*/
static void init_setup(CnetEvent ev, CnetTimer timer, CnetData data);
static void build_routing_table(CnetEvent ev, CnetTimer timer, CnetData data);
static void min_spanning_tree(LINKSTATE_BUFFER* graph);
static void print_routing_table(CnetEvent ev, CnetTimer timer, CnetData data);
static void print_LinkState_DB(CnetEvent ev, CnetTimer timer, CnetData data);
/*-----------------------------------------------------------------------------------------------------------------*/
static void application_ready(CnetEvent ev, CnetTimer timer, CnetData data)
{
MSG appMsg;
int length;
CnetAddr destaddr;
length = sizeof(MSG);
CNET_read_application(&destaddr, (char*)&appMsg, &length);
CNET_disable_application(ALLNODES);
/*message doesnt count if address doesnt correspond to set destination address
so read from application layer again*/
/*if (destaddr != DEST_NODE)
CNET_read_application(&destaddr, (char*)&appMsg, &length);*/
printf("Destination address is: %d\n", destaddr);
application_down_to_network(&appMsg, &length, destaddr);
}
static void application_down_to_network(MSG *msg, int *length, CnetAddr dest_address)
{
PACKET newMsgPkt;
int msg_pk_size = sizeof(PACKET);
/*intialize packet header informtion*/
newMsgPkt.pktData.src_addr = nodeinfo.address;
newMsgPkt.pktData.dest_addr = dest_address;
newMsgPkt.pktData.msgLen = *length;
newMsgPkt.type = PK_DATA;
memcpy(&newMsgPkt.pktData.msgData, (char *)msg, *length);
newMsgPkt.pktData.id_seq = nextMsgSeq_id++; /*assign and increment for next message*/
/*****************REMEMBER TO USE ROUTING TABLE TO DETERMINE LINK TO USE***************/
network_down_to_datalink(routing_table[newMsgPkt.pktData.dest_addr], &newMsgPkt, &msg_pk_size);
}
/**********************************************************************************************************/
static void network_down_to_datalink(int link, PACKET *pkt, int *length)
{
timeTransmitMsg = nodeinfo.time_of_day.sec;
CNET_write_physical_reliable(link, (char*)pkt, length);
}
/**************************************************************************************************************/
static void physical_ready(CnetEvent ev, CnetTimer timer, CnetData data)
{
timeReceiveAck = nodeinfo.time_of_day.sec;
/*array for holding arriving stream of bytes. Give it the maximum possible
size according the number of nodes*/
char new_msgFrame[sizeof(PACKET)]; /* + MAX_NODES*sizeof(NBR_INFO)]; */
int link, length;
length = sizeof(new_msgFrame);
CNET_read_physical(&link, new_msgFrame, &length);
datalink_up_to_network(new_msgFrame, &link, &length);
}
/****************************************************************************************************************/
static void datalink_up_to_network(char* frame, int* link, unsigned int* actual_size)
{
PACKET* new_msg_pkt;
new_msg_pkt = (PACKET*)frame; /*convert to packet format*/
unsigned int pk_size;
unsigned int length;
if (new_msg_pkt->type == PK_DATA)
{
if (nodeinfo.address == new_msg_pkt->pktData.dest_addr && new_msg_pkt->pktData.id_seq == nextMsgSeq_id)
{
length = new_msg_pkt->pktData.msgLen;
network_up_to_application((char*)&new_msg_pkt->pktData.msgData, &length, &nextMsgSeq_id, PK_DATA);
nextMsgSeq_id++;
printf("Sending acknowledgment for packet sequence number %d\n\n", (nextMsgSeq_id-1));
/*re-use packet as acknowledgement packet*/
CnetAddr oldDest = new_msg_pkt->pktData.dest_addr; /*Dont have to do this; just use nodeinfo.address*/
new_msg_pkt->pktData.dest_addr = new_msg_pkt->pktData.src_addr;
new_msg_pkt->pktData.src_addr = oldDest;
new_msg_pkt->pktData.msgLen = 0;
new_msg_pkt->type = PK_ACK;
new_msg_pkt->pktData.id_ackSeq = nextAckSeq_id++;
pk_size = sizeof(PACKET);
network_down_to_datalink(routing_table[new_msg_pkt->pktData.dest_addr], new_msg_pkt, &pk_size);
}
else
{
pk_size = sizeof(PACKET);
network_down_to_datalink(routing_table[new_msg_pkt->pktData.dest_addr], new_msg_pkt, &pk_size);
}
}
else if(new_msg_pkt->type == PK_ACK)
{
if (new_msg_pkt->pktData.dest_addr == nodeinfo.address && new_msg_pkt->pktData.id_ackSeq == nextAckSeq_id)
{
network_up_to_application((char*)&new_msg_pkt->pktData.msgData, &length, &nextAckSeq_id, PK_ACK);
nextAckSeq_id++;
}
else
{
pk_size = sizeof(PACKET);
network_down_to_datalink(routing_table[new_msg_pkt->pktData.dest_addr], new_msg_pkt, &pk_size);
}
}
else if (new_msg_pkt->type == PK_HELLO)
{
pk_size = sizeof(PACKET);
printf("Hello packet received from neighbour with node address %d ", new_msg_pkt->pktHello.src_addr);
printf("with seq id number %d\n", new_msg_pkt->pktHello.seq_no);
printf("Sending acknowledgement hello packet back to source\n\n");
/*create acknowledgement hello packet*/
new_msg_pkt->type = PK_HELLO_REPLY;
new_msg_pkt->pktHello.adjNode_addr = nodeinfo.address;
network_down_to_datalink(*link, new_msg_pkt, &pk_size);
}
else if (new_msg_pkt->type == PK_HELLO_REPLY)
{
/*record neighbour address and link attached to it*/
if (nbrsHello_ackd < nodeinfo.nlinks)
{
neighbours[nbrsHello_ackd].nodeAddress = new_msg_pkt->pktHello.adjNode_addr;
neighbours[nbrsHello_ackd].linkNo = *link;
nbrsHello_ackd++;
}
pk_size = sizeof(HELLO_PACKET);
network_up_to_application((char*)&new_msg_pkt->pktHello, &pk_size, &new_msg_pkt->pktHello.seq_no, PK_HELLO_REPLY);
}
else if (new_msg_pkt->type == PK_LINKSTATE)
{
/*if (aFirstLinkState == FALSE)*/
CNET_stop_timer(timerIDReceiveLS); /*stop timer and prevent building of routing table and wait for more LS packets*/
/*else
aFirstLinkState = FALSE;*/
int currNeighbourNode = new_msg_pkt->theLinkState.nodeAddress;
/*check if linkstate packet received is newer than the one stored for the node*/
if (new_msg_pkt->theLinkState.seq > LSPktsBuffer.LSPackets[currNeighbourNode].seq)
{
if (LSPktsBuffer.LSPackets[currNeighbourNode].seq == 0)
LSPktsBuffer.currNoOfNodes++;
/*Replace stored link state with stored received link state*/
LSPktsBuffer.LSPackets[currNeighbourNode].nodeAddress = currNeighbourNode;
LSPktsBuffer.LSPackets[currNeighbourNode].seq = new_msg_pkt->theLinkState.seq;
LSPktsBuffer.LSPackets[currNeighbourNode].noOfNbrs = new_msg_pkt->theLinkState.noOfNbrs;
/*Check for old neighbour information for foreign node*/
if (LSPktsBuffer.LSPackets[currNeighbourNode].neighbours != NULL)
{
free(LSPktsBuffer.LSPackets[currNeighbourNode].neighbours);
LSPktsBuffer.LSPackets[currNeighbourNode].neighbours = NULL;
}
int numberOfNbrs = new_msg_pkt->theLinkState.noOfNbrs;
LSPktsBuffer.LSPackets[currNeighbourNode].neighbours = (NBR_INFO*)malloc(sizeof(NBR_INFO) * numberOfNbrs);
int i = 0;
while (i < numberOfNbrs)
{
LSPktsBuffer.LSPackets[currNeighbourNode].neighbours[i].nodeAddress = new_msg_pkt->theLinkState.neighbours[i].nodeAddress;
LSPktsBuffer.LSPackets[currNeighbourNode].neighbours[i].linkNo = new_msg_pkt->theLinkState.neighbours[i].linkNo;
LSPktsBuffer.LSPackets[currNeighbourNode].neighbours[i].delay = new_msg_pkt->theLinkState.neighbours[i].delay;
i++;
}
/*TEST LINK STATE INFO*/
printf("Updated link state info for node %d\n", currNeighbourNode);
printf("Current link state sequence number is %d\n", LSPktsBuffer.LSPackets[currNeighbourNode].seq);
printf("Current number of neighbours is %d\n", LSPktsBuffer.LSPackets[currNeighbourNode].noOfNbrs);
printf("Neighbours and their info are:\n");
i=0;
while (i < numberOfNbrs)
{
printf("%d ", i+1);
printf("%d ", LSPktsBuffer.LSPackets[currNeighbourNode].neighbours[i].nodeAddress);
printf("delay: %d\n", LSPktsBuffer.LSPackets[currNeighbourNode].neighbours[i].delay);
i++;
}
printf("\n");
/*forward linkstate to other neighbours*/
i=1;
while (i <= nodeinfo.nlinks)
{
if (i != *link)
network_down_to_datalink(i, new_msg_pkt, actual_size);
i++;
}
}/*end if*/
waitLSTimeout = WAIT_LINKSTATE_TIMEOUT;
/*Set timer to trigger off building of routing table after a pre-dertermined number of seconds*/
timerIDReceiveLS = CNET_start_timer(EV_TIMER2, waitLSTimeout, 0);
}/*end else if */
}
/************************************************************************************************************/
static void network_up_to_application(char *data, int* len, int* msgSeq, PACKETKIND pktype)
{
if (pktype == PK_DATA)
{
printf("Data arrived. Sequence no: %d Writing to Application Layer\n", *msgSeq);
CNET_write_application(data, len);
}
else if (pktype == PK_ACK)
{
printf("Acknowledgement arrived for message sequence no: %d\n\n", *msgSeq);
printf("Time taken for ack to arrive is: %ld", timeReceiveAck-timeTransmitMsg);
if(nodeinfo.nodenumber == SOURCE_NODE && numOfMsgGen < 0)
{
CNET_enable_application(DEST_NODE);
numOfMsgGen++;
}
}
else if (pktype == PK_HELLO_REPLY)
{
HELLO_PACKET* replyHello = (HELLO_PACKET*)data;
printf("Acknowledgement arrived for hello packet sequence number %d ", *msgSeq);
printf("from node number %d\n\n", replyHello->adjNode_addr);
}
else if (pktype == PK_LINKSTATE)
{
}
}
/**********************************************************************************************************/
static void init_setup(CnetEvent ev, CnetTimer timer, CnetData data)
{
if (firstTime == TRUE)
{
/*create and intialize array to hold all nodes in topology*/
LSPktsBuffer.LSPackets = (LINKSTATE_PACKET*) malloc(sizeof(LINKSTATE_PACKET) *MAX_NODES);
LSPktsBuffer.currNoOfNodes = 0;
/*allocate space for the working array used for computing minimum spanning tree*/
allNodes = (DIJKSTRAS_NODE*) malloc(sizeof(DIJKSTRAS_NODE) *MAX_NODES);
routing_table = (int*) malloc(sizeof(int) * MAX_NODES);
/*Initialize packets in buffer*/
int i=0;
while (i<MAX_NODES)
{
LSPktsBuffer.LSPackets[i].seq = 0;
LSPktsBuffer.LSPackets[i].neighbours = NULL;
i++;
}
determine_neighbours();
/*measured in nanoseconds*/
CnetInt64 helloTimeout = HELLO_TIMEOUT;
timerIDBuildLS = CNET_start_timer(EV_TIMER1, helloTimeout, 0);
firstTime = FALSE;
}
}
/**********************************************************************************************************/
static void determine_neighbours()
{
CNET_disable_application(ALLNODES);
PACKET hello;
unsigned int sizeOfHelloPkt = sizeof(PACKET);
/*check to see that neighbour is not already in use*/
if (neighbours != NULL)
{
free(neighbours);
neighbours = NULL;
}
/*create as many neighbour objects as there are links attached to this node*/
unsigned int currNoOfLinks = nodeinfo.nlinks;
neighbours = (NBR_INFO*) malloc(currNoOfLinks * sizeof(NBR_INFO));
hello.type = PK_HELLO;
hello.pktHello.seq_no = nextHelloSeq_id++;
hello.pktHello.src_addr = nodeinfo.address;
/*send hello packets to all links*/
printf("Sending hello packets for sequence number %d\n\n", hello.pktHello.seq_no);
int i=1;
while (i <= nodeinfo.nlinks)
{
network_down_to_datalink(i, &hello, &sizeOfHelloPkt);
i++;
}
}
/**********************************************************************************************************/
static void init_build_linkstate_update(CnetEvent ev, CnetTimer timer, CnetData data)
{
if (timer == timerIDBuildLS)
{
if (nbrsHello_ackd == nodeinfo.nlinks)
{
create_linkstate_update(nbrsHello_ackd, neighbours);
}
else
{
CnetInt64 helloTimeout = 5000; /*measured in nanoseconds so timeout is set to half a second*/
timerIDBuildLS = CNET_start_timer(EV_TIMER1, helloTimeout, 0);
}
}
}
/*************************************************************************************************************/
static void create_linkstate_update(unsigned int no_Of_Nbrs, NBR_INFO* neighbours)
{
int i=0;
while(i < no_Of_Nbrs)
{
neighbours[i].delay = linkinfo[neighbours[i].linkNo].propagationdelay;
i++;
}
PACKET lsPkt;
lsPkt.type = PK_LINKSTATE;
lsPkt.theLinkState.nodeAddress = nodeinfo.address;
lsPkt.theLinkState.seq = currLinkState_id++;
lsPkt.theLinkState.noOfNbrs = no_Of_Nbrs;
/*Use current number of links to intialize size of neighbours buffer
since thats the represents maximum neighbours a node can have
but not all neigbours may be 'alive' at any instant*/
lsPkt.theLinkState.neighbours = (NBR_INFO*) malloc(nodeinfo.nlinks * sizeof(NBR_INFO));
unsigned int tempSize = (sizeof(NBR_INFO)*nodeinfo.nlinks); /*used for copying and transmitting*/
memcpy(lsPkt.theLinkState.neighbours, neighbours, tempSize);
/*store your own link state information in link state buffer for purposes of constructing dijkstra's graph*/
LSPktsBuffer.LSPackets[nodeinfo.address].nodeAddress = nodeinfo.address;
if(LSPktsBuffer.LSPackets[nodeinfo.address].seq == 0) /*check if this is new node added to your buffer*/
LSPktsBuffer.currNoOfNodes++; /*statement should only occur once if algorithm is correct*/
LSPktsBuffer.LSPackets[nodeinfo.address].seq = currLinkState_id - 1;
LSPktsBuffer.LSPackets[nodeinfo.address].noOfNbrs = no_Of_Nbrs;
if (LSPktsBuffer.LSPackets[nodeinfo.address].neighbours != NULL)
free(LSPktsBuffer.LSPackets[nodeinfo.address].neighbours);
LSPktsBuffer.LSPackets[nodeinfo.address].neighbours = (NBR_INFO*) malloc(nodeinfo.nlinks * sizeof(NBR_INFO));
memcpy(LSPktsBuffer.LSPackets[nodeinfo.address].neighbours, neighbours, tempSize);
/*transmit link packet*/
tempSize = sizeof(lsPkt); /*or += ?*/
/*if (nodeinfo.nodenumber == 1)*/
i=1;
while(i <= nodeinfo.nlinks)
{
network_down_to_datalink(i, &lsPkt, &tempSize);
i++;
}
printf("Transmitting linkstate packet by flooding\n\n");
waitLSTimeout = WAIT_LINKSTATE_TIMEOUT;
/*Set timer to trigger off building of routing table after a pre-dertermined number of seconds*/
timerIDReceiveLS = CNET_start_timer(EV_TIMER2, waitLSTimeout, 0);
}
/************************************************************************************************************/
static void build_routing_table(CnetEvent ev, CnetTimer timer, CnetData data)
{
if(timer == timerIDReceiveLS)
printf("In build_routing_table function\n\n");
if (LSPktsBuffer.LSPackets != NULL)
{
min_spanning_tree(&LSPktsBuffer);
/*back track from each destination to this node.
Link connected to node immediately before this node
node will be the link to route incoming packet
with*/
unsigned int i=0;
unsigned int thisNode = nodeinfo.address;
unsigned int descendent;
while(i < LSPktsBuffer.currNoOfNodes)
{
if (i != thisNode) /*dont need to back track this node*/
{
descendent = i; /*why assign i?*/
while(allNodes[descendent].parent != nodeinfo.address)
descendent = allNodes[descendent].parent;
int j=0;
BOOLEAN found = FALSE;
while(j < nodeinfo.nlinks && found ==FALSE)
{
if (neighbours[j].nodeAddress == descendent)
{
routing_table[i] = neighbours[j].linkNo;
found = TRUE;
}
j++;
}
}
i++;
}/*end while*/
printf("Routing table built.....\n\n");
aFirstLinkState = TRUE;
if (nodeinfo.address == SOURCE_NODE)
CNET_enable_application(DEST_NODE);
}
}
/*************************************************************************************************************/
static void min_spanning_tree(LINKSTATE_BUFFER* graph)
{
/*initialize start node and rest of undiscovered node*/
unsigned short currWkngNode = nodeinfo.nodenumber;
allNodes[currWkngNode].parent = currWkngNode; /*Source node's parent is itself*/
allNodes[currWkngNode].length = 0;
allNodes[currWkngNode].status = permanent;
int x=0;
while(x < graph->currNoOfNodes)
{
if (x != currWkngNode) /*this node already initialized so skip it*/
{
allNodes[x].parent = INFINITY;
allNodes[x].length = INFINITY;
allNodes[x].status = unknown;
}
x++;
}
unsigned int numOfPermNodes=1; /*There is already one permanent node: the source node*/
unsigned int currNbrAddr;
unsigned int delayToCurrNbr;
unsigned int crrLstCstTntatveNde;
while(numOfPermNodes < graph->currNoOfNodes)
{
/*Visit all neighbours attached to the current permanent node*/
int j=0;
while(j < graph->LSPackets[currWkngNode].noOfNbrs)
{
currNbrAddr = graph->LSPackets[currWkngNode].neighbours[j].nodeAddress;
delayToCurrNbr = graph->LSPackets[currWkngNode].neighbours[j].delay;
if (allNodes[currNbrAddr].status == unknown)
{
/*node is discovered so give it initial details*/
allNodes[currNbrAddr].parent = currWkngNode;
allNodes[currNbrAddr].length = allNodes[currWkngNode].length + delayToCurrNbr;
allNodes[currNbrAddr].status = tentative;
}
else if (allNodes[currNbrAddr].status == tentative) /*has it already been visited?*/
{
/*check if distance currently labeled on it is greater than distance through
the current permanent node*/
if (allNodes[currNbrAddr].length > (allNodes[currWkngNode].length + delayToCurrNbr))
{
allNodes[currNbrAddr].parent = currWkngNode;
allNodes[currNbrAddr].length = allNodes[currWkngNode].length + delayToCurrNbr;
}
}
j++;
}/*end while*/
/*Iterate through all the tentative nodes and find the
one with shortest length to source node*/
/*QUESTION: WHAT SHOULD BE DONE WHEN YOUR COMPARING TWO TENTATIVE NODES
WITH THE SAME LENGTH?*/
j=0;
crrLstCstTntatveNde = INFINITY;
while(j < graph->currNoOfNodes)
{
if (allNodes[j].status == tentative)
{
if (crrLstCstTntatveNde == INFINITY)
crrLstCstTntatveNde = j;
else
if (allNodes[j].length < allNodes[crrLstCstTntatveNde].length)
crrLstCstTntatveNde = j;
}
j++;
}/*end while*/
/*next permanent node*/
currWkngNode = crrLstCstTntatveNde;
allNodes[currWkngNode].status = permanent;
numOfPermNodes++;
}/*end while*/
}
static void print_routing_table(CnetEvent ev, CnetTimer timer, CnetData data)
{
int i=0;
while(i < LSPktsBuffer.currNoOfNodes)
{
if (i != nodeinfo.address)
{
printf("Best route from node %d ", i);
printf("is: %d,",i);
int k=i;
do{
printf("%d,", allNodes[k].parent);
k = allNodes[k].parent;
} while(k != nodeinfo.address);
printf("\n");
}
i++;
}/*end while*/
printf(" DEST LINK_TO_USE \n");
i=0;
while(i < LSPktsBuffer.currNoOfNodes)
{
if (i != nodeinfo.address)
{
printf(" %d %d\n", i, routing_table[i]);
}
i++;
}
}
/**********************************************************************************************************/
static void print_LinkState_DB(CnetEvent ev, CnetTimer timer, CnetData data)
{
int i=0;
while (i < LSPktsBuffer.currNoOfNodes)
{
printf("Node %d ", LSPktsBuffer.LSPackets[i].nodeAddress);
printf("has %d neighbours.\n", LSPktsBuffer.LSPackets[i].noOfNbrs);
printf("They are:\n");
int j=0;
while(j < LSPktsBuffer.LSPackets[i].noOfNbrs)
{
printf("%d. ", j+1);
printf("%d-", LSPktsBuffer.LSPackets[i].neighbours[j].nodeAddress);
printf("delay to it is %d, ", LSPktsBuffer.LSPackets[i].neighbours[j].delay);
j++;
}
printf("\n\n");
i++;
}
}
/**********************************************************************************************************/
static void shutdown(CnetEvent ev, CnetTimer timer, CnetData data)
{
if (neighbours != NULL)
free(neighbours);
/*Free the Link State Buffers*/
if (LSPktsBuffer.LSPackets != NULL)
{
/*check if there are any contained pointers
pointing to objects*/
if (LSPktsBuffer.currNoOfNodes > 0)
{
int i=0;
while (i < LSPktsBuffer.currNoOfNodes)
{
if(LSPktsBuffer.LSPackets[i].neighbours != NULL)
free(LSPktsBuffer.LSPackets[i].neighbours);
i++;
}
}
free(LSPktsBuffer.LSPackets);
}
if (allNodes != NULL)
free(allNodes);
if (routing_table != NULL)
free(routing_table);
}
/**********************************************************************************************************/
void reboot_node(CnetEvent ev, CnetTimer timer, CnetData data)
{
CNET_set_handler(EV_APPLICATIONREADY, application_ready, 0);
CNET_set_handler(EV_PHYSICALREADY, physical_ready, 0);
CNET_set_handler(EV_SHUTDOWN, shutdown, 0);
CNET_set_handler(EV_TIMER1, init_build_linkstate_update, 0);
CNET_set_handler(EV_TIMER2, build_routing_table,0);
CNET_set_handler(EV_TIMER3, init_setup, 0);
CNET_set_handler(EV_DEBUG1, print_LinkState_DB, 0);
CNET_set_debug_string(EV_DEBUG1, "Print L.S DB");
/*CNET_set_handler(EV_DEBUG3, build_routing_table, 0);
CNET_set_debug_string(EV_DEBUG3, "Build R.T");*/
CNET_set_handler(EV_DEBUG2, print_routing_table, 0);
CNET_set_debug_string(EV_DEBUG2, "Print RT");
if (firstTime == TRUE);
CNET_start_timer(EV_TIMER3, 100000, 0);
}
