Coded caching for cache-aided communication and computing with nonuniform demands

Abstract

In this dissertation, we consider the caching system of multiple cache-enabled users with nonuniform demands. We thoroughly characterize the structure of the optimal cache placement of the coded caching scheme (CCS).We show there are at most three file groups in the optimal placement and obtain the closed-form solution in each file grouping case. A simple algorithm is developed to obtain the final optimal cache placement, which only computes a set of closed-form solutions in parallel. We propose a tighter lower bound for caching and characterize the file subpacketization in the optimal CCS. Upon obtaining the optimal placement of the CCS, we characterize the memory-rate tradeoff for caching with uncoded placement. Focusing on the modified coded caching scheme( MCCS), we formulate a cache placement optimization problem to obtain the optimal placement. We present two lower bounds for caching with uncoded placement and compare them with the MCCS to characterize the memory-rate tradeoff and provide insights. We extend our study to accommodate both nonuniform file popularity and sizes and characterize the exact memory-rate tradeoff for two users. We then study the memory-rate tradeoff for decentralized caching. We formulate the cache placement optimization problem for the decentralized modified coded caching scheme (D-MCCS). To solve this non-convex problem, we develop a successive Geometric Programming (GP) approximation algorithm and a two-file-group-based low-complexity approach. We propose a lower bound for decentralized caching and compare it with the optimized D-MCCS to characterize the memory-rate tradeoff in special cases. Beyond caching problems, we consider the coded distributed computing (CDC) with arbitrary number of files of nonuniform popularity. We formulate a mixed-integer linear programming (MILP) problem that jointly optimizes the mapping and shuffling strategies to minimize the shuffling load. To solve this generally NP-hard problem, we propose a two-file-group-based low-complexity approach that achieves close shuffling load as conventional branch-and-cut method which has high computational complexity.