Abstract
Cloud video streaming traditionally relies on replicating files across multiple servers. However, modern data centers are increasingly adopting erasure coding to achieve massive storage savings. While efficient for storage, erasure coding introduces complex queuing dynamics that make quantifying streaming latency difficult. This paper provides a mathematical framework to analyze and optimize video stall durations when streaming from distributed, erasure-coded storage. The authors demonstrate that joint optimization of chunk placement and scheduling can reduce mean stall times by up to 60%.
Introduction: The Challenge of Erasure-Coded Streaming
As video streaming dominates global internet traffic, cloud providers must balance storage efficiency with user Quality of Experience (QoE). Erasure coding—where a file is divided into $k$ chunks and encoded into $n$ chunks ($n > k$)—is significantly more storage-efficient than simple replication. To reconstruct the original data, a client only needs to retrieve any $k$ out of the $n$ chunks.
However, streaming from such a system is fundamentally different from downloading a static file. In streaming, segments must arrive sequentially; a stall occurs if a segment is not ready when the previous one finishes playing. Quantifying these stall durations is challenging due to the "state explosion" problem in queuing theory. This paper addresses this by characterizing the mean stall duration and the stall duration tail probability (the likelihood of long, frustrating stalls).
System Model and Methods
The researchers modeled the distributed storage system as a set of servers acting as M/G/1 queues. The time to serve a chunk follows a shifted-exponential distribution, capturing both processing and network latency.
As shown in the figure above, each video segment $G_{i,j}$ is divided into $k_i$ blocks and encoded into $n_i$ chunks ($C_{i,j}^{(1)}, ..., C_{i,j}^{(n_i)}$). These chunks are then distributed across $m$ servers. To manage requests, the system employs a Joint Scheduler. Instead of complex real-time state tracking, the scheduler uses optimized probability weights to dispatch requests to subsets of servers.
The authors derived rigorous mathematical upper bounds for QoE metrics using Moment Generating Functions (MGFs) and ordered statistics. They formulated a non-convex optimization problem to minimize a weighted combination of mean and tail stall durations. This was solved using an iterative algorithm called iNner cOnVex Approximation (NOVA), which jointly optimizes chunk placement, access probabilities, and auxiliary bounding variables.
Key Insights
- Streaming vs. Downloading: Traditional file download metrics do not apply to streaming. Because segments are played sequentially, the playback time of one segment is heavily correlated with the previous one, requiring a novel recursive mathematical approach.
- Erasure Coding vs. Replication: Counterintuitively, erasure coding can outperform replication in terms of latency. By breaking data into smaller chunks and providing more server combinations (e.g., any 4 out of 10), the scheduler can more effectively bypass congested nodes.
- The Mean-Tail Trade-off: Optimizing for average stall time can lead to poor worst-case performance. The authors found that configurations optimizing the mean stall duration could have a tail probability 12 times higher than the optimal possible value, necessitating explicit trade-offs in system design.
Results and Performance
The proposed joint optimization algorithm was evaluated in a simulated environment with 12 to 48 nodes and up to 2000 video files. Key findings include:
- 60% Reduction in Stall Duration: Under high load, the algorithm reduced mean stall times from approximately 700s to 250s compared to baseline random placement strategies.
- Improved Tail Probability: The algorithm reduced the likelihood of catastrophic buffering events by orders of magnitude.
- Tighter Bounds: The new MGF-based bounds are up to 30% tighter than previous state-of-the-art mathematical models for file downloads.
Limitations and Future Directions
While the framework is robust, several areas remain for future exploration. The current model assumes a fixed video quality, whereas modern Adaptive Bitrate (ABR) streaming dynamically changes quality based on buffer levels. Additionally, the model assumes strict First-In-First-Out (FIFO) queues at servers; implementing deadline-aware scheduling or accounting for dynamic decoding latency could further refine the analysis. Finally, integrating edge caching into the core optimization remains an open challenge.
Summary updated