Coded Caching for Files with Distinct File Sizes

Abstract—Coded caching can exploit new multicast opportuni-ties even when multiple users request different pieces of content, and thus can significantly reduce the backhaul requirement for serving high-volume content. However, existing studies of coded caching have been limited to the scenarios where all files of interest are of a common size. This work studies the performance limits of coded caching when the file sizes are different. We derive a new lower bound and an achievable upper bound for the worst-case transmission rate under coded caching, and show that these two bounds differ by at most a Θ(logK) factor, whereK is the number of users in the system. There are two key novelties in our analysis. First, our lower bound is derived by considering a new cut-set bound where larger files are requested more times. The analysis of this new cut-set bound requires careful concatenation of several entropy inequalities. Compared to a lower bound using standard cut-set arguments, our lower bound is improved by a Θ(logK) factor. Second, our achievable scheme uses a caching probability that increases proportionally with the file size. Compared to schemes that use a common caching probability, the achievable rate of our scheme is reduced by a Θ ( K log2K factor. I