EECS 489 Fall 1999

 

Programming Assignment 1

DUE DATE 10/14/1999, 1:30 pm
Note: The source files that you will need to modify can be found in the directory /afs/engin.umich.edu/class/f99/eecs489/assignments/pa1/source. It is possible that there may be bugs in the code. Please let us know asap if you suspect a bug.

1 The Virtual Network

For this assignment, you are to write a router for a virtual network. Our virtual network consists of two parts: the virtual router ( vrouted henceforth) itself and a topology seeder. To construct your own private virtual network, you run one copy of seeder and one or more copies of vrouted. The seeder must be run before the vrouted's. Aside from seeding the topology of the virtual network, the seeder also sends some test messages on the virtual network. Hence you might want to start with testing one instance of your vrouted. To do so, you log yourself into two Solaris machines, say a.engin and b.ummu. On the respective machines you type:
         a.engin% seeder -n 1
          b.ummu% vrouted -S a.engin
Once you have debugged the single instance of your vrouted, you can test multiple instances of it. For example, to create a 4-node virtual network consisting of b.ummu, c.eecs, d.engin, and e.ummu, with the seeder running on a.engin, you do:
         a.engin% seeder -n 4
          b.ummu% vrouted -S a.engin
          c.eecs% vrouted -S a.engin
         d.engin% vrouted -S a.engin
          e.ummu% vrouted -S a.engin

2 Addressing on the Virtual Network

Each of your vrouteds is addressed by the IPv4 address of the machine they run on and a well-known port number. The default well-known port number is VRTD_PORT defined in vnet.h. In case you need to share a machine with someone else running vrouted, you can choose a different port number with the -p option of vrouted. All of your vrouted's must be using the same well-known port. For example, to use port number 7896 in the above 4-node scenario, you do:
         a.engin% seeder -n 4
          b.ummu% vrouted -S a.engin -p 7896
          c.eecs% vrouted -S a.engin -p 7896
         d.engin% vrouted -S a.engin -p 7896
          e.ummu% vrouted -S a.engin -p 7896
In case your seeder conflicts with another seeder on the same machine, the well-known port number of the seeder can also be changed. To use port number 8707 with your seeder, you do:
         a.engin% seeder -n 4 -p 8707
          b.ummu% vrouted -S a.engin -P 8707 -p 7896
          c.eecs% vrouted -S a.engin -P 8707 -p 7896
         d.engin% vrouted -S a.engin -P 8707 -p 7896
          e.ummu% vrouted -S a.engin -P 8707 -p 7896
To address each other, vrouted's use the virtual internetwork address (vin_addr_t henceforth) depicted in Fig. 1, where the IPv4 Address is the IPv4 address of the machine the vrouted runs on, the Port Number is the well-known port number the vrouted listens on, and the metric is the metric of the link to be interpreted by higher level protocols. All the numbers in a vin_addr_t must be kept in network byte-order at all times.
Figure 1:  vin_addr_t
\begin{figure}\begin{center}\hspace*{10ex}\epsfig {file=vin.eps,width=.4\linewidth}\end{center}\end{figure}
 

3 Virtual Links

Upon start up, each vrouted registers itself with the given seeder. The seeder then determines the connectivity of the virtual network, i.e. which vrouted connects to which other. With prompting from the seeder, each vrouted opens a permanent virtual link (vif) to pull up its designated neighbors. Each vif is assumed to be a bidirectional (full-duplex) link. The virtual link layer is provided to you. In the file vif.c you will find the definition of the following APIs for the vif layer:
int vif_pullup(vif_t *vif, char *buf, int len);
int vif_pullupn(vif_t *vif, char *buf, int len);
int vif_output(vif_t *vif, u_short prot, vbuf_t *vbp);
When a packet arrives for your vrouted, the vif on which the packet arrives parses the vif header of the packet and calls the appropriate upper layer protocols' APIs. You are to write several such upper layer protocols' APIs in this programming assignment (see Sections 5.1 and 5.2 below). Your upper layer protocol can call vif_pullup to its data from the virtual link just like you use recv(3N). Or it can call vif_pullupn to pull up n bytes. You call vif_output to put data on the virtual wire. See the function definitions in vif.c. In case you wonder at the choice of the API names, they are similar to what are used in the BSD kernel, so you get an experience of writing kernel code without most of the hassle usually associated with it.

4 Virtual Buffer Chain

One obvious way to encapsulate a higher layer message into a lower layer message is allocate enough space for the lower layer header and the upper layer message. Unfortunately, message copying is very expensive. Actually, memory copy has been identified as one of the most expensive operations in networking code. We would like to reduce copying to a minimum. For that purpose, we have defined a virtual buffer chain (vbuf_t). Each vbuf_t element points to a chunk of bits and records the size of the chunk. As a message traverses down the protocol layer stack, each layer creates a new vbuf_t element for its header and prepends the new element to the virtual buffer chain before passing the chain down to the next lower layer. Fig. 2 depicts the vbuf chain of a message going down the VTP, VIP, and VIF layers. The virtual link layer at the bottom transmits each vbuf_t element without making extra copies.
Figure 2:  vbuf Chain Traversing the Protocol Stack.
\begin{figure}\begin{center}\epsfig {file=vbufchain.eps,width=.5\linewidth}\end{center}\end{figure}
 

5 Virtual Router

Our virtual router (vrouted) speaks 4 protocols:
VIP:
Virtual Internetwork Protocol, a connectionless internetwork protocol.
VCMP:
Virtual Control Message Protocol, an error reporting control message protocol.
VRP:
Virtual Routing Protocol, a distance-vector protocol that implements split-horizon with poisonous reverse, path hold-down, and route poisoning.
VTP:
Virtual Transport Protocol, currently does nothing but prints out the data it receives on the screen.

