Caching of popular content during off-peak hours is a strategy to reduce network loads during peak hours. Recent work has shown significant benefits of designing such caching strategies not only to deliver part of the content locally, but also to provide coded multicasting opportunities even among users with different demands. Exploiting both of these gains was shown to be approximately optimal for caching systems with a single layer of caches. Motivated by practical scenarios, we consider in this work a hierarchical content delivery network with two layers of caches. We propose a new caching scheme that combines two basic approaches. The first approach provides coded multicasting opportunities within each layer; the second approach provides coded multicasting opportunities across multiple layers. By striking the right balance between these two approaches, we show that the proposed scheme achieves the optimal communication rates to within a constant multiplicative and additive gap. We further show that there is no tension between the rates in each of the two layers up to the aforementioned gap. Thus, both layers can simultaneously operate at approximately the minimum rate. The demand for high-definition video streaming services such as YouTube and Netflix is driving the rapid growth of Internet traffic. In order to mitigate the effect of this increased load on the underlying communication infrastructure, content delivery networks deploy storage memories or caches throughout the network. These caches can be populated with some of the popular content during off-peak traffic hours. This cached content can then be used to reduce the network load during peak traffic hours when users make the most requests. Content caching has a rich history, see for example [1] and references therein. More recently, it has been studied in the context of video-on-demand systems for which efficient content placement schemes have been proposed in [2], [3] among others. The impact of different content popularities on the caching schemes has been investigated for example in [4]- [6] . A common feature among the caching schemes studied in the literature is that those parts of a requested file that are available at nearby caches are served locally, whereas the remaining files parts are served via orthogonal transmissions from an origin server hosting all the files. Recently, [7] , [8] proposed a new caching approach, called coded caching, that exploits cache memories not only to deliver part of the content locally, but also to create coded multicasting opportunities among users with different demands. It is shown there that the reduction in rate due to these coded multicasting opportunities is significant and can be on the order of the number of users in the network. The setting considered in [7] , [8] consists of a single layer of caches between the origin server and the end users. The server communicates directly with all the caches via a shared link, and the objective is to minimize the required transmission rate by the server. For this basic network scenario, coded caching is shown there to be optimal within a constant factor. These results have been extended to nonuniform demands in [9] and to online caching systems in [10] . In practice, many caching systems consist of not only one but multiple layers of caches, usually arranged in a tree-like hierarchy with the origin server at the root node and the users connected to the leaf caches [2], [11] , [12] . Each parent cache communicates with its children caches in the next layer, and the objective is to minimize the transmission rates in the various layers.
A two-level hierarchy of caches was considered in REF , and a scheme that provides coded multicasting opportunities within each layer and across multiple layers was devised and shown to achieve the optimal communication rates to within a constant multiplicative and additive gap.
Hierarchical Coded Caching
IEEE Transactions on Information Theory, vol. 62, pp. 3212 - 3229, June 2014
Computer Science Mathematics