UM EECS 489 Winter 2010

 

Programming Assignment 1

DUE DATE Mon, 2/8/2010, 9:00 am

Revised: 2/19 (2/19: fixed some bugs, 2/17:added Part IV, Part III is now optional.)

CAEN has prepared 10 additional machines for our use (caen-linuxlab1.engin.umich.edu to caen-linuxlab10.engin.umich.edu).

Note: The files mentioned here can be found in the assignment tarball: /afs/umich.edu/class/eecs489/w10/PAs/pa1.tgz. Or can be downloaded from here (pa1ReleaseNew_3) (updated on 2/19). You should have a working directory for 489 already created for you in /afs/umich.edu/class/eecs489/w10/<uniqname>/. You may need to first run /usr/um/bin/gettokens, and enter your ITCS (umich.edu) password, to be able to access the eecs489 directory. You would need to do this everytime you login.

1 The Virtual Network

For this assignment, you are to write a virtual host on a virtual network. Our virtual network consists of two parts: a virtual host (vrouter henceforth) and a topology seeder. To construct your own private virtual network, you run one copy of seeder and one or more copies of vrouter. The seeder must be run before the vrouter'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 vrouter. To do so, log yourself into two Linux machines, say caen-vnc01.engin.umich.edu and caen-vnc02.engin.umich.edu. On the respective machines you type the following (append the proper path to the executable names):

         caen-vnc01% seeder -n 1
         caen-vnc02% vrouter -S caen-linuxlab1
(This will happen by 1/15) CAEN has prepared a few machines for our use (caen-vnc01.engin.umich.edu to caen-vnc04.engin.umich.edu). You can find out the name of a host by issuing the command uname -n on the shell.

Once you have debugged the single instance of your vrouter, you can test multiple instances of it. For example, to create a 4-node virtual network consisting of caen-vnc01, caen-vnc02, caen-vnc03, and caen-vnc04, , with the seeder running on caen-vnc01, (caen-vnc05 is not yet available, substitute with any other linux machine) you do:

         caen-vnc01% seeder -n 4
         caen-vnc02% vrouter -S caen-vnc01
         caen-vnc03% vrouter -S caen-vnc01
         caen-vnc04% vrouter -S caen-vnc01
         caen-vnc05% vrouter -S caen-vnc01
The seeder will consider the first vrouter connected as vrouter 0, the second as vrouter 1, and so on. Initially, the seeder will only generate a simple linked-list topology.

2 Addressing on the Virtual Network

 Each of your vrouters 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 VROUTER_PORT defined in vnet.h. In case you need to share a machine with someone else running vrouter, you can choose a different port number with the -p option of vrouter. All of your vrouter's must use the same well-known port. For example, to use port number 7896 in the above 4-node scenario, do:

         caen-vnc01% seeder -n 4
         caen-vnc02% vrouter -S caen-vnc01 -p 7896
         caen-vnc03% vrouter -S caen-vnc01 -p 7896
         caen-vnc04% vrouter -S caen-vnc01 -p 7896
         caen-vnc05% vrouter -S caen-vnc01 -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:

         caen-vnc01% seeder -n 4 -p 8707
         caen-vnc02% vrouter -S caen-vnc01 -P 8707 -p 7896
         caen-vnc03% vrouter -S caen-vnc01 -P 8707 -p 7896
         caen-vnc04% vrouter -S caen-vnc01 -P 8707 -p 7896
         caen-vnc05% vrouter -S caen-vnc01 -P 8707 -p 7896

To address each other, vrouter'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 vrouter runs on, the Port Number is the well-known port number the vrouter listens on, and the Metric the cost of the link (to be interpreted by higher level protocols). The port number and metric in a vin_addr_t must be kept in network byte-order at all times.

 
Figure 1:  vin_addr_t
vin.gif

3 Virtual Links

Upon start up, each vrouter registers itself with the given seeder. The seeder then determines the connectivity of the virtual network, i.e., which vrouter connects to which other. With prompting from the seeder, each vrouter opens a virtual link (vif) to 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, vmbuf_t *vbp);

