Network-Coded Caching-Aided Multicast for Efficient Content Delivery

Consider a content delivery network in which storage and transport resources, characterized by their capacity and cost (e.g., energy) efficiency, are used to meet users' content object requests. The goal is to find the evolution of the objects being stored and transported by the network resources that meets user requests, satisfies network resource capacities and minimizes overall network cost. We first present a constructive offline solution that provides the maximum network efficiency (or minimum cost per object delivered) that can be achieved by dynamically exploiting network-coded caching and multicasting under arbitrary time-varying demands. We refer to the solution scheme as a dynamic network-coded caching-aided multicast (NCCAM) scheme, and illustrate it in a 6-node butterfly network. We then consider a single time period in which each user requests an arbitrary subset of content objects. We formulate the problem as a network coding problem on a caching-augmented graph and show that under uniform demand, random linear coded caching and multicasting is sufficient for achieving minimum cost caching-aided multicast. For the arbitrary demand scenario, we provide the transport-storage cost tradeoff of a polynomial-time distributed solution that uses popularity based uncoded caching and random linear coded transmission. We show that while for skewed Zipf popularity distributions such a simple scheme achieves close to optimal performance, as the Zipf parameter approaches zero (uniform popularity), significant cost reductions can be obtained at the expense of deterministic linear coded transmission schemes of increased computational complexity.