Stochastic Forecasts Achieve High Throughput and Low Delay over Cellular Networks

by Lakshminarayanan Subramanian

This is a highly refreshing paper among the large gamut of papers on congestion control in the research literature. The authors consider the problem of building a highly effective congestion control mechanism for cellular networks, especially to achieve the dual goals of high throughput and low delay. This paper has many interesting design surprises. One of the surprising observations in this paper is that link speeds change dramatically with time, and current transport protocols build up multi-second queues in network gateways, thereby yielding low throughputsand highly variable packet delays. This paper proposes Sprout, an end-to-end transport protocol primarily designed for interactive applications to function well over highly variable cellular network channels. The second surprising design choice in Sprout is that it does not function anything like any known TCP-style congestion control protocol;rather, it learns a stochastic model of the cellular channel based on packet arrival times, and uses the model to quickly adapt the transmission rate of a flow. Sprout specifically aims to avoid the queue buildup problem experienced by existing transport protocols. The third surprising aspect about the paper is the evaluation. Across four different cellular networks, the authors show that Sprout achieved a factor of 7-9 reduction in the end-to-end self-inflicted delay, and a factor of 2-4 enhancement in the bit rate throughput, for 3 popular interactive applications: Google Hangout, Skype and Apple FaceTime. The authors also show that Sprout matches or outperforms TCP Cubic coupled with an active queue management technique that requires changes to the cellular network. These surprises put together make this paper a very interesting read.

The key idea of Sprout is to adapt the sending rate to roughly match the current cellular network capacity while not overshooting it; by achieving this objective, Sprout can both maintain high throughput and avoid queuing delays in the network. To achieve this goal, Sprout models the cellular link using a Poisson process with an underlying rate which may change over time. Sprout models the evolution of the probability distribution on the underlying rate using Brownian motion, with which Sprout proposes a control protocol to determine the current transmission rate for an end-point. An interesting design choice made by the authors is to compute the evolution in the distribution of the underlying rate, as opposed to computing the evolution of the mean or median underlying rate. The distribution inherently captures a lot more information, and the authors can use this to compute a "safe" sending rate that has a good chance of incurring low queuing delays for the transmitted packets. They also propose Sprout-EWMA, a minor variant of Sprout that provides significant gains over Sprout as well.

There is definitely a lot more work that can be done in this space. I appreciate the authors explicitly pinpointing several limitations of their work, which leads to an array of interesting questions for future work. I will pinpoint two specific points. First, we need a much deeper understanding of the bandwidth and delay characteristics of cellular networks. Given these queuing effects, I am not sure if existing bandwidth and RTT measurement tools would be able to accurately capture these highly variable parameters. How do we distinguish between queuing based delays and non-queuing based delays? What is the impact of large or small buffers? Is there value in redesigning the queue management used in cellular networks? Second, from a Sprout design standpoint, the authors have not yet analyzed the case where Sprout cannot control delays due to competing traffic. The presence of competing traffic raises an array of questions including: (a) How do two Sprout flows compete on the same channel? (b) Does Sprout'sstochastic channel model hold in the face of competing traffic? (c) How do conventional congestion control algorithms compete with Sprout over the same cellular channel? I will end the summary with a fascinating sentence hidden in the paper: "TCP Vegas achieves lower delay than Sprout-EWMA." Are we back to the Vegas days and is this going to start a new war on congestion control?