UM EECS 489 Winter 2007
UM EECS 489 Winter 2007
Programming Assignment 2
DUE DATE 3/19/2007 (extended)
Download the code from here.
It is possible that there may be bugs in the code. Please let us
know asap if you suspect a bug.
Please first read this to learn the
virtual network set up. Now that you are comfortable using our virtual
network, you can work on building and maintaining it.
1 VRP:
Virtual Routing Protocol
The routing protocol used in our virtual
network is a distance-vector routing protocol that implements the
triggered update, split-horizon with poisonous reverse, path hold
down, and route poisoning heuristics. To do this programming
assignment, please refer to this note for the
definitions of triggered updates, split-horizon with poisonous
reverse, route poisoning, and path hold down.
Fig. 1 depicts the format
of VRP packets.
The version field must contain the current VRP_VERSION,
defined in vrp.h. Non-conforming packets should be dropped.
The type field specifies the type of data carried in the
VRP packet.
Currently we only recognize VRP_TYPEDV, which
specifies that the data carried is a list of distance vectors. Each
distance vector in a VRP packet contains the vin_addr_t
of a destination. The vad_metric field of the
vin_addr_t carries the distance between the sender of the VRP
packet and that destination. A VRP packet can be of size up to
the largest VIP packet size. The macro vrp_ndv
helps you determine how many distance vectors are carried in a VIP
packet of a given size.
Figure 1:
VRP Packet Format.
 |
