PaperlayerView exact revision on arXiv

Source-linked AI summary

BOLA: Near-Optimal Bitrate Adaptation for Online Videos

Kevin Spiteri, Rahul Urgaonkar, Ramesh K. Sitaraman

arXiv:1601.06748v3cs.NI

TL;DR

Video bitrate adaptation must balance playback quality against rebuffering under changing network conditions. The paper formulates this tradeoff as utility maximization and derives BOLA, a Lyapunov-based online algorithm using buffer information rather than bandwidth prediction. BOLA achieves near-optimal utility theoretically and empirically, and its updated implementation is deployed through dash.js.

  • Problem

    Bitrate adaptation must balance higher video quality against rebuffering when network bandwidth varies during segmented video playback.

  • Method

    BOLA uses Lyapunov optimization to maximize a utility combining average bitrate and rebuffering, using buffer occupancy without estimating available bandwidth.

  • Results

    BOLA's utility is within O(1/V) of optimal in the large-video regime, and experiments find near-optimal performance and utility at least as good as the best state-of-the-art algorithm in all test cases.

  • Takeaways & Limitations

    BOLA provides a theoretically justified buffer-based approach and has been implemented in dash.js for production use by Akamai, BBC, CBS, and Orange.

Abstract

from arXiv · show

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.

I. INTRODUCTION

ABR streaming must balance higher video quality against avoiding rebuffering across diverse devices and network conditions. BOLA formulates this tradeoff as utility maximization and provides a buffer-based online algorithm with theoretical and empirical support.

  • I. INTRODUCTION: ABR streaming adapts segment bitrates to device and network conditions, using buffering and bitrate switches to reduce rebuffering while preserving quality.Videos are segmented and encoded at multiple bitrates so the player can select successive segments according to available bandwidth.
  • I. INTRODUCTION: The paper defines utility to capture both average playback bitrate and rebuffer duration, allowing quality preferences to vary by content, provider, or device.Higher average bitrate increases utility, whereas rebuffering decreases it.
  • I. INTRODUCTION: BOLA uses Lyapunov optimization to provide a provably near-optimal online bitrate adaptation algorithm without requiring bandwidth prediction.The algorithm offers an explicit control parameter for the relative importance of video quality and rebuffering.
  • I. INTRODUCTION: The framework is extended to reduce frequent bitrate switches, and BOLA has been implemented in dash.js for production use by several major providers and delivery networks.The listed production users include Akamai, BBC, CBS, and Orange.
  • I. INTRODUCTION: BOLA is evaluated against an offline dynamic-programming optimum and four state-of-the-art algorithms across DASH and 3G network traces.The offline benchmark has perfect knowledge of future bandwidth variations.

III. PROBLEM FORMULATION

The formulation measures playback quality and smoothness over time-slotted downloads, while accounting for buffer evolution, rebuffering, and finite video playback.

  • Time-average playback quality depends on the bitrates of viewed segments, while playback smoothness is the expected fraction of time spent not rebuffering.The playback duration for N segments is Np seconds, and smoothness is bounded by 1.
  • Each slot records whether a segment at bitrate index m is downloaded, with at most one bitrate choice per slot.The indicator is 1 for the selected bitrate and 0 otherwise; no download is also allowed.
  • The buffer queue receives one segment when a download occurs and loses Tk/p segments during slot k, representing playback departures.The buffer level is measured in segments at the start of each slot.
  • The formulation excludes frequent bitrate switching from the primary objective, although the paper addresses it empirically later.The main metrics are playback quality and time spent not rebuffering.
  • Segments become playable only after complete download, so playback can finish later than the final segment download.This distinction is reflected by Tend exceeding the last segment’s download completion time.

A. Design Objective

The design objective maximizes a weighted combination of playback utility and smoothness while replacing difficult finite-horizon stochastic optimization with a tractable large-video formulation.

  • Design Objective: The objective maximizes υN + γsN subject to a finite buffer constraint, with γ controlling the relative priority of playback utility and smoothness.Playback utility captures quality, while smoothness captures rebuffering-related performance.
  • Design Objective: Traditional dynamic programming requires the distribution of network conditions and can have a very large state space involving time, network state, and buffer size.Discretizing the network process is also needed for a tractable DP solution.
  • Problem Relaxation: The paper considers the large-video regime N →∞ and replaces the finite buffer constraint with rate stability to simplify the optimization.These assumptions enable an algorithm with theoretical guarantees while still satisfying the finite buffer constraint.
  • Problem Relaxation: Rate stability requires average arrivals not to exceed average playback, but it is a relaxation because rate-stable policies need not have finite buffers.Under the relaxation, the optimal utility cannot be smaller than under the finite-buffer constraint.
  • Problem Relaxation: Lyapunov optimization over renewal frames converts the time-average problem into per-slot drift-plus-penalty ratio minimizations.Variable-length slots serve as renewal frames, and an i.i.d. stationary policy characterizes the large-video optimum.
  • Problem Relaxation: BOLA achieves utility within O(1/Qmax) of υ∗ + γs∗ without requiring knowledge of the network-condition distribution.The guarantee applies to the finite-buffer system developed from the relaxed design.

