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:
- 60%: a working program that correctly computes the shortest paths from
all-node startup and prints out the results in a reasonable time frame.
- 20%: correctly re-computes the shortest paths from link cost changes
and prints out the results in a reasonable time frame (at the absence of
the recursive-update problem) .
- 10%: quickly handle the recursive-update problem that only involves
two-node routing loops.
- 10%: a clear README file, clarity of your source code and completeness of
your comments.
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.