Novel outer bounds for combination networks with end-user-caches
Novel outer bounds for combination networks with end-user-caches
复制标题
具有最终用户缓存的组合网络的新颖外部边界
DOI：
10.1109/itw.2017.8277986
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Daniela Tuninetti
中科院分区：
文献类型：
--
作者：
Kai Wan;Mingyue Ji;P. Piantanida;Daniela Tuninetti
本文研究了网络中的内存大小M和下载时间/速率R之间的权衡，其中一个服务器与N个文件连接到H个中继（无缓存），而H个中继又连接到K个用户，这些用户配备了大小为M的文件的缓存。当每个用户连接到r个中继的不同子集时，即，K =（Hr），该系统被称为具有最终用户缓存的组合网络。在这项工作中，外边界推导出的实际动机的情况下，未编码的缓存内容，也就是说，位的各种文件被直接复制在用户缓存没有任何编码。在这种情况下，一旦该高速缓存的内容和用户需求是已知的，该问题就简化为一般的索引编码问题。本文表明，依赖于一个众所周知的“非循环索引编码外边界”的结果是不紧的最终用户缓存的组合网络（而不是没有中继的情况下）的边界，并提供了两种新的方法来获得最严格的已知的外边界。作为独立兴趣的结果，一个不等式，推广了著名的熵的子模。
This paper studies the tradeoff between the memory size M and the download time / rate R∗ for networks where a server with N files is connected to H relays (without caches), which in turns are connected to K users equipped with caches of size M files. When each user is connected to a different subset of r relays, i.e., K = (Hr), the system is referred to as a combination network with end-user-caches. In this work, outer bounds are derived for the practically motivated case of uncoded cache contents, that is, bits of the various files are directly copied in the user caches without any coding. In this case, once the cache contents and the user demands are known, the problem reduces to a general index coding problem. This paper shows that relying on a well known “acyclic index coding outer bound” results in bounds that are not tight for combination networks with enduser-caches (as opposed to the case without relays) and provides two novel ways to derive the tightest known outer bounds to date. As a result of independent interest, an inequality that generalizes the well-known sub-modularity of entropy is derived.