Papers
A Buffer-Based Approach to Rate Adaptation: Evidence from a Large Video Streaming Service
Te-Yuan Huang, Ramesh Johari, Nick McKeown, Matthew Trunnell, Mark Watson · ACM SIGCOMM 2014, 2014
The problem: choosing the video rate without overrunning the buffer
In the streaming services described in the paper, each video is encoded at several rates (typically from 235 kb/s, standard definition, up to 5 Mb/s, high definition) and stored on servers as separate files. The client (TV, console, browser, etc.) decides which rate to download for each segment, by observing the network and estimating the available capacity; this process is called adaptive bitrate selection, or ABR. An ABR algorithm tries to meet two goals at the same time. The first is to maximize quality, choosing the highest rate the network can sustain. The second is to minimize rebuffers, the playback stalls that occur when the playback buffer runs empty. Each goal on its own is trivial: always streaming at the maximum rate gives the best quality but risks many rebuffers; always streaming at the minimum rate nearly eliminates rebuffers but delivers low quality. The difficulty lies in getting good performance on both metrics together. The client requests video chunks of fixed duration (four seconds in the service studied), and the higher the rate, the larger the chunk in bytes. The buffer is measured in seconds of video and drains at one second per second; if the algorithm requests a rate above capacity, the buffer shrinks until playback freezes.
Why estimating bandwidth is fragile
The current approach, according to the paper, is to estimate future capacity from what was observed in the past and choose the rate based on that. In a stable network this works, but in environments with highly variable throughput an accurate estimate becomes difficult. The authors show a real trace from a Netflix player in which the throughput measured per chunk oscillates between about 17 Mb/s and 500 kb/s. The variation has several possible causes, such as WiFi interference, congestion in the network, the client, or the server. The authors define variation as the ratio between the 75th and 25th percentiles of throughput (5.6 in this trace) and report that approximately 10% of sessions have at least this much variation. Many algorithms try to compensate by applying an adjustment factor, a function of the buffer level, to the estimate: more aggressive with a full buffer, more conservative with a nearly empty buffer. The paper's analysis shows the limit of this: to guarantee there is no rebuffer, the factor must be smaller than the worst ratio between actual and estimated capacity. In the cited trace this ratio reaches 0.03, and the factor would have to be 0.03 or less, resulting in a rate of only 3% of what a correct estimate would allow. A Netflix example shows the opposite error: the client overestimated the bandwidth, kept requesting a high rate, and stalled for 200 seconds, in a case where the capacity never fell below the minimum rate.
The core idea: the rate as a function of the buffer level, with a reservoir
The proposed inversion is to treat the buffer, rather than the bandwidth estimate, as the starting point. The argument is that the buffer is exactly the state variable the algorithm needs to control. An algorithm is called buffer-based when it chooses the rate as a function of the current occupancy level, through a rate map that goes from the minimum rate (empty buffer) to the maximum rate (full buffer). Under idealized assumptions (infinitesimal chunks, any rate available, constant-rate encoding, infinite videos), the authors summarize a proof: any continuous map, strictly increasing in the middle range and pinned at both ends (minimum rate with zero buffer, maximum rate with full buffer), avoids unnecessary rebuffers and, when the capacity always stays between the minimum and maximum rates, makes the average rate track the average capacity. The reason for the first result is that, as long as the capacity does not drop below the minimum rate, the buffer starts growing before it empties. In the real world, with finite chunks, the map is shifted to the right, creating a reservoir: while the buffer is inside it, the minimum rate is always requested. Next comes the cushion area, where the rate rises, and an upper region where the maximum rate is already requested. In the first algorithm, BBA-0, the reservoir was fixed at 90 seconds, the cushion was 126 seconds, and the total buffer was 240 seconds.
VBR and the startup phase: where the estimate still helps
BBA-0 worked, but it left two problems. First, real videos are encoded at variable bit rate (VBR): the nominal rate is an average, and chunk sizes vary considerably within the same rate. For this, BBA-1 computes the reservoir dynamically from the sizes of future chunks (looking 480 seconds ahead, twice the buffer, and bounding the reservoir between 8 and 140 seconds) and replaces the rate map with a chunk map, which limits the maximum size of the next chunk according to the buffer. Second, at the start of the session the buffer is empty and carries almost no information about the network; BBA-1, with only the reservoir, requests the minimum rate and is too conservative. BBA-2 adds a simple estimate in this phase: it looks only at the throughput of the last chunk and steps up the rate if the chunk downloaded much faster than its playback time. The threshold starts at eight times faster and decreases linearly as the cushion fills. As soon as the chunk map suggests a higher rate, or the buffer starts to fall, BBA-2 goes back to being purely buffer-based. The authors compare this to TCP slow start: at the beginning the state says nothing about the network, but the rate increase must be controlled so as not to cause rebuffers.
Production results and the lesson of the paper
The experiments ran in Netflix's browser player, in A/B tests with more than half a million real users each, on three continents, over weekends between May and September 2013. Each group was compared to Netflix's default algorithm at the time (Control), which chose the rate mainly by capacity estimation, and to a group that always requested the minimum rate, used as an empirical lower bound on rebuffers. From the difference between Control and this bound, the authors conclude that 20 to 30% of rebuffers may come from poor rate choice. BBA-0 had a rebuffer rate 10 to 30% lower than Control, but delivered a video rate about 100 kb/s lower at peak hours and 175 kb/s lower off-peak. BBA-1 improved the rebuffer rate by 20 to 28% at peak; BBA-2 kept a 10 to 20% improvement at peak, with a video rate practically indistinguishable from Control and, excluding the first two minutes, generally higher. The BBA-Others variant, which smooths rate switches, reduced rebuffers by 20 to 30% compared to Control. The conclusion: capacity estimation is unnecessary in steady state, but useful at startup; and the burden of proof falls on whoever designs the algorithm and wants to add complexity.
See the ideas at work
Practice the designs that use this paper in the System Design school.