An Index Coding Approach to Caching With Uncoded Cache Placement
An Index Coding Approach to Caching With Uncoded Cache Placement
复制标题
DOI：
10.1109/tit.2020.2967753
复制
发表时间：
2020-03-01
影响因子：
2.5
通讯作者：
Piantanida, Pablo
中科院分区：
文献类型：
--
作者：
Wan, Kai;Tuninetti, Daniela;Piantanida, Pablo
缓存是一种减少高峰时段网络流量拥塞的有效方法，它可以将一些内容存储在用户的本地缓存中，即使不知道用户以后的需求。 Maddah-Ali 和 Niesen 提出了一种针对具有缓存辅助用户的广播频道的两阶段（放置阶段和交付阶段）编码缓存策略。本文研究了在内容未编码地放置在缓存中的约束下的相同模型，即文件的位被简单地复制到缓存中。当缓存内容未编码并且用户需求被揭示时，缓存问题可以与索引编码问题联系起来。本文重点是通过使用本工作中已知的或新开发的用于索引编码问题的工具来导出缓存问题的基本性能限制。首先，基于“非循环索引编码逆界”，提出了未编码缓存放置约束下的缓存问题的逆界。当文件数量不小于用户数量时，这个逆界被证明可以通过 Maddah-Ali 和 Niesen 的方案来实现，否则通过新导出的索引编码可实现的方案来实现。所提出的索引编码可实现方案基于分布式信源编码，严格改进了广泛使用的“复合（索引）编码”可实现界限及其改进，并且具有独立的兴趣。本文研究结果的一个重要结果是，只有考虑编码放置阶段的策略，才能在 Maddah-Ali 和 Niesen 提出的编码缓存问题上取得进展。然而，Yu 等人最近的一项工作表明，与本文中提出的结果相比，编码缓存放置最多可以减少一半的网络负载。
Caching is an efficient way to reduce network traffic congestion during peak hours, by storing some content at the user's local cache memory, even without knowledge of user's later demands. Maddah-Ali and Niesen proposed a two-phase (placement phase and delivery phase) coded caching strategy for broadcast channels with cache-aided users. This paper investigates the same model under the constraint that content is placed uncoded within the caches, that is, when bits of the files are simply copied within the caches. When the cache contents are uncoded and the users' demands are revealed, the caching problem can be connected to an index coding problem. This paper focuses on deriving fundamental performance limits for the caching problem by using tools for the index coding problem that were either known or are newly developed in this work. First, a converse bound for the caching problem under the constraint of uncoded cache placement is proposed based on the "acyclic index coding converse bound." This converse bound is proved to be achievable by the Maddah-Ali and Niesen's scheme when the number of files is not less than the number of users, and by a newly derived index coding achievable scheme otherwise. The proposed index coding achievable scheme is based on distributed source coding and strictly improves on the widely used "composite (index) coding" achievable bound and its improvements, and is of independent interest. An important consequence of the findings of this paper is that advancements on the coded caching problem posed by Maddah-Ali and Niesen are thus only possible by considering strategies with coded placement phase. A recent work by Yu et al has however shown that coded cache placement can at most half the network load compared to the results presented in this paper.