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 program.

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), regardless of whether the information has changed since the last announcement. This strategy improves the robustness of the protocol. For instance, a lost message will be automatically recovered by later messages. In this strategy, typically a host re-computes its distance vector and routing table right before sending out the routing information to its neighbors.

Since we don't have real network routers for you to play with, 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 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 format:

Your program at host x 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 "y cost", which stands for a link between node x and node y 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.

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

The input files at all hosts will look like the following: a.dat, b.dat, c.dat, d.dat, e.dat, and f.dat. Note that in the above example, a, b, ... stand for real machine names such as phelps, colden, and macomb in the CSUG lab.

Be aware that we will use DIFFERENT network topologies in our testing.

Output format:

Your program should produce a terminal output each time it sends out the routing information to its neighbors (i.e., once every 10 seconds). Each such output should include an incremental sequence number (1 for the first output, 2 for the second output, etc.). Each output should also include the cost and the next hop for the shortest paths to all other network nodes. For instance, one of the terminal outputs at node a may look like the following.
 ## sequence number 10
 shortest path to node b: the next hop is b and the cost is 2.0
 shortest path to node c: the next hop is d and the cost is 3.0
 shortest path to node d: the next hop is d and the cost is 1.0
 shortest path to node e: the next hop is d and the cost is 2.0
 shortest path to node f: the next hop is d and the cost is 4.0
      
You must produce the terminal output from the first time the host sends out its routing information to its neighbors. Yes, the first a few outputs often contain immature routing information.

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.

You program does not need to terminate. It should keep running and outputting the routing information until being killed (e.g., though Ctr-C).

Link cost change:

Your implementation should also be able to handle link cost changes. In our test platform, link cost changes manifest as value updates in the neighbor link input files. More specifically, to emulate the cost change of a link, the input files for the two nodes attached to the link should be updated. During your testing, you might not be able to update the two files simultaneously. But this is fine --- in practice the two attached nodes may not simultaneously detect a link cost change either. Due to a potential link cost change, your program at each host should re-read the link input file each time it is about to re-compute its distance vector and routing table (typically right before sending out the routing information to its neighbors).

Although normally a link cost change can be handled quickly, the distance vector algorithm may suffer from the recursive-update problem (recall our discussion in class). In class we also discussed a solution to solve the recursive-update problem that only involves two-node routing loops. You should implement this solution and test it.

Note that your implementation only needs to support link cost changes, not network topology changes.

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. Although in theory different nodes can listen at different UDP ports, for simplicity we assume all nodes will listen at the same UDP ports. So the input UDP port numbers at all nodes should be the same. The README file should contain a description of your design and implementation strategies. It should describe how to run your program (the exact parameter format, etc.). Please also provide a makefile that builds your program from submitted sources.

The turn-in procedure is the same as that of assignment #1.

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.