Fundamental Limits of Caching

By Mohammad Ali Maddah-Ali, Urs Niesen. IEEE Transactions on Information Theory, 2012

1,768 citations recorded by the source corpus.

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.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/e0ccc22a6a3d8874302e450b2fec897eed66710f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Private function retrieval (2017, background): “Finally, v (θ)W̃[2K+1− 1] and v (θ)W̃[2] are given in (12) and (14), respectively.”
Cache-enabled small cell networks: modeling and tradeoffs (2014, background): “Beside these solutions, information theoretical formulation of the caching problem is studied in [18].”
Coded caching with nonuniform demands (2013, methodology): “g expected link load of HPF under unicast delivery is 2=3F bits. If we allow broadcast delivery, then the expected link load of HPF is (1 p2 A )F= 5=9F. We next describe the coded caching scheme from [1]. We split each ﬁle into two parts of equal size so that A= (A 1;A 2) and B= (B 1;B 2). Store A 1”
A Fundamental Tradeoff Between Computation and Communication in Distributed Computing (2016, methodology): “The idea of efficiently creating and exploiting coded multicasting was initially proposed in the context of cache networks in [20], [21], and extended in [22], [23], where caches prefetch part of the content in a way to enable coding during the content delivery, minimizing the network traffic.”
White Paper on Broadband Connectivity in 6G (2020, methodology): “Coded caching (CC) was proposed in [123] as a way to increase the data rate, with the help of cache memories available throughout the network.”
Optimal and Scalable Caching for 5G Using Reinforcement Learning of Space-Time Popularities (2017, background): “Finally, recent studies have investigated the role of coding for enhancing performance in cache-enabled networks [18]–[20]; see also [21], [22], and [23], where device-to-device “structure-”
Decentralized coded caching attains order-optimal memory-rate tradeoff (2013, methodology): “Corollary 3 shows that the rate achieved by the decentralized coded caching scheme given by Algorithm 1 is at most a factor 12 worse than the one of the best known centralized algorithm from [8].”
Hierarchical coded caching (2014, background): “This single-layer setting was recently studied in [7], [8], where the authors proposed a coded caching scheme.”
Wireless caching: technical misconceptions and business barriers (2016, methodology): “Furthermore a recent technique [4] combined caching with coding and revolutionized how goodput scales in bandwidth-limited networks.”
Speeding Up Distributed Machine Learning Using Codes (2015, methodology): “Our coded shuffling algorithm is built upon the coded caching scheme by Maddah-Ali and Niesen [67].”
Wireless Device-to-Device Caching Networks: Basic Principles and System Performance (2013, methodology): “The coded multicasting approach in [25] constructs the cache contents and the coded delivery scheme in a combinatorial manner which does not scale well with n.”
High-Reliability and Low-Latency Wireless Communication for Internet of Things: Challenges, Fundamentals, and Enabling Technologies (2019, background): “, intermediate node caching or terminal caching [146].”
Caching at the wireless edge: design aspects, challenges, and future directions (2016, methodology): “In [3], an ingenious coded-multicast strategy was proposed, which precaches partial contents possibly requested by all the users with a carefully designed network coding.”
A Survey on Device-to-Device Communication in Cellular Networks (2013, background): “conventional unicast video transmission as well as the coded broadcasting [97].”
Analysis on Cache-Enabled Wireless Heterogeneous Networks (2015, methodology): “, [16] proposes a novel coded caching scheme to improve both the local and the global caching gain.”
FemtoCaching: Wireless Content Delivery Through Distributed Caching Helpers (2013, background): “Coded caching, posed as an index coding problem, has been studied in [30], [31] where a single base station is the only transmitter, the users cache content individually and user demands are arbitrary.”
A Survey on Mobile Edge Networks: Convergence of Computing, Caching and Communications (2017, background): “online caching, is a future direction of caching researches [154].”
Fundamental Limits of Caching in Wireless D2D Networks (2014, methodology): “Before proceeding in the presentation of our results, we would like to make a few remarks to clarify obvious questions and anticipate possible concerns that this line of work (see for example [2], [3], [5]–[8], [10], [21]–[32]) may raise.”
Coded MapReduce (2015, background): “1) Server 3 sends intermediate pairs (A, 11)[7], (A, 14)[8], (A, 10)[9], (A, 15)[10], (A, 15)[11], (A, 10)[12] and then (B, 21)[7], (B, 21)[8], (B, 21)[9], (B, 21)[10], (B, 21)[11], (B, 21)[12].”
A Survey on Low Latency Towards 5G: RAN, Core Network and Caching Solutions (2017, background): “Centralized caching [134]–[136], [139], [141], [143]–[149], [151]–[155] Various centralized caching is investigated with assumption that a coordinator with access to almost all the information about the storage capacities of different BSs, the connectivity of the users and BSs, and etc. Distributed…”