CS 244 Contestion-Control Contest

Updated April 4, 2018

In PA1, you will compete to build a congestion-control algorithm to maximize "power" (throughput / delay) on an emulated cellular network. You will start with a simple UDP sender and receiver, built on C++ networking classes that do most of the grunt work of opening sockets and reading and writing datagrams.

By modifying the behavior of the congestion controller (implemented in controller.cc), you can control how the sender decides when to send datagrams. The more datagrams it sends, the more your throughput will be, at the risk of building up an in-network standing queue and resulting delay.

Step 1: Watch video

Please watch this 25-minute video on the Sprout algorithm:

Step 2: Install the contest software

Please set up the contest software on a GNU/Linux machine (physical or virtual) of your choosing. If you use GNU/Linux on your computer, the below steps are probably best run directly. Otherwise, we have prepared a VirtualBox image that you can use to install the contest software. Please note that because your software runs in real time, the best performance will be achieved on a faster (and preferably non-virtual) machine. You may find that an EC2 instance gives more reliable results than your own laptop, but without the animated graphs that can give help for debugging and development.

Please post any difficulties on the Piazza forum. The following steps worked successfully on Ubuntu GNU/Linux 14.04 through 17.10:

sudo apt-get install build-essential git debhelper autotools-dev dh-autoreconf iptables protobuf-compiler libprotobuf-dev pkg-config libssl-dev dnsmasq-base ssl-cert libxcb-present-dev libcairo2-dev libpango1.0-dev iproute2 apache2-dev apache2-bin iptables dnsmasq-base gnuplot iproute2 apache2-api-20120211 libwww-perl

(these dependencies are listed in mahimahi/debian/control, plus some for the contest itself)
$ git clone https://github.com/ravinet/mahimahi (the mahimahi tools provide our emulated cellular network and measurement tools)
$ cd mahimahi
$ ./autogen.sh && ./configure && make (compile mahimahi the usual way)
$ sudo make install
$ cd ..
$ git clone https://github.com/keithw/sourdough
$ cd sourdough
$ ./autogen.sh && ./configure && make (compile the contest code the usual way)
$ sudo sysctl -w net.ipv4.ip_forward=1(have to enable Linux's IP forwarding for mahimahi to work)
$ cd datagrump

Step 3: run the example code

This command will run the congestion-controller in https://github.com/keithw/sourdough/blob/master/datagrump/controller.cc for about two minutes over an emulated Verizon LTE (4G) connection. While it runs, you will see an animation of the network's capacity, the sending rate of the algorithm, and the in-network queueing delay. After the run completes, it will upload your results to the contest website. If you do not see "upload successful," please report the problem on Piazza.

Please use the same scheme name for each of your submissions — otherwise you will pollute the leaderboard.

$ ./run-contest [scheme_name]

Listening on :::9090
Sending to 100.64.0.1:9090

Average capacity: 5.04 Mbits/s
Average throughput: 4.80 Mbits/s (95.2% utilization)
95th percentile per-packet queueing delay: 237 ms
95th percentile signal delay: 608 ms

Uploading data to server... done.

Upload successful (2427648 bytes).
For analysis, please visit:

   http://cs344g.keithw.org/report/?example-1453001748-thaiphei

Step 4: visit your analysis URL

The URL given by the uploader will allow you to see the results of your congestion-control scheme, compared with others in the class, the winning entries from previous classes, and the Sprout algorithm. (You will need to visit the URL for your algorithm to join the leaderboard.)

Step 5: the homework assignment

First, read through the existing congestion controller in the datagrump directory. To modify the congestion-control behavior, you will probably will only need to modify the controller.cc file, and perhaps controller.hh. If necessary, though, you are free to modify anything in sourdough (except the run-contest script).

Please write up your answers to the below exercises in a report, to be submitted in PDF form:

Warmup exercise A [10%]: Vary the fixed window size by editing controller.cc to see what happens. Make a 2D graph of throughput vs. 95-percentile signal delay (similar to what is seen on the contest analysis URLs) as you vary this value. What is the best single window size that you can find to maximize the overall "score" (log throughput/delay)? How repeatable are the measurements taken with the same window size over multiple runs?
Warmup exercise B [20%]: Implement a simple AIMD scheme, similar to TCP's congestion-avoidance phase. How well does this work? What constants, and what backoff trigger, did you choose?
Exercise C [65%]: the contest. Try different approaches and work to maximize your score on the final evaluation. Be wary about "overtraining": after the contest is over, we will collect new network traces and then run everybody's entries over the newly-collected evaluation trace. In your report, please explain your approach, including the important decisions you had to make and how you made them. Include illustrative plots.
Exercise D [5%]: pick a cool name for your scheme!

Step 6: submission

The homework is due at 5:00 p.m. Pacific time on Tuesday, April 17. Please submit your report as PDF and a link to a Git repository where we can download your code. Please run the submit script on your PDF file: /afs/ir/class/cs244/bin/submit 1 reportname.pdf.

Provisos: Your Git repository must inherit from the current commit on the datagrump repository. Please do not simply copy the files into a new Git repository—we would like you to make a series of small commits that inherit from the current master branch. (If you need assistant with Git, the course staff is happy to help!) Your code should work without modifying the run-contest script. Please include the summary statistics (score, delay, throughput) you achieved on the Verizon 140-second trace, so we can make sure your code is running as expected.