CS244 ’17: Comparison of Sprout and Verus Protocols


By Kevin Chavez and Jake Smola

Introduction

According to [1], for the first time in history, the number of mobile internet users surpassed that of desktop internet users. As this number continues to grow, so do the demands placed on the cellular networks serving mobile users. Unfortunately, cellular networks are already at somewhat of a disadvantage when compared to traditional networks. Cellular networks, including 3G and LTE, are highly variable in terms of their available link rate due to high burstiness caused by user mobility in addition to traditionally bursty internet traffic patterns [2].  Conventional congestion control protocols like TCP are poorly equipped to handle challenges associated with these types of networks and tend to offer lower throughput and higher delay than modern competitors like RemyCC [3] and Sprout [4]. Such high delay and low throughput can jeopardize the user experience as sudden drops in network capacity can lead to delays on the order of a few or more seconds.

To combat these issues Zaki et al. present Verus, an adaptive congestion control scheme intended for cellular networks and other highly variable packet-switched environments [5]. With Verus, the authors attempt to improve upon the inefficiencies in contemporary transport schemes for adapting the sending window size of hosts on a cellular network such as LTE. In doing so, the authors develop a delay-based congestion control algorithm which nicely models the delay-profile of the network state. Zaki et al. found that Verus outperformed TCP Cubic by offering higher throughput and lower end-to-end delay under changing cellular network conditions of 3G and LTE. Additionally, the authors found various configurations of Verus to outperform Sprout in delay or throughput but never both. In our work, we reproduce a subset of the results of Zaki et al. visible in Figure 1 to validate their findings and extend upon their work. We specifically chose to reproduce the results comparing Sprout and Verus under various configurations (R-parameters) in terms of delay and throughput using a local LTE network and a mahimahi emulated? network. We chose to focus on the comparison of Sprout and Verus due to the tremendous success of the two protocols as compared with conventional TCP implementations over cellular infrastructure.

verus_rep.PNG

Figure 1: Verus original results for reproduction.

Methodology

We conducted our experiment on a Google Compute Engine, Ubuntu virtual machine instance. Our environment included the most recent releases of Sprout, Verus, and Mahimahi–all accessible from public repositories on GitHub. We created and modified existing perl scripts to wrap and execute our trials as well as to plot our collected data using GNUPLOT. Leveraging Mahimahi’s simulation framework at the core of our project and Random Early Detection as a queue management policy, we spawned instances of Sprout and Verus using AT&T, Verizon, and T-Mobile LTE traces according to the following algorithm:

  • For each trace source in [ATT, Verizon, T-Mobile]:
    • For each class in [Verus (R=2), Verus (R=4), Verus (R=6), Sprout]:
      • Collect throughput/delay data
  • For each trace source in [ATT, Verizon, T-Mobile]:
    • Compute throughput/delay metrics & plot

Here the R parameter describes Zaki et al’s maximum-to-minimum delay ratio, a value that determines what conditions Verus deems tolerable and ultimately determines how Verus reacts to end-to-end delay.

Results

Zaki et al. found the best R-parameter for their environment to be R=6, since it facilitated only marginally higher delay alongside noticeably higher throughput than R=2 and R=4. The authors also found Verus with R=6 to similarly compete with Sprout, sacrificing some latency for improved throughput.

Our own results tend to echo this finding. Using the Verizon and T-Mobile traces, Verus achieved higher throughput and higher delay than Sprout, with data points roughly conforming to the assumed Paretto frontier that dictates the tradeoff between throughput and latency (see figures 3 and 4).  However, using the AT&T trace, Verus was unable to achieve similar results and significantly under-performed Sprout in both throughput and latency (see figure 2). Furthermore, the relative differences among the three Verus instances implemented do not seem to be as predictable as they are made out to be. Under the AT&T and T-Mobile traces, Verus with R=6 fails to differentiate itself in terms of throughput and latency from R=2 and R=4, begging the question of whether or not Verus’ inconsistent performance may be due to factors not yet accounted for.

To gain more insight about this phenomenon, we sought greater information from the comparative throughput plots for Sprout and Verus for the three traces, visible in figures 5-7. Both figure 5 and 6 suggest Verus, under its default configuration, may incorrectly predict available capacity in the face of changing cellular network conditions, over-utilizing available bandwidth during some sequential epochs and under utilizing it during others. Therefore. While Sprout seems to consistently predict the available bandwidth with accuracy, Verus is less precise.

We believe this inconsistency of Verus may be due to the default parameters established in its source code. In [8], the authors adjust these parameters to better suit the traces they use for experimentation. However, we sought to assess Verus “out-of-the-box” here, in hopes that the most recent version would have improved on these parameters or other mechanisms that would make it more competitive.

att_tput_delay.PNG

Figure 2: Sprout vs. Verus (R=6,4,2) – Average Throughput & 95th Percentile Delay over AT&T LTE

tm_tput_delay.PNG

Figure 3: Sprout vs. Verus (R=6,4,2) – Average Throughput & 95th Percentile Delay over T-Mobile LTE

verizon_tput_delay.PNG

