PaperlayerView exact revision on arXiv

Source-linked AI summary

Probe and Adapt: Rate Adaptation for HTTP Video Streaming At Scale

Zhi Li, Xiaoqing Zhu, Josh Gahm, Rong Pan, Hao Hu, Ali C. Begen, Dave Oran

arXiv:1305.0510v2cs.NI

TL;DR

When HAS clients compete, observed TCP throughput can misrepresent fair-share bandwidth, undermining conventional video-rate adaptation. The paper proposes proactive probing through PANDA, which reduces instability while maintaining strong bandwidth utilization.

  • Problem

    Competing HAS clients and discrete video bitrates can make observed TCP throughput misrepresent a client’s fair-share bandwidth.

  • Method

    PANDA proactively probes available capacity by incrementing a continuous target average data rate, which determines video bitrate and request timing.

  • Results

    75% reduction in instability: PANDA outperforms the second-best conventional player in the stability-responsiveness tradeoff and achieves the best bandwidth utilization.

  • Takeaways & Limitations

    Probe-and-adapt directly addresses the root cause of video-rate oscillation rather than relying on inaccurate direct TCP-throughput estimates.

  • Takeaways & Limitations

    Bandwidth overestimation can persist with competing streams and introduce large errors even under slight link undersubscription.

Abstract

from arXiv · show

Today, the technology for video streaming over the Internet is converging towards a paradigm named HTTP-based adaptive streaming (HAS). HAS comes with two unique flavors. First, by riding on top of HTTP/TCP, it leverages the network-friendly TCP to achieve firewall/NATS traversal and bandwidth sharing. Second, by pre-encoding and storing the video in a number of discrete bitrate levels, it introduces video bitrate adaptivity in a scalable way that the video encoding is excluded from the closed-loop adaptation. A conventional wisdom is that the TCP throughput observed by a HAS client indicates the available network bandwidth, thus can be used as a reliable reference for the video bitrate selection. We argue that this no longer holds true when HAS becomes a substantial fraction of the Internet traffic. We show that when multiple HAS clients compete at a network bottleneck, the presence of competing clients and the discrete nature of the video bitrates would together create confusion for a client to correctly perceive its fair-share bandwidth. Through analysis and real experiments, we demonstrate that this fundamental limitation would lead to, for example, video rate oscillation that negatively impacts the video watching experiences. We therefore argue that it is necessary to implement at the application layer a "probe-and-adapt" mechanism for HAS video rate adaptation, which is akin but orthogonal to the transport-layer network rate adaptation achieved by TCP. We present PANDA -- a client-side rate adaptation algorithm for HAS -- as an embodiment of this idea. Our testbed results show that compared to conventional algorithms, PANDA is able to reduce the instability of video rate by 60%, at a given risk of buffer underrun.

I. INTRODUCTION

HAS scales video delivery through HTTP/TCP and pre-encoded discrete bitrate levels, but conventional throughput-based adaptation becomes unreliable when multiple HAS clients share bottlenecks. The paper proposes application-layer probe-and-adapt rate control, implemented by PANDA, to address instability and bandwidth-estimation errors.

  • I. INTRODUCTION: HAS downloads short, pre-encoded segments over HTTP/TCP and selects each segment’s bitrate from discrete versions.The approach supports firewall/NAT traversal and scalable bitrate adaptivity without placing video encoding inside the adaptation loop.
  • I. INTRODUCTION: Conventional adaptation equates a client’s available bandwidth share with previously observed TCP throughput and uses it to select the next video bitrate.This reactive rule assumes observed throughput reliably represents available network bandwidth.
  • I. INTRODUCTION: Experiments report significant and regular video bitrate oscillation among competing Microsoft Smooth clients, persisting across diverse network and player settings.Observed settings include different player counts, link bandwidths, start times, RTTs, queueing parameters, WFQ, and moderate web-like cross traffic.
  • I. INTRODUCTION: When multiple HAS clients compete at a bottleneck, discrete bitrates and competing streams can make TCP throughput misrepresent fair-share bandwidth.The resulting ambiguity is a fundamental measurement problem rather than merely a filtering, quantization, or scheduling issue.
  • I. INTRODUCTION: The proposed probe-and-adapt principle uses throughput only when it is accurate, otherwise probing capacity through small sending-rate increments and backing off upon congestion.PANDA implements this mechanism at the application layer, independently of TCP, using per-segment rather than per-RTT control.
  • I. INTRODUCTION: PANDA creates a continuous probing decision space from discrete video bitrates by fine-tuning intervals between consecutive segment requests.The average network data rate determines both the selected video bitrate and the fine-granularity inter-request time.
  • I. INTRODUCTION: Probe-and-adapt improves bandwidth measurement, utilization, fairness convergence, and asymmetric rate shifting, including responsive downshift after sudden drops.The stated benefits include mitigation of buffer-underrun-induced playout stalls.

