In this lab, you will be writing a ``distributed'' set of procedures
that implement a distributed asynchronous distance vector routing for the
network shown in Figure Lab.4-1.
Figure Lab.4-1: Network topology and link costs for DV routing lab
For node 0, you will write the routines:
rtupdate0() is the ``heart'' of the distance vector algorithm. The values it receives in a routing packet from some other node i contain i's current shortest path costs to all other network nodes. rtupdate0() uses these received values to update its own distance table (as specified by the distance vector algorithm). If its own minimum cost to another node changes as a result of the update, node 0 informs its directly connected neighbors of this change in minimum cost by sending them a routing packet. Recall that in the distance vector algorithm, only directly connected nodes will exchange routing packets. Thus nodes 1 and 2 will communicate with each other, but nodes 1 and 3 will node communicate with each other.
As we saw in class, the distance table inside each node is the principal data structure used by the distance vector algorithm. You will find it convenient to declare the distance table as a 4-by-4 array of int's, where entry [i,j] in the distance table in node 0 is node 0's currently computed cost to node i via direct neighbor j. If 0 is not directly connected to j, you can ignore this entry. We will use the convention that the integer value 999 is ``infinity.''
Figure Lab.4-2 provides a conceptual view of the relationship of the
procedures inside node 0.
Figure Lab.4-2: Relationship between procedures inside node
0
extern struct rtpkt { int sourceid; /* id of node sending this pkt, 0, 1, 2, or 3 */ int destid; /* id of router to which pkt being sent (must be an immediate neighbor) */ int mincost[4]; /* min cost to node 0 ... 3 */ };Note that tolayer2() is passed a structure, not a pointer to a structure.
When you compile your procedures and my procedures together and run the resulting program, you will be asked to specify only one value regarding the simulated network environment:
A tracing value of 2 may be helpful to you in debugging your code. You
should keep in mind that real implementors do not have underlying
networks that provide such nice information about what is going to happen
to their packets!
You should put your procedures for nodes 0 through 3 in files called node0.c, .... node3.c. You are NOT allowed to declare any global variables that are visible outside of a given C file (e.g., any global variables you define in node0.c. may only be accessed inside node0.c). This is to force you to abide by the coding conventions that you would have to adopt is you were really running the procedures in four distinct nodes. To compile your routines: cc prog3.c node0.c node1.c node2.c node3. Prototype versions of these files are here: node0.c, node1.c, node2.c, node3.c. You can pick up a copy of the file prog3.c at http://gaia.cs.umass.edu/kurose/network/prog3.c.
This assignment can be completed on any machine supporting C. It makes no use of UNIX features.
As always, most instructors would expect you to hand in a code listing, a design document, and sample output.
For your sample output, your procedures should print out a message whenever your rtinit0(), rtinit1(), rtinit2(), rtinit3() or rtupdate0(), rtupdate1(), rtupdate2(), rtupdate3() procedures are called, giving the time (available via my global variable clocktime). For rtupdate0(), rtupdate1(), rtupdate2(), rtupdate3() you should print the identity of the sender of the routing packet that is being passed to your routine, whether or not the distance table is updated, the contents of the distance table (you can use my pretty-print routines), and a description of any messages sent to neighboring nodes as a result of any distance table updates.
The sample output should be an output listing with a TRACE value of
2. Highlight the final distance table produced in each node. Your program
will run until there are no more routing packets in-transit in the network,
at which point our emulator will terminate.
In order to complete the advanced part of the assignment, you will need to change the value of the constant LINKCHANGES (line 3 in prog3.c) to 1. FYI, the cost of the link will change from 1 to 20 at time 10000 and then change back to 1 at time 20000. Your routines will be invoked at these times.
We would again STRONGLY recommend that you first implement the
undergraduate assignment and then extend your code to implement the graduate
assignment. It will not be time wasted. (Believe me, I learned this
the hard way!)