Scheduling of access points for multiple live video streams

I-Hong Hou, Rahul Singh2013 · DOI

TL;DR

This paper tackles the challenge of efficiently serving multiple live video streams over unreliable wireless networks, where each stream has varying bitrates and clients have different delay and throughput needs. The authors introduce a novel scheduling policy, EPDF, that precisely characterizes and achieves the "capacity region" – the optimal balance of throughput and delay guarantees for these complex scenarios. Their simulations demonstrate that EPDF significantly outperforms existing methods.

What Problem Does This Paper Address?

The proliferation of live video streaming over wireless networks presents a significant challenge. Unlike traditional data, live video demands both timely delivery (low delay) and sufficient data rate (high throughput) to ensure a smooth viewing experience. This is complicated by several factors:

  • Variable Bitrate (VBR) Video: Video streams don't send data at a constant rate. They have bursts of activity, which can overwhelm network resources.
  • Unreliable Wireless Links: Wireless communication is inherently prone to errors due to factors like shadowing, fading, and interference, leading to packet loss.
  • Client-Specific Requirements: Different clients might have different tolerance for delay (e.g., live news vs. pre-recorded content) and varying throughput needs.
  • Buffering: To mitigate the effects of VBR traffic and unreliable links, clients buffer video packets. However, excessive buffering increases initial playback delay, which is undesirable for live content.

The core problem is to design an access point (AP) scheduling policy that can simultaneously satisfy the diverse delay and throughput requirements of multiple live video streams over an unreliable wireless channel, while minimizing the impact of buffering.

Methods

The paper proposes a two-pronged approach:

  1. Capacity Region Characterization: The authors first define and precisely characterize the "capacity region." This region represents the set of all possible combinations of per-packet delay and throughput guarantees that an access point can provide to a set of video streams, considering the buffering delay introduced at the server. They develop an analytical model to derive this region, which involves modeling the system as a controlled finite-state Markov chain.
  2. Earliest Positive-Debt Deadline First (EPDF) Policy: To achieve this capacity, they introduce a novel online scheduling policy called EPDF. This policy is designed to be practical and implementable. Key features include:
  3. Truncated Time Debt: A concept of "truncated time debt" is introduced for each client, which increases over time and decreases when the AP schedules a packet for that client. This debt is a crucial factor in the scheduling decision.
  4. Positive Debt Prioritization: The EPDF policy prioritizes scheduling packets from clients with strictly positive truncated time debts. This prevents certain clients from being starved while others are over-served.
  5. Deadline-Based Scheduling: Within the set of clients with positive debts, packets are scheduled based on their deadlines, similar to Earliest Deadline First (EDF).
  6. Adaptive Parameter (M): The policy uses a single tunable parameter, M (frame size), which influences how often the truncated time debt is updated. This parameter allows for a trade-off between long-term performance guarantees and short-term responsiveness.

The authors prove that the EPDF policy is "capacity achieving," meaning it can support any vector of throughputs that lies strictly within the derived capacity region.

Datasets

The paper uses real-world video traces from the Video Trace Library of Arizona State University. Specifically, they simulate three HD movies: "Harry Potter," "Finding Neverland," and "Transporter 2." These traces are used to generate traffic patterns for the simulations.

Key Insights and Ideas

  • The "Capacity Region" is Key: Precisely defining and understanding the achievable throughput-delay trade-offs is fundamental to designing effective scheduling policies for live video streaming.
  • Buffering is a Double-Edged Sword: While essential for smoothing VBR traffic and handling unreliability, buffering introduces initial playback delay, a critical concern for live content. The EPDF policy implicitly manages this by considering deadlines.
  • Positive Debt is Crucial for Fairness: Prioritizing clients with positive truncated time debts (rather than just any client with a deadline) is vital for ensuring fair resource allocation and preventing starvation.
  • The M Parameter's Trade-off: The tunable parameter M in EPDF highlights a critical trade-off. A larger M provides stronger long-term guarantees but can lead to poorer short-term performance (e.g., long periods of serving only one client). A smaller M improves short-term responsiveness but can, in extreme cases, lead to the policy failing to achieve capacity if packet generation patterns are highly irregular across frames.
  • EPDF's Practicality: The policy's reliance on only a few parameters (like M and client workload w_n) and its online nature make it well-suited for real-world implementation.

Key Results

  • EPDF Outperforms: Simulations show that the EPDF policy significantly outperforms other well-known scheduling policies (EDF, LDF, and a policy from Dua and Bambos) in terms of achieved throughput regions across all tested movies.
  • Delay Bounds Matter: Increasing delay bounds generally leads to larger achievable throughput regions, as it provides more flexibility for the scheduler to handle packet bursts and retransmissions.
  • Frame Size (M) Impact: While a smaller M leads to better short-term performance (less variation in packet delivery per second), the paper found that the long-term achieved throughput regions were surprisingly similar for very different values of M (e.g., M=1 vs. M=1000), suggesting robustness. However, extremely small M values can lead to capacity loss in specific scenarios.

Limitations and Future Work

  • Short-Term vs. Long-Term Trade-off: The paper acknowledges that while EPDF guarantees long-term performance, modifications to improve short-term performance might theoretically compromise long-term guarantees. However, their simulations suggest this impact is negligible in practical scenarios.
  • Assumptions: The analytical model relies on certain assumptions about packet generation (e.g., Markov chains) and channel reliability. While the EPDF policy itself is more general, the capacity region derivation is tied to these models.
  • Future Work: The paper suggests further investigation into practical issues and the trade-off between short-term and long-term performance guarantees, particularly when modifying the EPDF policy. The impact of different video coding standards and more complex network topologies could also be explored.

Summary updated

Abstract

This paper studies the problem of serving multiple live video streams to several different clients from a single access point over unreliable wireless links, which is expected to be major a consumer of future wireless capacity. This problem involves two characteristics. On the streaming side, different video streams may generate variable-bit-rate traffic with different traffic patterns. On the network side, the wireless transmissions are unreliable, and the link qualities differ from client to client. In order to alleviate the above stochastic aspects of both video streams and link unreliability, each client typically buffers incoming packets before playing the video. The quality of the video playback subscribed to by each flow depends, among other factors, on both the delay of packets as well as their throughput. In this paper we address how to schedule packets at the access point to satisfy the joint per-packet-delay-throughput performance measure. We test the designed policy on the traces of three movies. From our tests, it appears to outperform other policies by a large margin.
BibTeX
@misc{hou2013scheduling,
  author = {I-Hong Hou and Rahul Singh},
  title = {{Scheduling of access points for multiple live video streams}},
  year = {2013},
  doi = {10.1145/2491288.2491320},
}
Figure