On the Fundamental Limits of Coded Caching Systems with Restricted Demand Types

Caching is a technique to reduce the communication load in peak hours by prefetching contents during off-peak hours. An information theoretic framework for coded caching was introduced by Maddah-Ali and Niesen in a recent work, where it was shown that significant improvement can be obtained compared to uncoded caching. Considerable efforts have been devoted to identify the precise information theoretic fundamental limits of the coded caching systems, however the difficulty of this task has also become clear. One of the reasons for this difficulty is that the original coded caching setting allows all possible multiple demand types during delivery, which in fact introduces tension in the coding strategy. In this paper, we seek to develop a better understanding of the fundamental limits of coded caching by investigating systems with certain demand type restrictions. We first consider the canonical three-user three-file system, and show that, contrary to popular beliefs, the worst demand type is not the one in which all three files are requested. Motivated by these findings, we focus on coded caching systems where every file must be requested by at least one user. A novel coding scheme is proposed, which can provide new operating points that are not covered by any previously known schemes.Grant numbers : ARISTIDES - Aprendizaje Estadístico e Inferencia para Sistemas de Comunicación de Alta Dimensionalidad (RTI2018-099722-B-I00SGR-RC) and Suport als Grups de Recerca, "Grup de Tecnologies de les Comunicacions Ràdio" ( 03 August 2009 - 31 December 2013) ( Project code: 2009SGR1046) projects.© 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works