CS244 ’16: Sprout via Mahimahi


Danaë Metaxa-Kakavouli and Grace Muzny

Introduction

Cellular wireless networks present unique challenges because they exhibit high variance in link speed. Sprout is a transport protocol designed specifically for this situation (Winstein et al). Rather than relying on reactive congestion control, Sprout attempts to infer the dynamics of the network so that it is always sending the appropriate number of packets for the current and future link speeds. This stands in contrast to protocols like TCP, which react to indications like timeouts to correct for congestion on the network.

Sprout implements congestion control by observing packet arrival times and using this as a signal for congestion. This strategy allows Sprout to forecast sudden drops in bandwidth, which is vital to avoid incurring self-inflicted delay. Sprout aims to predict future bandwidth at 95% probability, allowing it to correct for rapidly changing bandwidth, and outperforms existing congestion control algorithms as a result.

In this blog post we outline our study of Sprout, in which we use a slightly different network setup (an emulated cellular link provided by Mahimahi) to reproduce measurements of throughput and delay on the uplink based on the original paper’s network traces across several congestion control algorithms including Sprout, TCP Cubic, and TCP Vegas. We also discuss our failed attempts to run Skype, Google Hangouts, and Sprout-EWMA on this experimental setup.

Sprout: Stochastic forecasts achieve high throughput and low delay over cellular networks

In the original paper, Winstein et al. find that Sprout out performs other transport protocols across a variety of cellular networks. They use the power score, a ratio of average throughput to 95th-percentile self-inflicted delay, of each transport protocol to visualize and evaluate its performance in relation to the others. For each cellular network that they test, the authors gathered 17 minute traces from the greater Boston area on which to test the protocols.

Across the board, the original results show that where Sprout excels is in achieving low self-inflicted delay. In all but one case (Google Hangouts, AT&T Downlink), it has the lowest self-inflicted delay of all tested protocols. The higher throughput variant that the authors present, Sprout-EWMA, trades some self-inflicted delay for higher throughput. However, this protocol still incurs less delay than most other protocols.

These results show that cellular networks demand transport protocols that take into account their unique properties. Since Sprout is able to easily adjust to plummeting or skyrocketing available bandwidth, it avoids the delays that strategies such as LEDBAT, Vegas, and Compound TCP incur while still maintaining reasonable throughput.

sprout

Reproduction

Motivation

We concentrate on reproducing the Sprout results in the context of TCP variants, as well as a variant of Sprout (Sprout EWMA) and the third-party applications tested in the original paper (Skype and Google Hangouts). Another motivation of this project is to examine results of running these results using a new setup through Mahimahi, in contrast to the original paper which used a physical setup, and past reproductions which used the CellSim network simulator.
cellsim

In this experiment, we seek to reproduce a subset of the graphs in Figure 7 of the original paper. This figure shows a comprehensive overview of the performance of various transport protocols on a variety of different types of cellular wireless networks. The motivation for picking this figure to reproduce is that it does a good job of summarizing the main contributions of the paper–that Sprout reduces end-to-end delay and increases the average throughput on a connection compared to other transport protocols.

Experimental Setup

Unlike previous replications, which used CellSim to replicate Sprout’s three-machine, two-way topology (see Figure above), we were interested in extending our understanding of Sprout by observing its behavior through a lighter-weight, single machine setup. To that end, and for maximum ease of reproducibility, we ran Sprout’s publicly available implementation on Mahimahi. We also attempted to run Sprout’s variant, Sprout-EWMA, but because this algorithm depends heavily on a two-way communication channel, which Mahimahi does not provide, we were unable to do so. This is because Sprout-EWMA requires the two-way communication channel to start up before reaching steady-state, making it ultimately unstable within our emulated network.

To test TCP variants, we experimented with a couple different solutions, including launching a client and server and saturating the link between them. For ease of use, however, we determined that the iperf tool was best suited for this replication. In addition to the TCP variants reported in the paper, we also evaluate TCP-BIC and TCP-Hybla. Even though these variants are designed for different kinds of networks, we were interested to see if these differences made them any more suitable for the cellular network case than TCP Cubic or Vegas.

We attempted to test Skype and Google Hangouts, to little success. While we attempted to launch Skype from the command line using Skype4Py, it proved to be unreliable, often unable to connect and failing silently. In the case of Hangouts, we were unable to find an automated way to run it from a command line interface. Further, after consulting with the authors of the original Sprout paper it’s not clear how it would even be possible to run Skype or Hangouts while using Mahimahi to emulate our network, as we were testing in this project.

We evaluate all algorithms on the traces used by the original authors, which are also publicly available on Github.

Results

