UM EECS 489 Winter 2010


Programming Assignment 2

DUE DATE Mon, 3/15/2010, 9:00 am

Plain Page for Printing

Note: The files mentioned here can be found in the assignment directory: /afs/ You need to copy all the files from this tarball, do not reuse files with the same name from PA1.

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. For this programming assignment, you need to review the lecture notes for the definitions and examples of split-horizon with poisonous reverse, route poisoning, and path hold down. 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, in network byte order, 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, using the -h command line option of vrouter. The following macros are defined in vrp.h: For example, to turn on route poisoning you run:
example.engine% 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(2) to retrieve the current time.)

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

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. Assume triggered update is not enabled. A is directly connected to B and C, each with a link cost of 1. A advertises cost to C of 1, B advertises cost of 2. Suppose link AC breaks and B's advertisement arrives at A shortly after. Now A adopts B as its neighbor to C, at cost 3 and starts the route poisoning timer. B gets A's old advertisement that was sent out before its link to C goes down and send out one more advertisement of cost 2 to C. Upon getting B's new advertisement, A could interpret B's advertisement as a sign that the network is now stable (cost hasn't been increasing) and stops the route poisoning timer.

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 smaller number of functions you have to modify, compared to that of PA1, fools you into thinking that this is a simpler PA. Start work on this PA early. All the functions you need to write/modify are in the file vrp.c.

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 the previous assignment, 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. 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(). To help with debugging, it is useful for vrp_propagate() to call vrp_dump() to output the routing table to screen everytime it sends out a route update.

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 before my implementation of these functions are available in _vrp.o. Note however, since these functions are more closely tied than functions in the previous assignment, 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_t's 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. You should also test your heuristics in conjunction with each other. 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:
  1. #include "file"
  2. , 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, the intention being that we want to wait for changes to propagate throughout the 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 for our virtual network to stabilize, hence the option for you to tell seeder how many seconds to wait before continuing, as an argument to the `,' directive.

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 command line 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.

If you run my vrouter with the command line option -o, it outputs to the screen latest snapshot of its routing table everytime it sends a VRP update. 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, as explained above.

You'll also notice that vrouter no longer sends out VTP test packets. If you'd like to test your connectivity by sending some VTP packets, there are two new command line options you can use with vrouter: -t <testnum> and -d <hostname>. The -t <testnum> option allows you to tell the vrouter how many test VTP packets you want it to send out, it defaults to zero. The -d <hostname> option allows you to tell the vrouter the destination hostname you want the test VTP packets sent. If not specified, the destination is chosen randomly for each packet. When a VTP test packet is sent, its ttl is probabilistically set to either the number of hop count needed to reach the destination or a number smaller than that.

If you haven't read my "General Advice on Programming Assignments," please do so.

Frequently Asked Questions