CS 43 — Lab 5: Reliable Transport

Due: Thursday, April 21 @ 11:59 PM

1. Overview

For this lab, you’ll be designing and implementing reliable data transfer over an unreliable (simulated) link. Your submission will 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.

Your transport protocol should be a stop-and-wait protocol for now. We’ll introduce high-performance pipelining features in lab 6.

1.1. Goals

  • Apply the principles and tools of reliable transport (e.g., acknowledgements and timeouts).

  • Design and implement a stop-and-wait transport protocol.

  • Simulate network characteristics with Mininet.

1.2. Handy References:

1.3. Lab Recordings

Week 1

Week 2

2. Requirements

For this lab, we’ll be building a stop-and-wait protocol with ACKs, timeouts, retransmissions, and RTT estimation on top of an unreliable channel. Your code will take the form of a library that applications and call into for reliable transport. The library will use UDP socket calls to get an unreliable channel, and we’ll use the network emulator mininet simulate link delay and packet losses in a controlled manner.

  • Protocol Library API: You are responsible for writing/editing only the following library functions:

    • in lab5.c: my_socket, my_send, my_rtt, my_recv and my_close.

    • in lab5.h: add header fields to struct lab5_hdr.

    • to send and receive data across the wire, we’ll be using UDP’s unreliable send and recvfrom in your implementation of a stop-and-wait version of my_send and my_recv. Your code in these functions is responsible for implementing reliability on top of UDP.

  • Application layer: lab5_sender.c and lab5_receiver.c implement the application layer that calls your library functions. Note that lab5_sender and lab5_receiver run as separate processes, so they each get their own independent copies of your library (i.e., they don’t share any memory or state).

    • You may edit lab5_sender.c and lab5_receiver.c for testing purposes, but when grading, I will use the starter versions, so do not rely on changes to the application layer for correct operation.

2.1. Workflow of Your Program

Your code submission should only modify lab5.c and lab5.h. These two files are transport layer functions and you can think of them as a reliable transport library that is independently being imported by lab5_sender.c and lab5_receiver.c. This means that lab5_sender and lab5_receiver will each get their own instance of (independent copy of the state from) the lab5.c and lab5.h files.

  1. Set up initial state in my_socket. You should initialize state that any reliable transport protocol implementation (either sender or receiver) would need to get started.

  2. Define your transport layer segment header format in lab5.h.

  3. Write a helper function that helps you maintain an RTT estimate based on sample RTT measurements.

  4. Implement reliable sending in my_send. To reliably send data, you will need to implement the following:

    1. Copy and send the application layer payload + transport header into your send buffer.

    2. Maintain data structures to estimate RTT.

    3. Keep track of segments sent and acknowledgements received.

    4. Attempt to receive acknowledgements, and resend data segments if you timeout on a segment.

  5. Implement reliable receive in my_recv. To reliably receive data, you will need to implement the following:

    1. Receive a segment over the network, you are not required to check for data corruption (e.g., with a checksum).

    2. Make sure you received the expected segment, and if so, send an appropriate acknowledgement to the sender.

    3. As segments are received in order, remove the transport layer header and copy the application layer payload to the application’s buffer.

    4. Return the number of bytes received to the application.

  6. Implement reliable closing in my_close. Your implementation should cleanly shut down connections on both ends, even if segments get lost.

    1. You are not required to implement the TCP behavior that allows each side to shutdown independently. Like TCP though, in my_close, you may want to wait for some time to ensure that the last ACK doesn’t get lost (leaving one end hanging).

    2. TIP: since you are closing reliably, you may find it helpful to call my_send from my_close.

2.2. Behavior Expectations

For full credit:

  • Your protocol should reliably transfer, in order, data across lossy links.

  • Your protocol should cleanly shut down connections on both ends, even if segments get lost. You should NOT rely on ICMP error messages to help your closing procedure. To be safe, it’s best to disable ICMP from both hosts before starting the sender and receiver with:

    iptables -I OUTPUT -p icmp -j DROP
  • While you may make changes to lab5_sender.c and lab5_receiver.c for debugging purposes, you must not rely on any changes to those files for correctness. Don’t change the interface for the library, and don’t do work in the application-layer sender or receiver that needs to be done by the library! When grading, I will use the default version, so you must not rely on changes to these files for correct operation.

  • As a stop-and-wait protocol, your protocol shouldn’t attempt to keep more than one segment "in flight" at a time. When grading, link packet buffers will be very small (mininet will set max_queue_size=2).

  • Your library should estimate the RTT similarly to TCP to determine how to set timeout values. Your my_rtt function should always return your library’s current estimate of the RTT. (Normally the transport layer wouldn’t export such information up to the application/user, but I’ll use this to check your RTT calculation.)

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

  • Your library 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 using tools like diff or md5sum.

  • You should not generate any warnings or memory leaks when running with valgrind.

