  To address the exponentially rising demand for wireless content, use of
caching is emerging as a potential solution. It has been recently established
that joint design of content delivery and storage (coded caching) can
significantly improve performance over conventional caching. Coded caching is
well suited to emerging heterogeneous wireless architectures which consist of a
dense deployment of local-coverage wireless access points (APs) with high data
rates, along with sparsely-distributed, large-coverage macro-cell base stations
(BS). This enables design of coded caching-and-delivery schemes that equip APs
with storage, and place content in them in a way that creates coded-multicast
opportunities for combining with macro-cell broadcast to satisfy users even
with different demands. Such coded-caching schemes have been shown to be
order-optimal with respect to the BS transmission rate, for a system with
single-level content, i.e., one where all content is uniformly popular. In this
work, we consider a system with non-uniform popularity content which is divided
into multiple levels, based on varying degrees of popularity. The main
contribution of this work is the derivation of an order-optimal scheme which
judiciously shares cache memory among files with different popularities. To
show order-optimality we derive new information-theoretic lower bounds, which
use a sliding-window entropy inequality, effectively creating a non-cutset
bound. We also extend the ideas to when users can access multiple caches along
with the broadcast. Finally we consider two extreme cases of user distribution
across caches for the multi-level popularity model: a single user per cache
(single-user setup) versus a large number of users per cache (multi-user
setup), and demonstrate a dichotomy in the order-optimal strategies for these
two extreme cases.