Figure 4: Sprout vs. Verus (R=6,4,2) – Average Throughput & 95th Percentile Delay over Verizon LTE

att_tput.PNG

Figure 5: Sprout vs. Verus (R=6) – Throughput over AT&T LTE

tm_tput.PNG

Figure 6: Sprout vs. Verus (R=6) – Throughput over T-Mobile LTE

verizon_tput.PNG

Figure 7: Sprout vs. Verus (R=6) – Throughput over Verizon LTE

Auxiliary Results

For our experiments we kept p_drop at 10% while varying min_thresh for several values of max_thresh to observe how it affects utilization and delay performance of Verus. We did not want to over-shape the traffic so as to overtake the Verus protocol with another congestion avoidance scheme, but it was worth exploring how intermediate protocols could aid in this respect.  We evaluated up to  7 data points of min_thresh (100, 200, 400,…,6400 bytes) per max_thresh value (1000, 3000, 8000). Our results show that tailoring the min_thresh and max_thresh variables to appropriate values have significant effects on the effective utilization and delay of the Verus protocol.  Low values of min_thresh (about 200 bytes/5 packets) create higher probability of dropping and have low effective utilization with high delay. The unnecessarily high probabilities of dropping packets at low min_thresh values therefore degrade performance.  At high values of min_thresh and max_thresh (> 1600 bytes/40 packets), the RED algorithm effectively acts as a lossless queue since egress traffic is not queued up to the min_thresh point and therefore neither threshold is reached.  Of course this results in increasing delay.  The plotted results can be seen in the appendix.

Challenges

Congestion Avoidance with RED Queue Management

The creators of Verus referenced Random Early Detection [7] (RED)  as a method of queue management.  They specify minimum threshold, maximum threshold, and drop probability parameters chosen, but it is not clear why these parameters are best fit. Upon inspection of how these parameters are described in the original paper in [7], we concluded that the threshold values are typically chosen to reflect the desired average queue size.  In particular, we chose to choose the minimum and maximum threshold values related to the average queue size so that parameter sensitivity was taken into account for the chose traces. The values were optimized so that utilization maintained while avoiding global synchronization issues discussed in [7].

The original implementation of Verus specifies a traffic shaper with RED parameters as, “minimum queue size 3 MBit, maximum queue size 9 MBit, and drop probability 10%”. The drop probability sets the maximal probability to drop a packet and can be seen a environment agnostic. Therefore, for all traces, it was maintained at 10%.  The minimum threshold must be set high enough so as to avoid under-utilization. As a rule-of-thumb given in [7], we used a maximum threshold at least twice the minimum.

In either case, RED was mostly a means of avoiding worst-case congestion while still allowing high utilization of the current available capacity. Dropping of packets was therefore undesirable unless under the conditions of a highly stressed link. Therefore, a loss of packets in these links was actually a rare occurrence.

Port and Process Confounding

Leveraging past work from [8], we were able to fairly quickly integrate Verus with Mahimahi and wrap our experiments in a consolidated program. However, we noticed significant discrepancies in some of our results, including highly variable throughput data for both Verus and Sprout. After several iterations of our experiment, we realized that we were not properly controlling for confounding effects of shared port numbers and zombie process that remained active after each trial. When running experiments back-to-back, we would fail to adequately terminate processes consisting of “sproutbt2”, “verus_client”, and “verus_server”. This resulted in a number of zombie processes that were bound to port/socket numbers that were then reused in successive trials. Consequently, during initial data-collection, some older processes adversely influenced the data collected on newer processes, yielding skewed results. We addressed this problem by introducing sure-fire process-killing logic that supplements the mechanism used by the existing codebase to terminate any child processes. Once we recovered from this issue, we saw more consistent and predictable data overall.

Sprout Port-Selection

Another issue that contributed to inconsistent and often “flatline” results when gathering Sprout data involved our port-selection for the Sprout client. To capture any simulated data using the send-only version of Sprout, the Mahimahi environment had to cooperate with Sprout entities that employed the same port number. When the ports did not match, no meaningful traffic would be logged and thus the simulation would fail to produce any throughput or delay values. To get around this issue, we stored the port-number provided by the network utility for Sprout’s use to a text file and then read that file when selecting the port-number for the other Sprout entity. With this method in place, both Sprout entities would utilize the same port-number under a given experiment and thus the simulation would proceed as expected.

Extensions

We made some careful choices about extending the Verus-Sprout experiment, aiming to preserve reproducibility while inducing modern, realistic in some cases sometimes necessary changes to the environment. One such change is the utilization of different, local LTE traces to assess Sprout’s and Verus’ abilities to adapt to different cellular environments. The authors of Verus cite its test case scenarios in the UAE using both a live Android clients and traces captured while driving, walking, as well as being stationary.  They also state that both 3G and LTE traces were collected from a carrier provider in the UAE and emulated over the OPNET network simulator. We employed three existing LTE traces collected by Keith Winstein and are available as part of his Mahimahi distribution. The three traces include capacity data from AT&T, Verizon, and T-Mobile LTE networks from a variable number of base stations for variable durations during weekday usage. 3G traces were not as readily available and so we did not use them.

