Caching in Combination Networks: Novel Multicast Message Generation and\n Delivery by Leveraging the Network Topology

Abstract

Maddah-Ali and Niesen's original coded caching scheme for shared-link\nbroadcast networks is now known to be optimal to within a factor two, and has\nbeen applied to other types of networks. For practical reasons, this paper\nconsiders that a server communicates to cache-aided users through $H$\nintermediate relays. In particular, it focuses on combination networks where\neach of the $K = \\binom{H}{r}$ users is connected to a distinct $r$-subsets of\nrelays. By leveraging the symmetric topology of the network, this paper\nproposes a novel method to general multicast messages and to deliver them to\nthe users. By numerical evaluations, the proposed scheme is shown to reduce the\ndownload time compared to the schemes available in the literature. The idea is\nthen extended to decentralized combination networks, more general relay\nnetworks, and combination networks with cache-aided relays and users. Also in\nthese cases the proposed scheme outperforms known ones.\n