IV. BOLA: AN ONLINE CONTROL ALGORITHM

BOLA makes buffer-based per-slot decisions by minimizing a Lyapunov drift-plus-penalty ratio, avoiding bandwidth prediction. Its guarantees establish a utility–buffer tradeoff while preserving the finite buffer limit.

  • Algorithm Design: Lyapunov optimization converts the time-average objective into per-slot minimization of expected drift-plus-penalty divided by expected slot length.This construction does not require knowledge of the network-condition distribution.
  • Algorithm Design: BOLA keeps the relative weighting of video quality and playback smoothness tunable through the control parameter V and the penalty terms.The parameter V trades buffer size against performance objectives.
  • Algorithm Design: BOLA chooses no download when the buffer exceeds every threshold V(υm + γp); otherwise it downloads the bitrate maximizing a positive ratio.The decision is made from the current buffer level and bitrate-dependent quantities.
  • Algorithm Design: BOLA depends only on buffer occupancy, unlike bandwidth-prediction strategies that require explicit prediction of available bandwidth.This buffer-based control is the source of the BOLA name and its online operation.
  • Guarantees: Theorem 1 guarantees that BOLA respects the finite buffer constraint and bounds queue backlog by V(υM + γp) + 1.The theorem applies when BOLA is implemented with an admissible control parameter V.
  • Guarantees: The utility gap is O(1/V), while backlog grows O(V), yielding the standard Lyapunov utility–backlog tradeoff.Larger V can reduce the utility gap but is constrained by buffer size.

A. Understanding BOLA With an Example

BOLA chooses segment bitrates from buffer occupancy using a utility-based decision rule. In the example, bitrate choices respond to changing network conditions through a feedback loop between download time and buffer level.

  • A. Understanding BOLA With an Example: BOLA requires only non-decreasing utilities and uses a logarithmic utility function in the example.The example sets υ_m = ln(S_m/S_1), with γ = 5.0/p and V = 0.93.
  • A. Understanding BOLA With an Example: BOLA’s bitrate choice is determined directly by the current buffer level through threshold-based decisions.The buffer level is measured in Qp seconds in the figures.
  • A. Understanding BOLA With an Example: For each slot, BOLA selects the bitrate maximizing (V υ_m + V γp − Q)/S_m across available bitrate indices.The intersections of the expression’s lines define buffer-level decision thresholds.
  • A. Understanding BOLA With an Example: A changing bitrate affects download time, which changes the buffer level used for the next decision.The example describes this as a feedback loop between bitrate, download time, and buffer occupancy.

B. Choosing Utility and Parameters γ and V

BOLA permits flexible utility functions while using γ and V to control rebuffering sensitivity and buffer behavior. Its evaluation combines simulated videos, DASH network profiles, mobile traces, and an offline dynamic-programming benchmark.

  • B. Choosing Utility and Parameters γ and V: Video providers may use any utility function satisfying the paper’s stated condition, including functions that account for device characteristics.The experiments use a logarithmic utility, while the framework allows broader choices.
  • B. Choosing Utility and Parameters γ and V: Increasing γ shifts bitrate thresholds higher, causing BOLA to download more low-bitrate segments to maintain a larger buffer.γ controls how strongly the algorithm prioritizes avoiding rebuffering.
  • B. Choosing Utility and Parameters γ and V: Increasing V expands the decision graphs horizontally, and for maximum buffer Q_max the paper sets V = (Q_max − 1)/(υ_M + γp).This setting avoids downloading unless there is room for one full segment.
  • B. Choosing Utility and Parameters γ and V: The simulation uses Big Buck Bunny encoded at 10 bitrates in 3-second segments, with playback extended by repeating the 10-minute movie.Segments can have variable bitrate despite each quality index having a specified average bitrate.
  • B. Choosing Utility and Parameters γ and V: Evaluation uses twelve DASH network profiles and 86 publicly available 3G traces, excluding one trace below the lowest video bitrate.The mobile-trace experiments use 50 ms latency, corresponding to a 100 ms RTT.
  • B. Choosing Utility and Parameters γ and V: An offline dynamic-programming algorithm computes the maximum achievable utility for a trace using states indexed by segment, time, and buffer level.The buffer level is capped at b_max, and rebuffering time is represented in the state transition.

C. Evaluating BOLA-BASIC

