  Modern video players employ complex algorithms to adapt the bitrate of the
video that is shown to the user. Bitrate adaptation requires a tradeoff between
reducing the probability that the video freezes (rebuffers) and enhancing the
quality of the video. A bitrate that is too high leads to frequent rebuffering,
while a bitrate that is too low leads to poor video quality. Video providers
segment videos into short segments and encode each segment at multiple
bitrates. The video player adaptively chooses the bitrate of each segment to
download, possibly choosing different bitrates for successive segments. We
formulate bitrate adaptation as a utility-maximization problem and devise an
online control algorithm called BOLA that uses Lyapunov optimization to
minimize rebuffering and maximize video quality. We prove that BOLA achieves a
time-average utility that is within an additive term O(1/V) of the optimal
value, for a control parameter V related to the video buffer size. Further,
unlike prior work, BOLA does not require prediction of available network
bandwidth. We empirically validate BOLA in a simulated network environment
using a collection of network traces. We show that BOLA achieves near-optimal
utility and in many cases significantly higher utility than current
state-of-the-art algorithms. Our work has immediate impact on real-world video
players and for the evolving DASH standard for video transmission. We also
implemented an updated version of BOLA that is now part of the standard
reference player dash.js and is used in production by several video providers
such as Akamai, BBC, CBS, and Orange.
