Coded Caching with Nonuniform Demands

We consider a network consisting of a file server connected through a shared link to a number of users, each equipped with a cache. Knowing the popularity distribution of the files in the database, the goal is to optimally populate the caches such as to minimize the expected rate over the shared link. For a single user, it is well known that caching the most popular files is optimal in this setting. In this paper, we show that this is no longer the case once we consider multiple users. Indeed, caching only the most popular files can be highly suboptimal. Instead, we propose a coded caching scheme and prove that it is close to optimal.