Tuesday, April 16, 2013

A Report on NSDI'13: Stochastic Forecasts Achieve High Throughput and Low Delay over Cellular Networks

This is a report and summery of the presentation done by Keith Winstein on April 5th 2013. Paper co-authors are: Keith Winstein, Anirudh Sivaraman, and Hari Balakrishnan, M.I.T. Computer Science and Artificial Intelligence Laboratory.


Keith started by highlighting some special characteristics of current cellular networks. He explained how cellular networks have probably became the means by which a majority of users access the Internet, but that cellular networks differ in many ways from the traditional Internet. One of these differences is that cellular networks are very variable in link speed. Keith showed measurements they took in Boston using Verizon LTE cell phones where they measured the downlink and uplink as they kept them busy and kept recording how fast packets crossed each link.  Keith presented a graph that showed how extremely variable the network is. Keith also pointed out that another way that this network is different than the “old fashioned” networks is that that they are too reliable. We talk about best-effort network delivery, but in fact it is insane-effort network delivery. Keith showed another graph showing one TCP download and it showed how there is a big delay in the round trip time.
Then Keith presented a graph showing Skype performance over the Verizon LTE network. This is to show that Skype is not using all the bandwidth available because Skype is way conservative. Also Skype is not being careful and sends higher than the available bandwidth and the result is a huge delay. To overcome this problem, Keith presented their protocol, Sprout. Sprout is a transmit protocol designed for real time interactive applications over these variable, semi-reliable networks. Sprout has a goal to provide the application with the most throughput possible, but the higher priority is to bound the risk of accumulating a large delay in gateway queues.
In order to control the risk of delay, the authors have separate parts of their algorithm. At the Sprout receiver, the authors infer the current link speed and they do that with Bayesian inference on a stochastic model. Then, part two, the receiver tries to predict what it is going to happen to the link speed in the future.  It makes a “cautious forecast” and sends this to the sender as part of its acknowledgments. In part three, the sender uses this forecast to control an evolving window that compromises between the desire for more throughput and to control the risk that a packet will spend more than 100 ms in a queue.
Keith later showed Sprout compared with other applications, such as Skype and Google-Hangout and Facetime. From the graph, Sprout performed better in term of throughput and delay. Keith said that a Stanford networking class class had reproduced these plots and the two students who chose Sprout were awarded the best project in the class. And also MIT students were challenged to beat Sprout and came up with 3,000 different algorithms with different compromises between throughput and delay. Keith indicated several limitations in their measurements in the conclusion of his talk. That Sprout was only evaluated the case of video conference and all measurements in Boston. The source code and directions to use it is are at this link: http://alfalfa.mit.edu/
Phil Levis from Stanford University asked since I see you are using LEDBAT, so if we move on that and say LEDBAT is designed to solve suddenly different problem, but do you think you should replace LETBAT with Sprout in sense of I don’t want to increase the delay for competing application using that this is background transmit protocol? Keith answered that LETBET tries to coexist with TCP on the same bottleneck queue in sort of scavenge available bandwidth. Although there are similarities between LETBET and Sprout like counter filter and one way delay estimation, in this paper we did not test it when you compete TCP on the same queue, so we don’t want to say that we do better than LETBAT in this situation.
Kurdis Hermerl from University of California Berkeley asked if the authors have thought about using geographical knowledge to help in this, this is because falls of in throughput traffic when user is switching towers, for example driving a car, so how would Sprout use that to make better prediction. Keith answered that there is previous work in NSDI on this kind of thing , and he is not sure if speed and location may affect his results or not. The second question by Kurdis Hermerl,where he pointed out that with cellular networks, there is whole circuit switch piece of technology that essentially designed to solve this question for voice traffic, how is that related to the problem Sprout is trying to solve? Is it something Sprout could just solve by doing call over that circuit switch network? Keith replied that circuit switching networks in cellular systems have admission control that gives users certain amount of bits per second and they don’t have that for large bit rate flows that need to vary in speed. The problem is that the link quality varies which you can’t just solve it with better policy. Another person from the audience asked, looking at the graph with the available bandwidth even if the mobile it stationary, have you tested Sprout with Sprout? Keith replied that they did that by testing six phones at the same cell so we did that type of testing.