CIS 432/532: Program #3

CIS 432/532 Introduction to Computer Networks
Fall 2002

Program #3: Implementing a Distance Vector Routing Protocol
Due December 4th, 2:00 PM, online and in class

Overview

In this assignment, you will be writing a set of procedures that implement a "distributed" asynchronous distance vector routing protocol. Two things will make your job somewhat easier than writing a "real" routing protocol. First, the code you write will run within a simulated network environment. Second, your code will run on a simple network with the topology and link costs shown below:

Network topology and link costs for DV routing assignment

In this network, all links are bi-directional and the costs in both directions are identical.

To implement the routing protocol, you will write the following procedures: rtinit0(), rtinit1(), rtinit2(), rtinit3(), rtupdate0(), rtupdate1(), rtupdate2(), and rtupdate3(). 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 if you were really running the procedures in four distinct nodes. To compile your code use the supplied Makefile. The simulator code and the node files are available in /cs/classes/cis432/program3.

Procedures

You will write the following routines which will ``execute'' asynchronously within the simulated 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. 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. 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 not 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.''

The figure below 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(), and rtupdate3().

Relationship between procedures inside node 0

Software Interfaces

The procedures described above are the ones that you will write. We have written the following routines that can be called by your procedures:

tolayer2(struct rtpkt pkt2send): rtpkt is the following structure

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(dtptr): pretty prints 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, and node3.c.

Link Cost Changes

Graduate students must also handle link cost changes. For undergraduates, they will receive extra credit for implementing this. To do this, you should 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 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 in routing.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 STRONGLY recommend that you first implement the rest of the assignment and then extend your code to implement this portion.

The simulated network environment

Your procedures rtinit0(), rtinit1(), rtinit2(), rtinit3(), rtupdate0(), rtupdate1(), rtupdate2(), and rtupdate3() send routing packets (whose format is described above) into the network. The network will deliver packets in-order and without loss to the specified destination. Only directly-connected nodes can communicate. The delay between a sender and receiver is variable (and unknown).

When you compile your program, you will be asked to specify the level of tracing to use in the simulated network environment. This is controlled with the TRACE variable in routing.c. Setting a tracing value of 1 or 2 will print out useful information about what is going on inside the simulation (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 verbose information that likely will not be helpful to you.

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 happening to their packets!

Turning in the Assignment

You must submit all your source code online. Do not submit any object code. Use the submission instructions for this program, which are available in the Schedule section of the class web page.

You must also print out and fill in the survey for this program. The survey is also available in the Schedule section of the class web page. Turn this in to me on the due date (or put it under my office door).

You must also include a printout showing some sample output from your program. Your procedures should print out a message whenever your rtinit0(), rtinit1(), rtinit2(), rtinit3(), rtupdate0(), rtupdate1(), rtupdate2(), and rtupdate3() procedures are called, giving the time (available via the global variable clocktime). For rtupdate0(), rtupdate1(), rtupdate2(), and 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 the 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 the simulator will terminate.

Grading

You will be graded based on how well your protocol implements the distance vector routing protocol. One of the primary sources of information for this grading will be your sample output. Be sure your annotation of the output is clear and illustrates the correct operation of your protocol.

If you wish to receive partial credit for a program that does not operate correctly, you must print out clear and concise information when the program is run. I will use this information to determine how much of your program works and therefore how much partial credit you will receive. The more helpful and clear your output is, the better your chances. You should apply this same standard to how you document your code.

Any program that does not compile will receive a 0.