CS244 ’16: TIMELY


Team

Andrew Fang, Emre Orbay

Paper

Mittal, R., Dukkipati, N., Blem, E., Wassel, H., Ghobadi, M., Vahdat, A., … & Zats, D. (2015, August). TIMELY: RTT-based Congestion Control for the Datacenter. In Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication (pp. 537-550). ACM.

Introduction

Mittal et al. introduced TIMELY, a delay-based congestion control protocol for data centers that uses hardware timestamps to make precise RTT measurements. TIMELY uses the gradient of RTT over time to adjust congestion window size before congestion happens. As discussed in the paper, latency in the datacenter is caused primarily by packets waiting in buffer queues.

We reproduced the results outlined in section 6 of the TIMELY paper and benchmarked the results against an “oracle” TIMELY implementation. The oracle congestion control implementation will have access to near real-time buffer occupancy. We argue that an omniscient algorithm that uses the gradient of buffer occupancy will perform at least as well TIMELY and will serve as a very good benchmark for the results outlined in the TIMELY paper.

The paper argues that RTT can be used to approximate buffer occupancy accurately. We agree with this claim and want to see how much better TIMELY could perform if instead of measured RTT, real-time queue occupancy was known. To do this, we used ns-3, a discrete-event network simulation software to simulate the the small scale TCP incast test described in the TIMELY paper.

Goals

The original paper introduces the idea of using RTT as an accurate measurement of queue occupancy in datacenter networks. Datacenter networks are distinctly different than end-user networks, especially because latency in the datacenter is caused primarily by packets waiting in buffer queues. Due to developments in hardware technology, RTT can be measured with accuracy to the microsecond. TIMELY uses this to adjust transmission rates based on changes in RTT to maintain high bandwidth with low latency.

Motivation

This problem is important because modern data centers need to be able to scale effectively. As more and more applications enter the cloud platform, network traffic becomes harder and harder to manage. Customers and end-users expect a certain quality of service, with baseline delay guarantees. Thus, proper congestion control is needed to make sure the links aren’t being jammed with too many packets.

Results

The authors built TIMELY and evaluated it on a topology composed of hundreds of machines. They found that in datacenters, RTT is strongly correlated with network queuing delays, and in fact TIMELY could effectively perform congestion control with these accurate RTT measurements. In tests, TIMELY effectively decrease application latency and increased utilization by preventing congestion and maintaining low queue occupancy.

Subset Goal

We will attempt to reproduce some of the experimental results described in the paper, particularly table 1, figure 13 and 14. This will both demonstrate the faithfulness of our emulation to the original experiment and verify the results advertised in the paper. Then, we will implement the modified version of TIMELY that is aware of the real-time queue occupancy at the egress link of the switch and/or the rate of change of queue occupancy. We’ll have to investigate what the best way to relay this information to the end hosts, currently our method of approach is to run the simulation inside a bigger EC2 instance and use pipes between the switch and the end hosts to communicate the real-time buffer occupancy. The latency of IPC using pipes should be under a microsecond, which is fast enough to appear “real-time” to the end-hosts.

Subset Motivation

TIMELY uses RTT as a proxy for measuring queue occupancy, so we want to see how it actually compares to such a system that knows the exact state of queues at the switches in the network. Of course, a real congestion control algorithm could not have access to real-time queue occupancy which is why TIMELY uses RTT instead. But if TIMELY uses RTT as a stand-in for queue occupancy, evaluating TIMELY against the queue occupancy algorithm will reveal how true the author’s assumptions are about the correlation between RTT and queuing delay, as well as tell us how much room there is for improvement in congestion control algorithms inside the datacenter.

Subset Results

We successfully implemented TIMELY in ns-3. We followed the pseudo code provided in the paper to approximate the congestion control protocol presented by the authors. They had some constants that they mentioned, but didn’t provide specific numbers for. So, we started by taking inspiration from the Jacobson and Karels paper and built our algorithm with an exponential weighted moving average (EWMA) value of 0.1, a multiplicative decrement factor (ß) of 0.5, an additive increment step (δ) of 1500, Tlow of 50, and Thigh of 500. After playing around for a bit, we settled on emwa = 0.1,Thigh = 500, Tlow = 50 on a 50 Mbps bandwidth, 10µs propagation delay link topology .

We ran TIMELY on a tree topology with one switch connected to eleven terminal nodes. The 11 terminal nodes all send traffic through the switch, and we capture network activity there. The original paper used links with 10Gbps bandwidth, but due to reasons discussed later in the challenges section, we present here results for links of capacity 50Mbps.

We ran our algorithm with a couple of different parameters for δ and ß. Our implementation of TIMELY with these comments  above mentioned constants gave us the following results.

