论文标题
对称未编码的缓存方案，子包装水平较低
Symmetric uncoded caching schemes with low subpacketization levels
论文作者
论文摘要
缓存是内容交付网络中常用的技术，旨在以最有效的方式传递从托管服务器到用户的信息。 2014年，麦达·阿里（Maddah-Ali）和尼森（Niessen）将缓存提出了正式的信息理论问题，从那时起，它引起了很多关注。众所周知，Ali-Niesen和Yu等人提出的缓存方案。 al。即最佳，也就是说，他们需要从服务器中最少的传输来满足所有用户的需求。但是，要使这些方案工作，每个文件都需要将每个文件分配到$ f^*$ subfiles（$ f^*$称为文件的子包装级别），$ f^*$在用户的数字$ k $中成倍增长。结果，在实际情况下应用这些方案是有问题的，在实际情况下，$ k $往往很大。存在以下问题：（1）是否有最佳方案将每个文件分配为$ f $ subfiles，其中$ f $不是指数级的，例如，$ k $中的多项式？ （2）如果这个问题的答案是否定的，是否有一个近乎最佳的方案，该方案在\ cite {ali1，yu}中与$ f $ polyenmial in $ k $中的方案一样好？这两个问题都是开放的。 本文我们的主要贡献是为上述问题提供答案。首先，我们证明，在对用户缓存率的一些轻度限制下，没有$ f $小于$ f^*$的最佳方案。此外，在这种情况下，我们为存在最佳方案提供了必要和充分的条件。其次，我们为上述明确的结构和详细的绩效分析提出的第二个问题提供了肯定的答案。
Caching is a commonly used technique in content-delivery networks which aims to deliver information from hosting servers to users in the most efficient way. In 2014, Maddah-Ali and Niessen formulated caching into a formal information theoretic problem and it has gained a lot of attention since then. It is known that the caching schemes proposed by Ali-Niesen and Yu et. al. are optimal, that is, they require the least number of transmissions from the server to satisfy all users' demands. However for these schemes to work, each file needs to be partitioned into $F^*$ subfiles ($F^*$ is called the subpacketization level of files) with $F^*$ growing exponentially in the number $K$ of users. As a result, it is problematic to apply these schemes in practical situations, where $K$ tends to be very large. There rise the following questions: (1) are there optimal schemes in which each file is partitioned into $F$ subfiles, where $F$ is not exponential, say polynomial for example, in $K$? (2) if the answer to this question is no, is there a near-optimal scheme, a scheme which is as asymptotically good as the one in \cite{ali1,yu}, with $F$ polynomial in $K$? Both these questions are open. Our main contribution in this paper is to provide answers to above questions. Firstly, we prove that under some mild restriction on user's cache rate, there are no optimal schemes with $F$ smaller than $F^*$. Moreover, we give necessary and sufficient conditions for the existence of optimal schemes in this case. Secondly, we provide an affirmative answer to the second question raised above by an explicit construction and a detailed performance analysis.