We found that our results closely mimicked those of the original paper in terms of relative performance of Sprout to the different variants of TCP with a few exceptions. Since these measurements were made on the uplink of our emulated cellular connection, they should be compared to the corresponding uplink graphs from the original paper. Overall, this means that we found  that Sprout did a good job of reducing 95th percentile signal delay while maintaining a reasonable throughput level. In the uplink case, we observe that the difference between Sprout and TCP Vegas is sometimes not very large, a result that can also be seen in the original paper’s results.

The biggest difference between the original results and our own is the across the board increase in throughput. We believe that this is simply a result of running the system over mahimahi on an ec2 machine. A smaller difference is the relative performance of TCP Vegas to Sprout–the original paper found that Vegas had higher throughput in all but one case (Verizon LTE), while we find that it achieves higher throughput in all cases except for on the ATT LTE trace. It is unsurprising that TCP Hybla and Bic performed very similarly to Cubic given that they are optimized for different kinds of networks and topologies than we were testing.

result_Verizon-LTE-drivingresult_Verizon-EVDO-drivingresult_TMobile-UMTS-drivingresult_ATT-LTE-driving

Conceptual & Implementation Challenges

The major challenge both conceptually and in our implementation was switching from the bi-directional topology recorded by the original paper to a one-direction setup. This switch is what created the most issues for us in attempting to run Skype and Hangouts, and made it unstable to run Sprout-EWMA, and required us to think creatively about the most consistent way to measure TCP variants.

An interesting issue we found was that TCP Reno does not appear to be available as a Linux module; running modprobe to add this module fails. This perhaps explains why Sprout’s current website does not report performance for this algorithm. In doing this work we consulted with previous replications, and found that ReproducingSprout from 2014, however, did report values for TCP Reno. Upon further examination, that group seems to have run their modprobe command with the -q (quiet) flag, which hid the error from its users. This is evidenced by their figures, which show TCP Reno and TCP Cubic overlapping on nearly every plot, since in reality the TCP algorithm was not being changed between the collecting of data for each algorithm.

Discussion

Critique

Though Mahimahi’s mm-link was set up to run algorithms like Sprout for PA2, it is perhaps not the best fit for studying congestion control algorithms. The added benefit of a lightweight startup was partially offset by needing to find various mismatched methods for evaluating the different classes of algorithm and, in the cases of Skype, Hangouts, and Sprout-EWMA, prevented these algorithms from being tested.

Conclusion

We found that the core results of the Sprout paper hold when reproduced. Given that these results have been reproduced in the past, this was not surprising. Since we did our reproduction using a very different tool than the original paper, which ran on three distinct physical machines, the perspective that our results give us is slightly different. Our results highlight the fact that on the uplink, Sprout isn’t extremely different than TCP Vegas. This suggests that downlink performance is the more important differentiator when examining congestion control protocols over cellular networks. Perhaps most importantly, we find that though in principle Mahimahi does the same thing that Cellsim from the original paper does (emulates a cellular network), this change in underlying topology causes many of the original tools produced for this research to break. While we hoped to find that the original results were easily generalizable across emulated networks, we instead found that technical roadblocks make this very hard to verify.

Reproducing our Reproduction

Our code can be found at: https://github.com/dmetaxak/cs244pa3

To reproduce our results:

  1. Clone our repo
  2. Install mahimahi
  3. Build Sprout
  4. Install iperf
  5. (Optional — if you want to make graphs) install matplotlib

Once these dependencies have been installed, running ./inception.sh will run our experiment. It will take approximately 5 hours and 20 minutes. Results are incrementally updated to results/out.txt and will be processed into a nice format at the end of the experiment in results/out.tsv.

If you would  like to generate graphs after the experiment has run:

$ python make_graphs.py results/out.tsv <PREFIX>

More detailed instructions, including what dependencies need to be installed can be found in the README in our github repo.

References

Netravali, Ravi, et al. “Mahimahi: a lightweight toolkit for reproducible web measurement.” ACM SIGCOMM Computer Communication Review. Vol. 44. No. 4. ACM, 2014.

Winstein, Keith, Anirudh Sivaraman, and Hari Balakrishnan. “Stochastic forecasts achieve high throughput and low delay over cellular networks.”Presented as part of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13). 2013.

Advertisements

One response to “CS244 ’16: Sprout via Mahimahi

  1. Reproducibility: 5/5.
    The code ran to completion, and the results were almost exactly the same as those presented in the blog post. Nice job.

    There’s not too much to say about the results themselves, I think, since we already saw for ourselves how well Sprout minimizes delay on PA2. It’s definitely good to see that it gets higher throughput now than it did in the original experiment; technology marches on.

    TCP Reno is actually available on Linux (or at least on EC2 Ubuntu). It’s not available as a module because it’s already installed. However, if a previous group found that it performed identically to Cubic, then it probably wouldn’t have made much of a difference in your results.

    — Nick and Bryce

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