Memory-Rate Tradeoff for Caching With Uncoded Placement Under Nonuniform Random Demands

This paper considers a caching system of a single server and multiple users. We aim to characterize the memory-rate tradeoff for caching with uncoded cache placement, under nonuniform file popularity. Focusing on the modified coded caching scheme (MCCS) recently proposed by Yu, etal. , we formulate the cache placement optimization problem for the MCCS to minimize the average delivery rate under nonuniform file popularity, restricting to a class of popularity-first placements. We then present two information-theoretic lower bounds on the average rate for caching with uncoded placement, one for general cache placements and the other restricted to the popularity-first placements. By comparing the average rate of the optimized MCCS with the lower bounds, we prove that the optimized MCCS attains the general lower bound for the two-user case, providing the exact memory-rate tradeoff. Furthermore, it attains the popularity-first-based lower bound for the case of general $K$ users with distinct file requests. In these two cases, our results also reveal that the popularity-first placement is optimal for the MCCS, and zero-padding used in coded delivery incurs no loss of optimality. For the case of $K$ users with redundant file requests, our analysis shows that there may exist a gap between the optimized MCCS and the lower bounds due to zero-padding. We next fully characterize the optimal popularity-first cache placement for the MCCS, which is shown to possess a simple file-grouping structure and can be computed via an efficient algorithm using closed-form expressions. Finally, we extend our study to accommodate nonuniformity in both file popularity and size, where we show that the optimized MCCS attains the lower bound for the two-user case, providing the exact memory-rate tradeoff. Numerical results show that, for general settings, the gap between the optimized MCCS and the lower bound only exists in limited cases and is very small.