The Exact Rate Memory Tradeoff for Large Caches with Coded Placement

Abstract

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 satisfy the demands of $K$ users (equipped with independent caches of size $M$ each). Among other results, their work provided a characterization of the exact rate memory tradeoff for the problem when $M\ge \frac{N}{K}(K-1)$. In this paper, we improve this result for large caches with $M\ge \frac{N}{K}(K-2)$. For the case $\lceil \frac{K+1}{2}\rceil \le N\le K$, we propose a new coded caching scheme, and derive a matching lower bound to show that the proposed scheme is optimal. This extends the characterization of the exact rate memory tradeoff to the case $M\ge \frac{N}{K}(K-2+\frac{(K-2+1/N)}{(K-1)})$. For the case $1\le N\le \lceil \frac{K+1}{2}\rceil$, we derive a new lower bound, which demonstrates that the scheme proposed by Yu et al. is optimal and thus extend the characterization of the exact rate memory tradeoff to the case $M\ge \frac{N}{K}(K-2)$.