Skip to Main content Skip to Navigation
Journal articles

An Index Coding Approach to Caching With Uncoded Cache Placement

Abstract : Caching is an efficient way to reduce network trafficcongestion during peak hours, by storing some content at theuser’s local cache memory, even without knowledge of user’slater demands. Maddah-Ali and Niesen proposed a two-phase(placement phase and delivery phase) coded caching strategyfor broadcast channels with cache-aided users. This paper in-vestigates the same model under the constraint that content isplaced uncoded within the caches, that is, when bits of the filesare simply copied within the caches. When the cache contentsare uncoded and the users’ demands are revealed, the cachingproblem can be connected to an index coding problem. Thispaper focuses on deriving fundamental performance limits forthe caching problem by using tools for the index coding problemthat were either known or are newly developed in this work.First, a converse bound for the caching problem under theconstraint of uncoded cache placement is proposed based onthe “acyclic index coding converse bound.” This converse boundis proved to be achievable by the Maddah-Ali and Niesen’sscheme when the number of files is not less than the numberof users, and by a newly derived index coding achievable schemeotherwise. The proposed index coding achievable scheme isbased on distributed source coding and strictly improves on thewidely used “composite (index) coding” achievable bound and itsimprovements, and is of independent interest.An important consequence of the findings of this paper is thatadvancements on the coded caching problem posed by Maddah-Ali and Niesen are thus only possible by considering strategieswith coded placement phase. A recent work by Yuet alhashowever shown that coded cache placement can at most half thenetwork load compared to the results presented in this paper.
Document type :
Journal articles
Complete list of metadatas

Cited literature [41 references]  Display  Hide  Download
Contributor : Delphine Le Piolet <>
Submitted on : Monday, September 28, 2020 - 6:36:21 PM
Last modification on : Wednesday, October 14, 2020 - 4:21:45 AM


Files produced by the author(s)



Kai Wan, Daniela Tuninetti, Pablo Piantanida. An Index Coding Approach to Caching With Uncoded Cache Placement. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2020, 66 (3), pp.1318-1332. ⟨10.1109/tit.2020.2967753⟩. ⟨hal-02951659⟩



Record views


Files downloads