On the optimality of uncoded cache placement

Wan Kai (1) , Daniela Tuninetti (2) , Pablo Piantanida (1)

1 L2S - Laboratoire des signaux et systèmes
2 Department of Electrical and Computer Engineering University of Illinois at Chicago

Caching is an effective way to reduce peak-hour network traffic congestion by storing some contents at user's local cache. Maddah-Ali and Niesen (MAN) initiated a fundamental study of caching systems by proposing a scheme (with uncoded cache placement and linear network coding delivery) that is provably optimal to within a factor 4.7. In this paper, when the cache contents and the user demands are fixed, we connect the caching problem to an index coding problem and show the optimality of the MAN scheme under the conditions that (i) the cache placement phase is restricted to be uncoded (i.e, pieces of the files can only copied into the user's cache), and (ii) the number of users is no more than the number of files. As a consequence, further improvements to the MAN scheme are only possible through the use of coded cache placement.

Domaines: Théorie de l'information [cs.IT]; Réseaux et télécommunications [cs.NI]; Théorie de l'information et codage [math.IT]; Statistiques [math.ST]

Wan Kai, Daniela Tuninetti, Pablo Piantanida. On the optimality of uncoded cache placement. Information Theory Workshop (ITW), 2016 IEEE, Sep 2016, cambridge, United Kingdom. ⟨10.1109/ITW.2016.7606816⟩. ⟨hal-01436898⟩