2.3. Assumptions / Simplifications

  • You may assume that the application will not pass more than MAX_SEGMENT bytes to my_send. That is, the len parameter passed to my_send will be less than or equal to MAX_SEGMENT.

  • You do not have to deal with checksums or error detection and corruption.

  • Your protocol does not need to be bi-directional. You can assume that application data will only flow in one direction (from "sender" to "receiver").

2.4. Checkpoint

By the end of the first week, you should be able to:

  • In my_send: attach transport headers application data and send it

  • in my_recv: receive data, remove transport headers, and pass data from the body to the application.

It’s ok if your sends and receives aren’t fully reliable yet, but you need to make non-trivial progress towards reliability (convince me).

3. Examples and Testing

For this lab, we’ll run Mininet in a virtual machine (VM) to emulate a network with delays and losses.

First, start the VM and ssh to it:

ssh -Y localhost -p 22222 -l mininet

Next, move into the directory with your lab code:

cd Lab5-usernames/

From there, start mininet with appropriate delay and loss parameters.

sudo -E mn --link tc,delay='10ms',loss=5,max_queue_size=2 -x

The above command sets the delay to 10 ms and loss rate to 5% for each link that a segment traverses, and there are two links to traverse in each direction. So, with these parameters, every time you send a segment, it will have a RTT of around 40 ms and an overall round trip loss rate of ~18.5%.

You may want to experiment with different parameters depending on what you’re trying to test. For example, when testing your RTT estimate, it makes sense to use 0% loss.

Running the mininet command above will open four terminal windows. You only care about h1 and h2, which represent two hosts. You can safely close the other two. Host 1 will be 10.0.0.1, and host 2 will be 10.0.0.2.

From the h2 window, run the receiver.

To see output on the terminal, run:

./lab5_receiver 9000 > output.txt

To capture output to a file to analyze later, run:

./lab5_receiver 9000 > output.txt 2> output.err

This command will redirect standard out to the file named output.txt (containing the data you’re transferring), and it will redirect standard error to the file named output.err (containing your debugging output).

From the h1 window, run the sender:

./lab5_sender 10.0.0.2 9000 < 1000lines

That should start the file transfer. After it completes, you can verify that the files are byte-for-byte identical:

md5sum 1000lines output.txt

187323fe69aa075411d75dd0849f8263  1000lines
187323fe69aa075411d75dd0849f8263  output.txt

4. Tips & FAQ

  • Test your code in small increments. It’s much easier to localize a bug when you’ve only changed a few lines.

  • If you want to add a print statement to your library, use fprintf to print to the stderr stream rather than the usual stdout. There are examples of this in the library already. The benefit of using this method is that it won’t interfere with the results that the receiver outputs, since it captures only stdout.

  • You should experiment with a range of loss rates in mininet. You can go from 1% to 10% (effective overall loss rate of 35%) at most. If you set higher loss rates, you will need larger files to allow your RTT estimate to converge to the network RTT.

  • You can test with larger files by generating them with the generate_test_files.py script.

  • 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.

4.1. Setting Timeouts

Though we didn’t use it in lab 4, the select system call takes an optional timeout parameter.

For this lab, when you send data in my_send, you want my_send to wait until either…​

  1. You receive an acknowledgement, in which case you move on to sending the next segment, or

  2. You time out while waiting for the acknowledgement, in which case you want to retransmit the last segment.

Thus, you can use select with just one socket in the read set (the socket you expect to receive the ACK from). When select returns, you can look at the return value to determine which case you’re in. A return value of 0 means that select timed out.

To set a timeout, you can pass a struct timeval, which looks like:

struct timeval {
    long tv_sec;   /* whole seconds */
    long tv_usec;  /* microseconds */
}

The starter code provides helper functions that will help with converting values into different units of time.

You need to reinitialize the timeout value in the struct timeval before each call to select.

