Combination Networks with Caches: Novel Inner and Outer Bounds with Uncoded Cache Placement.
Kai Wan, Mingyue Ji, Pablo Piantanida, Daniela Tuninetti · arXiv (Cornell University) · 2017
Caching is an efficient way to reduce network traffic congestion during peak hours by storing some content at the user's local cache memory. For the shared-link network with end-user-caches, Maddah-Ali and Niesen proposed a two-phase coded caching strategy, referred to as MAN. In practice, users may communicate with the server through intermediate relays. 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=\binom{H}{r}$, the system is referred to as a combination network with end-user-caches. In this work, converse 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 converse bound results in bounds that are not tight for combination networks with end-user-caches and provides two novel ways to derive the tightest known converse bounds to date. As a result of independent interest, an inequality that generalizes the well-known sub-modularity of entropy is derived. Several novel caching schemes are proposed, based on the MAN cache placement. These schemes leverage the structure of the combination network and perform interference elimination at the end-users. The proposed schemes are proved: (i) to be (order) optimal for some parameters regimes of (N,M,H,r) with or without the constraint of uncoded cache placement, and (ii) to outperform the state-of-the-art schemes in numerical evaluations.