Fairness Scheduling for Coded Caching in Multi-AP Wireless Local Area Networks

1. Problem Statement

The paper addresses the challenge of implementing Coded Caching (CC) for on-demand video streaming in practical Multi-Access Point (Multi-AP) Wireless Local Area Networks (WLANs).

• The Gap: While theoretical CC schemes offer significant information-theoretic gains by turning unicast traffic into multicast transmissions, most existing works rely on physical-layer modifications (e.g., complex precoding) that are incompatible with current standards (like IEEE 802.11/WiFi). Furthermore, traditional CC optimization focuses on minimizing worst-case delivery time for file downloads, which is unsuitable for video streaming where continuous, fair delivery rates (goodput) are critical to prevent buffer starvation.
• The Specific Challenge: The authors aim to design a CC system that operates "over IP" (above the MAC/PHY layers) in a decentralized, asynchronous environment with multiple APs. The core problem is fairness scheduling: ensuring that all users receive video chunks at a rate sufficient for playback while maximizing network utility (fairness) under a collision-type interference model typical of WiFi (CSMA-like behavior).

2. Methodology

System Model

• Network: A server connects to $H$ spatially distributed APs, serving $K$ users.
• Interference Model: A collision model is used where a user successfully receives a packet only if they are within the transmission radius ($r_{trans}$) of an active AP and outside the interference radius ($r_{inter}$) of all other active APs.
• Streaming: Video files are split into "chunks." Users request chunks sequentially. A chunk is only useful once all its subpackets are delivered.
• Cache Placement: A decentralized, asynchronous placement phase where users randomly select one of $L$ distinct cache profiles. Each profile stores a specific fraction ($\gamma$) of every file, partitioned into subpackets based on combinatorial subsets.

Key Components

1. Goodput Definition: The performance metric is defined as goodput—the long-term time-averaged number of video chunks delivered per unit time to a user's playback buffer.
2. Fairness Formulation: The problem is formulated as maximizing a network utility function over the achievable goodput region (the convex hull of all instantaneous rate vectors). Two fairness criteria are considered:
   • Proportional Fairness (PF): Maximizes the sum of logarithms of goodputs ($\sum \log(\bar{r}_k)$).
   • Hard Fairness (HF): Maximizes the minimum goodput ($\min \bar{r}_k$).
3. Optimization Challenge: The exact solution requires enumerating all possible AP activation patterns and codeword combinations, leading to a combinatorial explosion (variables grow faster than exponentially with network size).

Proposed Solutions

To overcome computational intractability, the authors propose a hierarchy of solutions based on the Lyapunov Drift-Plus-Penalty (DPP) framework:

• A. Optimal Stationary Solution (Baseline): Formulates the problem as a convex optimization over stationary policies. It is computationally feasible only for very small networks.
• B. Reduced-Complexity Dynamic Solution:
  • Exploits symmetry among users with identical cache profiles and spatial properties.
  • Uses the DPP method to dynamically update virtual queue backlogs ($Q_t$).
  • Heuristic for Codeword Formation: Instead of searching all codewords, it selects the user with the largest queue backlog for each cache profile within an AP's range. It then constructs codewords using only these "representative" users, drastically reducing the search space from exponential to linear in the number of APs.
• C. Virtual Queue Heuristic (Scalable):
  • Designed for very large networks where even the reduced solution is too complex.
  • Sorts users by virtual queue backlog.
  • Assigns users to APs sequentially, activating APs only if they increase the weighted sum-rate and do not cause interference to already active users. This mimics a greedy, queue-aware CSMA approach.

3. Key Contributions

1. First Rigorous Fairness Framework for CC in Multi-AP WLANs: The paper bridges the gap between theoretical CC and practical deployment by explicitly targeting fair user goodput in a multi-AP, collision-prone environment.
2. "Over IP" Implementation: Proposes a solution that leaves the physical and MAC layers untouched, making it compatible with existing WiFi standards (IEEE 802.11).
3. Dynamic Scheduling Algorithms:
   • Developed a provably optimal dynamic scheduler for stationary conditions with reduced complexity.
   • Introduced a scalable heuristic that prioritizes users with large queue backlogs, achieving a favorable trade-off between performance and complexity.
4. Comprehensive Baseline Comparison: The study compares the proposed schemes against:
   • Conventional (uncoded) prefix caching.
   • Spatial reuse schemes (orthogonal channels).
   • CSMA-inspired distributed coordination.

4. Results

Extensive simulations were conducted to validate the proposed methods:

• Performance Gain: Coded Caching consistently outperforms conventional uncoded caching across all scenarios due to multicast gains.
• Optimality vs. Heuristic:
  • The Optimal Solution and the Reduced-Complexity Dynamic Solution achieve nearly identical performance in small-to-medium networks.
  • The Virtual Queue Heuristic performs very close to the optimal solution in large networks, significantly outperforming all baseline schemes.
• Baseline Comparison:
  • Spatial Reuse: Performs poorly because it restricts AP activation unnecessarily, leading to underutilization of the network.
  • CSMA-Inspired: Performs suboptimally because random activation order ignores queue backlogs, leading to interference that negates CC gains, especially at moderate cache profile counts ($L$).
• Impact of Cache Profiles ($L$): Increasing $L$ (more cache profiles) generally increases goodput by creating more multicast opportunities. However, the gain saturates as $L$ becomes very large relative to the number of users.
• Fairness Trade-offs:
  • Hard Fairness (HF) ensures a higher minimum goodput for the worst-off users but reduces the overall geometric mean.
  • Proportional Fairness (PF) allows some users to stream at higher qualities (beneficial for adaptive bitrate streaming) but results in a lower minimum goodput.
• Dynamic Adaptation: The DPP-based algorithms successfully adapt to network topology changes (users joining/leaving), converging to new optimal goodput points rapidly.

5. Significance

This work is significant because it moves Coded Caching from a theoretical construct to a practical, deployable solution for modern wireless networks.

• Standard Compatibility: By operating "over IP," it avoids the need for hardware or firmware changes to WiFi routers and client devices.
• Real-World Applicability: It addresses the specific constraints of video streaming (latency, continuity, fairness) rather than just file download completion time.
• Scalability: The proposed heuristics make CC viable for crowded venues (stadiums, airports, trains) where hundreds of users share multiple APs, demonstrating that CC can provide substantial capacity gains without requiring a complete overhaul of existing network infrastructure.