4.2. Packet Headers and Connection State

  • The segment header in lab5.h should initially look like the following:

    struct lab5_hdr {
        uint32_t sequence_number;
        uint32_t ack_number;
    };
  • You can add variable(s) if you want (e.g., a flag for closing), but you don’t need to add many. Try to keep it simple. One is probably enough.

  • Your code does not need to implement the full TCP header! The state we have (seg #, ack #, …​) should be all we need.

4.2.1. Header Casting Tricks

Network folks often write code with the following weird syntax:

char packet[MAX_PACKET];
memset(packet, 0, sizeof(packet));
struct lab5_hdr *hdr = (struct lab5_hdr *) packet;
  • The syntax above lets us create a pointer to the packet of type struct lab5_hdr. This means, that anytime we want to pack values into the header we can use a more intuitive representation of the data we are packing.

    uint32_t ack_number = 1;
    
    /* without struct casting (UGLY!) */
    memcpy(packet+4, htonl(ack_number))              //packing
    ack_number = ntohl(*((uint32_t *) &packet[4]))   //unpacking
    
    /* with struct casting */
    hdr->ack_number = htonl(ack_number);             //packing
    ack_number = ntohl(hdr->ack_number);             //unpacking

4.2.2. Setting Up State

  • Currently, the only state in lab5.c is int sequence_number.

  • Your code should probably have a few more global state variables to maintain things like RTT estimates and a state variable for closing.

4.3. RTT Estimation

  • Your implementation will need to perform RTT estimation to determine how it should set timeout values.

  • Use current_msec() to get an estimate of the current time stamp and use msec_to_timeval() to fill out struct timeval.

  • To estimate RTT, use an exponentially weighted moving average (EWMA) estimate as discussed in class.

    EstimatedRTT  = (1 – a) * EstimatedRTT + a * SampleRTT, with a = 1/8
    DevRTT = (1 – B) * DevRTT + B * | SampleRTT – EstimatedRTT |, with b = 1/4
    TimeoutInterval = EstimatedRTT + 4*DevRTT + 15

    Normally you wouldn’t export such information up to the application/user, but I’ll use this to check your RTT calculation.

  • You should initialize your RTT to a large value like 500 ms.

  • Like TCP, you should compute your timeout as a function of the current RTT estimate, sampling only those segments for which no retransmission is necessary. If a timeout occurs, you should double the timeout for each subsequent retransmission of the same segment.

Adjusting the Timeout Interval

The EstimatedRTT and DevRTT estimation assumes that there is some noise in your estimation (DevRTT > 0), as it tries to converge to the network RTT. In practice, network RTT also has some variance, but since this is mininet, we have artificially set a fixed value for the network RTT for every packet.

This means, as we increase the file sizes that we send, the estimate of DevRTT will start to converge to zero! With DevRTT zero, the TimeoutInterval will be exactly equal to the RTT and most of your calls to send will timeout! If we add some constant parameter to your timeout formula we can ensure that you are not going to timeout exactly at EstimatedRTT.

Thus, when setting timeouts, you may want to add a small constant of 10-15 ms to the timeouts to account for our artificial environment.

5. Mininet VM

For this lab, we’ll be using network emulation software called Mininet to create virtual links that allow us to vary their performance characteristics (latency, loss rate, etc.). Because it requires special permissions to execute, we’ll be running it inside of a virtual machine. The VM image will NOT fit in your home directory, so you’ll need to work in /local, which is the local hard disk of the machine you’re using.

Storing things in /local has two major implications that you need to account for:

  1. The data in /local is stored on a single disk (unlike your home directory, which is split across multiple disks for redundancy). When you’re done working, you should save your important lab files elsewhere (e.g., push them to GitHub) to avoid data loss in the event of a disk failure. When you’re done working on your VM, you should shut it down nicely: sudo shutdown -h now.

  2. The /local partition on each machine is only available on that machine. This means that if you want to move and work on a different machine, you’ll need to set up a new VM at the new location or copy your VM image from /local on one machine to /local on another with something like scp.

5.1. VM Setup

Please follow these steps carefully. You don’t want to accidentally fill your home directory’s quota!

To get started, you’ll need to import a copy of the starter VM image:

  1. Run virtualbox in a terminal or open it from your favorite graphical menu.

  2. Go to File→Preferences, set your "Default Machine Folder" to "/local", and then close the preferences window.

  3. Go to File→Import Appliance. Choose: /local/CS43-MininetVM-S22.ova and push next once.

  4. You should now be seeing "Appliance settings". Edit the name to include your username at the end. For example, CS43-MininetVM-S22-kwebb.

  5. Click import and wait a minute for it to complete.

After you’ve completed these steps, you should see the your VM in the list of VMs available to start. Go ahead and turn it on.

While you could work from within the new VM window that just came up, doing so is a huge pain if you enjoy nice things like graphical interfaces. Instead, it’s much easier to connect to the VM via ssh with X11 forwarding turned on. The VM is already configured such that you can connect to it by sshing to your local machine on port 22222. (Port 22222 on your machine gets forwarded to port 22 on the VM):

ssh -Y localhost -p 22222 -l mininet
(The password is: mininet)

Before going any further, you should use the passwd command to set a new password to protect your VM. After that, you’ll need to configure an SSH key so that you can access GitHub. You have two options:

  1. Create a new key for the VM and add it to your GitHub account. (Instructions)

  2. Copy your existing ssh key from your CS account to the VM.

5.2. Working with Mininet

Once you’ve connected to the VM, you can run Mininet. From your terminal that’s sshed to the VM, run Mininet, and tell it to create a minimal network topology with two hosts connected to a switch with 10ms latency on each link, 5% packet loss on each link, and a buffer of size 2. Note that there are no spaces between link parameters:

sudo -E mn --link tc,delay='10ms',loss=5,max_queue_size=2 -x

This will pop up four terminal windows: one for each of the two hosts (h1 and h2), one for the switch (s1), and one for a controller (c0). Close the controller and switch terminals, you won’t be using those for this lab. All the operations you perform within these windows act as if you were sshed to two lab machines. They work independently like different machines but share the same files. If you run ifconfig on each of them, you’ll see that h1 has an IP address of 10.0.0.1 and h2 has 10.0.0.2. You should be able to transmit data between the two. Test that by running the ping command at h1:

ping 10.0.0.2

You should see a (round trip time) delay of about 40 ms with approximately a 19% loss rate (each link has an independent 5% chance of dropping a packet).

5.3. Editing Files on the VM

The VM is set up just to run Mininet, so it doesn’t have much other software installed, and that makes it annoying to edit files directly on the VM. As an alternative, I’d suggest using sshfs to mount the VM’s files on the host machine so that you can edit them with the same editor you normally use.

First, you need to create a directory to mount the files in. This needs to be in /local (/home is a NFS mount, and sshfs doesn’t support NFS):

# Replace the username with your actual username...
mkdir -p /local/sshfs-username

Then, you can use sshfs to mount the files:

sshfs -p 22222 mininet@localhost:/home/mininet /local/sshfs-username/

After that, you can cd /local/sshfs-username and you’ll see the files of the VM there. Edit them however you with.

Use sshfs to edit "remote" files that are on the VM. When you go to run make or execute git commands, it’s best to do those from the VM directly.

5.4. Cleaning Up

When you’re done working, before you shut down the VM:

  1. Use git to add/commit/push your files to GitHub.

  2. Close any files from the VM that you have open locally and cd out of the sshfs-mounted directory.

  3. Unmount your sshfs file system:

    fusermount -u /local/sshfs-username
  4. Shut down the VM gracefully:

    sudo shutdown -h now

5.5. Copying Files Between Machines

If you need to move files between machines, you can use scp, the secure copy utility. It works like the normal cp command, where you do:

cp [source file location] [destination file location]

With scp though, one of the locations is allowed to be a remote machine that you can ssh to. Formatting the remote side is:

username@host:/path/to/file

If you want to copy an entire directory instead of just one file, you can pass the -r flag to do a recursive copy.

For example, if you want to copy your VM files from one machine to another, you have two options:

  1. From the machine that has the VM, you could do:

    # "desthost" is the host name of the machine you'd like to move the VM files to.
    scp -r /local/CS43-MininetVM-S22-username username@desthost:/local/
  2. From the destination machine, you could do:

    # "srchost" is the host name of the machine you'd like to move the VM files from.
    scp -r username@srchost:/local/CS43-MininetVM-S22-username /local/

If you’d like to work on a laptop, you can install virtualbox on your laptop and copy the VM image to that.

6. Submitting

Please remove any excessive debugging output prior to submitting.

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