A. Process of HAS Server-Client Interaction

HAS clients repeatedly download pre-encoded segments, choose the next bitrate, measure throughput, update the buffer, and schedule the next request. A four-step model separates estimating, smoothing, quantizing, and scheduling, while conventional players use reactive throughput estimation and bimodal scheduling.

  • A. Process of HAS Server-Client Interaction: A HAS stream is divided into equal-duration segments, each stored at the server in multiple ordered video bitrate levels.The available bitrate set is R := {R1, ..., RL}.
  • A. Process of HAS Server-Client Interaction: At each sequential download step, the client selects the next segment’s bitrate and target inter-request time before issuing an HTTP GET.The process permits variable durations between consecutive segment requests.
  • A. Process of HAS Server-Client Interaction: If downloading finishes before the target delay, the client waits an off-interval; otherwise, the next download starts immediately.These are identified as Scenario A and Scenario B, respectively.
  • A. Process of HAS Server-Client Interaction: Downloaded segments accumulate in a client buffer that is consumed at an average rate of one video second per real second.The buffer duration at the end of each step is represented by B[n].
  • A. Process of HAS Server-Client Interaction: The generic adaptation model consists of estimating bandwidth, smoothing the estimate, quantizing it to a discrete bitrate, and scheduling the next request.This model encompasses conventional algorithms and PANDA.
  • A. Process of HAS Server-Client Interaction: Conventional players reactively set available bandwidth to the previous segment’s on-interval TCP throughput, then smooth and quantize the result.Smoothing may use methods such as an EWMA or harmonic mean, while quantization can incorporate bitrate and buffer history.
  • A. Process of HAS Server-Client Interaction: Conventional scheduling is bimodal: requests are immediate while the buffer grows, then separated by one segment duration in steady state.The target delay is zero below a maximum buffer and τ at or above that threshold.

IV. ANALYSIS OF THE CONVENTIONAL APPROACH

The analysis examines how competing HAS clients share a bottleneck under perfect subscription, oversubscription, and undersubscription. It shows that TCP throughput accurately reflects fair share only in fully overlapped sharing, while other modes produce bandwidth overestimation.

  • Perfect Subscription: Perfect subscription permits unlimited bandwidth-sharing modes determined by clients’ download start times.
  • Oversubscription: Oversubscription causes unfinished downloads to overlap progressively until clients enter fully overlapped sharing.
  • Undersubscription: Undersubscription fills clients’ off-intervals before converging to a sharing mode determined by download start times.
  • TCP throughput represents fair share only in fully overlapped mode; otherwise it overestimates fair share by one to n times for n competing clients.
  • 100 thin clients measured about 3x the approximately 1-Mbps fair share below 100% subscription, but estimation became accurate above 100%.This transition at 100% subscription is termed the bandwidth cliff effect.

B. Video Bitrate Oscillation

