The Exact Rate Memory Tradeoff for Large Caches with Coded Placement

• Published in: arXiv.org 2021-01
• Main Authors: Vijith Kumar K P, Rai, Brijesh Kumar, Jacob, Tony
• Format: Article
• Language: English
• Subjects: Caching; Lower bounds; Tradeoffs; User satisfaction
• ISSN: 2331-8422

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\geq\frac{N}{K}(K-1)\). In this paper, we improve this result for large caches with \(M\geq \frac{N}{K}(K-2)\). For the case \(\big\lceil\frac{K+1}{2}\big\rceil\leq N \leq 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\geq \frac{N}{K}\Big(K-2+\frac{(K-2+1/N)}{(K-1)}\Big)\). For the case \(1\leq N\leq \big\lceil\frac{K+1}{2}\big\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\geq \frac{N}{K}(K-2)\).