Improved Approximation of Storage-Rate Tradeoff for Caching With Multiple Demands

Avik Sengupta, Ravi Tandon

TL;DR

This paper provides a significantly tighter characterization of the fundamental tradeoff between cache storage and transmission rate in networks where users request multiple files. By developing a new lower-bounding technique based on Han’s Inequality, the authors prove that simple schemes—which merely repeat single-demand strategies—are order-optimal, narrowing the known gap between theoretical limits and practical performance.

What Problem Does This Paper Address?

As multimedia traffic dominates wireless networks, "caching at the edge" (storing content on user devices or local base stations) has become essential to prevent network congestion. The core challenge is the storage-rate tradeoff: if you store more locally (high storage $M$), you need to transmit less over the air (low rate $R$).

While previous work by Maddah-Ali and Niesen established these tradeoffs for users requesting a single file, real-world scenarios often involve users requesting multiple items (e.g., several video chunks or files) in a single interval. Existing "cut-set" bounds used to estimate the theoretical limits of these systems were notoriously loose. This paper seeks to find tighter lower bounds to determine exactly how much "coded caching" actually helps when demands are high.

Methods

The authors employ an information-theoretic approach to derive new converse bounds (mathematical proofs of the best possible performance).

  • Han’s Inequality: The "secret sauce" of this paper is the application of Han’s Inequality on subsets of random variables. Unlike standard cut-set bounds—which essentially look at the "pipes" of information flow—this technique better captures the complex correlations between what is stored in different users' caches and what is sent in multicast transmissions.
  • Two Delivery Models: They analyze both Centralized Delivery (a server multicasts to all users) and D2D-Assisted Delivery (users share cache content with each other via device-to-device multicasting).
  • Repetition Schemes: For the "achievable" side (the upper bound), they use a straightforward approach: taking existing optimal schemes for single-file demands and repeating them $L$ times to satisfy $L$ demands per user.

Datasets

As a theoretical information theory paper, no empirical datasets were used. The results are derived using a mathematical model where a library of $N$ files is distributed i.i.d. (independent and identically distributed), and user demands are analyzed for the "worst-case" scenario to ensure robust performance.

Key Insights and Ideas

  • The Power of Han’s Inequality: The authors show that cut-set bounds fail because they don't fully account for how information is "shared" across overlapping subsets of caches. By using Han’s Inequality, they can bound the joint entropy of cache contents more precisely, leading to a "strictly tighter" lower bound.
  • Complexity Isn't Always Necessary: A major "aha moment" is the discovery that for multiple demands, you don't necessarily need a brand-new, hyper-complex coding architecture. Simply repeating the single-demand coded caching scheme is order-optimal. This simplifies the design of future caching protocols.
  • Symmetrization: The proof relies on "symmetrizing" over all possible demand vectors and cache subsets, which allows the authors to turn a specific instance of network traffic into a general law of the storage-rate tradeoff.

Key Results

The paper successfully narrows the "gap" between what we know is possible (achievable schemes) and the theoretical limit (the converse):

  • Centralized Caching: For users requesting $L$ files, the gap between the achievable rate and the new lower bound is reduced to a constant factor of 11 (improving upon the previous gap of 18).
  • Single Demand Case ($L=1$): The gap is reduced to 8 (improving upon the previous gap of 12).
  • D2D Caching: The authors provide the first-known converse for the multiple-demand D2D scenario, showing the gap is within a factor of 10.
  • Tightness: Numerical results show the new bounds are significantly closer to achievable rates than traditional cut-set bounds, especially in the low-cache regime where network congestion is most critical.

Limitations and Future Work

  • Uniform Popularity: The paper assumes all files are equally likely to be requested. In reality, content popularity usually follows a Zipf distribution (a few files are much more popular than others). Extending these tighter bounds to non-uniform demands is a logical next step.
  • Fixed File Sizes: The model assumes all files are the same size ($B$ bits). Variable file sizes would add another layer of complexity to the storage-rate tradeoff.
  • Closing the Gap: While a multiplicative gap of 8 or 11 is a major improvement, it is still not "exact." Future work could look for even more sophisticated bounds or new coding schemes to close this gap to 1.

Summary updated

Abstract

Caching at the network edge has emerged as a viable solution for alleviating the severe capacity crunch in modern content centric wireless networks by leveraging network load-balancing in the form of localized content storage and delivery. In this paper, we consider a cache-aided network, where the cache storage phase is assisted by a central server and users can demand multiple files at each transmission interval. To service these demands, we consider two delivery models: (1) centralized content delivery, where user demands at each transmission interval are serviced by the central server via multicast transmissions; and (2) device-to-device assisted distributed delivery, where users multicast to each other in order to service file demands. For such cache-aided networks, we present new results on the fundamental cache storage versus transmission rate tradeoff. Specifically, we develop a new technique for characterizing information theoretic lower bounds on the storage-rate tradeoff and show that the new lower bounds are strictly tighter than cut-set bounds from literature. Furthermore, using the new lower bounds, we improve the constant factor approximation of the optimal storage-rate tradeoff for cache-aided systems under both delivery models.
BibTeX
@article{sengupta2017improved,
  author = {Avik Sengupta and Ravi Tandon},
  title = {{Improved Approximation of Storage-Rate Tradeoff for Caching With Multiple Demands}},
  journal = {IEEE Trans. Communications},
  year = {2017},
  url = {https://openreview.net/forum?id=vnbMCLbIDs},
}

Loading related content...

Figure