BOLA-BASIC reaches about 80% of the offline optimum but loses utility during startup while filling larger buffers. Finite-video adaptations improve utility by managing startup, wind-down, and download abandonment.

  • C. Evaluating BOLA-BASIC: BOLA-BASIC obtains about 80% of the offline optimal bound across 10-, 30-, and 120-minute videos.The offline optimum is nearly unchanged across video lengths.
  • C. Evaluating BOLA-BASIC: Increasing buffer size slightly decreases BOLA-BASIC utility because startup requires more lower-bitrate segments before higher-bitrate thresholds are reached.The startup effect motivates improvements to BOLA-BASIC.
  • D. Adapting BOLA to Finite-Sized Videos: BOLA-FINITE adapts BOLA-BASIC for smaller videos because the basic version assumes videos are infinite.Its adaptations address startup and wind-down behavior.
  • D. Adapting BOLA to Finite-Sized Videos: BOLA-FINITE uses a dynamic buffer target so it does not fill the buffer too soon or maintain a full buffer too long.The algorithm still requires a minimum buffer size of 3p for effective operation.
  • D. Adapting BOLA to Finite-Sized Videos: Download abandonment lets BOLA-FINITE stop a high-bitrate download when progress indicates that the buffer may deplete.In the illustrated bandwidth drop, it avoids continuing a 3 Mbps download and instead uses 1.4 and 0.7 Mbps bitrates.
  • D. Adapting BOLA to Finite-Sized Videos: BOLA-FINITE’s time-average utility is much closer to the offline optimal bound than BOLA-BASIC’s.The comparison covers 10-, 30-, and 120-minute playback times.
  • D. Adapting BOLA to Finite-Sized Videos: The finite-video adjustments avoid a significant utility decrease from filling larger buffers with low-bitrate segments early in playback.This benefit becomes more evident as the buffer grows larger.

E. Avoiding Bitrate Oscillations

BOLA addresses bitrate oscillations caused by dense thresholds and bitrate quantization through two variants. BOLA-O prioritizes stability, while BOLA-U preserves utility and performs strongly across varied network profiles.

  • E. Avoiding Bitrate Oscillations: Bitrate switching can arise from bandwidth variation, dense buffer thresholds, or quantization between widely spaced encoded bitrates.Dense thresholds can cause overshoot even when bandwidth is stable, while quantization can create repeated switching between adjacent levels.
  • E. Avoiding Bitrate Oscillations: BOLA-O caps bitrate increases using measured bandwidth from the previous segment to mitigate oscillations.It avoids lowering bitrate below the previous download and lets the buffer reach the appropriate threshold when needed.
  • E. Avoiding Bitrate Oscillations: BOLA-U’s time-average utility is about 1.75 times that of the other algorithms in roughly half the evaluated cases.The comparison covers BOLA-O, ELASTIC, PANDA, MPC, and Pensieve across DASH profiles and mobile traces.
  • E. Avoiding Bitrate Oscillations: BOLA-U avoids sacrificing utility by allowing the bitrate to be one level higher than the sustainable bandwidth.This handles severe threshold-related oscillations but not all quantization-driven oscillations.
  • E. Avoiding Bitrate Oscillations: BOLA-U’s added stability improves performance with small buffer sizes.The paper identifies this benefit when comparing the variants in the finite-video evaluation.
  • E. Avoiding Bitrate Oscillations: BOLA-O has lower average adjacent-segment bitrate changes than BOLA-U, while BOLA-U provides higher utility.BOLA-O switches mainly in response to network bandwidth variations, whereas BOLA-U has higher changes due to quantization.

F. Comparison With State-of-the-Art Algorithms

Across diverse network profiles and mobile traces, BOLA generally achieves higher and more consistent utility than the compared state-of-the-art algorithms. Its tradeoffs include increased bitrate oscillations for BOLA-U and stronger performance when segment abandonment reduces rebuffering.

  • Evaluation conditions: The comparison uses a 25-second buffer for fairness, while the paper cautions that later evaluations should use stable BOLA implementations and equal buffer sizes.The caution concerns comparisons involving dash.js versions 2.0.0–2.5.0 and the default 12-second buffer in dash.js.
  • Overall comparison: BOLA-U consistently outperforms PANDA, while its advantage over ELASTIC is largest under profiles with greater bandwidth variation.BOLA-U and ELASTIC perform similarly for profiles 1–6, but BOLA-U performs significantly better for the other profiles.
  • Comparing BOLA-U with ELASTIC: For mobile traces, BOLA-U has a 3.5% rebuffer-to-play ratio versus ELASTIC’s 12.0%, despite ELASTIC’s marginally higher bitrate.For profiles 7–12, ELASTIC’s rebuffer-to-play ratio exceeds 20%, while BOLA-U has no rebuffering.
  • Comparing BOLA-U with PANDA: BOLA-U provides higher bitrate than PANDA on mobile traces, with rebuffer-to-play ratios of 3.5% and 2.6%, respectively.PANDA is more conservative and sometimes does not switch to a higher sustainable bitrate.
  • Comparing BOLA-U with MPC: BOLA-U and MPC have similar average bitrates, but MPC rebuffers on most profiles while BOLA-U does not.The text notes that MPC parameter tuning and bandwidth-estimation lag may contribute to its rebuffering.
  • Comparing BOLA-U with Pensieve: Pensieve lies between BOLA-O and BOLA-U in utility on profiles 1–12 but performs much worse on mobile traces because of excessive rebuffering.In the 3G evaluation, Pensieve’s average rebuffer-to-play ratio is 38%, producing negative utility.
  • Secondary metrics: BOLA-U sacrifices bitrate-oscillation performance while attempting to maximize utility, whereas BOLA-O is the relevant comparison for lower oscillation behavior.The experiments across videos with different content, segment durations, and bitrate sets show similar overall conclusions.

