A Novel Centralized Strategy for Coded Caching with Non-uniform Demands

Pierre Quinton, Saeid Sahraei, Michael Gastpar

Abstract

Despite significant progress in the caching literature concerning the worst case and uniform average case regimes, the algorithms for caching with nonuniform demands are still at a basic stage and mostly rely on simple grouping and memory-sharing techniques. In this work we introduce a novel centralized caching strategy for caching with nonuniform file popularities. Our scheme allows for assigning more cache to the files which are more likely to be requested, while maintaining the same sub-packetization for all the files. As a result, in the delivery phase it is possible to perform linear codes across files with different popularities without resorting to zero-padding or concatenation techniques. We will describe our placement strategy for arbitrary range of parameters. The delivery phase will be outlined for a small example for which we are able to show a noticeable improvement over the state of the art.

Introduction: The Challenge of Non-uniform Demands

In modern broadcast networks, such as those used for video streaming or software distribution, coded caching serves as a vital technique to mitigate peak traffic. This approach typically involves two distinct phases: a placement phase, where content is pre-stored in local user caches, and a delivery phase, where the server broadcasts coded messages (often XORed combinations) to satisfy multiple user requests simultaneously.

System model for a centralized coded caching network with $N$ files and $K$ users.

While standard coded caching algorithms perform optimally under uniform demand distributions, real-world scenarios are characterized by non-uniform popularity, where a small subset of files accounts for the majority of requests. Existing state-of-the-art methods, such as grouping and memory-sharing, struggle with this asymmetry. These methods often result in different "sub-packet" sizes for files of varying popularity, creating a technical barrier: you cannot efficiently XOR packets of different sizes without wasting bandwidth through zero-padding. This limitation prevents effective coding across different popularity groups.

Methodology: Introducing Strategy $\beta$

To overcome these inefficiencies, we propose Strategy $\beta$, a centralized framework designed to exploit non-uniform demands through a novel placement and delivery approach.

1. Uniform Sub-packetization

The core innovation of Strategy $\beta$ is maintaining a uniform sub-packetization structure. Regardless of a file's popularity or the amount of cache allocated to it, every file in the library is divided into the same number of sub-files ($S$). This symmetry is maintained across the entire library.

2. Nested Indexing and Placement

We utilize a combinatorial indexing system based on nested sets ($\tau_1, \dots, \tau_L$). This allows the system to allocate more cache space to "blockbuster" files while ensuring the underlying data structure remains identical. This structural consistency is what enables the subsequent coding gains.

3. Cross-Group Coding

Because all sub-packets are of equal size, the server can perform linear coding (XORing) across files belonging to different popularity groups during the delivery phase. This bypasses the need for zero-padding or concatenation, significantly reducing the total amount of data transmitted.

Key Results and Performance Analysis

The effectiveness of Strategy $\beta$ is evaluated through mathematical modeling and numerical comparisons against established benchmarks, such as the grouping strategy (Strategy $\alpha$).

Expected delivery rate comparison between Strategy $\alpha$ and Strategy $\beta$ as a function of the probability of requesting the most popular file.

Our analysis reveals several key insights:

  • Superior Efficiency: Strategy $\beta$ strictly outperforms Strategy $\alpha$ when the popularity of the primary file ($p$) falls within the range of 0.5 to approximately 0.79.
  • Significant Gains: At a popularity point of $p \approx 0.738$, Strategy $\beta$ achieves a delivery rate reduction of approximately 11% compared to existing methods ($R_\beta \approx 0.89 R_\alpha$).
  • Proximity to Theoretical Limits: The performance of Strategy $\beta$ sits much closer to the theoretical "converse bound"—the absolute physical limit of delivery efficiency—than previous centralized strategies.

Conclusion and Future Directions

Strategy $\beta$ demonstrates that the inability to code across different cache allocations is not a fundamental limit, but rather a consequence of sub-optimal placement strategies. By enforcing structural symmetry through uniform sub-packetization, we unlock significant efficiency gains in non-uniform demand environments.

Future work will focus on generalizing the delivery algorithm for an arbitrary number of users and files, as well as adapting the strategy for scenarios where file popularity varies between individual users.

Summary updated

Abstract

Despite significant progress in the caching literature concerning the worst case and uniform average case regimes, the algorithms for caching with nonuniform demands are still at a basic stage and mostly rely on simple grouping and memory-sharing techniques. In this work we introduce a novel centralized caching strategy for caching with nonuniform file popularities. Our scheme allows for assigning more cache to the files which are more likely to be requested, while maintaining the same sub-packetization for all the files. As a result, in the delivery phase it is possible to perform linear codes across files with different popularities without resorting to zero-padding or concatenation techniques. We will describe our placement strategy for arbitrary range of parameters. The delivery phase will be outlined for a small example for which we are able to show a noticeable improvement over the state of the art.
BibTeX
@inproceedings{quinton2018novel,
  author = {Pierre Quinton and Saeid Sahraei and Michael Gastpar},
  title = {{A Novel Centralized Strategy for Coded Caching with Non-uniform Demands}},
  booktitle = {Infoscience},
  year = {2018},
  doi = {10.3929/ethz-b-000245091},
}
Figure