5.1 VIP: Virtual Internetwork Protocol

Figure 3:  VIP Packet Header Format.
\begin{figure}\begin{center}\hspace*{5ex}\epsfig {file=vip.eps,width=.4\linewidth}\end{center}\end{figure}
 

VIP is a connectionless internetwork protocol. Fig. 3 depicts the packet header format of VIP. The Version field contains the version number, currently set to VIP_VERSION defined in vip.h . Packets with version number different from VIP_VERSION should be discarded. The Hop Limit field contains the number of hops a packet has traversed. At every router, this field should be decremented by one and the packet should be discarded if this field is <= 0. The Pkt Length field contains the size of packets in bytes, excluding the header. The Protocol field specifies whether this is a vcmp, vrp, or vtp packet. The protocol numbers of VRP, VCMP, and VTP are VIP_PROTOVCMP, VIP_PROTOVRP and VIP_PROTOVTP respectively, as defined in vip.h. VIP identifies a host by its vin_addr_t as described in Section 2.  The Checksum field is used for error checking of the packet header. Packets with incorrect checksums should be discarded. Hint for checksum computation: The checksum field is at the very end of the VIP header, and vip_cksum() takes a parameter specifying the length over which you wish to calculate the checksum.

5.2 VCMP: Virtual Control Message Protocol

When a non-VCMP packet encounters one of the following errors, the vrouted holding the packet should report the error back to the packet's sender. The above error codes and messages are defined in vcmp.h and vcmp.c. The format of a VCMP packet is depicted in Fig. 4.
Figure 4:  VCMP Packet Header Format.
\begin{figure}\begin{center}\hspace*{5ex}\epsfig {file=vcmp.eps,width=.4\linewidth}\end{center}\end{figure}
 

The version should be VCMP_VERSION and the error code one of the above listed. The VIP header of the packet encountering error is returned along with the error code. No error should be generated for VCMP packets.

5.3 VRP: Virtual Routing Protocol

VRP will be the subject of the next programming assignment. For this programming assignment, you may find the following functions useful:

5.4 VROUTED: A Virtual Router

Figure 5:  Design of the virtual router vrouted.
\begin{figure}\begin{center}\epsfig {file=vrouted.eps,height=.4\textheight,width=\linewidth}\end{center}\end{figure}
 

The design of the router (vrouted) is depicted in Fig. 5. 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. Files with comments suggesting what the functions could contain are available in the assignment directory. In the assignment directory you will also find the object code for our version of the functions you are to work on in this and the next programming assignments.
 
 

6 Your Mission

Here's your mission:

6.1 Part I: Packet Forwarding

Write the packet forwarding functions vip_input, vip_forw, vip_output, and vip_drop. Upon receipt of a packet, the virtual interface VIF that we provide will call your vip_input function to handle the packet. Your vip_input calls the provided vif_pullup or vif_pullupn to pull up the packet from the virtual interface to be placed in a buffer you have allocated.

If the packet is not addressed to the current router, vip_input checks for packet integrity and hands the packet to vip_forw. vip_forw calls vrp_route to find the interface for the next hop towards the destination of the packet and send it out that interface by calling vif_output.

If a packet is addressed to the current router, vip_input hands the packet to either vtp_input, vcmp_input, or vrp_update depending on the protocol of the packet.

When an upper layer protocol calls vip_output and gives it some data to send out, vip_output marshalls a VIP header, calculates a checksum for the header, prepends the header to the data, and sends it out by calling vif_output.

If vip_input receives a packet with unknown version number or bad checksum, it should drop the packet by calling vip_drop. Packets with unknown protocol are also dropped. When forwarding a packet, the packet should be dropped if it encounters transmission error, the router doesn't know where to forward the packet, or the hop limit of the packet has been exceeded. Some of these errors should cause a VCMP packet to be sent back to the source of the packet, others shouldn't.

6.2 Part II: Error Reporting

VCMP has two externally visible functions: vcmp_input and vcmp_output. When a VCMP packet reaches its destination (i.e. the source of the packet experiencing the error), your vip_input should call your vcmp_input. All vcmp_input input does is print out the content of the VCMP packet.

When a packet encounters one of the errors listed in Section 5.2, vcmp_output is called to create and send out a VCMP packet. A VCMP packet is also a VIP packet. So, your vcmp_output should call your vip_output to send out its VCMP packets.

Remember to comment your code. Insufficient comments will result in a loss of points. You should write enough comments to make it easy for someone else to follow your code.

6.3 Testing your Code

To test your code, first run seeder on the machine of your choice. Then run one or more vrouted(s) on some other machines. If your vrouted crashes, you may have to wait awhile for the socket states in the kernel to flush before you can run it again using the same port number. When this happens, you get an error message that says, ``Cannot assign requested address.'' If you don't want to wait, you can either move to another machine or use a different port number. Remember that if you change port number, you must use the same one for all of your vrouted.

To understand the ``normal'' behavior of vrouted and seeder, you may want to run our version on several machines first. You should allow the vrouteds to continue running even after the seeder tells you that it is done testing. The vrouteds continue to randomly send messages to randomly selected destinations. Hit Ctl-C when you're tired of seeing text scrolling on your windows.

7 What to Turn in

Use your turnin client from HW1 to turn in all the files, AND ONLY THE FILES, you modified or created. Same server name (kailash), same port number (4898).