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:
-
select
manual (for timeouts) -
The protocol you implement will be simpler than TCP, but you may find the course TCP slides or TCP’s header information to be useful for inspiration.
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
andmy_close
. -
in
lab5.h
: add header fields tostruct lab5_hdr
. -
to send and receive data across the wire, we’ll be using UDP’s unreliable
send
andrecvfrom
in your implementation of a stop-and-wait version ofmy_send
andmy_recv
. Your code in these functions is responsible for implementing reliability on top of UDP.
-
-
Application layer:
lab5_sender.c
andlab5_receiver.c
implement the application layer that calls your library functions. Note thatlab5_sender
andlab5_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
andlab5_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.
-
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. -
Define your transport layer segment header format in
lab5.h
. -
Write a helper function that helps you maintain an RTT estimate based on sample RTT measurements.
-
Implement reliable sending in
my_send
. To reliably send data, you will need to implement the following:-
Copy and send the application layer payload + transport header into your send buffer.
-
Maintain data structures to estimate RTT.
-
Keep track of segments sent and acknowledgements received.
-
Attempt to receive acknowledgements, and resend data segments if you timeout on a segment.
-
-
Implement reliable receive in
my_recv
. To reliably receive data, you will need to implement the following:-
Receive a segment over the network, you are not required to check for data corruption (e.g., with a checksum).
-
Make sure you received the expected segment, and if so, send an appropriate acknowledgement to the sender.
-
As segments are received in order, remove the transport layer header and copy the application layer payload to the application’s buffer.
-
Return the number of bytes received to the application.
-
-
Implement reliable closing in
my_close
. Your implementation should cleanly shut down connections on both ends, even if segments get lost.-
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). -
TIP: since you are closing reliably, you may find it helpful to call
my_send
frommy_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
andlab5_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
ormd5sum
. -
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 tomy_send
. That is, thelen
parameter passed tomy_send
will be less than or equal toMAX_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 thestderr
stream rather than the usualstdout
. 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 onlystdout
. -
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…
-
You receive an acknowledgement, in which case you move on to sending the next segment, or
-
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 |
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
isint 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 usemsec_to_timeval()
to fill outstruct 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:
-
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
. -
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 likescp
.
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:
-
Run
virtualbox
in a terminal or open it from your favorite graphical menu. -
Go to File→Preferences, set your "Default Machine Folder" to
"/local"
, and then close the preferences window. -
Go to File→Import Appliance. Choose:
/local/CS43-MininetVM-S22.ova
and push next once. -
You should now be seeing "Appliance settings". Edit the name to include your username at the end. For example,
CS43-MininetVM-S22-kwebb
. -
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:
-
Create a new key for the VM and add it to your GitHub account. (Instructions)
-
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
ssh
ed 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 ssh
ed 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 |
5.4. Cleaning Up
When you’re done working, before you shut down the VM:
-
Use
git
to add/commit/push your files to GitHub. -
Close any files from the VM that you have open locally and
cd
out of the sshfs-mounted directory. -
Unmount your
sshfs
file system:fusermount -u /local/sshfs-username
-
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:
-
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/
-
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.