Assignment #2 - Implementing the Distance Vector Routing Protocol

Due by 11:59pm, Friday, October 14.

Assignment requirements:
In this assignment you are asked to implement the distance vector routing protocol. Your program will be running at all hosts in the specified network. At each host, the input to your program is the set of directly attached links and their costs. Note that the program at each host doesn't know the complete network topology. Your routing program at each host should report the cost and the next hop for the shortest paths to all other hosts in the network. This is an individual assignment, so each person should turn in his/her own.

Instead of implementing the exact distance vector routing protocol described in the textbook, you are asked to implement a variation of the protocol. In this protocol, each host sends out the routing information to its neighbors at a certain frequency (once every 10 seconds), no matter if there has been any changes since the last announcement. This strategy improves the robustness of the protocol. For instance, a lost message will be automatically recovered by later messages.

Since we can't let you play with real network routers, your programs will run on desktop machines in the CSUG lab or the graduate software lab. However, if your routing software runs well on a set of desktop machines, it will also likely to work on real network routers. As specified in the distance vector protocols, your routing program at each host will exchange the routing information with directly connected neighbors. Real routing protocols use UDP for such exchanges. Under such a scheme, each host should listen at a UDP port for incoming routing messages.

Input/output format:
Your program at host n1 should take a text file as input, which describes the set of directly attached links and their costs. The first line of the text file is a single number, which stands for the number of directly attached links. All subsequent lines in the input file are in the format of "n2 cost", which stands for a link between node n1 and node n2 with cost cost. Note that cost can be a floating point number. The two fields are separated by a single space in each line of the input file. As output, your program should print out the cost and the next hop for the shortest paths to all other network nodes.

Let's look at an example with the network topology shown in the following figure.

Note that a, b, ... stand for real machine names such as phelps, colden, and macomb in the CSUG lab. The input files at all hosts will look like the following: a.dat, b.dat, c.dat, d.dat, e.dat, and f.dat. Your program output at node a should look like the following. We will use DIFFERENT network topology in our testing.

Startup and termination: It is possible that some hosts may start earlier than their neighbors. As a result, you might send the routing information to a neighbor which has not run yet. You should not worry about this since your routing program at each host will repeatedly send the routing information to its neighbors and a slow-starting neighbor will eventually get the information.

Termination can also be a tricky part of your implementation. Real routing programs run forever without termination, but your program need to print out the routing table at some point in order to successfully complete the assignment. The key is to find out when the routing distance vector has stabilized. We can assure you that when we test your program, we will start your routing program on all participating hosts within a short time period (e.g., 10 seconds) and there will not be link changes during the test. It will be your job to find out when the routing distance vector has stabilized and thus you can print out the output. Don't make us wait for more than three minutes!

Turn-in:
You are asked to turn in your source files, a makefile if needed, and a README file. No matter what programming language you choose to use, your program should take two parameters (its listening UDP port number and the input file that describes directly attached links) on startup. You should also name your executable to be dv_routing. If your program is written in Java, you should be able to launch your server using "java dv_routing <port-number> <input-file>". If your program is written in C/C++, you should be able to launch your server using "dv_routing <port-number> <input-file>".

The README file should contain a description of your design and implementation strategies. If your program requires any special compilation flag to build, you need to specify the full build command in the README file. Alternatively, you can provide a makefile, which is strongly preferred.

The turn-in procedure is the same as the first assignment.

Grading:

Late turn-in policy:
Late turn-ins will be accepted for up to three days, with 10% penalty for each late day. No turn-ins more than three-day late will be accepted.