Caching in Combination Networks

We study the throughput of a network formed by one server, k "helpers" and n users. The users may request any file from a fixed library of m files, where each file can be regarded as the realization of an independent random variable with entropy F bits. The users can locally cache up to M F information bits. Each user can connect simultaneously to r helpers. All links in the network (from the server to the helpers, and from the helpers to the users) have normalized capacity of F bits per unit time. We study the achievable download time, expressed in multiples of the time necessary to transmit F bits over a link. In particular, we are interested in minimizing the worst-case download time over all possible demand configurations and realizations of the user-helper connectivity. We present a simple scheme that combines network-coded multicasting and MDS coding and achieves a speed-up factor of 1/r in download time with respect to the case where the server is connected directly to the users through a shared multicast link. We also show that the achieved performance is order-optimal (up to at most a logarithmic factor) in the regime where the total system cache memory is large with respect to the file library size.