Towards The Optimal Rate Memory Tradeoff in Caching with Coded Placement

The idea of coded caching for content distribution networks was introduced by Maddah-Ali and Niesen, who considered the canonical (N, K) cache network in which a server with N, files satisfies the demands of K users (each equipped with an independent cache of size M). The optimal rate memory tradeoff for demands where all files are requested by at least one user has been characterized only for small caches where M ≤ ¹⁄_K and large caches where M ≥ N-^N⁄_K. For the case N ≤ K ≤ 2N-1 , we derive new lower bounds for small and large caches and propose a new coded caching scheme for large caches. Along with the scheme proposed by Gómez-Vilardebó, this leads to a characterization of the optimal rate memory tradeoff for M≤ ¹⁄_K+ ¹⁄_K(N-1) and M ≥ N- ^N⁄_K- ^N-1⁄_K(K-1). For the case 2N-1≤ K, we derive a new lower bound for large caches, which proves the optimality of the scheme proposed by Yu et al. and leads to a characterization of the optimal rate memory tradeoff for M≥ N- ^2N⁄_K. We also derive a new lower bound for small caches, which improves upon previously known lower bounds.

Download paper here

@inproceedings{kumar2019towards,
  title={Towards the exact rate memory tradeoff in coded caching},
  author={Vijith Kumar, K P and Rai, Brijesh Kumar and Jacob, Tony},
  journal={IEEE Transactions on Information Theory},
  year={2022},
  publisher={IEEE}
}