Hierarchical coded caching

By Nikhil Karamchandani, Urs Niesen, Mohammad Ali Maddah-Ali, Suhas N. Diggavi. 2014 IEEE International Symposium on Information Theory, 2014

352 citations recorded by the source corpus.

It has recently been demonstrated that for single-layer cache networks, jointly designing caching and delivery can enable significant benefits over conventional caching. This was based on strategically designing the cached content to induce coded multicasting opportunities even among users with different demands and without foreknowledge of the user demands. In this work, we extend this coded caching approach to a multi-hop hierarchical content delivery network with two layers of caches. We propose a new caching scheme that combines two basic approaches. The first approach provides coded multicasting opportunities within each layer (through decoding and forwarding); the second approach provides coded multicasting opportunities across multiple layers (through strategic forwarding without decoding). By striking the right balance between these two approaches, we show that the proposed scheme achieves the optimal communication rates to within a constant multiplicative and additive gap. We further show that there is no tension between the rates in each of the two layers up to the aforementioned gap. Thus, both layers can simultaneously operate at approximately the minimum rate.

Subfields: Computer Networks and Communications

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

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

Online Coded Caching (2013, background): “Since the long-term average of the optimal scheme is less than or equal to ¯ R , this implies ¯ R ⋆ ≤ ¯ R ≤ 2 R ( M, N, K ) + 6 , concluding the proof of the upper bound in Theorem 1.”
The Exact Rate-Memory Tradeoff for Caching With Uncoded Prefetching (2016, methodology): “Beyond these works, the techniques can also be applied in directions such as online caching [18], caching with non-uniform demands [19], and hierarchical caching [24], where improvements can be immediately achieved by directly plugging in our results.”
Coded MapReduce (2015, background): “The idea of efficiently creating and exploiting coded multicasting was initially proposed in the context of cache networks in [11], [12], and extended in [13], [14], where caches pre-fetch part of the content in a way that coding opportunities can be optimally exploited to reduce network traffic dur”
Speeding Up Distributed Machine Learning Using Codes (2015, neutral): “Coded caching has been studied in many scenarios such as decentralized coded caching [67], online coded caching [68], hierarchical coded caching for wireless communication [69], and device-to-device coded caching [70].”
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.”