The section explains bitrate oscillation as a feedback cycle caused by off-intervals, bandwidth overestimation, and discrete video bitrate levels. It then motivates probe-and-adapt rate control and its broader design objectives.

  • Video Bitrate Oscillation: When the buffer reaches Bmax, off-intervals make the link undersubscribed and cause bandwidth overestimation, triggering a bitrate upshift.
  • Video Bitrate Oscillation: The upshift can exceed available bandwidth, reducing the buffer until off-intervals disappear and measured throughput converges toward fair share.
  • Video Bitrate Oscillation: Quantized bitrate levels can then fall below fair share, allowing the buffer to grow and restarting the oscillation cycle.
  • Fundamental Limitation: Reactive estimators ignore off-interval network conditions, leaving clients unable to distinguish alone-link capacity from shared-link capacity with identical observed throughput.
  • Fundamental Limitation: The ambiguity persists despite improved filtering, quantization, or scheduling and can create large errors even with slight link undersubscription.
  • Probe-and-Adapt: Probe-and-adapt instead probes capacity with small sending-rate increments when client knowledge is impaired.

B. PANDA Algorithm

PANDA replaces reactive bandwidth estimation with proactive probing to estimate a target average rate, choose a discrete video bitrate, and schedule the next request. Its hybrid control design separates rate and request timing loops to reduce quantization-driven shifts.

  • Core Algorithm: PANDA probes for a target average data rate, then uses it to select the fetched video bitrate and next segment request interval.
  • Core Algorithm: It replaces conventional estimation and scheduling steps while retaining the surrounding adaptation structure.
  • Estimating: When undersubscription makes direct TCP throughput unreliable, PANDA increases its target rate by κ·w as a capacity probe.
  • Estimating: PANDA suppresses throughput evidence when it exceeds the target and backs off proportionally when throughput falls below the target, indicating congestion.
  • Estimating: The probing mechanism has an AIMD interpretation: additive increase uses κ·w, while decrease responds to measured-throughput reductions.
  • Control Design: Separate closed loops determine target rate and request timing, while the combined estimating, smoothing, quantizing, and scheduling path remains open loop to reduce bitrate shifts.

C. Functional Verification

Experiments verify PANDA’s behavior under changing bandwidth, startup, multiple-client competition, and stability conditions. The traces show target-rate adaptation and stability behavior under the tested settings.

  • Varying Bandwidth: Under bandwidth changes from 5 to 2 Mbps and back to 5 Mbps, PANDA ramps its target rate and fetched bitrate in response.
  • Startup: Startup logic uses the conventional algorithm until the buffer reaches Bmin, then switches to PANDA to improve ramp-up speed.
  • Multiple Clients: In the 36-client, 100-Mbps experiment, PANDA’s aggregate and per-client fetched bitrates are evaluated against the oscillation scenario.
  • Multiple Clients: For these clients, fair-share bandwidth is about 2.8 Mbps, while TCP throughput substantially overestimates it and varies considerably.
  • Measurement Trade-off: Strong filtering could smooth noisy measurements but would reduce responsiveness to bandwidth drops and increase buffer-underrun risk.
  • Stability: With τ = 2, stability requires κ < 1; when Δ = 0, the buffer does not converge to the 30-second reference level.

A. Evaluation Metrics

The paper evaluates HAS rate adaptation using buffer undershoot, instability, inefficiency, and unfairness, alongside experimental configurations and benchmark players.

  • Evaluation criteria: Four criteria guide evaluation: avoiding buffer underruns, quality smoothness, average quality, and fairness.Buffer undershoot measures the first criterion; instability, inefficiency, and unfairness measure the remaining criteria.
  • Buffer undershoot: Buffer undershoot is the 90th-percentile shortfall below a 30-second reference buffer after a bandwidth drop.Lower undershoot indicates a lower likelihood of buffer underrun.
  • Rate metrics: Instability uses a weighted history of fetched bitrates, with a 20-second window assigning greater weight to recent samples.The weight function is w(d) = k − d, with k selected as 20 seconds.
  • Rate metrics: Inefficiency compares aggregate fetched bitrate with available bandwidth, while unfairness is defined from Jain’s fairness index.The inefficiency definition is revised to avoid penalizing aggregate rates that exceed available bandwidth.

