Combinatorial Designs for Coded Caching on Hierarchical Networks

This paper considers a hierarchical caching system where a server connects with multiple mirror sites, each connecting with a distinct set of users, and both mirror sites and users are equipped with caching memories. Although there already exist works studying this setup and proposing coded caching schemes to reduce transmission loads, two main problems are remained to address: 1) the optimal communication load R-1 under the uncoded placement for the first layer is still unknown. 2) the previous schemes are based on Maddah-Ali and Niesen's data placement and delivery, which require high subpacketization level. How to achieve a good tradeoff between transmission loads and subpacketization level for the hierarchical caching system is unclear. In this paper, we aim to address these two problems. We first propose a new combination structure named hierarchical placement delivery array (HPDA), which characterizes the data placement and delivery for a hierarchical caching system. Then we construct two classes of HPDAs, where the first class leads to a scheme achieving the optimal R-1 for some cases, and the second class requires a smaller subpacketization level at the cost of slight increase in transmission loads.

Automated summary

This paper studies a hierarchical caching system with a server and multiple mirror sites, aiming to address two main problems: 1) the unknown optimal communication load under the uncoded placement for the first layer, and 2) the unclear tradeoff between transmission loads and subpacketization level in the existing schemes. The paper proposes a new structure called hierarchical placement delivery array (HPDA) to characterize the data placement and delivery, and constructs two classes of HPDAs to achieve optimal R-1 or lower subpacketization level with slight increase in transmission loads.