UM EECS 489 Winter 1998 Programming Assignment 2

UM EECS 489 Fall 1999

Programming Assignment 2

DUE DATE 11/11/1999, 1:30 pm

Note: For this and all subsequent homeworks and programming assignments in this course, whenever we refer to the course directory, we mean the directory /afs/engin.umich.edu/class/f99/eecs489 on CAEN's machines. Each homework and programming assignment will have its own subdirectory under the course directory assignments with the name hw1, hw2, pa3, pa4, etc., we will refer to each assignment's directory as the assignment directory. It is possible that there may be bugs in our code. Please let us know asap if you suspect a bug.

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 the 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. 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.
$\begin{figure}\centerline{\epsfig {file=vrp.eps,width=.5\linewidth}}\end{figure}$

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. A vrouter sends a triggered update whenever there is an increase in any of its entries' metric. A link going up or down also causes the propagation of a triggered update. A triggered update only causes modified entries 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. In keeping track of time, you may find the marco time_diff of help.

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. To implement route poisoning, if the metric of a route has been increasing for VRP_INFLTRND number of updates, set the metric to VRP_INFINITY. To implement path holddown, do not switch path to a destination for a period of VRP_HOLDNRND*VRP_UPDTSECS seconds when the cost of that path increases. Be sure to implement the logic needed to choose the heuristics used from the command line.

2 Your Mission

Fig. 2 depicts the structure of vrouted.

**Figure 2:** Structure of the virtual router `vrouted`.
$\begin{figure}\centerline{\epsfig {file=vrouted.eps,width=\linewidth}}\end{figure}$

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. There's a reason we give you two weekends to work on it. Files with comments suggesting what the functions could contain are available in the assignment directory.

2.1 The Routing Table

The file vrt.h contains the definition of vrt_t, the routing table we use. The first entry of the routing table is treated special and is referred to as of type vrt_self_t. In the previous assignment, we 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.

2.2 The Routing Functions

The main virtual router code calls your vrp_periodic function periodically to manage and propagate your route table.

Your function vrp_update is called by vip_input when a route update arrives from one of your neighbor. 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. Your vrp_propagate sends your route update packets out by calling vip_output.

Your function vrp_reconfig is called when one or more of your vrouted's virtual links go up or down. This function should call vif_isdown on each vif presents in your route table to check whether the link has gone down. In which case, you must change the cost of all destinations you reach through that link to VRP_INFINITY. You must also initiate path hold down and route poisoning for these destinations if called for. For each down vif, you must call vif_offline on it, to tell the vif layer that you have dealt with the link down event. Your vrp_reconfig must also call vif_online to find out the number of vifs that have come up and to actually get the list of recently up vifs. See the function definition of vif_online in the file vif.c for its calling convention. For each up link, add an entry for your new neighbor to your routing table. You can get the name of your new neighbor from the vif. See the vif data structure in vif.h to figure out how to access your new neighbor's name.

2.3 Testing Your Code

To test your code, run a copy of the seeder and several (>= 5 suggested) copies of vrouted as in PA1. The first thing you will notice is that vrouted's output is now much different. Instead of telling you what packet is sent and received, it periodically shows you the latest snapshot of its routing table. Study the routing table vrt_t and the code for function vrp_dump to figure out how to read vrouted's output.

The seeder has also been modified. It now prompts you whether you want to continue testing your vrouteds. If you say yes, it reconfigures the topology of the virtual network connecting your vrouteds. It is okay to see the virtual network partitioned, i.e. some nodes being completely cut off from other nodes. After each reconfiguration, you want to observe the routing tables of your vrouteds and see if they are morphing as your implementation has intended. Once you are satisfied that the routing tables of your vrouteds have stopped changing, you can let the seeder initiate another reconfiguration of the virtual topology.

Each new virtual topology is generated by the seeder randomly. But, just like in a computer game, the successive topologies created by the seeder follow the same pattern each time you run seeder cold. The nice thing about this is that if you have a bug in your code that shows itself only after n topology reconfigurations, you can always be certain that seeder will generate the same topology after every n iterations. If, on the other hand, you want to see some new topologies without going through the same n old topologies, you can change the random seed used by seeder with its -r option. Given the same random seed, seeder always generates the same series of topologies. (Kind of makes one feel blasé about computer games, doesn't it?)

Each of the routing heuristics can be activated or deactivated. In vrp.h wedefine the following macros:

VRP_HEURSHPR as 0x3 for split horizon with poisonous reverse.
VRP_HEURPHD as 0x4 for path hold down.
VRP_HEURRP as 0x8 for route poisoning.

You can specify which of the three heuristics you want to turn on by using vrouted's optional argument -h. For example, to turn on route poisoning you run vrouted -h 8. To turn on both route poisoning and path hold down you run vrouted -h 12. The default setting is to have all three turned on (vrouted -h 15). Look into the definition of vrp_init to see where the heuristics selection is stored.

What to Turn in

Use your turnin client from HW1 to turn in all the files you modified or created. The server name will be announced. Use the same port number (4898). Do not turn in files you do not modify. You shouldn't need to turn in more than the file vrp.c. You do not need to turn in another copy of your info file. If you work in a group, also turn in a README file with the names of all group members.