Timely  (δ=2,ß=.3)
Average throughput: 25.4915 Mbit/s
Average queue occupancy: 0
95th percentile queue occupancy: 1
Average RTT: 868 µs
95th percentile RTT: 1371 µs
TIMELY-timelyQTIMELY-timelyRTT
Timely (δ=4,ß=.01)
Average throughput: 29.0381 Mbit/s
Average queue occupancy: 2
95th percentile queue occupancy: 7
Average RTT: 1411 µs
95th percentile RTT: 2568 µs
TIMELY-timely2QTIMELY-timely2RTT

 

As a reminder, here are the results from the paper
TIMLEY-originalResults

We can clearly see the distinct difference in values between our implementation and the paper’s results. We are unable to get the same throughput and RTT as Mittal et al., and in fact our throughput and RTT measurements are about 1000x worse than TIMELY’s performance.  However, the behavior we experience is on the same order of magnitude as TCP NewReno or Vegas run on ns-3. There are many reasons why our results are not even close to what the paper presented. Most important, we are running on a virtual environment with link speeds of 50Mbps, compared to the original experiment which ran on 10Gbps NICs. The difference between link speeds and a virtual vs physical network results in the divergence of results.

We wanted to compare this to an Oracle congestion control protocol that knows the queue occupancy size at all times.  We built this by feeding back queue occupancy sizes into our TIMELY implementation (so instead of using RTT to modify send rate, we use the actual number of items in the queue).

Here are the statistics

Oracle (thigh=20 tlow=5 addstep=4 --beta=0.01)
Average throughput: 32.9797 Mbit/s
Average queue occupancy: 58
95th percentile queue occupancy: 133
Average RTT: 43368 µs
95th percentile RTT: 89295 µs
TIMELY-oracleQTIMELY-oracleRTT

 

Unfortunately, our oracle implementation didn’t work exactly the way we wanted it to. Part of the reason (we suspect) is that the constants that we chose for running TIMELY with RTT needed to be tweaked further to apply to queue occupancy measurements. 

The TIMELY paper also compared their algorithm to TCP Vegas, so we ran Vegas on our topology.

Vegas
Average throughput: 31.4018 Mbit/s
Average queue occupancy: 29
95th percentile queue occupancy: 72
Average RTT: 12179 µs
95th percentile RTT: 14903 µs
TIMELY-vegasQTIMELY-vegasRTT

Here’s a quick summary of what we’ve accomplished. Our implementation of TIMELY successfully keeps the queue occupancy and RTT low compared to TCP Vegas. Although this does not directly correlate itself with the throughput achieved, we attribute this to confounding factors in the simulated network that would not be existent in a real data center environment. In such an environment, queue occupancy and RTT would more directly influence the average throughput.

 

Timely
(δ=2,ß=.3)
Timely
(δ=4,ß=.01)
Oracle Vegas
Average throughput (Mbps) 25.4915 29.0381 32.9797 31.4018
Average queue occupancy (packets) 0 2 58 29
95th percentile queue occupancy (packets) 1 7 133 72
Average RTT (µs) 868 1411 43368 12179
95th percentile RTT (µs) 1371 2568 89295 14903

Challenges

We didn’t have experience working with ns-3 before, so we spent a bit of time setting up the environment. At first, we tried setting it up on a virtual machine on our local computers, but we soon realized that ns-3 requires a lot of memory for all of its package dependencies. So, we then decided to launch an EC2 instance and just work off of that. ns-3 documentation is pretty thorough, but they have many different start-up guides, each which differs a little from each other. The setup process was quite lengthy given its many dependencies.

A challenge that we faced for generating results is that TIMELY is heavily reliant on the super-accurate RTT measurements from the NIC. Obviously in our virtual network, we don’t have the same level of accuracy that the authors had in their datacenters. This is a large reason why we couldn’t get the same levels of throughput as the in the paper.

The original paper uses links with bandwidth capacity 10Gbps. We tried setting up our topology with this capacity, but not only did the system slow done a ton, but the simulation also failed to complete. This could a factor of how ns-3 implements “link speed” — what it does is it simulates traffic on a virtual time that’s disjoint from the actual system time. To get faster link speeds, ns-3 slows down the virtual time. 

Another important problem for us was that the authors of TIMELY took a clean slate approach to congestion control. Part of this is the decoupling of “rate computation” from “rate control”, which we couldn’t have implemented without writing our own transport protocol. We opted to use TCP and modify the internals of the ns3 TCP implementation instead.

Linux has an interface for writing pluggable TCP congestion control algorithms (which ns3 mimics) but unfortunately the interface does let the algorithm directly control the rate enforcement and had to be modified to delegate the entirety of rate computation to TIMELY. We believe TIMELY would perform better if the software and hardware based pacing could be integrated into the simulation, instead of our reliance on controlling cwnd.

Critique