Another change included the choice of parameters involved with Random Early Detection (RED); these parameters were also explored as part of this experiment to compensate for the difference trace simulations in Verus and Sprout. Similar to past work in [8], implementing a version of RED into Mahimahi as opposed to a lossless queue was needed to run the experiments according to the simulation specifications discussed in [7].  The traffic shaper ran according to specified parameters which were an obstacle that needed some fitting to get right. See our above discussion on the challenges faced.
Our experiments ran with constant packets sizes of 40 bytes which would variably fill up a lossless queue. The authors in [7] note that Verus performs similar on both downlink and uplink measurements using the RED scheme of queue management/traffic shaping given their values of p_drop, min_thresh, and max_thresh.

Evaluation

Given our results, we feel that Sprout is a more stable protocol that a) more consistently predicts available bandwidth and b) better manages congestion on average. However, we cannot conclude this with certainty and would need to investigate further to determine the root cause of the results we observed. It is possible that the stock parameters included with Verus had been honed or “over-trained” for specific network conditions on the networks employed by Zaki et al. Additionally, it is possible that Random Early Detection parameters also negatively influenced Verus.

In regards to RED, high differences in min_thresh and max_thresh allow for much lower delay while intermediate differences give higher utilization with the cost of high delay.  The overall trend with respect to parameterizing RED traffic tracing was that being generous with the size of the min_thresh and max_thresh prevented aggressive queue management.   This allowed both protocols, especially Verus, to perform better by being less restricted in terms of packet dropping.  In real-world scenarios, more aggressive queue management by schemes like RED may result in congestion control algorithms like Sprout and Verus to experience similar types of traffic shaping.

To best evaluate our findings, we would need to continue working and assess the effects of all parameters involved, including Verus and RED.

Platform

System

Google Compute Engine Virtual Instance (Ubuntu 16.04 LTS) with 8x vCPU, 30GB Memory

Traces

We employ the Verizon, T-Mobile and AT&T LTE driving/short traces available as part of the Mahimahi distribution. The traces available as part of the Mahimahi distribution, which we used to simulate Verus and Sprout under the cellular conditions described by the traces and to collect/produce our data.

Future Work

Verus has a rich variety of parameters that may be evaluated and tweaked to fit to particular environments. They are worth looking into in order to see exactly how much “fitting” can benefit performance in different network traces. For example, further adjusting the window estimator, which makes use of the R parameter might adjust the Verus algorithm to be more aggressive in cutting the sending window size.  Changes in both delta values, ẟ1 and 2 , can further factor into particular network traces which change variably from epoch to epoch.

Another interesting extension to reproducing research from Sprout and Verus, would be to again put Sprout and Verus on the same mobile platform such as the Samsung Galaxy S4 and Sony Experia Z1 phones used as part of the testbed for Verus.  After all, the authors in [5] had only tethered laptops during their real-world LTE experiments.  Accounting as many variables as possible is crucial to fairly compare the two algorithms, but such future work would require a similar Android application made by the developers of Verus.

Instructions to Reproduce

Please see instructions at https://github.com/jakesmo/cs244_pa3/.

References

[1] Mobile and tablet internet usage exceeds desktop for first time worldwide. Nov. 2016. Available from: http://gs.statcounter.com/press/mobile-and-tablet-internet-usage-exceeds-desktop-for-first-time-worldwide

[2] R. Schoenen, A. Otyakmaz, and Z. Xu. Resource Allocation and Scheduling in FDD Multihop Cellular Systems. In ICC Workshops 2009. IEEE International Conference on, pages 1{6, June 2009.

[3] K. Winstein and H. Balakrishnan. TCP ExMachina: Computer-generated Congestion Control. In Proceedings of the ACM SIGCOMM 2013 Conference, 2013.

[4] K. Winstein, A. Sivaraman, H. Balakrishnan, Stochastic forecasts achieve high throughput and low delay over cellular networks. Proc. USENIX NSDI, 459-472, Apr. 2013.

[5] Y. Zaki, T. Pötsch, J. Chen, L. Subramanian, and C. Görg. Adaptive congestion control for unpredictable cellular networks. ACM SIGCOMM CCR, 45(5):509–522, Oct. 2015.

[7] Floyd, S., and Van J. “Random early detection gateways for congestion avoidance.” IEEE/ACM Transactions on Networking (ToN) 1, no. 4 (1993): 397-413.

[8] Hermstein, R., Lim, A. “CS244 ’16: Verus vs. Sprout.” Stanford University, Reproducing Network Research Blog. Available from: https://reproducingnetworkresearch.wordpress.com/2016/05/30/cs244-16-verus-vs-sprout/

Appendix

red_util.png

Figure A1: Percent utilization of Verus in a T-Mobile LTE Network

red_delay.png

Figure 2A: 95th Percentile Delay of Verus in a T-Mobile LTE Network

Advertisements

One response to “CS244 ’17: Comparison of Sprout and Verus Protocols

  1. 5/5! Very easy to reproduce. Simple command, nice scripts. The results are 6 html files that match the plots in the report.

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