C. Performance Tradeoffs

The tradeoff experiments assess stability, efficiency, fairness, and responsiveness before and after a bandwidth drop, showing that PANDA combines stability with responsiveness.

  • Tradeoffs: PANDA achieves the best stability-responsiveness tradeoff, reducing instability by more than 75% versus the second-best conventional player at equal buffer undershoot.Its tradeoff remains mostly flat across parameter variations except at extreme values.
  • Tradeoffs: PANDA has the lowest inefficiency as instability varies, while conventional adaptation outperforms FESTIVE and Smooth has the highest inefficiency.The probing mechanism supports efficient bandwidth utilization, although greater bitrate fluctuation moderately increases inefficiency.
  • Tradeoffs: FESTIVE achieves the best fairness, while PANDA and conventional players perform similarly and both outperform Smooth.The fairness ranking reflects the effects of randomized scheduling and the players’ adaptation behavior.
  • Increasing number of players: With fixed 10-Mbps bandwidth, conventional and Smooth instability increase quickly as player count grows, whereas PANDA maintains stability as clients increase.PANDA’s behavior depends on selected bitrate levels at two players but avoids bandwidth-overestimation symptoms through probing.
  • Increasing number of players: PANDA consistently has the best efficiency as player count grows, while FESTIVE and conventional adaptation outperform Smooth.The comparison covers both fixed-bandwidth and fixed 1-Mbps/player scenarios.
  • Increasing number of players: Fairness depends strongly on bitrate levels at low client counts; in the varying-bandwidth case, FESTIVE, PANDA, conventional, and Smooth rank in that order.Two PANDA clients receiving 5.3 Mbps and 3.7 Mbps illustrate how discrete levels can produce high unfairness.

E. Competing Mixed Players

The paper compares PANDA with mixed HAS players and frames its contributions around the bandwidth-cliff diagnosis, probe-and-adapt design, and systematic evaluation.

  • Mixed-player competition: In mixed-player experiments, Smooth’s bandwidth capture depends strongly on its server’s TCP stack: over 3 Mbps with IIS versus about 1 Mbps with Apache.PANDA, conventional, and FESTIVE use the same TCP implementation in this comparison.
  • Performance summary: PANDA offers the best stability-responsiveness tradeoff and bandwidth utilization in the reported performance summary.The tradeoff is reported as a 75% reduction in instability versus the second-best conventional player.
  • Performance summary: FESTIVE is tuned for stability, efficiency, and fairness but underperforms in responsiveness to bandwidth drops.Its design prioritizes steady behavior while sacrificing response to sudden bandwidth changes.
  • Performance summary: The conventional player provides good efficiency but lacks stability, bandwidth-drop responsiveness, and fairness.It differs from PANDA in estimating and scheduling while sharing smoothing and quantization functions.
  • Performance summary: Smooth underperforms in efficiency, stability, and fairness, and its bandwidth capture reflects the aggressiveness of its underlying TCP stack.This dependence explains why server configuration materially changes its observed fetched bitrate.
  • Contributions: The paper identifies the bandwidth cliff effect as the root cause of bitrate oscillation and a limitation of reactive measurement-based adaptation.It proposes probe-and-adapt and PANDA, plus a generic four-step model for fair comparison with conventional adaptation.
  • Contributions: Probe-and-adapt and PANDA improve HAS stability without reducing responsiveness in the reported evaluations.PANDA probes at the application layer on a per-segment rather than per-RTT timescale.

APPENDIX A BANDWIDTH CLIFF EFFECT: THEORETICAL ANALYSIS

