Coded Caching for Multicast Content Delivery

36 concepts32 papers1 proposal

In a traditional broadcast network, delivering unique content to multiple users simultaneously creates a severe bandwidth bottleneck. If ten users request ten different high-definition videos from a single base station, the server must transmit ten distinct data streams. The required network throughput scales linearly with the number of active users, even if the users are listening to the exact same shared wireless channel.

Local caching on user devices (such as smartphones or edge routers) mitigates this problem, but traditional caching only provides a local gain: a user benefits if and only if they request a file that is already sitting in their own storage.

Coded caching fundamentally changes this dynamic. By combining strategic content placement with bitwise algebraic operations (like XOR), coded caching transforms distinct unicast requests into a single, shared multicast transmission. This creates a global caching gain, where the cache contents of one user are used to cancel out interference and decode the requested files of entirely different users.

The Core Intuition: Algebraic Cancellation

To understand why coded caching works, consider a simple network with a single server and two users connected via a shared broadcast channel. The server holds a library of two files, $A$ and $B$.

Suppose User 1 has file $B$ in their local cache, and User 2 has file $A$ in their local cache. Now, the users make their requests: User 1 wants file $A$, and User 2 wants file $B$.

User 1 (Has B) <─── Wants A ─── [ Server ] ─── Wants B ───> User 2 (Has A)

Instead of transmitting file $A$ and then transmitting file $B$ (requiring two full transmissions), the server broadcasts a single XOR-coded packet:

$$\text{Broadcast} = A \oplus B$$

When this combined packet arrives at the users, they use their local cache contents as side information to isolate their desired files:

  • User 1 computes: $(A \oplus B) \oplus B = A$
  • User 2 computes: $(A \oplus B) \oplus A = B$

With a single transmission, the server has simultaneously satisfied two completely different requests. The local cache of User 1 served as the key to unlock the request of User 2, and vice versa.

The Two-Phase Framework: Placement and Delivery

To scale this toy example to networks with thousands of users and files, content delivery must be split into two distinct phases: a placement phase and a delivery phase.

In the foundational work by Mohammad Ali Maddah-Ali et al., the placement phase occurs during off-peak hours when network traffic is low. Files are partitioned into subpackets and distributed across user caches according to a precise combinatorial design. Crucially, this placement is content-agnostic—it happens before users reveal what specific files they want to watch.

By strategically distributing these subfiles, the server ensures that no matter what combination of files the users eventually request during peak hours, the delivery phase will always find overlapping side information to exploit. As highlighted by Georgios S. Paschos et al., this decouples the required transmission bandwidth from the total number of active users, allowing network capacity to scale with the aggregate memory available across the entire network.

Index Coding and Side Information Repositories

This mechanism is deeply rooted in the mathematical framework of index coding. As explored by Alex Dimakis et al., local caches act as distributed side information repositories. When users experience cache misses, the base station leverages the contents of these repositories to compress the broadcast signal, reducing total network traffic by a factor of two or more in realistic scenarios.

In practical wireless deployments, this approach drastically reduces airtime consumption and error-recovery overhead. For instance, Sayandeep Sen demonstrated that combining lost packets via XOR operations allows a single recovery transmission to repair different data losses across multiple distinct WiFi clients simultaneously. Similarly, Xiumin Wang et al. applied this principle to wireless sensor networks, showing that state synchronization over lossy links can be achieved with significantly fewer transmissions by treating local node data as side information.

Adapting to Real-World Asymmetries and Content Structures

While the idealized coded caching model assumes identical cache sizes and completely independent files, real-world networks require relaxing these assumptions to handle asymmetry and content relationships.

Heterogeneous Caches and Crowded Networks

Users rarely possess identical hardware. Mohammad Mohammadi Amiri et al. extended the framework to asymmetric networks where users have distinct cache capacities, optimizing how the server groups requests to maintain multicast opportunities even when cache distributions are highly skewed. Furthermore, when a network becomes crowded and the number of users exceeds the number of available files, Kai Wan et al. showed that a two-stage delivery mechanism—performing intra-file coding followed by inter-file redundancy removal—can compress the broadcast even further by exploiting the fact that multiple users are requesting identical items.

Correlated and Multi-Layer Content

Files in a library often share information, such as different episodes of the same television show or multi-layered video streams. Deniz Gunduz et al. introduced correlation-aware coded caching, which models file similarities as shared subfiles and allocates cache space based on their "level of commonness."

By combining this content awareness with physical-layer channel characteristics, Qianqian Yang et al. and Deniz Gunduz et al. demonstrated that joint cache-channel coding can dramatically reduce transmission power and video distortion over Gaussian broadcast channels. This allows users with poor signal conditions to still decode high-quality video layers by leveraging their local cache state.

Asynchronous Demands

In practice, users do not request videos at the exact same millisecond. To bridge the gap between theoretical synchrony and practical streaming, Qianqian Yang et al. proposed a slotted-time delivery system. This system identifies overlapping data requirements among users who request content at different times, allowing the server to use XOR-based coding to combine multiple requested chunks into a single transmission despite asynchronous arrival patterns.

Beyond Content Delivery: Distributed Data Shuffling

The core intuition of coded caching—using redundant local storage to create coded broadcast opportunities—extends far beyond media streaming. It has become a vital tool for accelerating distributed machine learning.

During the training of large-scale machine learning models, worker nodes must shuffle data chunks between training epochs to ensure the optimization algorithms converge correctly. This shuffling process creates a massive communication bottleneck.

Mohamed Adel Attia et al. and Kai Wan et al. reframed this data shuffling process as a decentralized coded caching problem. Because each worker node already holds the data fragments from the previous epoch in its local memory, that data can be treated as side information.

Worker 1 (Has Chunk X) ── Wants Chunk Y ──┐
                                          ├──> Broadcast: X ⊕ Y
Worker 2 (Has Chunk Y) ── Wants Chunk X ──┘

By broadcasting XOR-coded combinations of data fragments, a central master server (or the workers themselves in a peer-to-peer setup) can satisfy different shuffling requirements for multiple nodes simultaneously, drastically reducing the communication overhead of distributed training.

Pliable and Content-Type Coding

In some modern applications, the strict requirement of delivering a specific file index can be relaxed. For instance, a user might not care which specific advertisement or hummingbird photo they receive, as long as it is a new message belonging to that specific category.

Christina Fragouli introduced Content-Type Coding to exploit this exact flexibility. When clients possess side information and require any new message from a type category, the server gains additional degrees of freedom to choose which specific messages to combine. This flexibility significantly reduces the minimum number of transmissions required to satisfy the network.

To make these relaxed constraints computationally practical, Linqi Song et al. developed deterministic, polynomial-time algorithms for pliable index coding. These algorithms find near-optimal XOR combinations efficiently, proving that coded caching concepts can scale effectively to massive, dynamic data-management systems.

Key Foundational Work

Index Coding Problem with Side Information Repositories (2013) — contributed 2 concept elements to this direction.
Data Dissemination in Wireless Sensor Networks with Network Coding (2010) — contributed 2 concept elements to this direction.
Scalable WiFi Media Delivery through Adaptive Broadcasts (2010) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_xor_based_network_coding_3e0f8d4b,
  title = {XOR-based network coding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/xor-based-network-coding/rdr_3e0f8d4b6d8943a8952991c73ee66b5e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_xor_based_network_coding_3e0f8d4b_v1,
  title = {XOR-based network coding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/xor-based-network-coding/rdr_3e0f8d4b6d8943a8952991c73ee66b5e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake