Fundamental Structure of Optimal Cache Placement for Coded Caching with Heterogeneous Demands
Yong Deng, Min Dong · arXiv (Cornell University) · 2019
This paper studies the caching system of multiple cache-enabled users with heterogeneous demands. Under nonuniform file popularity, we thoroughly characterize the structure of the optimal uncoded cache placement for the coded caching scheme (CCS). Formulating the cache placement as an optimization problem to minimize the average delivery rate, we identify the file grouping structure under the optimal solution. We show that, regardless of file popularity, there are at most three file groups under the optimal cache placement. We further characterize the complete structure of the optimal cache placement and obtain the closed-form solution in each possible file grouping case. A simple algorithm is developed to obtain the final optimal cache placement, which only computes a set of candidate closed-form solutions in parallel. We provide insights into the file groups formed by the optimal cache placement. The optimal placement solution also indicates that coding between file groups may be explored during delivery, in contrast to the existing heuristic file grouping schemes. Using the file grouping in the optimal cache placement, we propose a new information-theoretic converse bound for coded caching that is tighter than existing ones. Moreover, using the optimal cache placement solution, we characterize the file subpacketization in the optimal CCS and show that the maximum subpacketization level in the worst case scales as $\mathcal{O}(2^K/\sqrt{K})$ for $K$ users.