Fundamental Limits of Caching

Caching is a technique to reduce peak traffic rates by prefetching popular content in memories at the end users. One benefit of this prefetching, which is traditionally exploited by caching strategies, is to deliver requested content in part from the local caches rather than through the network. The gain offered by this approach, which we term local caching gain, depends on the local cache size (i.e, the cache available at each individual user). In this paper, we identify a second gain, which we term global caching gain. This gain depends on the aggregate global cache size (i.e., the cumulative cache available at all users), even though there is no cooperation among the caches. To evaluate and isolate these two gains, we introduce a new, information-theoretic formulation of the caching problem focusing on its basic structure. We propose an achievable scheme for this setting that exploits both local and global caching gains. We show that the proposed scheme can significantly outperform conventional caching strategies. In particular, the rate required by the proposed scheme can be smaller by a factor on the order of the number of users in the network compared to conventional caching strategies. Moreover, we argue that the performance of the proposed scheme is within at most a factor 12 from the information-theoretic optimum for all values of the problem parameters.