An Approximation Algorithm for Optimal Clique Cover Delivery in Coded Caching

Seyed Mohammad Asghari, Yi Ouyang, Ashutosh Nayyar, Amir Salman Avestimehr

Introduction

In modern content delivery networks, caching is a fundamental technique used to reduce peak-hour traffic by storing popular content closer to end-users. Coded caching extends this concept by leveraging mathematical XOR operations to satisfy multiple distinct user requests with a single multicast transmission. While theoretical models often assume a centralized "placement phase" where the server dictates cache contents, real-world scenarios frequently involve "arbitrary placement," where users manage their own cache space independently. This paper addresses the delivery challenges inherent in such decentralized environments.

The Arbitrary Placement Problem

When cache placement is arbitrary, the delivery phase transforms into an Index Coding problem. Index coding is notoriously difficult; finding an optimal solution is NP-hard, and even approximation is challenging. In these settings, subfiles required by different users often vary significantly in size. Existing delivery algorithms frequently overlook these size disparities or fail to identify the most efficient combinations of subfiles to XOR together, leading to "zero-padding" and inefficient bandwidth utilization.

The Size-Aware Coded Multicast (SACM) Algorithm

The authors propose the Size-Aware Coded Multicast (SACM) algorithm to optimize data delivery under arbitrary placement. SACM focuses on "clique cover delivery," where the server identifies groups (cliques) of subfiles that can be XORed into a single packet. Each recipient in the group can then decode their requested subfile using their local cache.

The core innovation of SACM is its formulation as a Weighted Set Cover problem. Instead of an exhaustive search for all possible cliques—a computationally prohibitive task—SACM utilizes a Subfile-Based Optimizer (SBO). This function identifies the most efficient clique to transmit by evaluating the number of subfiles covered relative to the size of the resulting XORed packet.

Visualizing the selection of cliques for different user subsets in the SACM algorithm.

Theoretically, SACM achieves a logarithmic approximation ratio of $(1 + \log K)$, where $K$ is the number of users. This represents a significant improvement over the linear ratios found in previous state-of-the-art schemes, ensuring better scalability as the network size grows.

Performance Evaluation

The effectiveness of SACM was evaluated through extensive numerical simulations across systems with 3 to 10 users, using 100 random samples of arbitrary cache placements to ensure robustness.

Performance comparison of SACM against existing coded caching schemes.

The results demonstrate that SACM consistently outperforms existing methods:

  • Bandwidth Reduction: In a 10-user scenario, SACM reduced required bandwidth by up to 72% compared to traditional uncoded delivery.
  • Comparative Advantage: SACM reduced the total bits sent by 15% to 45% compared to the next-best coded schemes, such as GCCM.
  • Small-Scale Optimality: For small systems (e.g., $K=3$) where the true optimal solution is computable, SACM matched the optimal performance exactly, whereas other greedy heuristics fell short.

Conclusion and Future Directions

SACM provides a powerful, size-aware framework for coded caching delivery with arbitrary placement. By bridging the gap between theoretical index coding and practical network constraints, it offers substantial bandwidth savings. While the algorithm's complexity remains exponential ($O(\tau_K K 2^K)$), it is a major step forward from the "double exponential" complexity of exact solvers. Future research may explore non-clique-based strategies, such as interference alignment, to further push the boundaries of delivery efficiency in large-scale decentralized networks.

Summary updated

BibTeX
@inproceedings{asghari2018approximation,
  author = {Seyed Mohammad Asghari and Yi Ouyang and Ashutosh Nayyar and Amir Salman Avestimehr},
  title = {{An Approximation Algorithm for Optimal Clique Cover Delivery in Coded Caching}},
  booktitle = {ICC},
  year = {2018},
  doi = {10.1109/icc.2018.8422194},
}
Figure