Figure Lab.4-1: Network topology and link costs for DV routing lab
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
The routines you will write For the basic part of the assignment, you are to write the following routines which will ``execute'' asynchronously within the emulated environment that we have written for this assignment.
For node 0, you will write the routines:
rtinit0() This routine will be called once at
the beginning of the emulation. rtinit0() has no
arguments. It should initialize the distance table in node 0
to reflect the direct costs of 1, 3, and 7 to nodes 1, 2, and
3, respectively. In Figure 1, all links are bi-directional
and the costs in both directions are identical. After
initializing the distance table, and any other data
structures needed by your node 0 routines, it should then
send its directly-connected neighbors (in this case, 1, 2 and
3) the cost of it minimum cost paths to all other network
nodes. This minimum cost information is sent to neighboring
nodes in a routing packet by calling the routine
tolayer2(), as described below. The format of
the routing packet is also described below.
rtupdate0(struct rtpkt *rcvdpkt). This
routine will be called when node 0 receives a routing packet
that was sent to it by one if its directly connected
neighbors. The parameter *rcvdpkt is a pointer
to the packet that was received.
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.
Similar routines are defined for nodes 1, 2 and 3. Thus, you
will write 8 procedures in all: rtinit0(),
rtinit1(), rtinit2(),
rtinit3(), rtupdate0(),
rtupdate1(), rtupdate2(),
rtupdate3()
Figure Lab.4-2: Relationship between procedures
inside node 0
The procedures described above are the ones that you will write. We have written the following routines that can be called by your routines:
tolayer2(struct rtpkt pkt2send)where rtpkt is the following structure, which
is already declared for you. The procedure
tolayer2() is defined in the file prog3.c
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.
printdt0()will pretty print the distance table for node 0. It is
passed a pointer to a structure of type
distance_table. printdt0() and the
structure declaration for the node 0 distance table are
declared in the file node0.c. Similar
pretty-print routines are defined for you in the files
node1.c, node2.c,
node3.c.
Your procedures rtinit0(), rtinit1(), rtinit2(),
rtinit3() and rtupdate0(), rtupdate1(), rtupdate2(),
rtupdate3() send routing packets (whose format is
described above) into the medium. The medium will deliver packets
in-order, and without loss to the specified destination. Only
directly-connected nodes can communicate. The delay between is
sender and receiver is variable (and unknown).
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:
Tracing. Setting a tracing value of 1 or 2 will print out useful information about what is going on inside the emulation (e.g., what's happening to packets and timers). A tracing value of 0 will turn this off. A tracing value greater than 2 will display all sorts of odd messages that are for my own emulator-debugging purposes.
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 are to write the procedures rtinit0(),
rtinit1(), rtinit2(),
rtinit3() and rtupdate0(),
rtupdate1(), rtupdate2(),
rtupdate3() which together will implement a
distributed, asynchronous computation of the distance tables for
the topology and costs shown in Figure 1.
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.
You are to write two procedures, rtlinkhandler0(int
linkid, int newcost) and rtlinkhandler1(int linkid,
int newcost), which will be called if (and when) the cost
of the link between 0 and 1 changes. These routines should be
defined in the files node0.c and
node1.c, respectively. The routines will be passed
the name (id) of the neighboring node on the other side of the
link whose cost has changed, and the new cost of the link. Note
that when a link cost changes, these routines will have to update
the distance table and may (or may not) have to send updated
routing packets to neighboring nodes.
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!)
When we've taught this lab in our introductory neworking course, students have posed versious questions. If you are interested in looking at the questions we've received (and answers), check out http://gaia.cs.umass.edu/kurose/network/programming_assignment_QA.htm