PAs:


	PA1 Virtual Network
	PA2 Virtual Routing
	PA3 Open Project

HWs:


	HW1(sol)
	HW2(sol)
	HW3(sol)

Don't see the menu?

UM EECS 489 Winter 2010 Programming Assignment 2

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/umich.edu/class/eecs489/w10/PAs/pa2.tgz. 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:

VRP_HEURTRGD (0x1) for triggered update,
VRP_HEURSHPR (0x2) for split horizon with poisonous reverse,
VRP_HEURPHD (0x4) for path hold down,
VRP_HEURRP (0x8) for route poisoning,
VRP_HEURALL (0xf) for all of the above,
VRP_HEURNONE (0x0) for none of the above (default).

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

#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, 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

Q: How is the vrouter_nent field in the routing table used?
A: It is used for memory management. VRP_INITSIZE number of entries are created at a time. If you have more than that number of routers, you can reallocate more memory for the routing table. vrouter_nent tells you how many entries you can have in your route table.
Assuming you've started path hold down, when you receive an update from your current next hop,
Q: If the cost decreases what should happen?
A: The router changes metric and stops hold down.
Q: If the cost increases what should happen?
A: The router changes metric and continues hold down.
Q: If triggered updates is implemented and the cost increases even more. Would this trigger an update to be sent? If route poisoning is also used, is it OK to send out the redundant infinities as triggered updates?
A: Any INCREASE in the cost of a path triggers an update in triggered updates.
Q: For route posioning, if the route has been going up for the required amount of cycles, do we update the route table with infinity or do we only advertise infinity to the neighbors and keep the route table as is?
A: You only advertise infinity, the route table should reflect actual cost.
Q: In struct _vrp {}, the vrp_dv element is listed as being the first of an array of distance vectors. Doesn't this have to be a pointer of some kind if the subsequent elements of that array are going to be accessible?
A: Nope, just make the array big enough to hold all entries you want to send. So, a vrp pkt looks like:
```
   version | type
   entry 1
   entry 2
   entry 3
   .
   .
   .
   entry n
```
Only |version|type|entry1 is defined in vrp_t, the rest you allocate as necessary.
Q: How does a vrouter know who are its neighbors at the beginning? Since a vrouter only has its own address in its router table when it starts, if the vrouter's all just know their own addresses, there is no way to link them together.
A: The seeder tells each vrouter who its neighbors are.
Q: When is vrp_dump() called? Can vrp_update() also call it if it receives a vrp pkt from neighbor that has an invalid version number?
A: vrp_dump() is called from vrp_propagate(). As you can see from Fig 2 of the project description, vrp_dump is not part of the routing protocol. You call it whenever you feel like dumping out the routing table to help you debug. However, before you turn in your code, be sure to leave only one call to vrp_dump() in your code, namely the one made by vrp_propagate() every time it sends out a route updates (and only when it sends out a route update).
Q: If we send out a vrp packet after a triggered update, do we need to include our address (the first entry in the routing table) as a distance vector in the vrp packet?
A: When doing triggered update, you only send the routing table entries whose costs have gone up.
Q: Should an empty slot in the vrouter be indicated by a NULL vif, or a 0 cost?
A: Cost == 0 means the link is definitely down, except for entry 0, which always has cost == 0. The link could ALSO be down if vif is NULL and cost == VRP_INFINITY. You shouldn't be mucking around in the vif layer. If you're in this deep, come talk to me.
Q: If a periodic update followed immediately after triggered update, it would probably show the cost of that path to be same as well. Since the router would now have received an update in which the path cost has not increased, it would set the inflation step back down to 0, even though it really should be either 1 or 2.
A: That's fine. If there were a true counting to infinity going on, you'll get more triggered updates subsequently and be able to do the right thing then.
Q: Where do we use the second parameter of vrp_periodic() function? Do we need to update this value?
A: The second argument is used by vrp_periodic() to communicate to the calling function (vrouter.c:main()) the interval after which to call vrp_periodic() again in the future. It is used in the select() statement in vrouter.c:main(). To avoid all vrouter's sending out updates in a synchronized fashion, the value of the timer should be set to VRP_UPDTSECS plus or minus some small random value.