On the Fundamental Limits of Caching in Combination Networks

The capacity of caching networks has received considerable attention in the past few years. The problem consists of finding the minimum rate (or load) to deliver all users' requested messages from the sources and/or caches in the network. In particular, the capacity of two network models, shared link caching networks and device-to-device caching networks, is relatively well understood. To advance the understanding of the capacity of more general caching networks, in this paper, we study a class of networks of increasing practical interest, namely, the combination caching networks. These networks are formed by a single source connected to n = (_r^k) user nodes through a layer of k relay nodes, such that each user node is connected to a unique subset of r relay nodes, and caching takes place at the user nodes only. In this setting, particularly useful to model heterogeneous wireless and wireline networks, we show that, in most parameter regimes, by using a concatenated coded multicasting - combination network coding (CM-CNC) scheme, the achievable maximum link load is inversely proportional to the per-user storage capacity M and to the degree of each user r. In addition, we provide an information theoretic converse and show that the gap between achievability and converse bounds is within a logarithmic factor of the system parameters in most regimes of practical interest