Distance Vector Routing
// DVector.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#define LINKCHANGES 1
/* ******************************************************************
Programming assignment 3: implementing distributed, asynchronous,
distance vector routing.
THIS IS THE MAIN ROUTINE. IT SHOULD NOT BE TOUCHED AT ALL BY STUDENTS!
**********************************************************************/
int TRACE = 1; /* for my debugging */
int YES = 1;
int NO = 0;
void creatertpkt(struct rtpkt *initrtpkt,
int srcid,
int destid,
int mincosts[])
{
int i;
initrtpkt->sourceid = srcid;
initrtpkt->destid = destid;
for (i=0; i<4; i++)
initrtpkt->mincost[i] = mincosts[i];
}
/*****************************************************************
***************** NETWORK EMULATION CODE STARTS BELOW ***********
The code below emulates the layer 2 and below network environment:
- emulates the tranmission and delivery (with no loss and no
corruption) between two physically connected nodes
- calls the initializations routines rtinit0, etc., once before
beginning emulation
THERE IS NOT REASON THAT ANY STUDENT SHOULD HAVE TO READ OR UNDERSTAND
THE CODE BELOW. YOU SHOLD NOT TOUCH, OR REFERENCE (in your code) ANY
OF THE DATA STRUCTURES BELOW. If you're interested in how I designed
the emulator, you're welcome to look at the code - but again, you should have
to, and you defeinitely should not have to modify
******************************************************************/
struct event {
double evtime; /* event time */
int evtype; /* event type code */
int eventity; /* entity where event occurs */
struct rtpkt *rtpktptr; /* ptr to packet (if any) assoc w/ this event */
struct event *prev;
struct event *next;
};
struct event *evlist = NULL; /* the event list */
/* possible events: */
#define FROM_LAYER2 2
#define LINK_CHANGE 10
double clocktime = 0.000;
// Function Prototypes
void init(); /* initialize the simulator */
double jimsrand(void);
void insertevent(struct event *p);
void printevlist();
void tolayer2(struct rtpkt packet);
int _tmain(int argc, _TCHAR* argv[])
{
struct event *eventptr;
init();
while (1) {
eventptr = evlist; /* get next event to simulate */
if (eventptr==NULL)
goto terminate;
evlist = evlist->next; /* remove this event from event list */
if (evlist!=NULL)
evlist->prev=NULL;
if (TRACE>1) {
printf("MAIN: rcv event, t=%.3f, at %d",
eventptr->evtime,eventptr->eventity);
if (eventptr->evtype == FROM_LAYER2 ) {
printf(" src:%2d,",eventptr->rtpktptr->sourceid);
printf(" dest:%2d,",eventptr->rtpktptr->destid);
printf(" contents: %3d %3d %3d %3d\n",
eventptr->rtpktptr->mincost[0], eventptr->rtpktptr->mincost[1],
eventptr->rtpktptr->mincost[2], eventptr->rtpktptr->mincost[3]);
}
}
clocktime = eventptr->evtime; /* update time to next event time */
if (eventptr->evtype == FROM_LAYER2 ) {
if (eventptr->eventity == 0)
rtupdate0(eventptr->rtpktptr);
else if (eventptr->eventity == 1)
rtupdate1(eventptr->rtpktptr);
else if (eventptr->eventity == 2)
rtupdate2(eventptr->rtpktptr);
else if (eventptr->eventity == 3)
rtupdate3(eventptr->rtpktptr);
else { printf("Panic: unknown event entity\n"); return(-9); }
}
else if (eventptr->evtype == LINK_CHANGE ) {
if (clocktime<10001.0) {
linkhandler0(1,20);
linkhandler1(0,20);
}
else {
linkhandler0(1,1);
linkhandler1(0,1);
}
}
else
{ printf("Panic: unknown event type\n"); return(-9); }
if (eventptr->evtype == FROM_LAYER2 )
free(eventptr->rtpktptr); /* free memory for packet, if any */
free(eventptr); /* free memory for event struct */
}
terminate:
printf("\nSimulator terminated at t=%f, no packets in medium\n", clocktime);
return 0;
}
void init() /* initialize the simulator */
{
int i;
double sum, avg;
struct event *evptr;
printf("Enter TRACE:");
scanf("%d",&TRACE);
srand(9999); /* init random number generator */
sum = 0.0; /* test random number generator for students */
for (i=0; i<1000; i++)
sum=sum+jimsrand(); /* jimsrand() should be uniform in [0,1] */
avg = sum/1000.0;
if (avg < 0.25 || avg > 0.75) {
printf("It is likely that random number generation on your machine\n" );
printf("is different from what this emulator expects. Please take\n");
printf("a look at the routine jimsrand() in the emulator code. Sorry. \n");
return;
}
clocktime=0.0; /* initialize time to 0.0 */
rtinit0();
rtinit1();
rtinit2();
rtinit3();
/* initialize future link changes */
if (LINKCHANGES==1) {
evptr = new struct event;
evptr->evtime = 10000.0;
evptr->evtype = LINK_CHANGE;
evptr->eventity = -1;
evptr->rtpktptr = NULL;
insertevent(evptr);
evptr = (struct event *)malloc(sizeof(struct event));
evptr->evtype = LINK_CHANGE;
evptr->evtime = 20000.0;
evptr->rtpktptr = NULL;
insertevent(evptr);
}
}
/****************************************************************************/
/* jimsrand(): return a float in range [0,1]. The routine below is used to */
/* isolate all random number generation in one location. We assume that the*/
/* system-supplied rand() function return an int in therange [0,mmm] */
/****************************************************************************/
double jimsrand()
{
double mmm = RAND_MAX; /* largest int - MACHINE DEPENDENT!!!!!!!! */
double x; /* individual students may need to change mmm */
x = rand()/mmm; /* x should be uniform in [0,1] */
return(x);
}
/********************* EVENT HANDLINE ROUTINES *******/
/* The next set of routines handle the event list */
/*****************************************************/
void insertevent(struct event *p)
{
struct event *q,*qold;
if (TRACE>3) {
printf(" INSERTEVENT: time is %lf\n",clocktime);
printf(" INSERTEVENT: future time will be %lf\n",p->evtime);
}
q = evlist; /* q points to header of list in which p struct inserted */
if (q==NULL) { /* list is empty */
evlist=p;
p->next=NULL;
p->prev=NULL;
}
else {
for (qold = q; q !=NULL && p->evtime > q->evtime; q=q->next)
qold=q;
if (q==NULL) { /* end of list */
qold->next = p;
p->prev = qold;
p->next = NULL;
}
else if (q==evlist) { /* front of list */
p->next=evlist;
p->prev=NULL;
p->next->prev=p;
evlist = p;
}
else { /* middle of list */
p->next=q;
p->prev=q->prev;
q->prev->next=p;
q->prev=p;
}
}
}
void printevlist()
{
struct event *q;
printf("--------------\nEvent List Follows:\n");
for(q = evlist; q!=NULL; q=q->next) {
printf("Event time: %f, type: %d entity: %d\n",q->evtime,q->evtype,q->eventity);
}
printf("--------------\n");
}
/************************** TOLAYER2 ***************/
void tolayer2(struct rtpkt packet)
{
struct rtpkt *mypktptr;
struct event *evptr, *q;
double lastime;
int i;
int connectcosts[4][4];
/* initialize by hand since not all compilers allow array initilization */
connectcosts[0][0]=0; connectcosts[0][1]=1; connectcosts[0][2]=3;
connectcosts[0][3]=7;
connectcosts[1][0]=1; connectcosts[1][1]=0; connectcosts[1][2]=1;
connectcosts[1][3]=999;
connectcosts[2][0]=3; connectcosts[2][1]=1; connectcosts[2][2]=0;
connectcosts[2][3]=2;
connectcosts[3][0]=7; connectcosts[3][1]=999; connectcosts[3][2]=2;
connectcosts[3][3]=0;
/* be nice: check if source and destination id's are reasonable */
if (packet.sourceid<0 || packet.sourceid >3) {
printf("WARNING: illegal source id in your packet, ignoring packet!\n");
return;
}
if (packet.destid<0 || packet.destid >3) {
printf("WARNING: illegal dest id in your packet, ignoring packet!\n");
return;
}
if (packet.sourceid == packet.destid) {
printf("WARNING: source and destination id's the same, ignoring packet!\n");
return;
}
if (connectcosts[packet.sourceid][packet.destid] == 999) {
printf("WARNING: source and destination not connected, ignoring packet!\n");
return;
}
/* make a copy of the packet student just gave me since he/she may decide */
/* to do something with the packet after we return back to him/her */
mypktptr = (struct rtpkt *) malloc(sizeof(struct rtpkt));
mypktptr->sourceid = packet.sourceid;
mypktptr->destid = packet.destid;
for (i=0; i<4; i++)
mypktptr->mincost[i] = packet.mincost[i];
if (TRACE>2) {
printf(" TOLAYER2: source: %d, dest: %d\n costs:",
mypktptr->sourceid, mypktptr->destid);
for (i=0; i<4; i++)
printf("%d ",mypktptr->mincost[i]);
printf("\n");
}
/* create future event for arrival of packet at the other side */
evptr = (struct event *)malloc(sizeof(struct event));
evptr->evtype = FROM_LAYER2; /* packet will pop out from layer3 */
evptr->eventity = packet.destid; /* event occurs at other entity */
evptr->rtpktptr = mypktptr; /* save ptr to my copy of packet */
/* finally, compute the arrival time of packet at the other end.
medium can not reorder, so make sure packet arrives between 1 and 10
time units after the latest arrival time of packets
currently in the medium on their way to the destination */
lastime = clocktime;
for (q=evlist; q!=NULL ; q = q->next)
if ( (q->evtype==FROM_LAYER2 && q->eventity==evptr->eventity) )
lastime = q->evtime;
evptr->evtime = lastime + 2.*jimsrand();
if (TRACE>2)
printf(" TOLAYER2: scheduling arrival on other side\n");
insertevent(evptr);
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
node0.cpp
#include "stdafx.h"
extern int TRACE;
extern int YES;
extern int NO;
struct distance_table dt0;
int cx[4] = {0,1,3,7};
/* students to write the following two routines, and maybe some others */
void rtinit0()
{
const int x=0;
for (int x = 0;x<4;x++)
{
for(int y=0;y<4;y++)
{
dt0.costs[x][y] = 999;
}
}
for(int y=0;y<4;y++)
{
dt0.costs[x][y] = cx[y];
dt0.costs[y][x] = cx[y];
}
struct rtpkt packet;
for(int w=0;w<4;w++)
{
if((w!=x) && (dt0.costs[x][w]!=INFTY))
{
creatertpkt(&packet,x,w,&dt0.costs[x][0]);
tolayer2(packet);
}
}
}
void rtupdate0(struct rtpkt * rcvdpkt)
{
const int x=0;
const int v=rcvdpkt->sourceid;
int tempcost[4];
for(int i=0;i<4;i++)
{
dt0.costs[v][i] = rcvdpkt->mincost[i];
tempcost[i] = dt0.costs[x][i];
}
bool changed = false;
for(int y=0;y<4;y++)
{
if(dt0.costs[x][v]+dt0.costs[v][y] < tempcost[y])
{
changed = true;
dt0.costs[x][y] = dt0.costs[x][v]+dt0.costs[v][y];
}
}
struct rtpkt packet;
for(int w=0;w<4;w++)
{
if((w!=x && (dt0.costs[w][x] != INFTY)) && changed)
{ // note, you should only sent to directly connected nodes
// this will not work using INFTY in the distance table
// once the node is reachable (even if not directly connected)
// it will no longer be INFTY
// use cx (above) instead
creatertpkt(&packet,x,w,&dt0.costs[x][0]);
tolayer2(packet);
printdt0(&dt0); // print distance table(new)
}
}
}
void printdt0(struct distance_table *dtptr)
{
printf(" via \n");
printf(" D0 | 1 2 3 \n");
printf(" ----|-----------------\n");
printf(" 1| %3d %3d %3d\n",dtptr->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]);
}
void linkhandler0(int linkid, int 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.cpp
#include "stdafx.h"
extern int TRACE;
extern int YES;
extern int NO;
struct distance_table dt1;
int cq[4] ={1, 0, 1, 999};
/* students to write the following two routines, and maybe some others */
void rtinit1()
{
const int x=1;
for(int xx=0; xx<4; xx++){
for(int y=0; y<4; y++){dt1.costs[xx][y]=999;}
}
for(int y=0; y<4; y++)
{
dt1.costs[x][y]=cq[y];
dt1.costs[y][x]=cq[y];
}
struct rtpkt packet;
for(int w=0; w<4; w++)
{
if((w!=x) && (dt1.costs[x][w]!=INFTY))
{
creatertpkt(&packet,x,w,&dt1.costs[x][0]);
tolayer2(packet);
}
}
}
void rtupdate1(struct rtpkt *rcvdpkt)
{
const int x=1;
const int v=rcvdpkt->sourceid;
int tempcost[4];
for(int i=0; i<4; i++)
{
dt1.costs[v][i]=rcvdpkt->mincost[i];
tempcost[i]=dt1.costs[x][i];
}
bool changed = false;
for(int y=0; y<4; y++)
{
if(dt1.costs[x][v]+dt1.costs[v][y] < tempcost[y])
{
changed = true;
dt1.costs[x][y] = dt1.costs[x][v]+dt1.costs[v][y];
}
}
struct rtpkt packet;
for(int w=0; w<4; w++)
{
if((w!=x && (dt1.costs[w][x] != INFTY)) && changed)
{
creatertpkt(&packet,x,w,&dt1.costs[x][0]);
tolayer2(packet);
printdt1(&dt1); // print distance table(new)
}
}
}
void printdt1( struct distance_table *dtptr)
{
printf(" via \n");
printf(" D1 | 0 2 \n");
printf(" ----|-----------\n");
printf(" 0| %3d %3d\n",dtptr->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]);
}
void linkhandler1(int linkid, int newcost)
/* called when cost from 1 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 */
{
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
node2.cpp
#include "stdafx.h"
extern int TRACE;
extern int YES;
extern int NO;
struct distance_table dt2;
int connectcosts2[4] = { 3, 1, 0, 2 };
/* students to write the following two routines, and maybe some others */
void rtinit2()
{
const int x=2;
for(int xx=0; xx<4; xx++){
for(int y=0; y<4; y++){dt2.costs[xx][y]=999;}
}
for(int y=0; y<4; y++)
{dt2.costs[x][y]=connectcosts2[y];
dt2.costs[y][x]=connectcosts2[y];
}
struct rtpkt packet;
for(int w=0; w<4; w++)
{
if((w!=x) && (dt2.costs[x][w]!=INFTY))
{
creatertpkt(&packet,x,w,&dt2.costs[x][0]);
tolayer2(packet);
}
}
}
void rtupdate2(struct rtpkt *rcvdpkt)
{
const int x=2;
const int v=rcvdpkt->sourceid;
int tempcost[4];
for(int i=0; i<4; i++)
{
dt2.costs[v][i]=rcvdpkt->mincost[i];
tempcost[i]=dt2.costs[x][i];
}
bool changed = false;
for(int y=0; y<4; y++)
{
if(dt2.costs[x][v]+dt2.costs[v][y] < tempcost[y])
{
changed = true;
dt2.costs[x][y] = dt2.costs[x][v]+dt2.costs[v][y];
}
}
struct rtpkt packet;
for(int w=0; w<4; w++)
{
if((w!=x && (dt2.costs[w][x] != INFTY)) && changed)
{
creatertpkt(&packet,x,w,&dt2.costs[x][0]);
tolayer2(packet);
printdt2(&dt2); // print distance table(new)
}
}
}
void printdt2( struct distance_table *dtptr)
{
printf(" via \n");
printf(" D1 | 0 2 \n");
printf(" ----|-----------\n");
printf(" 0| %3d %3d\n",dtptr->costs[0][0], dtptr->costs[0][3]);
printf("dest 2| %3d %3d\n",dtptr->costs[1][0], dtptr->costs[1][3]);
printf(" 3| %3d %3d\n",dtptr->costs[3][0], dtptr->costs[3][3]);
}
void linkhandler2(int linkid, int newcost)
/* called when cost from 1 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 */
{
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
node3.cpp
#include "stdafx.h"
extern int TRACE;
extern int YES;
extern int NO;
struct distance_table dt3;
int connectcosts3[4] = { 7, 999, 2, 0 };
/* students to write the following two routines, and maybe some others */
void rtinit3()
{
const int x=3;
for (int xx = 0;xx<4;xx++)
{
for(int y=0;y<4;y++)
{
dt3.costs[x][y] = 999;
}
}
for(int y=0; y<4; y++)
{
dt3.costs[x][y]=connectcosts3[y];
dt3.costs[y][x]=connectcosts3[y];
}
struct rtpkt packet;
for(int w=0; w<4; w++)
{
if((w!=x) && (dt3.costs[x][w]!=INFTY))
{
creatertpkt(&packet,x,w,&dt3.costs[x][0]);
tolayer2(packet);
}
}
}
void rtupdate3(struct rtpkt *rcvdpkt)
{
const int x=3;
const int v=rcvdpkt->sourceid;
int tempcost[4];
for(int i=0; i<4; i++)
{
dt3.costs[v][i]=rcvdpkt->mincost[i];
tempcost[i]=dt3.costs[x][i];
}
bool changed = false;
for(int y=0; y<4; y++)
{
if(dt3.costs[x][v]+dt3.costs[v][y] < tempcost[y])
{
changed = true;
dt3.costs[x][y] = dt3.costs[x][v]+dt3.costs[v][y];
}
}
struct rtpkt packet;
for(int w=0; w<4; w++)
{
if((w!=x && (dt3.costs[w][x] != INFTY)) && changed)
{
creatertpkt(&packet,x,w,&dt3.costs[x][0]);
tolayer2(packet);
printdt3(&dt3); // print distance table(new)
}
}
}
void printdt3( struct distance_table *dtptr)
{
printf(" via \n");
printf(" D1 | 0 2 \n");
printf(" ----|-----------\n");
printf(" 0| %3d %3d\n",dtptr->costs[0][0], dtptr->costs[0][2]);
printf("dest 2| %3d %3d\n",dtptr->costs[1][0], dtptr->costs[1][2]);
printf(" 3| %3d %3d\n",dtptr->costs[2][0], dtptr->costs[2][2]);
cout << "\nconnectcosts[0][0]=" << dtptr->costs[0][0] << "connectcosts[0][1]=" << dtptr->costs[0][1]
<< "\nconnectcosts[0][2]=" << dtptr->costs[0][2] << "connectcosts[0][3]="<< dtptr->costs[0][3] << endl;
cout << "\nconnectcosts[1][0]=" << dtptr->costs[1][0] << "connectcosts[1][1]=" << dtptr->costs[1][1]
<< "\nconnectcosts[1][2]=" << dtptr->costs[1][2] << "connectcosts[1][3]="<< dtptr->costs[1][3] << endl;
cout << "\nconnectcosts[2][0]=" << dtptr->costs[2][0] << "connectcosts[2][1]=" << dtptr->costs[2][1]
<< "\nconnectcosts[2][2]=" << dtptr->costs[2][2] << "connectcosts[2][3]="<< dtptr->costs[2][3] << endl;
cout << "\nconnectcosts[3][0]=" << dtptr->costs[3][0] << "connectcosts[3][1]=" << dtptr->costs[3][1]
<< "\nconnectcosts[3][2]=" << dtptr->costs[3][2] << "connectcosts[3][3]="<< dtptr->costs[3][3] << endl;
}
void linkhandler3(int linkid, int newcost)
/* called when cost from 1 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 */
{
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// stdafx.cpp : source file that includes just the standard includes
// DVector.pch will be the pre-compiled header
// stdafx.obj will contain the pre-compiled type information
#include "stdafx.h"
// TODO: reference any additional headers you need in STDAFX.H
// and not in this file
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
DVector.h
void creatertpkt(struct rtpkt *initrtpkt,
int srcid,
int destid,
int mincosts[]);
void tolayer2(struct rtpkt packet);
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
nodes.h
/* a rtpkt is the packet sent from one routing update process to
another via the call tolayer3() */
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 */
};
struct distance_table
{
int costs[4][4];
};
#define INFTY INT_MAX
#define UNKNOWN -1
// Function Prototypes
void rtinit0() ;
void rtupdate0(struct rtpkt * rcvdpkt);
void linkhandler0(int linkid, int newcost);
void printdt0(struct distance_table *dtptr) ;
void rtinit1();
void rtupdate1(struct rtpkt *rcvdpkt);
void linkhandler1(int linkid, int newcost);
void printdt1(struct distance_table *dtptr);
void rtinit2();
void rtupdate2(struct rtpkt *rcvdpkt);
void linkhandler2(int linkid, int newcost);
void printdt2(struct distance_table *dtptr);
void rtinit3();
void rtupdate3(struct rtpkt *rcvdpkt);
void linkhandler3(int linkid, int newcost);
void printdt3(struct distance_table *dtptr);
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
stdafx.h
// stdafx.h : include file for standard system include files,
// or project specific include files that are used frequently, but
// are changed infrequently
//
#pragma once
#include "targetver.h"
#include <stdio.h>
#include <tchar.h>
// TODO: reference additional headers your program requires here
#include <stdlib.h>
#include "nodes.h"
#include "DVector.h"
#include <limits.h>
#include <iostream>
using namespace std;
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
targetver.h
#pragma once
// The following macros define the minimum required platform. The minimum required platform
// is the earliest version of Windows, Internet Explorer etc. that has the necessary features to run
// your application. The macros work by enabling all features available on platform versions up to and
// including the version specified.
// Modify the following defines if you have to target a platform prior to the ones specified below.
// Refer to MSDN for the latest info on corresponding values for different platforms.
#ifndef _WIN32_WINNT // Specifies that the minimum required platform is Windows Vista.
#define _WIN32_WINNT 0x0600 // Change this to the appropriate value to target other versions of Windows.
#endif
//
#include "stdafx.h"
#define LINKCHANGES 1
/* ******************************************************************
Programming assignment 3: implementing distributed, asynchronous,
distance vector routing.
THIS IS THE MAIN ROUTINE. IT SHOULD NOT BE TOUCHED AT ALL BY STUDENTS!
**********************************************************************/
int TRACE = 1; /* for my debugging */
int YES = 1;
int NO = 0;
void creatertpkt(struct rtpkt *initrtpkt,
int srcid,
int destid,
int mincosts[])
{
int i;
initrtpkt->sourceid = srcid;
initrtpkt->destid = destid;
for (i=0; i<4; i++)
initrtpkt->mincost[i] = mincosts[i];
}
/*****************************************************************
***************** NETWORK EMULATION CODE STARTS BELOW ***********
The code below emulates the layer 2 and below network environment:
- emulates the tranmission and delivery (with no loss and no
corruption) between two physically connected nodes
- calls the initializations routines rtinit0, etc., once before
beginning emulation
THERE IS NOT REASON THAT ANY STUDENT SHOULD HAVE TO READ OR UNDERSTAND
THE CODE BELOW. YOU SHOLD NOT TOUCH, OR REFERENCE (in your code) ANY
OF THE DATA STRUCTURES BELOW. If you're interested in how I designed
the emulator, you're welcome to look at the code - but again, you should have
to, and you defeinitely should not have to modify
******************************************************************/
struct event {
double evtime; /* event time */
int evtype; /* event type code */
int eventity; /* entity where event occurs */
struct rtpkt *rtpktptr; /* ptr to packet (if any) assoc w/ this event */
struct event *prev;
struct event *next;
};
struct event *evlist = NULL; /* the event list */
/* possible events: */
#define FROM_LAYER2 2
#define LINK_CHANGE 10
double clocktime = 0.000;
// Function Prototypes
void init(); /* initialize the simulator */
double jimsrand(void);
void insertevent(struct event *p);
void printevlist();
void tolayer2(struct rtpkt packet);
int _tmain(int argc, _TCHAR* argv[])
{
struct event *eventptr;
init();
while (1) {
eventptr = evlist; /* get next event to simulate */
if (eventptr==NULL)
goto terminate;
evlist = evlist->next; /* remove this event from event list */
if (evlist!=NULL)
evlist->prev=NULL;
if (TRACE>1) {
printf("MAIN: rcv event, t=%.3f, at %d",
eventptr->evtime,eventptr->eventity);
if (eventptr->evtype == FROM_LAYER2 ) {
printf(" src:%2d,",eventptr->rtpktptr->sourceid);
printf(" dest:%2d,",eventptr->rtpktptr->destid);
printf(" contents: %3d %3d %3d %3d\n",
eventptr->rtpktptr->mincost[0], eventptr->rtpktptr->mincost[1],
eventptr->rtpktptr->mincost[2], eventptr->rtpktptr->mincost[3]);
}
}
clocktime = eventptr->evtime; /* update time to next event time */
if (eventptr->evtype == FROM_LAYER2 ) {
if (eventptr->eventity == 0)
rtupdate0(eventptr->rtpktptr);
else if (eventptr->eventity == 1)
rtupdate1(eventptr->rtpktptr);
else if (eventptr->eventity == 2)
rtupdate2(eventptr->rtpktptr);
else if (eventptr->eventity == 3)
rtupdate3(eventptr->rtpktptr);
else { printf("Panic: unknown event entity\n"); return(-9); }
}
else if (eventptr->evtype == LINK_CHANGE ) {
if (clocktime<10001.0) {
linkhandler0(1,20);
linkhandler1(0,20);
}
else {
linkhandler0(1,1);
linkhandler1(0,1);
}
}
else
{ printf("Panic: unknown event type\n"); return(-9); }
if (eventptr->evtype == FROM_LAYER2 )
free(eventptr->rtpktptr); /* free memory for packet, if any */
free(eventptr); /* free memory for event struct */
}
terminate:
printf("\nSimulator terminated at t=%f, no packets in medium\n", clocktime);
return 0;
}
void init() /* initialize the simulator */
{
int i;
double sum, avg;
struct event *evptr;
printf("Enter TRACE:");
scanf("%d",&TRACE);
srand(9999); /* init random number generator */
sum = 0.0; /* test random number generator for students */
for (i=0; i<1000; i++)
sum=sum+jimsrand(); /* jimsrand() should be uniform in [0,1] */
avg = sum/1000.0;
if (avg < 0.25 || avg > 0.75) {
printf("It is likely that random number generation on your machine\n" );
printf("is different from what this emulator expects. Please take\n");
printf("a look at the routine jimsrand() in the emulator code. Sorry. \n");
return;
}
clocktime=0.0; /* initialize time to 0.0 */
rtinit0();
rtinit1();
rtinit2();
rtinit3();
/* initialize future link changes */
if (LINKCHANGES==1) {
evptr = new struct event;
evptr->evtime = 10000.0;
evptr->evtype = LINK_CHANGE;
evptr->eventity = -1;
evptr->rtpktptr = NULL;
insertevent(evptr);
evptr = (struct event *)malloc(sizeof(struct event));
evptr->evtype = LINK_CHANGE;
evptr->evtime = 20000.0;
evptr->rtpktptr = NULL;
insertevent(evptr);
}
}
/****************************************************************************/
/* jimsrand(): return a float in range [0,1]. The routine below is used to */
/* isolate all random number generation in one location. We assume that the*/
/* system-supplied rand() function return an int in therange [0,mmm] */
/****************************************************************************/
double jimsrand()
{
double mmm = RAND_MAX; /* largest int - MACHINE DEPENDENT!!!!!!!! */
double x; /* individual students may need to change mmm */
x = rand()/mmm; /* x should be uniform in [0,1] */
return(x);
}
/********************* EVENT HANDLINE ROUTINES *******/
/* The next set of routines handle the event list */
/*****************************************************/
void insertevent(struct event *p)
{
struct event *q,*qold;
if (TRACE>3) {
printf(" INSERTEVENT: time is %lf\n",clocktime);
printf(" INSERTEVENT: future time will be %lf\n",p->evtime);
}
q = evlist; /* q points to header of list in which p struct inserted */
if (q==NULL) { /* list is empty */
evlist=p;
p->next=NULL;
p->prev=NULL;
}
else {
for (qold = q; q !=NULL && p->evtime > q->evtime; q=q->next)
qold=q;
if (q==NULL) { /* end of list */
qold->next = p;
p->prev = qold;
p->next = NULL;
}
else if (q==evlist) { /* front of list */
p->next=evlist;
p->prev=NULL;
p->next->prev=p;
evlist = p;
}
else { /* middle of list */
p->next=q;
p->prev=q->prev;
q->prev->next=p;
q->prev=p;
}
}
}
void printevlist()
{
struct event *q;
printf("--------------\nEvent List Follows:\n");
for(q = evlist; q!=NULL; q=q->next) {
printf("Event time: %f, type: %d entity: %d\n",q->evtime,q->evtype,q->eventity);
}
printf("--------------\n");
}
/************************** TOLAYER2 ***************/
void tolayer2(struct rtpkt packet)
{
struct rtpkt *mypktptr;
struct event *evptr, *q;
double lastime;
int i;
int connectcosts[4][4];
/* initialize by hand since not all compilers allow array initilization */
connectcosts[0][0]=0; connectcosts[0][1]=1; connectcosts[0][2]=3;
connectcosts[0][3]=7;
connectcosts[1][0]=1; connectcosts[1][1]=0; connectcosts[1][2]=1;
connectcosts[1][3]=999;
connectcosts[2][0]=3; connectcosts[2][1]=1; connectcosts[2][2]=0;
connectcosts[2][3]=2;
connectcosts[3][0]=7; connectcosts[3][1]=999; connectcosts[3][2]=2;
connectcosts[3][3]=0;
/* be nice: check if source and destination id's are reasonable */
if (packet.sourceid<0 || packet.sourceid >3) {
printf("WARNING: illegal source id in your packet, ignoring packet!\n");
return;
}
if (packet.destid<0 || packet.destid >3) {
printf("WARNING: illegal dest id in your packet, ignoring packet!\n");
return;
}
if (packet.sourceid == packet.destid) {
printf("WARNING: source and destination id's the same, ignoring packet!\n");
return;
}
if (connectcosts[packet.sourceid][packet.destid] == 999) {
printf("WARNING: source and destination not connected, ignoring packet!\n");
return;
}
/* make a copy of the packet student just gave me since he/she may decide */
/* to do something with the packet after we return back to him/her */
mypktptr = (struct rtpkt *) malloc(sizeof(struct rtpkt));
mypktptr->sourceid = packet.sourceid;
mypktptr->destid = packet.destid;
for (i=0; i<4; i++)
mypktptr->mincost[i] = packet.mincost[i];
if (TRACE>2) {
printf(" TOLAYER2: source: %d, dest: %d\n costs:",
mypktptr->sourceid, mypktptr->destid);
for (i=0; i<4; i++)
printf("%d ",mypktptr->mincost[i]);
printf("\n");
}
/* create future event for arrival of packet at the other side */
evptr = (struct event *)malloc(sizeof(struct event));
evptr->evtype = FROM_LAYER2; /* packet will pop out from layer3 */
evptr->eventity = packet.destid; /* event occurs at other entity */
evptr->rtpktptr = mypktptr; /* save ptr to my copy of packet */
/* finally, compute the arrival time of packet at the other end.
medium can not reorder, so make sure packet arrives between 1 and 10
time units after the latest arrival time of packets
currently in the medium on their way to the destination */
lastime = clocktime;
for (q=evlist; q!=NULL ; q = q->next)
if ( (q->evtype==FROM_LAYER2 && q->eventity==evptr->eventity) )
lastime = q->evtime;
evptr->evtime = lastime + 2.*jimsrand();
if (TRACE>2)
printf(" TOLAYER2: scheduling arrival on other side\n");
insertevent(evptr);
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
node0.cpp
#include "stdafx.h"
extern int TRACE;
extern int YES;
extern int NO;
struct distance_table dt0;
int cx[4] = {0,1,3,7};
/* students to write the following two routines, and maybe some others */
void rtinit0()
{
const int x=0;
for (int x = 0;x<4;x++)
{
for(int y=0;y<4;y++)
{
dt0.costs[x][y] = 999;
}
}
for(int y=0;y<4;y++)
{
dt0.costs[x][y] = cx[y];
dt0.costs[y][x] = cx[y];
}
struct rtpkt packet;
for(int w=0;w<4;w++)
{
if((w!=x) && (dt0.costs[x][w]!=INFTY))
{
creatertpkt(&packet,x,w,&dt0.costs[x][0]);
tolayer2(packet);
}
}
}
void rtupdate0(struct rtpkt * rcvdpkt)
{
const int x=0;
const int v=rcvdpkt->sourceid;
int tempcost[4];
for(int i=0;i<4;i++)
{
dt0.costs[v][i] = rcvdpkt->mincost[i];
tempcost[i] = dt0.costs[x][i];
}
bool changed = false;
for(int y=0;y<4;y++)
{
if(dt0.costs[x][v]+dt0.costs[v][y] < tempcost[y])
{
changed = true;
dt0.costs[x][y] = dt0.costs[x][v]+dt0.costs[v][y];
}
}
struct rtpkt packet;
for(int w=0;w<4;w++)
{
if((w!=x && (dt0.costs[w][x] != INFTY)) && changed)
{ // note, you should only sent to directly connected nodes
// this will not work using INFTY in the distance table
// once the node is reachable (even if not directly connected)
// it will no longer be INFTY
// use cx (above) instead
creatertpkt(&packet,x,w,&dt0.costs[x][0]);
tolayer2(packet);
printdt0(&dt0); // print distance table(new)
}
}
}
void printdt0(struct distance_table *dtptr)
{
printf(" via \n");
printf(" D0 | 1 2 3 \n");
printf(" ----|-----------------\n");
printf(" 1| %3d %3d %3d\n",dtptr->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]);
}
void linkhandler0(int linkid, int 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.cpp
#include "stdafx.h"
extern int TRACE;
extern int YES;
extern int NO;
struct distance_table dt1;
int cq[4] ={1, 0, 1, 999};
/* students to write the following two routines, and maybe some others */
void rtinit1()
{
const int x=1;
for(int xx=0; xx<4; xx++){
for(int y=0; y<4; y++){dt1.costs[xx][y]=999;}
}
for(int y=0; y<4; y++)
{
dt1.costs[x][y]=cq[y];
dt1.costs[y][x]=cq[y];
}
struct rtpkt packet;
for(int w=0; w<4; w++)
{
if((w!=x) && (dt1.costs[x][w]!=INFTY))
{
creatertpkt(&packet,x,w,&dt1.costs[x][0]);
tolayer2(packet);
}
}
}
void rtupdate1(struct rtpkt *rcvdpkt)
{
const int x=1;
const int v=rcvdpkt->sourceid;
int tempcost[4];
for(int i=0; i<4; i++)
{
dt1.costs[v][i]=rcvdpkt->mincost[i];
tempcost[i]=dt1.costs[x][i];
}
bool changed = false;
for(int y=0; y<4; y++)
{
if(dt1.costs[x][v]+dt1.costs[v][y] < tempcost[y])
{
changed = true;
dt1.costs[x][y] = dt1.costs[x][v]+dt1.costs[v][y];
}
}
struct rtpkt packet;
for(int w=0; w<4; w++)
{
if((w!=x && (dt1.costs[w][x] != INFTY)) && changed)
{
creatertpkt(&packet,x,w,&dt1.costs[x][0]);
tolayer2(packet);
printdt1(&dt1); // print distance table(new)
}
}
}
void printdt1( struct distance_table *dtptr)
{
printf(" via \n");
printf(" D1 | 0 2 \n");
printf(" ----|-----------\n");
printf(" 0| %3d %3d\n",dtptr->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]);
}
void linkhandler1(int linkid, int newcost)
/* called when cost from 1 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 */
{
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
node2.cpp
#include "stdafx.h"
extern int TRACE;
extern int YES;
extern int NO;
struct distance_table dt2;
int connectcosts2[4] = { 3, 1, 0, 2 };
/* students to write the following two routines, and maybe some others */
void rtinit2()
{
const int x=2;
for(int xx=0; xx<4; xx++){
for(int y=0; y<4; y++){dt2.costs[xx][y]=999;}
}
for(int y=0; y<4; y++)
{dt2.costs[x][y]=connectcosts2[y];
dt2.costs[y][x]=connectcosts2[y];
}
struct rtpkt packet;
for(int w=0; w<4; w++)
{
if((w!=x) && (dt2.costs[x][w]!=INFTY))
{
creatertpkt(&packet,x,w,&dt2.costs[x][0]);
tolayer2(packet);
}
}
}
void rtupdate2(struct rtpkt *rcvdpkt)
{
const int x=2;
const int v=rcvdpkt->sourceid;
int tempcost[4];
for(int i=0; i<4; i++)
{
dt2.costs[v][i]=rcvdpkt->mincost[i];
tempcost[i]=dt2.costs[x][i];
}
bool changed = false;
for(int y=0; y<4; y++)
{
if(dt2.costs[x][v]+dt2.costs[v][y] < tempcost[y])
{
changed = true;
dt2.costs[x][y] = dt2.costs[x][v]+dt2.costs[v][y];
}
}
struct rtpkt packet;
for(int w=0; w<4; w++)
{
if((w!=x && (dt2.costs[w][x] != INFTY)) && changed)
{
creatertpkt(&packet,x,w,&dt2.costs[x][0]);
tolayer2(packet);
printdt2(&dt2); // print distance table(new)
}
}
}
void printdt2( struct distance_table *dtptr)
{
printf(" via \n");
printf(" D1 | 0 2 \n");
printf(" ----|-----------\n");
printf(" 0| %3d %3d\n",dtptr->costs[0][0], dtptr->costs[0][3]);
printf("dest 2| %3d %3d\n",dtptr->costs[1][0], dtptr->costs[1][3]);
printf(" 3| %3d %3d\n",dtptr->costs[3][0], dtptr->costs[3][3]);
}
void linkhandler2(int linkid, int newcost)
/* called when cost from 1 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 */
{
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
node3.cpp
#include "stdafx.h"
extern int TRACE;
extern int YES;
extern int NO;
struct distance_table dt3;
int connectcosts3[4] = { 7, 999, 2, 0 };
/* students to write the following two routines, and maybe some others */
void rtinit3()
{
const int x=3;
for (int xx = 0;xx<4;xx++)
{
for(int y=0;y<4;y++)
{
dt3.costs[x][y] = 999;
}
}
for(int y=0; y<4; y++)
{
dt3.costs[x][y]=connectcosts3[y];
dt3.costs[y][x]=connectcosts3[y];
}
struct rtpkt packet;
for(int w=0; w<4; w++)
{
if((w!=x) && (dt3.costs[x][w]!=INFTY))
{
creatertpkt(&packet,x,w,&dt3.costs[x][0]);
tolayer2(packet);
}
}
}
void rtupdate3(struct rtpkt *rcvdpkt)
{
const int x=3;
const int v=rcvdpkt->sourceid;
int tempcost[4];
for(int i=0; i<4; i++)
{
dt3.costs[v][i]=rcvdpkt->mincost[i];
tempcost[i]=dt3.costs[x][i];
}
bool changed = false;
for(int y=0; y<4; y++)
{
if(dt3.costs[x][v]+dt3.costs[v][y] < tempcost[y])
{
changed = true;
dt3.costs[x][y] = dt3.costs[x][v]+dt3.costs[v][y];
}
}
struct rtpkt packet;
for(int w=0; w<4; w++)
{
if((w!=x && (dt3.costs[w][x] != INFTY)) && changed)
{
creatertpkt(&packet,x,w,&dt3.costs[x][0]);
tolayer2(packet);
printdt3(&dt3); // print distance table(new)
}
}
}
void printdt3( struct distance_table *dtptr)
{
printf(" via \n");
printf(" D1 | 0 2 \n");
printf(" ----|-----------\n");
printf(" 0| %3d %3d\n",dtptr->costs[0][0], dtptr->costs[0][2]);
printf("dest 2| %3d %3d\n",dtptr->costs[1][0], dtptr->costs[1][2]);
printf(" 3| %3d %3d\n",dtptr->costs[2][0], dtptr->costs[2][2]);
cout << "\nconnectcosts[0][0]=" << dtptr->costs[0][0] << "connectcosts[0][1]=" << dtptr->costs[0][1]
<< "\nconnectcosts[0][2]=" << dtptr->costs[0][2] << "connectcosts[0][3]="<< dtptr->costs[0][3] << endl;
cout << "\nconnectcosts[1][0]=" << dtptr->costs[1][0] << "connectcosts[1][1]=" << dtptr->costs[1][1]
<< "\nconnectcosts[1][2]=" << dtptr->costs[1][2] << "connectcosts[1][3]="<< dtptr->costs[1][3] << endl;
cout << "\nconnectcosts[2][0]=" << dtptr->costs[2][0] << "connectcosts[2][1]=" << dtptr->costs[2][1]
<< "\nconnectcosts[2][2]=" << dtptr->costs[2][2] << "connectcosts[2][3]="<< dtptr->costs[2][3] << endl;
cout << "\nconnectcosts[3][0]=" << dtptr->costs[3][0] << "connectcosts[3][1]=" << dtptr->costs[3][1]
<< "\nconnectcosts[3][2]=" << dtptr->costs[3][2] << "connectcosts[3][3]="<< dtptr->costs[3][3] << endl;
}
void linkhandler3(int linkid, int newcost)
/* called when cost from 1 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 */
{
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// stdafx.cpp : source file that includes just the standard includes
// DVector.pch will be the pre-compiled header
// stdafx.obj will contain the pre-compiled type information
#include "stdafx.h"
// TODO: reference any additional headers you need in STDAFX.H
// and not in this file
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
DVector.h
void creatertpkt(struct rtpkt *initrtpkt,
int srcid,
int destid,
int mincosts[]);
void tolayer2(struct rtpkt packet);
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
nodes.h
/* a rtpkt is the packet sent from one routing update process to
another via the call tolayer3() */
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 */
};
struct distance_table
{
int costs[4][4];
};
#define INFTY INT_MAX
#define UNKNOWN -1
// Function Prototypes
void rtinit0() ;
void rtupdate0(struct rtpkt * rcvdpkt);
void linkhandler0(int linkid, int newcost);
void printdt0(struct distance_table *dtptr) ;
void rtinit1();
void rtupdate1(struct rtpkt *rcvdpkt);
void linkhandler1(int linkid, int newcost);
void printdt1(struct distance_table *dtptr);
void rtinit2();
void rtupdate2(struct rtpkt *rcvdpkt);
void linkhandler2(int linkid, int newcost);
void printdt2(struct distance_table *dtptr);
void rtinit3();
void rtupdate3(struct rtpkt *rcvdpkt);
void linkhandler3(int linkid, int newcost);
void printdt3(struct distance_table *dtptr);
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
stdafx.h
// stdafx.h : include file for standard system include files,
// or project specific include files that are used frequently, but
// are changed infrequently
//
#pragma once
#include "targetver.h"
#include <stdio.h>
#include <tchar.h>
// TODO: reference additional headers your program requires here
#include <stdlib.h>
#include "nodes.h"
#include "DVector.h"
#include <limits.h>
#include <iostream>
using namespace std;
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
targetver.h
#pragma once
// The following macros define the minimum required platform. The minimum required platform
// is the earliest version of Windows, Internet Explorer etc. that has the necessary features to run
// your application. The macros work by enabling all features available on platform versions up to and
// including the version specified.
// Modify the following defines if you have to target a platform prior to the ones specified below.
// Refer to MSDN for the latest info on corresponding values for different platforms.
#ifndef _WIN32_WINNT // Specifies that the minimum required platform is Windows Vista.
#define _WIN32_WINNT 0x0600 // Change this to the appropriate value to target other versions of Windows.
#endif
No comments:
Post a Comment