DUE DATE Mon, 3/15/2010, 9:00 am
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.
example.engine% vrouter -h 8To 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.
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.example.engin% seeder -n 5 -f test_shprThen run a vrouter on 5 different machines with the following command:
% vrouter -S example.engin -h 2Unless 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:
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.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.
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.
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 nOnly |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.