PLVER: Joint Stable Allocation and Content Replication for Edge-Assisted Live Video Delivery

Huan Wang, Guoming Tang, Kui Wu, Jianping Wang

Introduction

In traditional Content Delivery Networks (CDNs), caching follows a "client-driven" or pull-based model. When a new video segment is generated, an edge server only fetches it from the cloud after a user explicitly requests it. For live video streaming, this creates a critical performance bottleneck known as the "thundering herd" problem.

Because millions of users may request a newly encoded segment simultaneously, the first wave of requests often arrives at the edge before the segment has been cached. These requests must travel back to the origin server, leading to startup delays, playback stalls, and a degraded user experience. While some solutions introduce artificial delays to allow caches to "warm up," this sacrifices the real-time nature of the stream.

The timeline of a cache miss during live video delivery, illustrating the delay between segment encoding and edge availability.

The PLVER Framework

To address these challenges, the authors propose PLVER (Joint Stable Allocation and Content Replication), a proactive "push" scheme. Instead of waiting for requests, PLVER pushes content to the edge before users ask for it. The system operates through a two-stage framework:

  1. Stable One-to-Multiple Allocation (ISOA Algorithm): Rather than using simple greedy assignments, PLVER employs an adaptation of the Gale-Shapley "stable marriage" algorithm. The ISOA (Integral Stable One-to-multiple Allocation) algorithm matches user groups to edge clusters based on mutual preferences, such as minimizing latency for viewers while maintaining load balance for servers. This ensures a more predictable and stable Quality of Experience (QoE).
  2. Proactive Video Replication: Once users are assigned, the system determines which specific video segments to push to which edge servers. This is modeled as a Multiple Knapsack Problem (MKP). To handle the computational complexity, PLVER uses a two-step heuristic that first maximizes traffic coverage greedily and then redistributes workloads from overloaded servers to those with spare capacity.
The PLVER architecture, showing the interaction between the replication table, origin server, and stable allocation module.

Evaluation and Key Insights

The study evaluated PLVER using a massive, real-world Twitch dataset from January 2014, covering 0.3 million viewers and over 300 channels. The network topology was modeled using geoISP data to simulate a realistic deployment of 641 edge clusters across 470 cities.

Key Results

  • Superior Traffic Offloading: PLVER carries 82% more traffic than the standard "caching on requested time" (CORT) method and 28% more than auction-based replication methods.
  • High-Quality Streaming: For demanding 720p high-resolution requests, PLVER achieved a 36% satisfaction ratio, nearly doubling the performance of auction-based alternatives (19%).
  • Resilience: The system proved robust against viewership fluctuations. Even with a 30% change in audience size, the offloading ratio remained stable, demonstrating that the heuristic effectively leverages historical viewership data to predict near-future demand.

Conclusion

PLVER represents a paradigm shift in live video delivery by replacing reactive pulling with proactive pushing. By combining stable allocation with intelligent replication, it significantly mitigates the thundering herd problem without sacrificing stream liveness. Future work may explore the complexities of real-time request redirection and the coordination of proactive pushes across global CDN controllers at an even larger geographic scale.

Summary updated

Abstract

Live streaming services have gained extreme popularity in recent years. Due to the spiky traffic patterns of live videos, utilizing distributed edge servers to improve viewers' quality of experience (QoE) has become a common practice nowadays. Nevertheless, the current client-driven content caching mechanism does not support pre-caching from the cloud to the edge, resulting in a considerable amount of cache misses in live video delivery. By jointly considering the features of live videos and edge servers, we propose PLVER, a proactive live video push scheme to address the cache miss problem in live video delivery. Specifically, PLVER first conducts a one-to-multiple stable allocation between edge clusters and user groups to balance the load of live traffic over the edge servers. It then adopts proactive video replication algorithms to speed up video replication among the edge servers. We conduct extensive trace-driven evaluation, covering 0.3 million Twitch viewers and more than 300 Twitch channels. The results demonstrate that with PLVER, edge servers can carry 28 and 82 percent more traffic than the auction-based replication (ABR) method and the caching on requested time (CORT) method, respectively.
BibTeX
@article{wang2021plver,
  author = {Huan Wang and Guoming Tang and Kui Wu and Jianping Wang},
  title = {{PLVER: Joint Stable Allocation and Content Replication for Edge-Assisted Live Video Delivery}},
  journal = {IEEE Transactions on Parallel and Distributed Systems},
  year = {2021},
  doi = {10.1109/tpds.2021.3090784},
}
Figure