Symmetry, demand types and outer bounds in caching systems
Chao Tian · 2016
The fundamental limit of coded caching is considered in this work. We started with an investigation of the symmetry structure in the caching problem, which is used to show the existence of optimal symmetric solutions, as well as to motivate the notion of demand types. With a combination of analytical analysis using the symmetry and a computational approach developed earlier for the regenerating code problem, we obtain the following results on the memory-rate tradeoff: (1) A complete solution for any systems with K = 2 users; (2) A complete solution for the case with N = 2 files and K = 3 users; (3) The best outer bound for the cases (N, K) = (2, 4) and (N, K) = (3, 3) in the literature, which are tight in certain regimes. These results provide new insights to the problem, and also help to identify the main coding challenges for different system parameters.