When a packet arrives for your vrouter, 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 pull up its data from the virtual link just like you use recv(2). Or it can call vif_pullupn() to pull up n bytes. The function vif_pullupn() tries to pull up n bytes of data in one call. However, it doesn't guarantee that it will always succeed pulling up that many bytes. You should always check the return value of calls to both function to make sure they are not returning error. If vif_pullupn() returns error, it usually means there's something wrong in your code, so just dump core and abort.

You call vif_output() to put data on the virtual wire. You still need to call htons(), ntohs(), and friends whenever you transmit/receive an integer. See the function definitions in vif.c. (In case you wonder at the choice of the API names and programming style, I try to make them as similar as possible to the ones in the BSD kernel, so you get an experience of writing kernel code without most of the hassle associated with it.) Read the comments in vif.c to find out more fully how to use these vif related functions.

4 Virtual Buffer Chain

One obvious way to encapsulate a higher layer message into a lower layer message is for each layer to allocate enough space for the lower layer header and the upper layer message, and copy the upper layer packet into it. 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, I have defined a virtual buffer chain (vmbuf_t). Each vmbuf_t element points to a chunk of bytes and records the size of the chunk (in bytes). As a message traverses down the protocol layer stack, each layer creates a new vmbuf_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 vmbuf chain of a message going down the VTP, VIP, and VIF layers. The virtual link layer at the bottom transmits each vmbuf_t element without making extra copies.

 
Figure 2:  vmbuf Chain Traversing the Protocol Stack.
vmbufchain.gif

5 Virtual Router

Our virtual router (vrouter) 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.
vip.gif

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 host, except the packet's destination host, 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 the packet in bytes, excluding the header. The Protocol field specifies whether this is a vcmp, vrp, or vtp packet. The protocol numbers of VCMP, VRP, and VTP are VIP_PROTOVCMP, VIP_PROTOVRP and VIP_PROTOVTP respectively, as defined in vip.h. There is also a protocol number VIF_PROTOVIP for VIP defined in vif.h. VIP identifies a host by its vin_addr_t as described in Section 2.

5.2 VCMP: Virtual Control Message Protocol

 When a non-VCMP packet encounters one of the following errors, the vrouter holding the packet should report the error back to the packet's source. 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.
vcmp.gif

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. In generating a VCMP packet, you may find the macro VRP_INFINITY defined in vrp.h useful. Following IP's convention, a packet is dropped, not forwarded, and a VCMP_EHOPS packet is generated when the hop limit reaches 0. The destination host should still receive packets with hop limit 0 though. No error should be generated when VCMP packets themselves encounter errors (why?).

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:

Read the comments in vrp.c to find out more fully how to use these functions.

5.4 VROUTER: A Virtual Router


 
Figure 5:  Design of the virtual router vrouter.
vhost.gif

The design of the virtual host (vrouter) is depicted in Fig. 5. In the figure, data structures are enclosed in rounded boxes and functions in square boxes. (This figure shows vif_input() calling vip_input(). In the code, vif_input() actually returns the VIF and the main() routine in vrouter.c calls vip_input().) 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 tarball. In the assignment tarball you will also find the object code for my version of these functions. For example, vip_input() in vip.c calls my code _vip_input(), which is given to you only in object form in _vip.o. Your task is to replace the call to _vip_input() in vip_input() with your own code that performs what vip_input() is supposed to perform, not to write your copy of _vip_input().


6 Your Tasks

There are 3 tasks:

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 I 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 host, vip_input() checks for packet integrity and hands the packet to vip_forw(). The function 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 host, 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, prepends the header to the data, and sends it out by calling vif_output().

If vip_input() receives a packet with unknown version number, 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 host 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. Read the comments in vip.c to find out what these functions are supposed to do.

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() 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. So for example, if the route to a host is not found, send back VCMP_EHOST. Send back VCMP_ELINK if a route is found but there is an error in transmission. A VCMP packet is also a VIP packet. So, your vcmp_output() should call your vip_output() to send out its VCMP packets. Read the comments in vcmp.c to find out what these functions are supposed to do.

Remember to comment your code.

