Sprout is a transport protocol for interactive applications that desire high throughput and low delay.

In evaluations on traces from commercial LTE and 3G networks, Sprout achieved 2–4 times the throughput of Skype, Apple Facetime, and Google Hangout, while reducing self-inflicted delay by 7–9 times.

— Keith Winstein, Anirudh Sivaraman, and Hari Balakrishnan

Research paper » Tech video » Source code »

Stochastic Forecasts Achieve High Throughput and Low Delay over Cellular Networks, in the proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2013), Lombard, Ill., April 2013.

Slides and a public summary are available on the open-access conference proceedings site.

The talk was given April 5, 2013.

The source code to Sprout (evaluated in the research paper) is available on GitHub.

Source code to Sprout Tunnel (allows TCP to be tunneled within Sprout) available on GitHub

Our "explicit-state" MPEG-2 implementation includes an encoder API (based on mpeg2enc) and a decoder API (built around libmpeg2).

Our code for saturating wireless networks and then replaying those traces on a hardware gateway is also available on GitHub.

Our implementation of the "CoDel" AQM algorithm is available in a different repository.

Mininet port of cellsim

The page here describes a Mininet port of our trace driven emulator, cellsim, used as part of a problem set in MIT's graduate networking class (6.829).

Data Collection

Cellular network traces were collected while driving in Boston, Mass., and surrounding municipalities. We simultaneously saturated the uplink and downlink of an Android smartphone tethered to a Linux laptop and measured the times when packets arrived across each link. Uplink datagrams were sent to a server at MIT, generally less than 50 ms RTT from the carrier's first/last hop.

The code for the saturatr can be found on GitHub.

The Verizon LTE and 1xEV-DO (3G) traces used a Samsung Galaxy Nexus smartphone running Android Ice Cream Sandwich. The AT&T trace used a Samsung Galaxy S3 smartphone. The T-Mobile trace used a Nexus S smartphone running Android Jelly Bean.

For each network, raw traces for both the uplink and the downlink are available here

Raw data used to generate the plots

The raw data along with instructions to reproduce all of our results( Figures 7,8 and 9 and the tables in Section 5.6 and 5.7 ) from the raw data are available here. Please contact us at alfalfa at mit dot edu in case you have any questions/comments.

Reproducing our results

You will need 3 separate physical machines to reproduce our results:

  1. The first should have a direct connection to the Internet (henceforth to be referred to as the server).
  2. The second one (to be referred to as cellsim_machine) should have 2 ethernet cards, one of which is directly connected to the Internet (eth0)
  3. The third one (to be referred to as the client) should have one Ethernet card and its ethernet cable should be connected into the second ethernet card (eth1) of cellsim_machine. As described in the paper, cellsim_machine routes traffic from the client to the Internet and back.

Cellsim machine instructions

Once, the hardware setup is done, do the following on cellsim_machine:
  1. Download the source for cellsim, our trace driven emulator from here : here
  2. cd into the sender directory and run make cellsim ( You 'll need C++11 support ). This will create the cellsim executable.
  3. Ensure both ethernet interfaces on cellsim_machine are UP and set to promiscous mode. To do this, run :
     sudo ifconfig ethX up promisc 
  4. Turn off all segmentation offloads on both interfaces using :
     sudo ethtool --offload ethX gso off  tso off gro off 
  5. Run :
     sudo ./cellsim uplink_trace downlink_trace client_mac loss_rate 
    where :
    1. uplink_trace is a cellular network trace for the uplink.
    2. downlink_trace is a cellular network trace for the downlink.
    3. client_mac is the MAC address of the client machine (ie the third machine in the description above).
    4. loss_rate simulates probabilistic head drop and is a fraction between 0 and 1.
    5. NOTE: Both uplink_trace and downlink_trace need timestamps in milliseconds that start from zero for cellsim to function properly. The traces here have absolute UNIX timestamps in nanoseconds which need to be converted to relative timestamps before feeding them to cellsim.
    6. NOTE2: The interface connected to the Internet is hard coded as eth0 and the interface connected to the client is hardcoded as eth1. If you have different names on your machine, you will need to change both in cellsim.cc.
  6. Once cellsim is running, it produces a sequence of packet deliveries in both the uplink and the downlink direction. These can be analysed using the scorer and quantiles scripts as described here

Client/Server machine instructions

Cellsim is designed to operate transparently. So, you should be able to run pretty much anything on the client so long as the client has a public IP. In particular, you can setup TCP connections using different congestion control algorithms on Windows and Linux. To set the congestion control algorithm in Linux on either the client or the server, run(as root). (Replace vegas with cubic for TCP cubic.)

 modprobe tcp_vegas
 echo "vegas" > /proc/sys/net/ipv4/tcp_congestion_control

To enable, Compound TCP on Windows 7, run the following on an elevated command prompt :

 netsh int tcp set global congestionprovider=ctcp

Our version of LEDBAT is taken from the libutp implementation, available here

Running CoDel

Our version of cellsim, with CoDel integrated into it is available here . cd into codel-for-cellsim and run make cell-codel-sim ( you ll need C++11 support). Then, run :

 sudo ./cell-codel-sim uplink_trace downlink_trace client_mac codel_enable 
Set codel_enable to 1 or 0 depending on whether you want it enabled. Running it with 0 is equivalent to running the original cellsim. uplink_trace, downlink_trace and client_mac have the same interpretations as for cellsim.

Running Sprout

The version of Sprout that was evaluated in the paper is available : here . You will need to install the following libraries to build Sprout:
 sudo apt-get install libboost-math1.50-dev libboost-math1.50.0 libprotobuf7 libprotobuf-dev 
Next, cd into alfalfa, and run:
 ./configure --enable-examples
The Sprout executable should now available at src/examples/sproutbt2. To run the Sprout server, type :
To run the Sprout client, type :
 ./sproutbt2 server_address 60001 
Sprout might need between 20 and 40 seconds to start up (to precompute Gaussian Distributions required for inference).

Evaluation of Systems

We used a physical gateway computer, with two Ethernet interfaces, to replay the recordings from cellular networks. The gateway queued incoming packets indefinitely, and released them to the other interface according to the schedule previously recorded in the trace.

The code for the cellsim tool (used to replay traces from the saturatr) can be found on GitHub.

We evaluated videoconferencing systems and TCP variants with one computer connected directly to a gigabit switch and to the Internet. The other computer was connected to the cellsim, whose other Ethernet interface was connected to the same gigabit switch.

We tested the following configurations:

Sprout"evaluated" and "ewma-evaluated" tagsLinux 3.2.0-29-generic (Ubuntu 12.04 LTS)Intel Core i7 PC
Skype5.10.0.116Windows 7Intel Core i7 PC
Google Hangoutin Chrome 21.0.1180.89Windows 7Intel Core i7 PC
Apple Facetime2.0 (1070)OS X 10.8.1MacBook Pro (2.3 GHz i7), MacBook Air (1.8 GHz i5)
TCP CUBICin Linux 3.2.0Intel Core i7 PC
TCP Vegasin Linux 3.2.0Intel Core i7 PC
LEDBATin uTPLinux 3.2.0Intel Core i7 PC
COMPOUND TCPin Windows 7Intel Core i7 PC
Please e-mail alfalfa at mit dot edu with any questions.