The analysis models HAS clients as sequential segment downloaders with fixed requested bitrates and shows that slight link undersubscription can produce gaps, periodic traffic, and TCP-throughput overestimation of fair share.

  • Model: Each client downloads fixed-size segments sequentially, with segment size rk · τ and requesting times determined by prior download duration.The model distinguishes selected bitrate rk from instantaneous downloading rate Rk(t).
  • Model: Under idealized TCP behavior, active flows share capacity C equally, while no active flows create a gap with zero aggregate traffic.The model abstracts away TCP slow-start restart and heterogeneous RTT effects.
  • Link undersubscription: A gap forces each client to request exactly one segment during the following interval of duration τ.The result follows from the request-time recurrence and the absence of unfinished residue data after the gap.
  • Link undersubscription: When the sum of requested bitrates is below C, each client’s downloading-rate pattern eventually converges to a periodic pattern with period τ, regardless of initial state.The convergence argument applies repeatedly across consecutive τ-length intervals after a gap emerges.
  • Bandwidth estimation: Even slight undersubscription can make some clients’ measured TCP throughput exceed their fair-share bandwidth when requesting times are misaligned.No overestimation occurs only when all clients remain active together and their segment data sizes are equal.

C. Link Oversubscription

For an oversubscribed link, the analysis identifies when TCP throughput converges to fair-share bandwidth: all requested bitrates must exceed the per-client share.

  • Link Oversubscription: The oversubscribed case assumes the sum of clients’ requested bitrates exceeds link capacity C.The analysis seeks conditions under which observed TCP throughput correctly predicts fair-share bandwidth.
  • Link Oversubscription: When every client’s requested bitrate exceeds C/K, TCP throughput eventually equals C/K for every client.The proof establishes that all clients remain active after some segment index, yielding equal sharing under the idealized TCP model.
  • Link Oversubscription: If every requested bitrate satisfies rk ≥ C/K and at least one satisfies rk′ > C/K, all clients’ TCP throughput converges to fair-share bandwidth.This is presented as a sufficient and necessary condition for correct fair-share estimation.

APPENDIX B ANALYSIS OF PANDA

The PANDA analysis studies equilibrium and stability in the single-client case, where the system has an equilibrium point.

  • APPENDIX B ANALYSIS OF PANDA: The equilibrium and stability analysis simplifies PANDA to a single-client system.The stated reason is that this case has an equilibrium point.
  • APPENDIX B ANALYSIS OF PANDA: The analysis focuses on PANDA’s equilibrium behavior rather than the multi-client dynamics developed elsewhere.This scope statement is limited to the single-client case described in the passage.
  • APPENDIX B ANALYSIS OF PANDA: The single-client simplification defines the scope of the presented equilibrium analysis.No broader equilibrium claim is stated in the supplied passage.

A. Analysis of ˆx

Near equilibrium, the bandwidth estimate follows a difference equation whose convergence requires a stability condition, while the quantization margin keeps the selected rate below capacity.

  • A. Analysis of ˆx: At equilibrium, the estimate satisfies ˆxo = C + w, which is greater than the measured throughput ˜xo = C.The equilibrium relation follows by setting the update equation to zero.
  • A. Analysis of ˆx: The quantization margin must keep the equilibrium requested rate below C so the system remains on the multiplicative-decrease side.Under the stated simplifications, ro = ˆxo − ∆ < C.
  • A. Analysis of ˆx: With intervals between downloads matching playout duration, the estimated bandwidth follows a simple difference equation.The passage introduces this form for behavior close to equilibrium.
  • A. Analysis of ˆx: The recurrence constants are a = 1 − κ · τ and b = κ · (C + w) · τ.These constants determine the sequence’s convergence behavior.
  • A. Analysis of ˆx: 0 < κ < 2/τ is required for convergence of the estimated-bandwidth sequence.This follows from the criterion |a| < 1.
Loading 1305.0510v2…