Solving Bufferbloat – The CoDel Way

Team: Rishita Anubhai and Amogh Vasekar.

Key Result(s): CoDel is a no-knobs approach to managing buffers in a router, and this project is an independent evaluation of CoDel results from Van Jacobson and Kathleen Nichols. We were also able to evaluate fq_codel (not in the paper), which shows good improvement vis-a-vis CoDel. Thus, our simulations corroborate with CoDel’s claim of being markedly better than RED and Tail-Drop.

Source(s):

1. Controlling Queue Delay ACM Queue, Kathleen Nichols, Van Jacobson, May, 2012
2. Notes on CoDel algorithm and implementation: addenda, clarifications, and information.
3. CoDel Wiki
4. Pollere, Inc.

Contacts: Rishita Anubhai (rishita@stanford.edu) + Amogh Vasekar (amoghvk@stanford.edu)

Introduction:

CoDel is an extremely new queuing algorithm proposed by Kathleen Nichols and Van Jacobson. It holds great promise for addressing at least some of the bufferbloat problem in many forms of network gear, from routers to dslams to servers to wireless.

Its code is being continually updated in the Linux 3.5 (Net-Next) branch as you read this. (June,2012)

CoDel is thus, a novel “no knobs”, “just works”, “handles variable bandwidth and RTT”, and simple AQM algorithm.

• It is parameterless — no knobs are required for operators, users, or implementers to adjust.
• It treats good queue and bad queue differently – that is, it keeps the delays low while permitting bursts of traffic.
• It controls delay, while insensitive to round-trip delays, link rates, and traffic loads.
• It adapts to dynamically changing link rates with no negative impact on utilization.

CoDel is the first advance in the state of the art of network Active Queue Management in many, many years.

Methods: 

Our simulation set-up consists of :

• Amazon EC2 running Xen Virtualization platform
• (Unreleased) Linux 3.5 Net-Next branch
• OpenVSwitch 1.7.1 branch + OpenFlow
• Mininet network simulator platform
• (Unversioned) iproute2 branch modified to add support for CoDel

Please note that the Linux branch we used contained a broken RealTek driver, which was removed from our build. It is safe to assume this does not affect the simulation or the results.

We needed the 1.7.0+ branch of OpenVSwitch to accommodate for the changes made in 3.5 kernel. Specifically, OVS is now a part of the core kernel modules.

We have changed a file (link.py) in Mininet to provide codel and fq_codel support, as qdiscs, on top of htb.

The iproute2 branch was used mainly to validate correct installation of codel by looking at the command-line outputs (outside the simulation)

Topology and traffic:

Our topology is a single-switch-two-host topology, with each interface of the switch running a qdisc of interest.

The traffic consists of long-lived, stable iperf flows from one host to the other. This is to simulate TCP flows that are a good representation of traffic on the internet.

The bandwidth of the connecting links between hosts is changed instantaneously, as indicated in the graphs, to show the real effect of bufferbloat. This also serves to simulate a wireless link with highly variable bandwidth.

We use tcpdump and libpcap to log and analyze the packets.

Configuration Parameters for qdiscs:

Mininet uses htb for rate limiting, and thus htb is a part of every simulation run.

CoDel needs no explicit tuning being a no-knobs switch (though there are couple of parameters that may be used).

We have tried to optimize RED parameters somewhat, which is a difficult task. We have used the default FIFO parameters for Tail-Drop.

Results:

The goal is to show the effect of bufferbloat in today’s deployments, and how CoDel improves packet delays.

The graphs plot per-packet queuing delay, with x-axis representing a time-period. We measure the per-packet delay using the ingress and egress (pseudo-kernel) timestamps via tcpdump, and match packets using custom C++ code (validated separately).

Our 5 simulation runs show near-exact results.

Within the time-period, we vary the link bandwidth every 15 seconds (50 seconds in the paper), simulating a wireless network.

