|
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.
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.
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.
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.
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.
There are 3 tasks:
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.
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.
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.9840You should watch for two things:
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 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.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:
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.
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.
int temp; // declare temp. variable
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.
stdout with unnecessary
output. Use gdb to debug.
stderr unless there is an error.
To encourage early start on the assignment, we will stop helping you to debug 48 hours before the due date. For a Monday 11:00 am deadline, we stop helping you at 11:00 am on the Saturday prior.
Comment: On the virtual network created in PA1, you still need to call htons, ntohs, and friends to handle transmissions/receptions of integers.
Q: If there are 3 vrouters connected in a chain, do the two hosts at the ends of the chain know each other exist? Or does a vrouter only know about the vrouter's it is directly linked to?
A: Unless the virtual network is partitioned, all vrouter's should know of each other.
Q: The VCMP_EHOST specifies that host is unreachable. Doesn't this imply that hop number <= 0 ?
A: Not necessarily. The link to the host may be down or the host may not exist in the route table.
Q: When multiple packets arrive at a vrouter at the same time, how are they buffered? How big is this input buffer? What is the use of macro VIP_MAXPKTSIZE?
A: Multiple incomming packets are buffered on FIFO basis. Input buffer is as big as the socket buffer in the kernel. Macro VIP_MAXPKTSIZE is used when you want to check that a packet is not larger than the maximum packet size VIP can handle.
Q: Clarification on VTP header:
A: VTP header is not currently used, hence you see that it is not wrapped around the user data in vtp_input(). But in writing vip_output(), you shouldn't care whether there is a VTP header, just put a VIP header in front of the vmbuf chain given to you.
Q: More on how to test.
A:seeder has an option to change the random seed (-r). Test your code with different random seeds. Look at the output and make sure that every pkt sent by a sender gets to the intended destinations. Make sure you try it with virtual networks consisting of more than 2 or 3 nodes.
Q: What is default number of hops in VIP header?
A: There is no default value. The function vip_output() takes as an argument the ttl of the packet. If the ttl given is not 0, use it as the hop limit. Otherwise, get the number of hops towards the destination from vrp_route().
Q: In the part about passing the data up to the higher level protocol I am assuming that it refers to VTP/VRP and if it is referring to vtp, do we send the data to vtp_input()?
A: The purpose here is to print out the bad pkt to the screen so that you can debug it if it's a coding error. It turns out that vcmp_input() and vtp_drop() do exactly that: print the pkt out to screen. So, yes, you can call vcmp_input() and vtp_drop() from vip_drop() if the pkt belongs to either of these protocols.
Q: In vip_input(), when clearing the interface of bits in case of error, how much do I need to pull up off vif_pullup() and how do I make sure that I don't start pulling up the header for the next packet?
A: You can't be sure that you're not pulling up the header for the next packet. What we are doing here is called "Panic-mode recovery" in the parlance of parser construction. Here's the definition from the dragon book (Aho, Sethi, and Ullman, _Compilers: Principles, Techniques, and Tools), "On discovering an error, the parser discards input symbols one at a time until one of a designated set of synchronizing tokens is found. The synchronizing tokens are usually delimiters, such as semicolon or *end*, whose role in the source program is clear." In our code, we use an empty pipe as the synchronizing "token"/delimiter. Put another way, consider a push-down automaton, we recognize an empty pipe as the symbol denoting end of input that allows us to accept the input and pop the stack.
Empty pipe is detected when vif_pullup() returns -1 with errno(3) set to EWOULDBLOCK. You can print out the error message associated with an errno by calling perror(3).
Q: Why are the source and destination addresses printed out the same?
A: Do not call inet_ntoa() twice in the same printf(), because inet_ntoa() uses static buffer to store the hostname.