Rate-Memory Trade-off for Multi-Access Coded Caching With Uncoded Placement

Kota Srinivas Reddy

doi:10.1109/TCOMM.2020.2980817

2020-06-01

Kota Srinivas Reddy *

Nikhil Karamchandani

DOI：10.1109/TCOMM.2020.2980817

原文链接

原文求助

摘要

En 中文

We study a multi-access variant of the popular coded caching framework, which consists of a central server with a catalog of N files, K caches with limited memory M, and K users such that each user has access to L consecutive caches with a cyclic wrap-around and requests one file from the central server's catalog. The server assists in file delivery by transmitting a message of size R over a shared error-free link and the goal is to characterize the optimal rate-memory trade-off. This setup was studied previously by Hachem et al., where an achievable rate and an information-theoretic lower bound were derived. However, the multiplicative gap between them was shown to scale linearly with the access degree L and thus order-optimality could not be established. A series of recent works have used a natural mapping of the coded caching problem to the well-known index coding problem to derive tighter characterizations of the optimal rate-memory trade-off under the additional assumption that the caches store uncoded content. We follow a similar strategy for the multi-access framework and provide new bounds for the optimal rate-memory tradeoff R*(M) over all uncoded placement policies. In particular, we derive a new achievable rate for any L >= 1 and a new lower bound, which works for any uncoded placement policy and L >= K/ 2. We then establish that the (multiplicative) gap between the new achievable rate and the lower bound is at most 2 independent of all parameters, thus establishing an order-optimal characterization of R* (M) for any L >= K/2. This is a significant improvement over the previously known gap result, albeit under the restriction of uncoded placement policies. Finally, we also characterize R* (M) exactly for a few special cases.

Keyword:

Content delivery network

caching

index coding problem (ICP)