CS 43: Lab 6

Handy references:

The protocol you implement will be simpler than TCP, but you may find TCP's header information to be useful for inspiration.
select() manual. (You will need to set timers for your timeout, select makes this easy.)
mininet documentation

For this lab, you'll be continuing your development of a reliable data transfer protocol over an unreliable (simulated) link, only this time, your transfer rate should improve significantly! Your submission will still be in the form of a library that mimics the type of functionality that you would expect to get from an OS's transport-layer implementation.

You may implement either a go-back-N or selective repeat style of protocol.

Requirements

You must use C to implement your library code, and the underlying transport that it uses to transfer messages must be UDP. TCP would give you reliability, which would obviously defeat the purpose...

Your protocol should provide as much performance as network conditions will reasonably allow. If links have free space in their queues, your protocol should attempt to take advantage of that. If it overflows the queues, it should back off. You should mimic TCP's AIMD congestion control behavior. You may assume that the window size will never need to go above WINDOW_SIZE_CAP. A good default value of WINDOW_SIZE_CAP is 2000, but your code should still work if it's lowered. I might change this value when I'm testing, so make sure that you always refer to it via the #defined macro rather than hard-coding a number! Please record the maximum window size you use over the course of a run and make that value available via a function named my_max_window that has the following prototype:
```
int my_max_window(int sock);
```

Your protocol should provide in-order delivery. That is, the receiver should receive packets in the same order that the sender sends them, even if something occurs (e.g., losses) that causes a later-sent packet to arrive before an earlier-sent one.

Because you're pipelining multiple packets, you need to keep track of all the outstanding data that needs to be sent and send up to an entire window at once. This means there is no longer a 1:1 correspondence between my_send() and send(). There are two general architectures you might use to account for this difference. You may use either approach:
- You may code my_send() to store packets in your window in addition to sending them. The number of packets its willing to store at any given time will depend on your current window size. If the user ever calls my_send when the window is full, it should wait for free window space to open up (receiving an ACK just, just like your implementation of my_send() in lab 5).
- You may use additional threads (at most two: one for sending, one for receiving), which are responsible for doing the sending, receiving, acking, timeouts, and window sizing. In this model, when the user calls my_send(), it adds the new data to a shared location that the sending thread will deliver later, and my_recv checks to see if there is any buffered data to return up to the user. This is the more "realistic" option, but is also more challenging because it requires thread synchronization due to the shared buffers.
In either case, when the user calls my_close(), you need to ensure that all of the outstanding data is delivered before you initiate the shutdown sequence.

The example code includes a test application that sits above your library and uses it to transfer a file. You may edit the test application for your own testing, but when grading, I will use the default version, so do not rely on changes to these files for correct operation. Your library (lab6.h and lab6.c) should allow any application that's built on top of it to achieve reliable communication. When transferring files with your library, you should get byte-for-byte identical copies. Use diff, md5sum, etc. to veryify that everything is transferred properly.

As a part of your implementation of reliability, you'll need to perform RTT estimation to determine how you should set timeout values. You should use an EWMA-based mechanism like TCP does. The library function my_rtt() should always return your library's current estimate of the RTT. Normally you wouldn't export such information up to the application/user, but I'll use this to check your RTT calculation.

Your implementation should cleanly shut down connections on both ends, even if packets get lost. You do NOT need to implement the TCP behavior that allows each side to shutdown independently, but in my_close(), you may want to wait for some time, to make sure the last ACK didn't get lost (leaving one end hanging).

Environment

For this lab, we'll be using the same mininet emulation software that we used in lab 5, with slightly different parameters. Refer to the lab 5 environment section for details about creating a VM. To test pipelining, you'll need buffer sizes that are larger than two packets. When you run mininet, test with a variety of max_queue_size parameter values. You should see the performance increase as the queue size increases, up to a certain point of diminishing returns. A larger queue means you're able to support more packets in flight at once.

Grading Rubric

This assignment is worth five points.

1½ - Your protocol delivers packets reliably and in-order, regardless of link buffer size, with a window size that is larger than 1.
1 - Your protocol's performance increases significantly when network conditions are more favorable.
1 - Your protocol correctly detects (within ~10%) the maximum window size it can use for the path. (See requirement 2.)
½ - Your protocol cleanly terminates connections such that both ends agree that the connection is closed.
1 - Your protocol has no memory leaks or invalid memory accesses (i.e., valgrind should not complain about anything). Your pseudo-kernel library will need to keep track of the window and outstanding packets, and it would be very bad for the kernel to have memory problems.

Tips

START EARLY! The earlier you start, the sooner you can ask questions if you get stuck. Test your code in small increments. It's much easier to localize a bug when you've only changed a few lines.

To run the example test application, start up a receiver first. It will write the file it receives to standard out. For example, on h2:
```
./lab6_receiver 9000 > [output_file]
```
Once that's running, you can fire up a sender that will send a file to it. The sender reads its input from standard in. For example, on h1:
```
./lab6_sender 10.0.0.2 9000 < [input_file]
```
Note: If you haven't implemented reliability yet, this will not succeed unless you A) create a virtual link that does not drop packets, and B) create a virtual link that has large enough buffers to prevent congestion losses.

Your favorite function from lab4, select(), will likely be useful to you again in this lab. It has the nice capability of telling you if you've received anything within a specified amount of time, and if not, it will return and indicate that it timed out. Look at documentation for the last parameter of select for details.

You may find the textbook to be more useful for this lab than it has been previously. It has good descriptions of the various reliability mechanisms that you might want to adopt.

Because you have root account access on your VM, you will have the necessary permissions to run Wireshark. You may find that to be useful while debugging. It won't be quite as nice as when we used it to look at DNS, since it knows how to decode DNS and it knows nothing about your protocol, but you can still use it to look at the raw values, if necessary.

If you have any questions about the lab requirements or specification, please post on Piazza.

Submitting

Please remove any debugging output prior to submitting.

Please do not submit output file(s) that you used in testing.

To submit your code, simply commit your changes locally using git add and git commit. Then run git push while in your lab directory.