Coded Caching under Arbitrary Popularity Distributions Jinbei Zhang',Xiaojun Lin,Xinbing Wangt Dept.of Electronic Engineering,Shanghai Jiao Tong University,China School of Electrical and Computer Engineering,Purdue University,USA Email:abelchina @sjtu.edu.cn,linx @purdue.edu,xwang8@sjtu.edu.cn Abstract-Caching plays an important role in reducing the large (compared to N),this local caching gain will not differ backbone traffic when serving high-volume multimedia content. significantly from 1 (i.e.,the baseline with no-caching).Note Recently,a new class of coded caching schemes have received sig- that the broadcast capability of the system is not exploited here nificant interest because they can exploit coded multi-cast oppor- tunities to further reduce backbone traffic.Without considering because each user can request a different file.In contrast,with file popularity,prior works have characterized the fundamental the coded caching scheme in [7],the worst-case transmission performance limits of coded caching through a deterministic rate at the upstream link is reduced toK(1The worst-case analysis.However,when heterogeneous file popularity is taken into account,there remain open questions regarding the additional factorwhich is referred to as the global fundamental limits of coded caching performance.In this work, caching gain in [7,suggests a significant improvement over for an arbitrary popularity distribution,we first derive a new the uncoded case when the global storage capability KM of information-theoretical lower bound on the expected transmission all users is comparable to,or larger than,N.The key idea rate of any coded caching schemes.We then show that a simple of [7]is to transmit coded packets so that multiple users can coded-caching scheme attains an expected transmission rate that benefit from the same broadcast packet.Thus,the broadcast is at most a constant factor away from the lower bound.Unlike other existing studies,the constant factor that we derived is capability in the system can be exploited even if different users independent of the popularity distribution. request different files.[7]further shows in an information- theoretic sense that the worst-case transmission rate of the coded caching scheme in [7]is at most a constant factor I.INTRODUCTION (specifically,12 times)away from the minimum possible.In As the amount of Internet traffic continues to grow,video is this sense,the performance of the coded caching scheme of [7] expected to dominate 69%of the overall traffic [2],which will is close to the fundamental limit for the system studied.The greatly stress the underlying communication infrastructure. works in [8,14-16]extend this idea to decentralized caching, Historically,caching has played a significant role in reducing hierarchical networks,multiple group-cast,and online caching, the bandwidth requirement for serving video traffic.By placing respectively. contents closer to,or even at the end-users,the bandwidth The studies cited above all focus on the deterministic worst- requirement at the upstream links can be greatly reduced.Most case,i.e.,not only does each user request distinct files,the of such studies of caching have focused on the case where performance of the system is studied against the worst-case uncoded video packets were stored and transmitted (see,e.g., request pattern.Arguably,if the popularity of the files are 3-6]and references therein). identical,the probability of each request pattern will vary Recently,a new class of caching schemes,called coded less significantly.Then,the worst-case performance may not caching [7-16],have gained significant interest because it differ significantly from the average-case performance [9].In can significantly reduce the upstream bandwidth requirement reality,however,the file popularity can differ significantly,and in systems with broadcast/multicast capabilities.Consider K thus some request patterns will occur much more frequently users requesting contents from one server through a shared than other request patterns.As a result,the average-case communication link with broadcast capability.Each user may performance can differ significantly from the worst-case bound request any one of the N files(N>K),but each user only has (see also the discussions at the end of Section I). a storage with size M<N.In the worst case,each user may request a distinct file.With conventional (uncoded)caching While the average-case performance of coded caching un- scheme,it is easy to see that the worst-case transmission rate der heterogeneous file popularity was studied in [9-13].the on the upstream link must be K(1-4).because each user optimality bounds obtained are substantially weaker than the can only cache fraction of all the contents.[7]refers to results in [7]because the gap between the achievable bound this factor (1-)as the local caching gain.Unless M is and the lower bound depends on various system parameters Specifically,in [9],contents are divided into groups with An earlier version of this paper has appeared in Information Theory and similar popularity.Each group is assigned a separate portion Applications Workshop,UCSD,Feb.2015 [1]. of the cache and uses the coded caching scheme of [8.The Copyright (c)2017 IEEE.Personal use of this material is permitted. However,permission to use this material for any other purposes must be gap between the corresponding transmission rate and the lower obtained from the IEEE by sending a request to pubs-permissions@ieee.org bound is found to increase with the total number of groups.1 Coded Caching under Arbitrary Popularity Distributions Jinbei Zhang† , Xiaojun Lin‡ , Xinbing Wang† †Dept. of Electronic Engineering, Shanghai Jiao Tong University, China ‡School of Electrical and Computer Engineering, Purdue University, USA Email: abelchina@sjtu.edu.cn, linx@purdue.edu, xwang8@sjtu.edu.cn Abstract—Caching plays an important role in reducing the backbone traffic when serving high-volume multimedia content. Recently, a new class of coded caching schemes have received sig￾nificant interest because they can exploit coded multi-cast oppor￾tunities to further reduce backbone traffic. Without considering file popularity, prior works have characterized the fundamental performance limits of coded caching through a deterministic worst-case analysis. However, when heterogeneous file popularity is taken into account, there remain open questions regarding the fundamental limits of coded caching performance. In this work, for an arbitrary popularity distribution, we first derive a new information-theoretical lower bound on the expected transmission rate of any coded caching schemes. We then show that a simple coded-caching scheme attains an expected transmission rate that is at most a constant factor away from the lower bound. Unlike other existing studies, the constant factor that we derived is independent of the popularity distribution. I. INTRODUCTION As the amount of Internet traffic continues to grow, video is expected to dominate 69% of the overall traffic [2], which will greatly stress the underlying communication infrastructure. Historically, caching has played a significant role in reducing the bandwidth requirement for serving video traffic. By placing contents closer to, or even at the end-users, the bandwidth requirement at the upstream links can be greatly reduced. Most of such studies of caching have focused on the case where uncoded video packets were stored and transmitted (see, e.g., [3–6] and references therein). Recently, a new class of caching schemes, called coded caching [7–16], have gained significant interest because it can significantly reduce the upstream bandwidth requirement in systems with broadcast/multicast capabilities. Consider K users requesting contents from one server through a shared communication link with broadcast capability. Each user may request any one of the N files (N > K), but each user only has a storage with size M < N. In the worst case, each user may request a distinct file. With conventional (uncoded) caching scheme, it is easy to see that the worst-case transmission rate on the upstream link must be K(1 − M N ), because each user can only cache M N fraction of all the contents. [7] refers to this factor (1 − M N ) as the local caching gain. Unless M is An earlier version of this paper has appeared in Information Theory and Applications Workshop, UCSD, Feb. 2015 [1]. Copyright (c) 2017 IEEE. Personal use of this material is permitted. However, permission to use this material for any other purposes must be obtained from the IEEE by sending a request to pubs-permissions@ieee.org. large (compared to N), this local caching gain will not differ significantly from 1 (i.e., the baseline with no-caching). Note that the broadcast capability of the system is not exploited here because each user can request a different file. In contrast, with the coded caching scheme in [7], the worst-case transmission rate at the upstream link is reduced to K(1− M N ) 1 1+KM/N . The additional factor 1 1+KM/N , which is referred to as the global caching gain in [7], suggests a significant improvement over the uncoded case when the global storage capability KM of all users is comparable to, or larger than, N. The key idea of [7] is to transmit coded packets so that multiple users can benefit from the same broadcast packet. Thus, the broadcast capability in the system can be exploited even if different users request different files. [7] further shows in an information￾theoretic sense that the worst-case transmission rate of the coded caching scheme in [7] is at most a constant factor (specifically, 12 times) away from the minimum possible. In this sense, the performance of the coded caching scheme of [7] is close to the fundamental limit for the system studied. The works in [8, 14–16] extend this idea to decentralized caching, hierarchical networks, multiple group-cast, and online caching, respectively. The studies cited above all focus on the deterministic worst￾case, i.e., not only does each user request distinct files, the performance of the system is studied against the worst-case request pattern. Arguably, if the popularity of the files are identical, the probability of each request pattern will vary less significantly. Then, the worst-case performance may not differ significantly from the average-case performance [9]. In reality, however, the file popularity can differ significantly, and thus some request patterns will occur much more frequently than other request patterns. As a result, the average-case performance can differ significantly from the worst-case bound (see also the discussions at the end of Section II). While the average-case performance of coded caching un￾der heterogeneous file popularity was studied in [9–13], the optimality bounds obtained are substantially weaker than the results in [7] because the gap between the achievable bound and the lower bound depends on various system parameters. Specifically, in [9], contents are divided into groups with similar popularity. Each group is assigned a separate portion of the cache and uses the coded caching scheme of [8]. The gap between the corresponding transmission rate and the lower bound is found to increase with the total number of groups