A. The DASH Reference Player

BOLA is connected to practical DASH deployment through parameter choices that map provider-facing buffer targets to its control parameters. The implementation was integrated into dash.js and used in production by several major providers and delivery networks.

  • Production deployment: BOLA was implemented in dash.js, the open-source DASH reference player, and is used in production by Akamai, BBC, CBS, and Orange.Deployment introduced challenges including operation with smaller buffer capacities and correct handling of production conditions.
  • Parameter selection: BOLA parameters γ and V can be derived from intuitive provider requirements involving maximum and low buffer levels.These requirements specify Qmax, the highest bitrate at Qmax, and bitrate switching around Qlow.
  • Parameter selection: The parameter derivation makes BOLA’s control behavior expressible in terms of provider-preferred buffer thresholds.The construction enforces highest-bitrate selection near Qmax and lower-to-higher bitrate switching around Qlow.
  • Parameter selection: Choosing a larger Qlow increases γ and gives rebuffering more weight, while choosing a larger Qmax increases V.The paper links these parameter changes to the earlier intuition for γ and V.
  • Relation to prior work: BOLA differs from several prior approaches because its buffer-based control does not depend on predicting network bandwidth.Related algorithms such as FESTIVE and PANDA estimate bandwidth, while BBA uses buffer occupancy but lacks BOLA’s theoretical guarantees.

APPENDIX PROOF OF THEOREM 1

The appendix proves Theorem 1 using bounded-buffer induction and Lyapunov optimization over variable-size frames. The proof handles queue evolution through cases and derives the required drift bound for BOLA.

  • Buffer bound: The buffer bound Q(tk) ≤ V(υM + γp) + 1 is established by induction from the initial condition Q(t1)=0.The induction considers how the buffer can change between successive slots.
  • Buffer bound: When the buffer exceeds V(υM + γp), BOLA chooses no download, preventing the buffer from increasing beyond the bound.This is the second case of the induction argument.
  • Buffer interpretation: The proof identifies Q(tk) as the total number of segments in the buffer and relates it to the maximum buffer level Qmax.The appendix uses the queue representation to connect the segment count with buffer control.
  • Lyapunov analysis: For the utility guarantee, the proof defines a Lyapunov function and conditional per-slot drift, then bounds the drift using two queue cases.The cases are Q(tk) ≤ Tk/p and Q(tk) > Tk/p.
  • Proof assumptions: The appendix assumes the relevant quantity is finite and uses the queueing dynamics and Lyapunov drift framework to establish the theorem’s bounds.The finiteness condition is stated as an assumption in the proof.
  • Policy comparison: BOLA greedily maximizes the frame-level decision objective, enabling comparison with the stationary policy used in the proof.The argument labels decisions under BOLA and the stationary policy as BOLA and STAT, respectively.

E{T BOLA

The final proof step aggregates the drift inequality over frames, substitutes stationary-policy averages, and takes a long-run limit. This yields the stated bound in Theorem 1.

  • Online optimization: The ratio used in the proof can be minimized without knowledge of ωavg, preserving the online nature of the decision rule.The denominator is expressed using the relevant segment and slot quantities before applying the preceding bound.
  • Stationary-policy substitution: The proof substitutes the time-average values associated with the stationary policy into the drift-based inequality.The stationary policy’s expected arrival rate is denoted rSTAT and is rate stable.
  • Long-run bound: Taking conditional expectations and summing over k from 1 to KN produces the accumulated inequality used for the theorem.This step precedes division by V and passage to the long-run limit.
  • Long-run bound: Dividing by V and taking the limit as N →∞ yields the bound in (12).This is the concluding step of the appendix derivation.
Loading 1601.06748v3…