Towards the Optimal Rate Memory Tradeoff in Caching With Coded Placement
Vijith Kumar K P, Brijesh Kumar Rai, Tony Jacob · IEEE Transactions on Information Theory · 2022
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\leq \frac {1}{K}$and large caches where$M\geq N-\frac {N}{K}$. For the case$N \leq K \leq 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\leq \frac {1}{K}+\frac {1}{K(N-1)}$and$M\geq N-\frac {N}{K}-\frac {N-1}{K(K-1)}$. For the case$2N-1\leq 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\geq N-\frac {2N}{K}$. We also derive a new lower bound for small caches, which improves upon previously known lower bounds.