Testing your Code
To test your code, first run seeder on a machine of your choice, then run one or more vrouter(s) on some other machines. To understand the ``normal'' behavior of vrouter and seeder, you may want to run my version on several machines first. Start up seeder on your favorite machine, tell it to expect four vrouter's. On four other windows, each connected to a different machine, run a vrouter. (See the second example on the first page of this note.) After the seeder heard from all four vrouter's, it will create a simple linked-list virtual topology connecting the four vrouter's, for example:
N e t w o r k   T o p o l o g y
R0: 141.213.52.95.9840    links = 1
        L0: 141.213.52.96.9840  up
R1: 141.213.52.96.9840    links = 2
        L0: 141.213.52.95.9840  up
        L1: 141.213.52.103.9840  up
R2: 141.213.52.103.9840    links = 2
        L0: 141.213.52.96.9840  up
        L1: 141.213.52.101.9840  down
R3: 141.213.52.101.9840    links = 1
        L0: 141.213.52.103.9840  down
The seeder will then prompt you if you want to continue testing, just say no.

You should allow the vrouters to continue running even after the seeder tells you that it is done testing. The vrouter's continue to randomly send messages to randomly selected destinations. You control the number of test packets sent by modifying the macro VTP_TESTNUM in vtp.c. So, continue to observe the windows where the vrouter's are running. You should see messages like:

VTP pkt received from caen-vnc02.engin.umich.edu.9840:
Seq#: 38
Src: caen-vnc02.engin.umich.edu.9840, Dest: caen-vnc03.engin.umich.edu.9840

VCMP from vrouter caen-vnc05.engin.umich.edu.9840: Hop count exceeded
Original VIP header:
ver: 8; hlim: 0
plen: 76; proto: 4
saddr: 141.213.52.95.9840; daddr: 141.213.52.96.9840
You should watch for two things:
  1. The vrouter at one end of your virtual topology (the one denoted R0 in the seeder output) receives VTP packets from the vrouter at the other end of your virtual topology (R3). This tells you that you are forwarding packets properly.
  2. You should see VCMP error messages when the hop limit put on your packet is less than the hop count towards your destination. The code in vtp_test() puts a random number smaller than required hop count on the packets it sends out half of the time.
Each packet from a host is given a unique sequence number. My version of vip_output() sets the time-to-live (ttl) of a packet based on the ttl value passed to it as one of the formal arguments. As part of the test harness, however, if the ttl passed to vip_output is 0, it automatically sets the ttl of the pkt to the actual hop count towards the destination. This is why at the source node, you see pkts sent with ttl=0, which are not dropped by latter nodes. In your version of vip_output(), you can set ttl to VRP_INFINITY when the ttl passed into vip_output() is 0 or figure out the actual number of hop to destination, by calling vrp_route() to find out the cost, in terms of hop count, to destination. (Alternatively, if you are feeling adventurous, you can modify the code in vtp_test() to generate only deterministic test cases.) Change the macro VTP_TESTNUM in vtp.c to control the number of test packets generated.

If your vrouter 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'' or ``connect: Address already in use.'' If you don't want to wait, you can use a different port number. Remember that if you change port number, you must use the same one for all of your vrouter.

To facilitate testing, in addition to generating random topologies, the seeder can also generate topologies described in a script file. Here's a sample topology file:

   # Line starting with '#' denotes comments and the whole line is ignored.
   ! Line starting with '!' denotes a warning that has to be printed out.
   # The topology depicted below forms a ring of 3 nodes.
   # Each line is the following format: 'first_vrouter' 'second_vrouter' 'up_down'
   #   for example line "0 1 1" means establish a link between vrouter 0 and 1,
   #   line "0 1 0" means take down the link between vrouter 0 and 1.
   # Line starting with ',' tells the seeder to send out the seeds and wait 
   #   for the new topology to stabilize.  The wait time (in seconds) may be 
   #   specified.
   # A line starting with '.' means the end of the script file.
   0 1 1
   1 2 1
   0 2 1
   , 1
   .
The file CHAIN4 in the assignment tarball creates a simple linked-list virtual topology of four nodes.

Part III: Dynamic Seeder

Part III is optional

