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

Avik Sengupta, Ravi Tandon

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 work, 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 (D2D) 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 vs. 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 establish the optimal storage-rate tradeoff to within a constant multiplicative gap. We show that, for multiple demands per user, achievable schemes based on repetition of schemes for single demands are order-optimal under both delivery models.

Introduction

As multimedia traffic continues to dominate wireless network usage, "caching at the edge"—storing content on user devices or local base stations—has become essential to prevent network congestion. The core challenge in these systems is the storage-rate tradeoff: increasing local storage capacity ($M$) allows for a reduction in the required transmission rate ($R$) over the air. While foundational 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) in a single interval. This paper addresses the loose nature of existing "cut-set" bounds used to estimate theoretical limits in high-demand scenarios.

System Models and Methodology

The authors analyze two distinct delivery architectures to service user file demands, as illustrated in Figure 3.

System models for (a) centralized content delivery and (b) D2D-assisted distributed delivery.
  1. Centralized Delivery: A central server services user demands via multicast transmissions over a shared link.
  2. D2D-Assisted Delivery: Users share content directly with one another through device-to-device multicasting, reducing the load on the central infrastructure.

To derive tighter theoretical limits, the authors employ an information-theoretic approach centered on Han’s Inequality. Unlike standard cut-set bounds that treat the network as simple "pipes," Han’s Inequality captures the complex correlations between information stored across different user caches. This allows for a more precise bounding of the joint entropy of cache contents. On the practical side, the authors demonstrate that "repetition schemes"—which simply repeat optimal single-demand strategies $L$ times to satisfy $L$ demands—are surprisingly effective.

Key Results

The primary contribution of this work is the significant narrowing of the gap between achievable rates and theoretical lower bounds. Numerical analysis confirms that the new lower bounds are strictly tighter than traditional cut-set bounds, particularly in the low-cache regime where network congestion is most critical.

Rate-storage tradeoff comparison for (a) single demand ($L=1$) and (b) multiple demands ($L=2$).

As shown in Figure 4, the "New Lower Bound" tracks the achievable rate much more closely than the "Cut Set Bound." Specifically:

  • Centralized Caching: For $L$ demands, the gap is reduced to a constant factor of 11 (down from 18). For $L=1$, it is reduced to 8 (down from 12).
  • D2D Caching: The paper provides the first-known converse for multiple-demand D2D scenarios, establishing a gap within a factor of 10.

These results prove that complex new coding architectures are not strictly necessary for multiple demands; simple repetition of single-demand schemes is order-optimal.

Conclusion and Future Work

By leveraging Han’s Inequality, this research provides a significantly tighter characterization of the fundamental storage-rate tradeoff. This simplifies the design of future caching protocols by validating the use of straightforward repetition schemes. Future research may extend these bounds to scenarios with non-uniform content popularity (e.g., Zipf distributions) and variable file sizes to further bridge the gap between theoretical models and real-world network dynamics.

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 work, 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 (D2D) 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 vs. 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 establish the optimal storage-rate tradeoff to within a constant multiplicative gap. We show that, for multiple demands per user, achievable schemes based on repetition of schemes for single demands are order-optimal 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},
}
Figure