As is evident from the graph below, Tail-Drop introduces arbitrarily high packet delays in the face of an accumulating buffer. RED performs significantly better than FIFO, but is very hard to configure correctly in real-world scenarios. Also, while RED introduces constant delays when bandwidth changes, it takes a long time (or improved bandwidth) for RED to reduce the packet-delays.

The graphs indicate that CoDel tends to perform in a stable manner throughout the experiment. It is interesting to note that whenever the delay for CoDel spikes, it performs consistently well in smoothly reducing the subsequent packet delays. This is indicated by the graceful improvement of the green curves during spikes.

Match the top graph on left to the one on right. Notice the green curve at 200 on left, and 60 on right
Please note that the graph on left is not to scale

fq_codel’s improvement over codel (not in paper)
Notice how the spike near 60 is reduced significantly by fq_codel

In the graph above, we have evaluated fq_codel, a fair-queue implementation of CoDel, using the same set-up. Note how fq_codel nearly halves the spike introduced at around 60 secs due to a reduction in bandwidth.

In both the graphs above, the first 15 secs, and the last 15 secs, are not smooth enough. Note that during these two time periods, the bandwidth is relatively high at 100Mbps. We believe this is due to GNUPlot’s inability to handle very low granularity (microseconds) while plotting on the same graph. However, note that the bottom-left graph shows similar behavior.

We have tried to smoothen the initial and final spikes using statistical methods, but obviously fall short. We thus, refrain from making any comments about those two time periods, which are not really too important either.

Further Work :

We would have liked to calculate the packet-drop percentage by FIFO, RED and CoDel to see if any one is trading-off reliability for latency.

It would have been a better evaluation had we been able to include different types of traffic patterns, other than iperf, as well.

We would have also liked to use more accurate timestamping via kernel callbacks, since we are dealing with time in milliseconds and microseconds here.

A possible extension is to evaluate CoDel’s interaction in a system when routers run different algorithms, or a topology like VLB/VL-2 running different flavors like MPTCP etc.

Lessons Learned:

Linux qdisc is a very intricate piece of work, and very hard to configure correctly. It is important to pay special attention to it while administering a system, since it directly affects the network performance and user experience.

Of course, bufferbloat, even though around for more than a decade, is still an unsolved problem that warrants active research.

With respect to Mininet, it would have been really great to have a temporary handle for each packet that enters your system, allowing for better analysis.

Acknowledgements:

Special thanks to Prof. Nick McKeown, Nikhil, Brandon, Bob and Vimal for guiding us throughout. A big shout-out to the CoDel developers for their useful suggestions, especially Dave Taht for helping us while on vacation.

Instructions to Replicate This Experiment:

We have created a custom AMI since the kernel (net-next) is unreleased yet, and so is the OpenVSwitch branch we use. To replicate :

1. Launch a *small* instance on Amazon EC2 Oregon datacenter using AMI – CS244_amogh_rishita_CoDel

2. Log-in to the instance.

3. One time set-up to start OpenVSwitch using built-in kernel modules (Important – This is needed after every reboot too)

• $> cd ~/openflow/openvswitch
• $> perl start_ovs.pl
• This should give an output like : “/usr/var/…….. does not exist, creating” followed by messages indicating OVS has started

4. $> cd ~/project_codel

5. $> sudo python codel.py

Please make sure no “file not found” or “no data in graph” errors are produced. If you do, then please :

• $> sudo rm -rf /mnt/run*
• $> sudo rm -rf ~/project_codel/ts_*
• $> sudo rm -rf ~/project_codel/*.png
• Repeat steps 4 and 5

After the run is complete (approx. 7 mins), you will find two files in the directory : graph1.png and graph2.png

graph1.png corresponds to Graph-7 in CoDel paper, graph2.png is a result we present showing fq_codel’s improvement over CoDel.

scp the graphs to your machine to view (Note – Being an untested kernel, we do not know how the HTTP server might work and recommend simply scp-ing)

6. scp -i <key.pem> ubuntu@<host>:~/project_codel/*.png .