Novel outer bounds for combination networks with end-user-caches
Kai Wan, Mingyue Ji, Pablo Piantanida, Daniela Tuninetti · 2017
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.