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

Huan Wang, Guoming Tang, Kui Wu, Jianping Wang

TL;DR

This paper introduces PLVER, a novel system for live video delivery that tackles the "cache miss" problem in edge-assisted streaming. By intelligently allocating users to edge servers and proactively replicating video content, PLVER significantly improves traffic offloading and viewer Quality of Experience (QoE) compared to existing methods.

What Problem Does This Paper Address?

Live streaming has exploded in popularity, but delivering it efficiently, especially with interactive features, is challenging. A key issue is the "thundering herd" problem, where many users request the same content simultaneously, overwhelming servers. Edge computing offers a solution by bringing content closer to users, but a new problem arises: cache misses. When a new video segment is generated, it might not be fully cached on edge servers by the time the first users request it. This forces requests to go back to the origin server, increasing latency and degrading the viewer experience. Existing solutions often sacrifice the "liveness" of the stream by delaying content availability, which is undesirable for real-time broadcasts. This paper aims to solve the cache miss problem in edge-assisted live video delivery without compromising real-time performance.

Methods

PLVER employs a two-pronged approach:

  1. Stable One-to-Multiple Allocation: Instead of individual client routing, PLVER groups users and assigns them to edge server clusters. This "one-to-multiple" allocation (one user group to one edge cluster, but one edge cluster can serve multiple user groups) aims to balance the load across edge servers. It uses a stable marriage algorithm (ISOA) that considers both user group preferences for edge clusters and edge cluster preferences for user groups, ensuring a stable and efficient assignment that maximizes QoE.
  2. Proactive Video Replication: Once users are allocated, PLVER uses a proactive replication algorithm. This algorithm analyzes real-time viewership statistics to predict future content demands. It then intelligently pushes video segments to the assigned edge servers before they are requested, minimizing the chance of cache misses. This is a departure from traditional "pull-based" caching, which waits for client requests. The replication process is optimized to speed up content distribution across edge servers.

Datasets

The authors evaluated their system using a real-world dataset from Twitch. This dataset included:

  • Information on live channels, including viewership numbers, bitrates, and session durations.
  • Traces of approximately 0.3 million Twitch viewers and over 300 Twitch channels.

The network topology was built using data from US states (Washington and Oregon) and ISP coverage information, creating a simulated network of 641 edge clusters and 1253 user groups.

Key Insights and Ideas

  • Proactive is better than reactive for live video: The core insight is that for live streaming, anticipating demand through proactive replication is far more effective than waiting for requests and then caching. This directly addresses the inherent latency of client-driven caching.
  • Stable allocation is crucial for edge efficiency: Simply assigning users to the nearest edge server isn't enough. A stable, preference-aware allocation mechanism (like ISOA) is needed to balance load and ensure users are matched with edge servers that can best serve them, maximizing QoE.
  • Balancing performance and cost: The paper highlights the trade-off between maximizing traffic offloading (performance) and the cost of replicating content. PLVER's replication cost factor ($\alpha$) allows for tuning this balance, showing that there's an optimal point beyond which further replication yields diminishing returns.
  • Viewership statistics are powerful predictors: Leveraging real-time viewership data allows PLVER to make informed decisions about which content to push to which edge servers, significantly improving its effectiveness.

Key Results

PLVER demonstrated significant improvements over existing methods:

  • Traffic Offloading: Edge servers using PLVER carried 28% more traffic than the auction-based replication (ABR) method and 82% more traffic than the caching on requested time (CORT) method.
  • Allocation Improvement: The stable allocation algorithm (ISOA) allocated more user groups to their higher-ranked (more preferred) edge clusters compared to a greedy allocation strategy.
  • Quality of Service: PLVER provided a higher satisfaction ratio for video requests across different qualities, including a 36% satisfaction ratio for 720p requests, compared to ABR (19%) and CORT (30%).
  • Robustness to Fluctuation: Even with viewer number fluctuations of up to 70%, PLVER's performance degradation was relatively small, showing its resilience.

Limitations and Future Work

  • Replication Cost Factor Tuning: While the paper shows that performance improves with the replication cost factor ($\alpha$) up to a certain point (40-60%), finding the absolute optimal value for different scenarios might require further investigation.
  • Real-time Tracking: PLVER relies on viewership statistics, not individual viewer tracking. While this is a strength for privacy and efficiency, it means the system's decisions are based on aggregated data, which might miss nuances of individual user behavior.
  • Future Work: The authors suggest further research into optimizing the replication schedule and exploring more sophisticated allocation strategies. They also mention that the system's performance evaluation in the paper is based on a simulated network, and real-world deployment would be the next logical step.

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