In your implementation of VRP, you MUST allow each of the routing
heuristics to be turned on or off.
Use the following macros defined in vrp.h:
- VRP_HEURTRGD as 0x1 for triggered update,
- VRP_HEURSHPR as 0x2 for split horizon with poisonous reverse,
- VRP_HEURPHD as 0x4 for path hold down,
- VRP_HEURRP as 0x8 for route poisoning,
- VRP_HEURALL as 0xf for all of the above.
- VRP_HEURNONE as 0x0 for none of the above (default).
You can specify which of the four heuristics you want to turn on by
using vrouter's optional argument -h. For example, to
turn on route poisoning you run vrouter -h 8. To turn on both
route poisoning and path hold down you run vrouter -h 12.
To run all four heuristics, do vrouter -h 15.
The default setting is no heuristics (vrouter -h 0).
Look in the definition of vrp_init() to see where the
heuristics selection is stored.
1.1 Periodic and Triggered Updates
A vrouter's entire routing table is sent to all its neighbors
every VRP_UPDTSECS. Each entry in the route table has a time
stamp associated with it. For each distance vector present in an
incoming update packet, if the recipient uses the source of that
update packet as the next hop towards the destination named in the
distance vector, the recipient must refresh the corresponding entry in
its routing table by resetting the entry's timestamp to the current
time. (Hint: Use gettimeofday(3C) to retrieve the current
time.) If an entry has not been refreshed for more than
VRP_STALERND*VRP_UPDTSECS seconds it should be
considered stale and its metric set to VRP_INFINITY. If the
route is not refreshed VRP_PURGERND*VRP_UPDTSECS
seconds after it becomes stale, it must be deleted from the route
table. If triggered update is implemented, a vrouter sends a
triggered update whenever there is an increase in any of its
entries' metric. A link going down also causes the propagation of a
triggered update. A triggered update only causes entries with increased
cost to be propagated and does not cause a reset of the periodic update timer,
i.e. a periodic update could follow right after a triggered
update. You may find the fields vrouter_nmod in the
vrouter structure and vrtbl_mod in the
vrtbl_t structure useful to keep track of the number of
modified entries you need to send out and to mark the individual entry
you need to send out, respectively. In keeping track of time, you may
find the macro time_diff helpful.
1.2 Of Poisons, Spells, and Witches' Brew
To implement split-horizon with poisonous reverse, report the
metric of a route as VRP_INFINITY to the neighbor that is the
next hop for that route. You know that a node is a neighbor if the
cost to that node is VIF_DIRECT.
To implement path hold down, do not
switch the path to a destination for a period of
VRP_HOLDNRND*VRP_UPDTSECS seconds when the cost of that
path increases.
To implement route poisoning, if the
metric of a route has been increasing for VRP_INFLTRND number
of updates, advertise the metric as VRP_INFINITY.
When implementing route poisoning, you need to pay attention to the
following detail: it takes two updates for an old metric to leave the
system, for example, assume nodes A and B are involved in bouncing effect for
destination C. A advertises cost to C of 2, B advertises cost of 3.
Upon getting B's advertisement, A bumps up its cost to C to 4.
Upon getting A's advertisement, B bumps up its cost to C to 3.
Next B advertises cost to C of 3. If A is not careful, it could
interpret B's advertisement as a decrease in its cost to C (from 4 to 3)
and stop doing route poisoning. To prevent this in your implementation
of route poisoning, whenever you inflate your cost to a destination,
use the variable vrtbl_reflected to keep track of whether
you have seen your old cost ``reflected'' back from your current
next hop. You should ignore your own reflections and cancel route
poisoning only if the inflated cost to a destination stays constant
or lower beyond your reflection. Read also the comments associated with
vrtbl_reflected in vrp.h.
2 Your Mission
Fig. 2 depicts the structure of vrouter.
Figure 2:
Structure of the virtual router vrouter.
|
In the figure, data structures are enclosed in rounded boxes and
functions in square boxes. You are to define and implement the
functions depicted in bold. Don't let the small number of
functions you have to modify fool you into
thinking that this is a simple PA. Start work on this PA early.
All the functions you need to write/modify are in the file vrp.c
in the assignment directory.
2.1 The Routing Table
The file vrp.h contains the
definition of vrouter_t which is the top most data structure
representing a vrouter. It points to a virtual link table
(vit_t) and a routing table (vrtbl_t) along with
other state information about the vrouter. DO NOT use the
virtual link table (vrouter_vifs) in your code. Use only the
information available in the routing table (vrouter_rt).
In general, in doing this programming assignment,
you should not need to know anything about vifs
beyond accessing the interface's address (vif_vad).
The first entry of the routing table MUST always contain the
vrouter's own vin_addr_t with vad_metric
set to 0. In general, I stipulated that all
fields in a vin_addr_t must always be in network
byte order. Here's an exception to that rule: when, and only
when, stored in the routing table, the vad_metric field
of the route table entry's vrt_dst field, which is of type
vin_addr_t, must always be in host byte order. This
means that you need to translate between host and network byte orders
when copying the cost of a destination from the route table to a
distance vector in a VRP packet, and vice versa.
The definition of the routing table is available in the file
vrp.h in the assignment directory. You should read the
comments next to each field carefully. They tell you how to interpret
and use the fields.
2.2 The Routing Functions
The main virtual router code calls your vrp_periodic() function
periodically to manage and propagate your route table.
Your vrp_update() is called by vip_input() when a
route update arrives from one of your neighbors. Your
vrp_update() must implement triggered update and path
hold down.
Both vrp_update and vrp_periodic call your
vrp_propagate() to send out their route updates. Your
vrp_propagate() must implement both split horizon with
poisonous reverse and route poisoning (recall the above
discussion on catching your reflections). Your vrp_propagate()
sends your route update packets out by calling vip_output().
The function vrp_reconfig() is called when one or more of your
vrouter's virtual links go up or down. Most of this function
is given to you.
The only part you need to implement is when a link is down, you must
change the cost of all destinations you reach through that link to
VRP_INFINITY. You may also need to initiate any routing
heuristics applicable here.
The file vrp.c in the assignment directory contains the
skeletons of these functions with comments on what each of these
functions should contain. As usual my implementation of these
functions are available in _vrp.o. Note however, since
these functions are more closely tied than functions in previous
assignments, your version of any one of them may not work very
smoothly with mine.
In writing your code, you may find the macro vin_eq() useful
for comparing vin_addr_ts and the macro time_diff()
useful for comparing timestamps.
2.3 Testing Your Code
You should find the following three scenario files in the assignment
directory: test_shpr, test_phd, and test_rp.
They all require 5 vrouters. As the filenames indicate,
I found each one of them useful for testing the heuristics named in
the filename. See the comments at the top of each file for a description
of each scenario. To test the shpr heuristics for example,
run the seeder with the following command:
example.engin% seeder -n 5 -f test_shpr
Then run a vrouter on 5 different machines with the following
command:
% vrouter -S example.engin -h 2
Unless specified, no heuristics is assumed. I suggest running
each scenario without any heuristics to see how counting to infinity
manifests itself on that scenario. Then test the heuristics one
at a time. Usually when triggered updates is set, you don't
see counting to infinity at all, so test your implementation of the
various heuristics without triggered updates first. You should also
test your heuristics in conjunction with each other. There is another
scenario file, test_complex, in the assignment directory.
It builds a somewhat more complicated topology involving 7
vrouters. You should experiment with various scenarios
of your own to test your implementation.
You will find the following two directives useful in constructing
your scenario (script) files:
- #include "file"
- , n
The first allows you to include a scenario file in another scenario
file. The second allows you to commit and apply pending changes, wait for
n seconds for the routing tables to stabilize, before
continuing with the rest of the scenario file. See the file
test_rp for example usage. If n is not specified,
i.e. when the comma is on a line by itself, the seeder waits
for a period that is a multiple of the number of vrouters
before continuing with the rest of the script file.
After it finishes processing a script file, the seeder
presents you with the following prompt:
Continue testing (random, scriptfile, manual, quit) [n]?
If you select `r'andom, the seeder randomly connects
the nodes in your network. It is okay to see the virtual network
partitioned, i.e. some nodes being completely cut off from
other nodes. Successive random topologies created
by the seeder follow the same pattern each time you
start over. If you have a bug in your code that shows itself only
after k successive topology reconfigurations, you can always
be certain that seeder will generate the same sequence of
topologies after every k iterations. If, on the other hand,
you want to see some new topologies without going through the same
k old topologies, you can change the random seed used by
seeder with the -r option.
To have the seeder load a script file choose `s',
or you can enter the script manually by choosing `m'.
The syntax for manual entry is exactly the same as the syntax
for the script file. So after a network is set up, you can
manually bring down a link, manually bring up a down link,
or manually add a new link between two nodes, or specify a
list of additions and deletions.
When you run the new vrouter, the first thing you will notice
is that its output is now much different. Instead of messages about
VTP pkts sent and received, it periodically dumps the
latest snapshot of its routing table.
Study the routing table data structure vrt_t and the
code for function vrp_dump to figure out how to read
the routing table dumps.
After each reconfiguration of your virtual network, either through
seeder's random configuration, as part of your script file, or
by your manual reconstruction, you should study the routing tables
of all vrouters on your virtual network and see if they
are morphing as you have intended (or if they are changing in ways
similar to how they change when you run my vrouter). Once you
are satisfied that the routing tables of your vrouters
have stabilized (stopped changing), you can let the seeder
initiate another round of reconfiguration. Remember that you
can commit all changes to the virtual topology in your script files
by using the `,' directive. When executing the `,' directive,
the seeder waits a certain amount of time before continuing
with the rest of the script. This amount of time is a function
of the number of vrouters you have, the intention being
that we want to wait for changes to propagate throughout your
virtual network before making more changes. Sometimes, e.g. when
CAEN's network is heavily loaded, the automatically computed time
may not be long enough.
You can tell seeder how many seconds to wait before continuing
as an argument to the `,' directive as discussed above.
2.4 Extra Credit (20% of the project grade)
You may choose
not to do this part. You earn extra credit only if you get at least
90 out of 100 points for the main part of the programming assignment.
Otherwise, you get nothing, regardless how good it is. If you
implement this part, you will need to give me a demo of your code.
There are two options for extra credit. You will get credit for
only one of them.
2.4.1 Implement Path Vector
Path vector is defined in
lecture. In place of the heuristics above, implement path vector.
You will need to define a new data structure to hold the path vector
in the routing table. You will also need to modify the route update
packet format to carry path vectors instead of distance vectors. With
path vector, each vrouter must check a path for routing loops before
using it. It must also update the path vector of paths it uses before
sending them out. If you choose to do this part of the assignment,
you must also write a document similar to but more detailed than this
one to describe your implementation.
2.4.2 Implement Link-State Protocol
Similar to the above,
except that you implement a link-state routing protocol that uses
Dijkstra's Shortest Path First algorithm to compute shortest path.
This will entail even more drastic changes to your routing table and
route update messages.
What to Turn in
Use the turnin client from HW1 to turn in all the files,
AND ONLY THOSE FILES, you modified or created. Same server
name (koala.eecs.umich.edu), same port number (4891), for pa2.
Do not turn in files you do not modify. You shouldn't need to turn in
more than the file vrp.c. If you work in a group, also
turn in a README file with the names of all group members. Turn
in only ONE assignment per group. If you do the extra credit part,
say so in your README file. Prepend the tag extra_ to
all files created for the extra credit part and turn them in also.
Acknowledgments
The original turnin code was the
work of Prof. Sugih Jamin. This document is a modification of the
assignment created by Prof. Jamin.