In retrospect, this was a hard paper to reproduce results for. The power of TIMELY is that it is a good congestion control algorithm because hardware NICs could very accurately report RTTs, which TIMELY uses to adjust its send rate. We could not do this in our simulated environment. That said, we can see through our comparison with TCP New Reno, that TIMELY effectively keeps RTT and queue occupancy low. In our simulation, this didn’t help increase bandwidth beyond how TCP New Reno performs, but an explanation for this is that in a data center network, delay is directly correlated to congestion. This is not necessarily the case in our virtual network. Delay could be caused by other, non-congestion related factors, and this mucks with TIMELY’s congestion control.

Platform

We chose to build our project on ns-3. ns-3 provides great documentation and examples for setting up arbitrary network topologies with custom congestion control protocols. After setting up our environment, it was fairly straightforward to implement and run our version of TIMELY. We ran ns-3 on Amazon EC2, and we had plenty of resources on a m4.large instance. The setup is easily reproducible, and doesn’t include any dependencies besides the original ns-3 setup.

README

Setup – EC2

  1. Find the AMI image that we created named cs244_timely. (AMI ID =ami-3787745a, Owner id=887620843900). This will have all the source code and setup you need to run our code.
  2. Launch as a m4.large instance

Setup – Manual

  1. Launch a clean ubuntu 14.04 installation. We used a m4.large instance.
  2. Follow the steps here https://www.nsnam.org/docs/tutorial/html/getting-started.html to get ns-3 installed. I would recommend downloading and building with Bake
  3. cd ns-3-allinone/ns-3-dev/
  4. git clone https://github.com/andrewfang/244_timely

Running

  • Cd ns-3-allinone/ns-3-dev/
  • ./waf –run “star –cc=Timely”
    1. –cc=NAME to change the congestion control algorithm
      1. NAME = {Timely, NewReno, Vegas, HighSpeed, WestWood, Bic, Veno}
    2. –queueSize=INT to change the queueSize (500000)
    3. –oracle=BOOL to say whether or not to use the oracle queue-occupancy-aware TIMELY (false)
    4. –bw=STRING to change bandwidth of links (“100Mbps”)
    5. –pd=STRING to change prop delay of links (“1us”)
    6. –ewma=DOUBLE to change the TIMELY EWMA weight (0.1)
    7. –addstep=DOUBLE to change TIMELY add increase (4.0)
    8. –beta=DOUBLE to change TIMELY mult decrease (0.05)
    9. –thigh=INT to change TIMELY RTT High Threshold (4000)
    10. –tlow=INT to change TIMELY RTT Low Threshold (250)
    11. –printQueue=BOOL to toggle whether queue values are printed
    12. –printRTT=BOOL to toggle wheter queue values are printed

To get the graphs

  • ./waf –run “star –cc=Timely –printQueue=true” > timelyQ.txt 2>&1
  • ./waf –run “star –cc=Timely –printRTT=true” > timelyRTT.txt 2>&1
  • Then scp timelyQ.txt and timelyRTT.txt into the directory with the ipython notebook file
    • If you don’t have ipython notebook
      • pip install ipython
      • pip install matplotlib
      • ipython notebook
      • Then in box 2, change alg=timely
      • Run all the blocks, graphs will be generated in your directory
  • ./waf –run “star –cc=Vegas –printQueue=true” > vegasQ.txt 2>&1
  • ./waf –run “star –cc=Vegas –printRTT=true” > vegasRTT.txt 2>&1
  • ./waf –run “star –cc=Timely –oracle=true –printQueue=true” > oracleQ.txt 2>&1
  • ./waf –run “star –cc=Timely –oracle=true –printRTT=true” > oracleRTT.txt 2>&1
Advertisements

One response to “CS244 ’16: TIMELY

  1. Reproducability: 2

    The instructions here are missing a ton of steps that are needed for reproducing the results, and though we got the code to run and created the text files with the data to analyze we could not manage to get the ipython notebook running to reproduce the graphs.

    Here are some of the issues we ran into:
    – The ami id described here is incorrect. It is actually ‘ami-403ac320’
    – The username for ssh wasn’t provided anywhere (it’s ‘ubuntu’)
    – The commands in the blog-post were auto-formatted so copy-pasting them into an ssh terminal will give you weird errors. Make sure to change the em-dash character to ‘–‘ and the left-quote/right-quote characters to normal quotation marks.
    – Some commands needed to be run under sudo

    ——————————
    That describes what we needed to do to get the RTT and queue length data files, at which we succeeded. Converting that data into graphs had additional issues:

    -The provided ami didn’t have all of the necessary tools installed, (ipython, matplotlib, etc…) so you have to install them yourself.
    -The “ipython notebook file” mentioned is named “Graph RTT.ipynb”, and there are two conflicting copies of it, one in ns-3-allinone/ns-3-dev/, and one in ns-3-allinone/ns-3-dev/244-timely.
    -After wrestling for a couple hours with ipython/pip/matplotlib we still couldn’t get a working version that was recent enough to support the nbversion number.

    We think it would have gone much smoother if the ami had been pre-loaded with all the dependencies, and if it had generated the graphs in a simple python script instead of spinning up a whole web-server with the ipython notebook.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s