On Coding for Cache-Aided Delivery of Dynamic Correlated Content

Parisa Hassanzadeh, Antonia Maria Tulino, Jaime Llorca, Elza Erkip

Abstract

Cache-aided coded multicast leverages side information at wireless edge caches to efficiently serve multiple unicast demands via common multicast transmissions, leading to load reductions proportional to the aggregate cache size. However, the increasingly dynamic, unpredictable, and personalized nature of modern content challenges the efficiency of existing caching-based solutions, which typically rely on exact content reuse. This paper generalizes the cache-aided coded multicast problem to specifically account for correlation among content files—such as updated versions of dynamic data. We demonstrate that by caching content based on its correlation with the library and jointly compressing requested files using cached information as references, we can achieve load reductions significantly beyond those of state-of-the-art schemes. Our results show that in real-time or personalized media services, where exact cache hits are rare but updates exhibit high correlation, network cached information remains highly valuable as a reference for network compression.

Introduction

Traditional cache-aided delivery models, such as coded multicasting, operate on a simple premise: if multiple users request the same file and segments of that file are stored in local caches, the server can satisfy these demands simultaneously using a single XORed multicast transmission. While effective for static, popular content, this "exact match" requirement is a significant bottleneck in modern networks.

Today's content is increasingly dynamic (e.g., real-time news updates, sensor data) and personalized (e.g., different versions of the same video stream). In these scenarios, a user may request an updated version of a file while the cache holds only a previous iteration. Standard schemes treat this as a "cache miss," requiring the server to transmit the entire new file. This research proposes a shift in perspective: treating cached data not just as a storage bin for identical copies, but as a library of references for source coding with side information.

The Correlation-Aware Coded Multicast (CA-CACM) Framework

To address the limitations of correlation-unaware systems, we introduce the Correlation-Aware Coded Multicast (CA-CACM) scheme. This framework operates in two distinct phases designed to maximize delivery efficiency while maintaining robustness to library changes.

1. Caching Phase

Unlike previous approaches that attempted to jointly compress an entire library before caching—a method that fails if even a single file is added or updated—CA-CACM stores individually compressed pieces. This ensures the system remains flexible and robust to frequent library updates, as the cached content does not need to be re-synchronized whenever the global library changes.

2. Delivery Phase

The delivery phase exploits correlation on-demand through several key mechanisms:

  • Correlation-Aware Grouping: The server identifies cached packets that are $\delta$-correlated (statistically similar) to the requested packets.
  • Augmented Conflict Graph: In traditional index coding, a conflict graph tracks which users require which packets. We augment this graph by adding "virtual nodes" that represent correlated packets. This allows the system to identify multicast opportunities that are invisible to traditional models.
  • Greedy Group Coloring (GGC): Because finding the optimal multicast code is NP-hard, we utilize a GGC algorithm to find near-optimal ways to XOR packets together for transmission.
  • Refinement: If a user receives a correlated packet rather than the exact requested packet, the server follows up with a small refinement bitstream, ensuring the user can reconstruct the requested file losslessly.

Experimental Evaluation

We evaluated CA-CACM using numerical studies and synthetic correlated libraries modeled as $N$-component discrete memoryless sources (DMS). The simulations spanned various network environments, ranging from small-scale setups to larger networks with 1,000 files and 50 receivers.

Key Results

  • Static Setting: In a library of 90 correlated files, CA-CACM achieved a 1.7x reduction in network load compared to state-of-the-art correlation-unaware schemes.
  • Dynamic Setting: The gains are most pronounced when content changes frequently. In scenarios where 60% of the files were updated between the caching and delivery phases, the proposed scheme performed 3x better than traditional methods.
  • Theoretical Optimality: For a simplified case of two receivers and two files, we proved that CA-CACM achieves a rate within half of the mutual information of the files across all cache sizes.

Discussion and Future Work

The core innovation of this work is the "reference shift"—moving from exact-match caching to reference-based compression. By delaying the exploitation of correlation until the delivery phase, the system becomes resilient to data aging.

However, several challenges remain for large-scale deployment. While the GGC algorithm is polynomial-time, the underlying coloring problem remains complex, requiring further heuristics for networks with millions of users. Additionally, the system relies on a correlation threshold ($\delta$); determining the optimal $\delta$ for diverse content types like video versus sensor data is a significant engineering task. Future research will also explore non-symmetric correlation structures, such as "master" files that serve as references for multiple subordinate files.

Conclusion

As network services move toward real-time and personalized media, the likelihood of exact cache hits diminishes. Our results demonstrate that even when exact content is unavailable, cached information remains a powerful tool for network compression. By accounting for content correlation, CA-CACM provides a path toward significantly more efficient wireless edge delivery in dynamic environments.

Summary updated

Abstract

Cache-aided coded multicast leverages side information at wireless edge caches to efficiently serve multiple unicast demands via common multicast transmissions, leading to load reductions that are proportional to the aggregate cache size. However, the increasingly dynamic, unpredictable, and personalized nature of the content that users consume challenges the efficiency of existing caching-based solutions in which only exact content reuse is explored. This paper generalizes the cache-aided coded multicast problem to specifically account for the correlation among content files, such as, for example, the one between updated versions of dynamic data. It is shown that (i) caching content pieces based on their correlation with the rest of the library, and (ii) jointly compressing requested files using cached information as references during delivery, can provide load reductions that go beyond those achieved with existing schemes. This is accomplished via the design of a class of correlation-aware achievable schemes, shown to significantly outperform state-of-the-art correlation-unaware solutions. Our results show that as we move towards real-time and/or personalized media dominated services, where exact cache hits are almost non-existent but updates can exhibit high levels of correlation, network cached information can still be useful as references for network compression.
BibTeX
@article{hassanzadeh2018coding,
  author = {Parisa Hassanzadeh and Antonia Maria Tulino and Jaime Llorca and Elza Erkip},
  title = {{On Coding for Cache-Aided Delivery of Dynamic Correlated Content}},
  journal = {IEEE J. Sel. Areas Commun.},
  year = {2018},
  url = {https://openreview.net/forum?id=q8WDtmhk1r3},
}
Figure