The seeder as given must be told on the command line the number of vrouter's to expect. Modify the seeder such that if the -n option is not specified on the command line, the seeder simply waits for connection from an unlimited number of vrouter's. Everytime a new vrouter registers itself with the seeder, the seeder will assign it a random number of neighbors (peers), which are selected randomly. Each time the topology of the virtual network changes, the seeder should notify only the effected vrouter's. Each time the topology of the virtual network changes, be sure the print out the new topology, by calling sdr_dump(). You may also want to modify how vrouter's generate test VTP packets at the end of vrouter.c:main() function so as not to flood your virtual network.

You should reuse as much of the existing seeder code as possible, by modifying the existing code to accommodate the dynamic case. Make only the absolute minimal changes to the code to make the seeder dynamic. Before you make any changes, be sure to understand the current code. You may find the functions sdr_top(), sdr_rand(), sdr_toggle() particularly useful. You may also need to modify the function sdr_seed(); for example, you need to decide what to do when only one vrouter has registered with the seeder. If you don't know how to generate or use random numbers, see the use of lrand48(3) in sdr_rand().

Document your changes to seeder.c carefully. Tag all of your changes to the code with your uniqname and, where necessary, comment on what each new piece of code is doing. You will also need to write a description of how you have implemented the dynamic seeder and a summary of all your changes, which functions are modified and how they are modified, which functions are added, etc. Include this description as comment at the end of your modified seeder.c file.

Part IV: Reliable VTP packets (end-to-end retransmission)

You need to implement a simple scheme to ensure reliability of packet delivery. All changes are to be made in vtp.c (primarily in vtp_input, vtp_output, and vtp_retransmission).

Packet format: We consider three types of VTP packets: 1) reliable data packet whose data starts with "Seq#: number\n". 2) Acknowledgement (ACK) packet that is used to acknowledge reliable data packet. It always starts with "ACK#:number\n". 3) unreliable data packet which can have any content other than the first two.

Protocol: At the sender side, whenever a reliable data packet gets transmitted via vtp_output(), sender has to put it in a buffer so that it can retransmit it later on in case of packet loss. If a sender does not receive ACK packet from the same receiver with the same number within certain time period (5 seconds as defined in vtp.h), then the sender has to retransmit the packet via vtp_retranmission(). After a number of retries (2 as defined in vtp.h), sender will give up. If the sender receives the correct ACK packet, then it will remove the entry in the buffer. At the receiver side, whenever it receives a reliable data packet, it should respond with an ACK packet with the same number as the sequence number in the reliable data packet. Receiver does not have to buffer any ACK packets. Upon ACK packet loss, sender will timeout and retransmit the reliable data packet. For unreliable data packet, no retransmission needs to be done. For intermediate vrouters, they do not have to participate in retranmission. In fact, they do not even distinguish reliable and unreliable data packet. Retransmission is implemented purely at sender and receiver side. This is called end-to-end retransmission.

Suggestions: you can complete the first several tasks and then work on this task. Initially, you can first treat reliable packets as unreliable and gradually add the logic of retransmission once you can route packets to any destination you want. Reliable packets will be generated from vtp_test() function which will be called when you run vrouter with "-t max_sequence_no".

