Fundamental Limits of Caching
Top Cited Papers
- 11 March 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 60 (5), 2856-2867
- https://doi.org/10.1109/tit.2014.2306938
Abstract
Caching is a technique to reduce peak traffic rates by prefetching popular content into memories at the end users. Conventionally, these memories are used to deliver requested content in part from a locally cached copy 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 memory available at each individual user). In this paper, we introduce and exploit a second, global, caching gain not utilized by conventional caching schemes. This gain depends on the aggregate global cache size (i.e., the cumulative memory available at all users), even though there is no cooperation among the users. To evaluate and isolate these two gains, we introduce an information-theoretic formulation of the caching problem focusing on its basic structure. For this setting, we propose a novel coded caching scheme that exploits both local and global caching gains, leading to a multiplicative improvement in the peak rate compared with previously known schemes. In particular, the improvement can be on the order of the number of users in the network. In addition, we argue that the performance of the proposed scheme is within a constant factor of the information-theoretic optimum for all values of the problem parameters.Keywords
Other Versions
This publication has 15 references indexed in Scilit:
- Decentralized coded caching attains order-optimal memory-rate tradeoffPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2013
- Fundamental limits of distributed caching in D2D wireless networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2013
- Lexicographic Products and the Power of Non-linear Network CodingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- On the Hardness of Approximating the Network Coding CapacityIEEE Transactions on Information Theory, 2011
- Approximation Algorithms for Data Placement ProblemsSIAM Journal on Computing, 2008
- Elements of Information TheoryPublished by Wiley ,2001
- Placement Algorithms for Hierarchical Cooperative CachingJournal of Algorithms, 2001
- Network information flowIEEE Transactions on Information Theory, 2000
- Dynamic batching policies for an on-demand video serverMultimedia Systems, 1996
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985