On the Optimal Load-Memory Tradeoff of Cache-Aided Scalar Linear Function Retrieval
On the Optimal Load-Memory Tradeoff of Cache-Aided Scalar Linear Function Retrieval
复制标题
DOI：
10.1109/tit.2021.3066005
复制
发表时间：
2021-06
影响因子：
2.5
通讯作者：
Kai Wan;Hua Sun;Mingyue Ji;Daniela Tuninetti;G. Caire
中科院分区：
文献类型：
--
作者：
Kai Wan;Hua Sun;Mingyue Ji;Daniela Tuninetti;G. Caire
编码缓存有可能通过利用终端用户设备中可用的廉价且丰富的存储来大大减少网络流量，从而在交付阶段创造多播机会。在Maddah-Ali和Niesen（MAN）的开创性工作中，制定了共享链接编码缓存问题，其中每个用户需要一个文件（即，单个文件检索）。本文将MAN缓存问题从二进制域上的单个文件检索推广到任意有限域上的一般标量线性函数检索。所提出的新方案是线性的，基于MAN未编码的缓存放置，并利用干扰对齐的想法。令人惊讶的是，在所有可能的需求中，所提出的方案的最坏情况下的负载与Yu，Maddah-Ali和Avestimehr（YMA）的单文件检索方案的负载相同。因此，所提出的方案具有与YMA相同的最优性保证，即，它在未编码的高速缓存放置的约束下是最优的，否则在因子2内是最优的。然后讨论了该方案的一些扩展。结果表明，该方案不仅适用于任意有限域，而且适用于任意交换环。本文的核心思想也可以扩展到所有的场景，原来的城域网方案已经扩展到，包括但不限于需求私有检索和设备到设备网络。
Coded caching has the potential to greatly reduce network traffic by leveraging the cheap and abundant storage available in end-user devices so as to create multicast opportunities in the delivery phase. In the seminal work by Maddah-Ali and Niesen (MAN), the shared-link coded caching problem was formulated, where each user demands one file (i.e., single file retrieval). This article generalizes the MAN caching problem formulation from single file retrieval on the binary filed to general scalar linear function retrieval on an arbitrary finite field. The proposed novel scheme is linear, based on MAN uncoded cache placement, and leverages ideas from interference alignment. Quite surprisingly, the worst-case load of the proposed scheme among all possible demands is the same as the one of the scheme by Yu, Maddah-Ali, and Avestimehr (YMA) for single file retrieval. The proposed scheme has thus the same optimality guarantees as YMA, namely, it is optimal under the constraint of uncoded cache placement, and is optimal to within a factor 2 otherwise. Some extensions of the proposed scheme are then discussed. It is shown that the proposed scheme works not only on arbitrary finite field, but also on any commutative ring. The key idea of this article can be also extended to all scenarios to which the original MAN scheme has been extended, including but not limited to demand-private retrieval and Device-to-Device networks.