Notes:

  1. Some helper functions are provided to you to extract the sequence number and ACK number.
  2. Ideally, we want to retransmit every packet right after it is timed out. However, for this task, you only need to do retransmission when you get a chance to, i.e., when vtp_output() is called. This means that sometimes the reliable packets can be delayed infinitely if there is no additional data to send. We are designing it this way just to simplify the problem.
  3. In order to test your code, you will need to test the cases where ACK packets are lost. This can be achieved by either setting small TTLs or generate malformed ACK packet (so that the sender won't recognize it).

7 What to Turn in

Code that doesn't compile will be heavily penalized. Make sure your code compiles and works on CAEN Linux machines, gcc version 4.1.2.

Turn in ONLY the files you have modified, this should mean your vip.c, vcmp.c, and vtp.c. (seeder.c and vrouter.c are only changed for Part III, which is now optional)

Copy the files you want to submit to the following directory on IFS /afs/umich.edu/class/eecs489/w10/SUBMIT/<uniqname>/pa1. This path is accessible from any machine you've logged into using your ITCS (umich.edu) password. Report problems to ITCS.

For accessing the umich.edu AFS partition from CAEN machines you might first have to obtain AFS tokens. On Linux, this is performed using the gettokens command on the terminal, followed by your ITCS password.

Do not submit any binary files (object, executable, or image) with your assignment.

The timestamp on your source files will indicate the time of submission and if this is past the deadline your submission will be considered late. You are allowed multiple "submissions" without late-policy implications as long as you respect the deadline.

Test the compilation! Your submission must compile without errors and warnings on CAEN Linux machines, with gcc version 4.1.2.

General

You are allowed and encouraged to discuss various aspects of this assignment with your classmates. However, the overall design and final details and implementation must be your own.

Coding style

Use a reasonable organization for your overall program:
Design a fairly reasonable class structure. On the one hand, don't stick everything into one class/struct. On the other hand, don't be bureaucratic and require the reader to follow one class definition after another to find a single line of code wrapped in n layers of methods, with each method doing nothing but calling the next one. If the way you design your code feels sloppy to you, it probably is. Utilize multiple files in a way that is consistent with the general use of C. Don't use more files than necessary, you don't have to put each class/struct in a separate file of its own.

Don't use literals!
Use either const, enum, or #define to give your literals meaningful names. We do deduct points for each occurrence of literals, even if it is the same one. The only exceptions will be for loop counter, command-line options, NULL(0) and TRUE/FALSE(1/0) testing/setting, and help and error messages printed out to user.

Use reasonable comments:
Explain what each class does and what each data member is used for. A one or two line description of most member functions is also desirable. Where you use non-standard coding techniques, document them. List your name and the date last modified for each file.
 
Remember that a useless comment is worse than no comment at all.
int temp; // declare temp. variable
would be an example of a useless comment which just makes code harder to read!

Use reasonable formatting:
From indentation alone, it should be obvious where a given code block ends. Avoid lines that wrap in an 80 column display wherever possible. Your code should be tight, compact, and visually tidy. Don't let bits and pieces fly off every which way. Your code is not abstract painting.

Variable names:
Use reasonable and informative variable names, but limit name size to a reasonable length. A 40-character name better has a very good reason to exist. Variable names like 'i' and 'j' can be reasonable, but you should not use such variables to store meaningful long-term data. Other than LCV (loop control variables) you should use descriptive names for your variables, functions, classes, methods, structures, etc.

Reduce, Reuse, and Recycle your code, algorithms, and structures:
Try using inheritance, templating, polymorphism (virtual function), or similar methods to reduce the size of your code. Do not unnecessarily duplicate code. Less code leads to less debugging. If you find yourself rewriting basically the same code more than once, stop and try to see if you can somehow reuse the code by making it a function call or implementing a polymorphic function.
Unreadable code can cost you up to 10 points!

Empirical efficiency

We will check for empirical efficiency both by measuring the memory usage and running time of your code and by reading the code. We will focus on whether you use unnecessary temporary variables, whether you copy data when a simply reference to it will do, whether you use an O(n) algorithm or an O(n^2) algorithm, but not whether you use printf's or fprintf's. Nor whether your ADTs have the cleanest interfaces. In general, if the tradeoff is between illegible and fast code vs. pleasant to read code that is unnoticeably less efficient, we will prefer the latter. (Of course pleasant to read code that is also efficient would be best.) However, take heed what you put in your code. You should be able to account for every class, method, function, statement, down to every character you put in your code. Why is it there? Is it necessary to be there? Can you do without? Perfection is reached not when there is nothing more to add, but when there is nothing more that can be taken away, someone once said. Okay, that may be a bit extreme, but do try to mind how you express yourself in code.

Hints and advice

Testing Your Code

We will be grading for correctness primarily by running your program on a number of test cases. If you have a single silly bug that causes most of the test cases to fail, you will get a very low score on that part of the programming assignment even though you completed 95% of the work. Most of your grade will come from correctness testing. Therefore, it is imperative that you test your code thoroughly. Each testcase should test only one particular feature of your program.

If any part of this document is unclear, ambiguous, contradictory, or just plain wrong, please post your questions on the course forum. Have fun coding!

Frequently Asked Questions