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 characterize precisely the capacity of the wireless video server in terms of what combination of joint per-packet-delays and throughputs can be supported for the set of flows, as a function of the buffering delay introduced at the server. We also 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.
What Problem Does This Paper Address?
Streaming live video over wireless networks presents a "perfect storm" of technical challenges. First, video traffic is naturally bursty due to Variable Bit Rate (VBR) encoding, meaning the network can suddenly be flooded with data. Second, wireless channels are notoriously unreliable due to fading and interference, and these conditions vary significantly between different clients.
To mitigate these issues, clients typically buffer video. However, for live content like sports or news, large buffers are unacceptable because they introduce significant lag relative to the real-time event. Most existing scheduling policies struggle in this environment: they either focus on meeting deadlines while ignoring long-term throughput (leading to frequent stalls), or they focus on throughput while ignoring deadlines (leading to packets arriving too late to be useful).
The authors seek to characterize the "capacity region"—the maximum combination of throughput and delay a system can handle—and design a policy that actually reaches it.
The EPDF Policy
The authors approach the problem by first modeling the system as a controlled Markov chain to define theoretical limits. They then propose the Earliest Positive-Debt Deadline First (EPDF) scheduling policy for the general case of heterogeneous clients and varying link qualities.
EPDF relies on two key mechanisms:
- Truncated Time Debt: The Access Point (AP) maintains a "debt" counter for each client. If a client hasn't received its required share of service, its debt increases.
- Conditional Prioritization: In each time slot, the AP prioritizes the packet with the earliest deadline, but only from clients who have a "positive debt." If no client has debt, the system defaults to standard earliest-deadline scheduling.
By restricting the AP from over-serving clients who have already met their requirements (zero debt), the system naturally reserves capacity for those struggling with poor channel conditions or sudden traffic bursts.
Key Results and Insights
The researchers evaluated EPDF using real-world high-definition video traces (e.g., Harry Potter, Finding Neverland) in an ns-2 simulator configured with an IEEE 802.11a MAC protocol.
- Superior Performance: EPDF outperformed existing standards like Earliest Deadline First (EDF) and Largest Debt First (LDF) by a large margin. In some scenarios, it supported a throughput region up to 13% larger than its closest competitor.
- Capacity Achieving: The authors mathematically proved that EPDF is "capacity-achieving," meaning it can support any set of video flows that are theoretically possible to serve within the system's physical limits.
- Buffering Trade-offs: The paper quantifies the throughput gains associated with buffering. For instance, increasing the delay bound from 0.1 seconds to 1 second can increase achievable throughput by roughly 20%.
Conclusion
EPDF provides a robust framework for managing the competing demands of throughput and strict delay constraints in live video streaming. While challenges remain regarding real-time parameter estimation in highly dynamic environments, the policy demonstrates a significant step forward in maximizing the capacity of wireless access points for high-demand media applications.
Summary updated