Coded Caching under Arbitrary Popularity Distributions

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

3 [10]studies a popularity model that can be viewed as an popularity distributions(see further discussions in Section IID). intermediate between worst-case analysis and average-case We establish this lower bound by a series of reduction and analysis.It models non-uniform popularity by assuming that merging steps that convert the original system with hetero- the file popularity has L different levels.Both the number of geneous popularity to other systems with uniform popularity. files at each level and the number of users requesting files Using these techniques,we are able to quantify the impact at each level are fixed.The authors then study the deter- of both "popular"files and "non-popular"files,which we ministic worst-case performance under such a setting.When believe is the main reason that we can obtain sharp constant- the number of users is large,this model can be seen as an factor characterizations even in the non-asymptotic settings. approximation of a stochastic-demand model.The theoretical (See further discussions at the end of Section IV.D.)These gap between the achievable transmission rate and the lower techniques may be of independent interest for future studies bound established in [10]increases as L3.The work in [13] of coded caching performance.Third,while our achievable is most related to ours.In [13],the authors propose a large scheme is similar to RLFU proposed [13](in the sense that class of achievable schemes,called RAP-GCC and RAP- for most parameter settings we divide the files into 2 groups, CIC,which place files in caches according to a popularity- correspondingly to popular and unpopular files,respectively), dependent caching distribution.However,because the optimal there are parameter settings where we need to divide the files caching distribution for RAP-GCC and RAP-CIC may not into 3 groups.This new modification turns out to be important have analytically tractable solutions in general,[13]then for attaining the constant-factor performance gap under all focuses on a sub-class of RAP-GCC,called RLFU (Random popularity distributions and non-asymptotic settings.Further, Least-Frequently-Used caching),to study the performance gap our division between popular and unpopular files uses a simple between the lower bound and achievable bound of the required threshold Ni.Specifically,suppose that the number of users is transmission rate.RLFU uses a clever and surprisingly simple K and the size of each user's storage is M.Then,the threshold caching distribution that divides the contents into 2 groups. Ni corresponds to the least-popular file among those whose Although both the lower bound and the achievable bound (by popularity is no smaller thanwhere M-max(M,3). RLFU)are given in [13]for arbitrary popularity distributions, Compared with the choice of the threshold (denoted by m) the gap between the achievable bound and the lower bound in [13 (either chosen as a function of the Zipf distribution is shown to be a constant only when the file popularity in the theoretical analysis,or obtained via a 1-dimensional follows a Zipf distribution.Note that the gaps estimated by optimization over an achievable bound).our choice of N the theoretical results of [13]depend on the parameters of the is in a simple closed-form that works for arbitrary popular Zipf distribution,and may also become large for certain ranges distributions (see further discussions in Section II).Finally, of the parameter values [13].Further,the constant factors are note that the RLFU scheme in [13]with the optimal threshold only shown in the asymptotic limit when the number of files m should in general attain a better performance than the and/or the number of users are large.Therefore,it remains an simpler choice of Ni in this paper.Thus,it implies that RLFU important open question what is the fundamental limit of the combined with appropriately dividing the files into 3 groups performance of coded caching for the more practical scenario under certain settings also attains an average transmission rate of heterogeneous file popularity,and whether one can find a that is away from the optimal by at most a constant factor, coded-caching scheme whose performance gap from the lower independently of the popularity distribution.(This immediately bound is independent of the popularity distribution even in the follows that the best scheme in the larger class of RAP-GCC non-asymptotic settings. will also attain a constant-factor gap.)However,the RLFU In this paper,we make the following contributions to answer scheme itself without the 3-group modification does not have the above open question.First,we show that a simple coded- this constant-factor performance guarantees under arbitrary caching scheme(which is a special case of RAP-GCC in [13] popularity distribution (see Section IID). and is also similar to RLFU)can attain an average transmission The remainder of this paper is as follows.We first present rate that is at most 55 times from the optimal.Although this the network model in Section II.Main results are summarized factor appears to be large,it is the first result in the literature in Section III.Followed is the analysis on the information with a constant-factor gap that is independent of the popularity theoretical lower bound in Section IV.The achievable scheme distributions and the system size.In contrast,as we discussed is analyzed in Section V.The gap between the lower bound earlier,the performance gap in prior studies could be arbitrar- and the achievable rate is derived in Section VI.Simulation ily large depending on either the number of groups [9],the results are presented in Section VII.Then,we conclude. number of levels [10],or the parameter of the Zipf distribution [11-13].Second,a key step towards this result is to use a new II.NETWORK MODEL construction in Section IV to establish a sharper lower bound In the following,we present the network model for a (in the order sense)on the achievable transmission rate of any video delivery system with both local caches and broadcast schemes.Specifically,our lower bound may be higher than the capabilities (see Figure 1). lower bound in [13]by an arbitrarily large factor under certain We assume that there are N distinct files from the setF= (F,F2,...,FN.The popularity of the file Fi is pi,where I Note that the conference version of this paper [1]not only shows a larger multiplicative factor,but also requires a small additive factor.The results in 1.Without loss of generality,we assume that the this paper use a more-refined analysis that eliminates the need for the additive file size is of unit length and the file popularity is decreasing factor. in the index,i.e.,P:≥Pi if i≤j

2 [10] studies a popularity model that can be viewed as an intermediate between worst-case analysis and average-case analysis. It models non-uniform popularity by assuming that the file popularity has L different levels. Both the number of files at each level and the number of users requesting files at each level are fixed. The authors then study the deter￾ministic worst-case performance under such a setting. When the number of users is large, this model can be seen as an approximation of a stochastic-demand model. The theoretical gap between the achievable transmission rate and the lower bound established in [10] increases as L 3 . The work in [13] is most related to ours. In [13], the authors propose a large class of achievable schemes, called RAP-GCC and RAP￾CIC, which place files in caches according to a popularity￾dependent caching distribution. However, because the optimal caching distribution for RAP-GCC and RAP-CIC may not have analytically tractable solutions in general, [13] then focuses on a sub-class of RAP-GCC, called RLFU (Random Least-Frequently-Used caching), to study the performance gap between the lower bound and achievable bound of the required transmission rate. RLFU uses a clever and surprisingly simple caching distribution that divides the contents into 2 groups. Although both the lower bound and the achievable bound (by RLFU) are given in [13] for arbitrary popularity distributions, the gap between the achievable bound and the lower bound is shown to be a constant only when the file popularity follows a Zipf distribution. Note that the gaps estimated by the theoretical results of [13] depend on the parameters of the Zipf distribution, and may also become large for certain ranges of the parameter values [13]. Further, the constant factors are only shown in the asymptotic limit when the number of files and/or the number of users are large. Therefore, it remains an important open question what is the fundamental limit of the performance of coded caching for the more practical scenario of heterogeneous file popularity, and whether one can find a coded-caching scheme whose performance gap from the lower bound is independent of the popularity distribution even in the non-asymptotic settings. In this paper, we make the following contributions to answer the above open question. First, we show that a simple coded￾caching scheme (which is a special case of RAP-GCC in [13] and is also similar to RLFU) can attain an average transmission rate that is at most 55 times from the optimal1 . Although this factor appears to be large, it is the first result in the literature with a constant-factor gap that is independent of the popularity distributions and the system size. In contrast, as we discussed earlier, the performance gap in prior studies could be arbitrar￾ily large depending on either the number of groups [9], the number of levels [10], or the parameter of the Zipf distribution [11–13]. Second, a key step towards this result is to use a new construction in Section IV to establish a sharper lower bound (in the order sense) on the achievable transmission rate of any schemes. Specifically, our lower bound may be higher than the lower bound in [13] by an arbitrarily large factor under certain 1 Note that the conference version of this paper [1] not only shows a larger multiplicative factor, but also requires a small additive factor. The results in this paper use a more-refined analysis that eliminates the need for the additive factor. popularity distributions (see further discussions in Section III). We establish this lower bound by a series of reduction and merging steps that convert the original system with hetero￾geneous popularity to other systems with uniform popularity. Using these techniques, we are able to quantify the impact of both “popular” files and “non-popular” files, which we believe is the main reason that we can obtain sharp constant￾factor characterizations even in the non-asymptotic settings. (See further discussions at the end of Section IV.D.) These techniques may be of independent interest for future studies of coded caching performance. Third, while our achievable scheme is similar to RLFU proposed [13] (in the sense that for most parameter settings we divide the files into 2 groups, correspondingly to popular and unpopular files, respectively), there are parameter settings where we need to divide the files into 3 groups. This new modification turns out to be important for attaining the constant-factor performance gap under all popularity distributions and non-asymptotic settings. Further, our division between popular and unpopular files uses a simple threshold N1. Specifically, suppose that the number of users is K and the size of each user’s storage is M. Then, the threshold N1 corresponds to the least-popular file among those whose popularity is no smaller than 1 KMr , where Mr = max(M, 3). Compared with the choice of the threshold (denoted by m˜ ) in [13] (either chosen as a function of the Zipf distribution in the theoretical analysis, or obtained via a 1-dimensional optimization over an achievable bound), our choice of N1 is in a simple closed-form that works for arbitrary popular distributions (see further discussions in Section III). Finally, note that the RLFU scheme in [13] with the optimal threshold m˜ should in general attain a better performance than the simpler choice of N1 in this paper. Thus, it implies that RLFU combined with appropriately dividing the files into 3 groups under certain settings also attains an average transmission rate that is away from the optimal by at most a constant factor, independently of the popularity distribution. (This immediately follows that the best scheme in the larger class of RAP-GCC will also attain a constant-factor gap.) However, the RLFU scheme itself without the 3-group modification does not have this constant-factor performance guarantees under arbitrary popularity distribution (see Section III). The remainder of this paper is as follows. We first present the network model in Section II. Main results are summarized in Section III. Followed is the analysis on the information theoretical lower bound in Section IV. The achievable scheme is analyzed in Section V. The gap between the lower bound and the achievable rate is derived in Section VI. Simulation results are presented in Section VII. Then, we conclude. II. NETWORK MODEL In the following, we present the network model for a video delivery system with both local caches and broadcast capabilities (see Figure 1). We assume that there are N distinct files from the set F = {F1, F2, ..., FN }. The popularity of the file Fi is pi P , where N i=1 pi = 1. Without loss of generality, we assume that the file size is of unit length and the file popularity is decreasing in the index, i.e., pi ≥ pj if i ≤ j

and transmission scheme 3,let r(K,Wi)denote the amount File N Popularity of broadcast transmission from the server that is needed to Server satisfy a request Wi.The expected rate under scheme 3 is therefore defined as ①File File Placement ② ③Transmission NK R(K,F,P)=∑r(K,W)Pw) (1) 1234 ②File N File i=1 Request ②File We wish to find the schedule that minimizes Request Rs(K,F,P).Define the optimal rate as User 1 User User K R(K,F,P)=min Ra(K,F,P) (2) Fig.1:An illustration of the network model. Unfortunately,finding the exact optimal schedule that achieves this optimal rate is very difficult [7-16].Like [7-16].our goal is to find a simple scheme whose achievable rate is as close There is one server who has all N files and who serves to the optimal rate R(K,F,P)as possible. these files to K users interested in these files.Each user has Remark:In [7],instead of studying the expected rate (1), a local cache with size M (again measured with respect to the authors focus on the worst-case rate,i.e., the unit-length of the files).The K users are connected to the server through a network with broadcast capability,i.e.,each maxrs(K,Wi) (3) Wi transmission from the server can be received by all users. Let be the optimal scheme that attains the minimum value Before users request any files,some of the contents are placed in the users'caches.This is called cache placement of (3),and let 3 be the scheme proposed in [7].Then [7] shows that and in practice is usually carried out during off-peak hours of maxw,r3(K,Wi) the network.Then,at each time,a user k will request file Fi maxw?(K,W≤12. (4) with probability pi,independently of all other users and files. If the user's local cache already has (some of)the content. However,in this paper since we are interested in the expected the request can be served locally.Otherwise,the server must rate given in (2),we would be interested in the gap transmit (via broadcast)contents not available from the local ΣrK.WPw cache.The goal is that every user should be able to reconstruct (5) the file that it requests with the information received from the ∑1r(K,W)P(WwW server and the cached content in its local cache. where*is the optimal scheme that attains the minimum value of)P(W).Note that the bound in (4 A.Definition of the Expected Transmission Rate does not imply that the expression in (5)is bounded by the same constant,especially when the probability P(Wi)varies In this subsection,we will define the expected rate needed significantly.In general,even if the bound in (4)holds,the from the server in serving the requests.Note that we do not expression in(5)can still be arbitrarily large.Thus,quantifying consider the transmission rate for cache placement. the performance gap in terms of the expected rate represents Let Wi [fi,fi2,...,fik}denote a request pattern. a new research problem where fij F is the requested file for the j-th user, 1<j<K.Note that there are NK such patterns.Let W III.MAIN RESULTS be the set of all possible request patterns from K users,i.e., W={W1,W2,...,WNK.Since each user can request one In this section,we provide an overview of our main file from N files independently,the probability for event Wi results.Given an arbitrary popularity distribution,our first is given by result establishes a fundamental lower bound on the expected K transmission rate for any coded caching scheme.Let [ P(w)=ΠP(f) denote max(0,)Recall that the files are indexed with non- j=1 increasing popularity.Without loss of generality,we assume where P(f)is the probability for a user to request file f pN+-0(which ensures the existence of N defined next Note that in our original system,the probability for a user even when p KM).Let Mr =max(M,3),and let Ni be to request file Fj is pj.However.later in the analysis we the integer that satisfies p.and pN+In will compare to another system with a different popularity other words,N is the least popular file among those whose distribution P.Hence,we use the notation W(K,F,P)to popularity is no smaller than 1/KM.If no such files exist, denote the set W of possible request patterns associated with let N1=0.Let N2= |24>NP4 the corresponding popularity distribution P. 2,+ Further,for any integer Obviously,given a set of files F and the files'corresponding popularity distribution P,there exists numerous caching and Nr:between 1 and N-1,let Ny(Nz)= >N Pi 2PN transmission schemes to meet users'request.For a caching Then,we have the following

3 File Placement User 1 File 1 ... File N User 2 ... User K File Request File Request File Transmission 1 2 3 2 2 2 Server Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ File Popularity ... 1 2 3 ... 4 N Fig. 1: An illustration of the network model. There is one server who has all N files and who serves these files to K users interested in these files. Each user has a local cache with size M (again measured with respect to the unit-length of the files). The K users are connected to the server through a network with broadcast capability, i.e., each transmission from the server can be received by all users. Before users request any files, some of the contents are placed in the users’ caches. This is called cache placement and in practice is usually carried out during off-peak hours of the network. Then, at each time, a user k will request file Fi with probability pi , independently of all other users and files. If the user’s local cache already has (some of) the content, the request can be served locally. Otherwise, the server must transmit (via broadcast) contents not available from the local cache. The goal is that every user should be able to reconstruct the file that it requests with the information received from the server and the cached content in its local cache. A. Definition of the Expected Transmission Rate In this subsection, we will define the expected rate needed from the server in serving the requests. Note that we do not consider the transmission rate for cache placement. Let Wi = {fi1, fi2, ..., fiK} denote a request pattern, where fij ∈ F is the requested file for the j-th user, 1 ≤ j ≤ K. Note that there are NK such patterns. Let W be the set of all possible request patterns from K users, i.e., W = {W1, W2, ..., WNK }. Since each user can request one file from N files independently, the probability for event Wi is given by P(Wi) = Y K j=1 P(fij ) where P(fij ) is the probability for a user to request file fij . Note that in our original system, the probability for a user to request file Fj is pj . However, later in the analysis we will compare to another system with a different popularity distribution P. Hence, we use the notation W(K, F,P) to denote the set W of possible request patterns associated with the corresponding popularity distribution P. Obviously, given a set of files F and the files’ corresponding popularity distribution P, there exists numerous caching and transmission schemes to meet users’ request. For a caching and transmission scheme F, let rF(K, Wi) denote the amount of broadcast transmission from the server that is needed to satisfy a request Wi . The expected rate under scheme F is therefore defined as RF(K, F,P) = X NK i=1 rF(K, Wi)P(Wi). (1) We wish to find the schedule F that minimizes RF(K, F,P). Define the optimal rate as R(K, F,P) = min F RF(K, F,P). (2) Unfortunately, finding the exact optimal schedule that achieves this optimal rate is very difficult [7–16]. Like [7–16], our goal is to find a simple scheme F whose achievable rate is as close to the optimal rate R(K, F,P) as possible. Remark: In [7], instead of studying the expected rate (1), the authors focus on the worst-case rate, i.e., max Wi rF(K, Wi). (3) Let F ′ be the optimal scheme that attains the minimum value of (3), and let F be the scheme proposed in [7]. Then [7] shows that maxWi rF(K, Wi) maxW′ i rF′ (K, W′ i ) ≤ 12. (4) However, in this paper since we are interested in the expected rate given in (2), we would be interested in the gap PNK i=1 rF(K, Wi)P(Wi) PNK i=1 rF∗ (K, W′ i )P(W′ i ) , (5) where F ∗ is the optimal scheme that attains the minimum value of PNK i=1 rF(K, W′ i )P(W′ i ). Note that the bound in (4) does not imply that the expression in (5) is bounded by the same constant, especially when the probability P(Wi) varies significantly. In general, even if the bound in (4) holds, the expression in (5) can still be arbitrarily large. Thus, quantifying the performance gap in terms of the expected rate represents a new research problem. III. MAIN RESULTS In this section, we provide an overview of our main results. Given an arbitrary popularity distribution, our first result establishes a fundamental lower bound on the expected transmission rate for any coded caching scheme. Let [x]+ denote max(0, x). Recall that the files are indexed with non￾increasing popularity. Without loss of generality, we assume pN+1 = 0 (which ensures the existence of N1 defined next even when pN ≥ 1 KMr ). Let Mr = max(M, 3), and let N1 be the integer that satisfies pN1 ≥ 1 KMr and pN1+1 < 1 KMr . In other words, N1 is the least popular file among those whose popularity is no smaller than 1/KMr. If no such files exist, let N1=0. Let N2 = P i>N1 pi 2/KMr + 1 2  . Further, for any integer Nx between 1 and N − 1, let Ny(Nx) = P i>Nx pi 2pNx + 1 2  . Then, we have the following

￥ Theorem /With K users requesting files independently in due to these Ni popular files is1-1) F according to the corresponding popularity distribution P. (assuming M >3).Thus,this lower bound is always less the lower bound on the expected transmission rate is given by than Note that using N in the place of N will not R(K,F,P)2i立max 1 (N1+N2-M) get a lower bound higher than either.To see this,if IM we do not consider the term N(N),the lower bound in the (6) max KPN2IN:+Nu(N:)-M] second term of Theorem 1 gives HKpN (N-M).Since Nz>N1+1 KpN N this lower bound can not be larger than The new lower bound in Theorem I is one of the main either.On the other hand.the lower bound given by contributions of the paper.It is sharper than those reported in Theorem 1 can be arbitrarily larger once the contribution for the literature [9,11-13]in the order sense.Specifically,we unpopular files is accounted.For example,when Ni <KM, will show shortly that our lower bound can be higher than the impact from unpopular files,can be approximated the lower bound in [13]by an arbitrarily large factor under as∑>NKPi=K-K∑sN,Kn≈K-Kg certain popularity distributions.Thus,this sharper bound is the When log N≥log KM,we would have≈O(K).In main reason behind the improved performance characterization other words,accounting for the impact of unpopular files can reported in this paper.We acknowledge that there will be increase the lower bound by a factor as large as O(log N).Due settings where our lower bound can be lower than that of [13]. to this reason,it is critical to use the improved lower bound However,even when this happens,the difference is at most a in Theorem 1 in order to prove constant-factor performance constant multiplicative factor since Theorem 2 establishes an gaps under arbitrary popularity distributions. achievable upper bound that is at most a constant factor away We next present an achievable scheme that can attain from our lower bound.Here.the index N in the first term of a corresponding upper bound.Our achievable scheme is a (6)plays an important role in most of the results in this paper. special case of RAP-GCC in [13]and is also similar to RLFU. Recall again that the popularity pi is non-increasing in the file Recall that each file is of unit length.In order to allow a index i.Roughly speaking,N is the index for the file whose portion of each file to be cached,we refer to a minimally popularity is aroundK.We may view all files i<Ni as the divisible portion of a file as a "bit",and assume that each "more popular"files,and all files i>Ni as the "unpopular" file has F "bits".We are most interested in the case of files.As readers will see in the proofs of Theorem 1 in Section large files,i.e.,when the bits are very small compared to the IV,we will first show that the expression NM+is a file size,and hence F+o0.Our achievable scheme is lower bound on the expected transmission rate for serving the similar to RLFU in most settings (i.e.,when N1>M and more popular files.Existing results in [9,11-13]use different M>3),but different in other settings (i.e.,when N<M variations of this expression as the lower bound.However, orM<3).Specifically,.when N1≥I and M≥3， since this expression neglects the contribution of the unpopular our proposed achievable scheme uses the decentralized coded files,it results into poorer performance characterization.In caching scheme of [8]to serve the "popular"files,and uses contrast,we show that the contribution of the unpopular files uncoded transmissions to serve the "unpopular"files.Each can be accounted for by having N2 in the first term of (6). user randomly caches an equal number of bits fromevery As readers will see in Section IV.D,here we introduce a file F1,...,FN.The remaining unpopular files are not cached. novel "merging"procedure that merges multiple unpopular After the users request the files according to the popularity files into one file with the sum of the popularities,so that distribution p,...,pN.the decentralized coded transmission the new popularity is greater than or equal to 1/(KM,).In scheme of [8 is used to serve those users requesting popular this way,N2 can be interpreted (approximately)as a lower files,and an uncoded transmission scheme is used to serve bound on the number of such "merged"files.Thus,N and those users requesting unpopular files.We note that this part N2 combined produce the lower bound in the first term of of the scheme is similar to the Random LFU scheme studied Theorem 1.However,the first term of(6)would be trivial if in [13].However,when N<M or M<3,we do not use N+N2 M.In that case,we will need to increase the RLFU.Instead,we divide the files into 3 groups and serve threshold index N to a larger value N,in order to obtain them separately.Specifically.we cache all files 1 to M], a sharper lower bound.The second term in (6)takes care of cache M-M]portion of file M+1,and not to cache this case.Details of the proof will be presented in Section IV.all other files.Note that this scheme can be seen as LFU with Difference from (13]:As we discussed above,a key d- fractional caching of the file M]+1 (when M is not an ifference between our lower bound and the prior results is integer).The following result summarizes an upper bound on that our lower bound accounts for the contribution of the the expected transmission rate of our achievable scheme. unpopular files.As one can see from the example below, Theorem 2:With K users independently requesting files in accounting for the contribution of the unpopular files to the F according to the popularity distribution P,as F+o0, lower bound is critical,because otherwise the lower bound the optimal achievable rate can be upper bounded by may be looser by an arbitrarily factor.Take Zipf distribution [N-M+ with a 1 as an example.Suppose that M>3 and the R(K,F,P)≤min +〉Kp: number of files N is large.Then,using the approximation max1,M0）N, (7) that∑l}≈logV,it is easy to see that p≈ogN,and thus the threshold N satisfies NThe lower bound KpNa(N-M)+∑Kp) >N3

4 Theorem 1: With K users requesting files independently in F according to the corresponding popularity distribution P, the lower bound on the expected transmission rate is given by R(K, F,P) ≥ 1 11 max n 1 Mr (N1 + N2 − M), max Nx≥N1+1 KpNx [Nx + Ny(Nx) − M] o . (6) The new lower bound in Theorem 1 is one of the main contributions of the paper. It is sharper than those reported in the literature [9, 11–13] in the order sense. Specifically, we will show shortly that our lower bound can be higher than the lower bound in [13] by an arbitrarily large factor under certain popularity distributions. Thus, this sharper bound is the main reason behind the improved performance characterization reported in this paper. We acknowledge that there will be settings where our lower bound can be lower than that of [13]. However, even when this happens, the difference is at most a constant multiplicative factor since Theorem 2 establishes an achievable upper bound that is at most a constant factor away from our lower bound. Here, the index N1 in the first term of (6) plays an important role in most of the results in this paper. Recall again that the popularity pi is non-increasing in the file index i. Roughly speaking, N1 is the index for the file whose popularity is around 1 KMr . We may view all files i ≤ N1 as the “more popular” files, and all files i > N1 as the “unpopular” files. As readers will see in the proofs of Theorem 1 in Section IV, we will first show that the expression 1 11Mr [N1−M]+ is a lower bound on the expected transmission rate for serving the more popular files. Existing results in [9, 11–13] use different variations of this expression as the lower bound. However, since this expression neglects the contribution of the unpopular files, it results into poorer performance characterization. In contrast, we show that the contribution of the unpopular files can be accounted for by having N2 in the first term of (6). As readers will see in Section IV.D, here we introduce a novel “merging” procedure that merges multiple unpopular files into one file with the sum of the popularities, so that the new popularity is greater than or equal to 1/(KMr). In this way, N2 can be interpreted (approximately) as a lower bound on the number of such “merged” files. Thus, N1 and N2 combined produce the lower bound in the first term of Theorem 1. However, the first term of (6) would be trivial if N1 + N2 ≤ M. In that case, we will need to increase the threshold index N1 to a larger value Nx, in order to obtain a sharper lower bound. The second term in (6) takes care of this case. Details of the proof will be presented in Section IV. Difference from [13]: As we discussed above, a key d￾ifference between our lower bound and the prior results is that our lower bound accounts for the contribution of the unpopular files. As one can see from the example below, accounting for the contribution of the unpopular files to the lower bound is critical, because otherwise the lower bound may be looser by an arbitrarily factor. Take Zipf distribution with α = 1 as an example. Suppose that M ≥ 3 and the number of files N is large. Then, using the approximation that PN i=1 1 i ≈ log N, it is easy to see that pi ≈ 1 i log N , and thus the threshold N1 satisfies N1 ≈ KM log N . The lower bound due to these N1 popular files is 1 11 ( N1 M − 1) ≈ 1 11 ( K log N − 1) (assuming M ≥ 3). Thus, this lower bound is always less than 1 11 K log N . Note that using Nx in the place of N1 will not get a lower bound higher than 1 11 K log N either. To see this, if we do not consider the term Ny(Nx), the lower bound in the second term of Theorem 1 gives 1 11KpNx (Nx − M). Since KpNxNx ≈ K log N , this lower bound can not be larger than 1 11 K log N either. On the other hand, the lower bound given by Theorem 1 can be arbitrarily larger once the contribution for unpopular files is accounted. For example, when N1 ≤ KM, the impact from unpopular files, N2 Mr , can be approximated as P i>N1 Kpi = K − K P i≤N1 Kpi ≈ K − K log N1 log N . When log N ≫ log KM, we would have N2 Mr ≈ O(K). In other words, accounting for the impact of unpopular files can increase the lower bound by a factor as large as O(log N). Due to this reason, it is critical to use the improved lower bound in Theorem 1 in order to prove constant-factor performance gaps under arbitrary popularity distributions. We next present an achievable scheme that can attain a corresponding upper bound. Our achievable scheme is a special case of RAP-GCC in [13] and is also similar to RLFU. Recall that each file is of unit length. In order to allow a portion of each file to be cached, we refer to a minimally divisible portion of a file as a “bit”, and assume that each file has |F| “bits”. We are most interested in the case of large files, i.e., when the bits are very small compared to the file size, and hence |F| → +∞. Our achievable scheme is similar to RLFU in most settings (i.e., when N1 ≥ M and M ≥ 3), but different in other settings (i.e., when N1 < M or M < 3). Specifically, when N1 ≥ M and M ≥ 3, our proposed achievable scheme uses the decentralized coded caching scheme of [8] to serve the “popular” files, and uses uncoded transmissions to serve the “unpopular” files. Each user randomly caches an equal number of M|F | N1 bits from every file F1, ..., FN1 . The remaining unpopular files are not cached. After the users request the files according to the popularity distribution p1, ..., pN , the decentralized coded transmission scheme of [8] is used to serve those users requesting popular files, and an uncoded transmission scheme is used to serve those users requesting unpopular files. We note that this part of the scheme is similar to the Random LFU scheme studied in [13]. However, when N1 < M or M < 3, we do not use RLFU. Instead, we divide the files into 3 groups and serve them separately. Specifically, we cache all files 1 to ⌊M⌋, cache M − ⌊M⌋ portion of file ⌊M⌋ + 1, and not to cache all other files. Note that this scheme can be seen as LFU with fractional caching of the file ⌊M⌋ + 1 (when M is not an integer). The following result summarizes an upper bound on the expected transmission rate of our achievable scheme. Theorem 2: With K users independently requesting files in F according to the popularity distribution P, as |F| → +∞, the optimal achievable rate can be upper bounded by R(K, F,P) ≤ min  [N1 − M]+ max(1, M) + X i>N1 Kpi , KpN3 (N3 − M) + X i>N3 Kpi ‹ , (7)

TABLE I:Comparisons of our work and [13] Our work 13] Performance gap (between achievable achievable schemes and lower bounds)is derived on- System Performance gap (between schemes and lower bounds)is derived & ly for Zipf distribution and for asymptotic settings Performance for arbitrary distribution and system size. settings when the system size is large.Gap Constant-factor gap independent of the depends on the parameter a of the Zipf ga即 popularity distribution and system size. distribution,and may approach infinity as a approaches 1. Lower bound only accounts for the l most- Lower bound accounts for the contribution popular files.and thus may be arbitrarily Lower bound of both popular files and unpopular files. lower than our lower bound for certain popularity distributions. The achievable scheme divides all files into either 2 groups or 3 groups depend- The achievable bound is analyzed based ing on system settings.Using a simple on RLFU,which divides the files into 2 Achievable bound expression for N,this scheme is shown groups.As a result,RLFU may incur an to be constant-factor away from the lower arbitrarily large gap from the lower bound bound under arbitrary popularity distribu- under certain popularity distributions. tion. where N3 M]+1. serve file N3 in an uncoded manner when any users request .In the first term of (7),when N1>M and M 3,it.On the other hand,if RLFU caches all N3 =M+1 N1-M+ ax, INis an upper bound on the expected files,the average transmission rate can be lower bounded by transmission rate to serve the more popular files (i.e.,with R1,which corresponds to the rate index i≤Ni),and∑i>M,Kpn:is an upper bound on when there is only one file being requested.In contrast,by the expected transmission rate to serve the unpopular files.caching all files 1 to M]and partially caching file N3,our However,the expression Kp:may become rate is R3 KpNa (M+1-M).We note that,depending too loose in certain cases (e.g,when N<M or M<3).on the system setting,R3 can be an arbitrarily small fraction In those cases,coded caching has little gain,and thus we of min{R,R2}.For example,for any integer H.by letting N=H,M=H-i,andp:=占-Km-可(i=lH- 1 use uncoded transmissions for all files,which leads to both the second term in (ad the terConsider the 91),pH=,,we have=o(品，R2=o()and 1 scenario when N M and M3.and thus the first Ra=().Thus,as H goes to infinity,the ratio mint term of (7)dominates.Note that increasing N by 1 will goes to zero.Since our achievable scheme is order optimal, increase -1 by 1/M.and will reduce Kpi by it implies that directly using RLFU is not order-optimal for roughly KpN Thus,by setting pN this index N this case.Hence,this part of dividing files into 3 groups (one is chosen such that the net effect to the first term of upper group is cached in its entirety,one file is cached partially,other bound(7)is approximately zero,and thus the first term in files are not cached)turns out to be critical for the constant-gap (7)is approximately minimized.This property was the main result.We acknowledge that the difference may be small under intuition behind our choice of N1.However,the analysis in Zipf distribution.However,since we are focusing on arbitrary the paper will account for all scenarios(not just N>M and distribution and non-asymptotic case in this paper,capturing M≥3). this subtle difference is critical for the overall results. Difference from(13/:Note that the above modification that From Theorem 1 and Theorem 2,we will show in Section divides the files into 3 groups in some settings turns out to be VI that the gap between the lower bound Ri and the upper crucial for attaining the constant-factor performance gap under bound Rup is bounded by a multiplicative constant. arbitrary popularity distributions,especially when the optimal Corollary I:With K users independently requesting files in transmission rate is small.The difference from RLFU occurs Faccording to the popularity distribution P,as F+, when N<M and when M is not an integer,i.e.,when the the lower bound R and the upper bound Rp can be bounded cache can hold all popular files and the cache size is not a by multiple of the file size.In this case,our optimal scheme is Rup≤55Rb (8) to cache all files1toLM」，cache M-LM」portion of file M+1,and not to cache all other files.To compare the Thus,the bounds differ at most by a multiplicative factor performance difference with RLFU:assuming that there are of 55.As we discuss in the introduction,although this factor M]+1 files.Let N3=M]+1.If RLFU caches at most may appear to be large,it is the first result in the literature M]files,the average transmission rate is R1=e(KPNa) with a constant-factor gap that is independent of the popularity when KpN=O(1).which is simply the rate for RLFU to distributions.In contrast,the gap (between upper-and lower-

5 TABLE I: Comparisons of our work and [13] Our work [13] System settings & Performance gap Performance gap (between achievable schemes and lower bounds) is derived for arbitrary distribution and system size. Constant-factor gap independent of the popularity distribution and system size. Performance gap (between achievable schemes and lower bounds) is derived on￾ly for Zipf distribution and for asymptotic settings when the system size is large. Gap depends on the parameter α of the Zipf distribution, and may approach infinity as α approaches 1. Lower bound Lower bound accounts for the contribution of both popular files and unpopular files. Lower bound only accounts for the l most￾popular files, and thus may be arbitrarily lower than our lower bound for certain popularity distributions. Achievable bound The achievable scheme divides all files into either 2 groups or 3 groups depend￾ing on system settings. Using a simple expression for N1, this scheme is shown to be constant-factor away from the lower bound under arbitrary popularity distribu￾tion. The achievable bound is analyzed based on RLFU, which divides the files into 2 groups. As a result, RLFU may incur an arbitrarily large gap from the lower bound under certain popularity distributions. where N3 = ⌊M⌋ + 1. In the first term of (7), when N1 ≥ M and M ≥ 3, [N1−M]+ max(1,M) = [N1−M]+ M is an upper bound on the expected transmission rate to serve the more popular files (i.e., with index i ≤ N1), and P i>N1 Kpi is an upper bound on the expected transmission rate to serve the unpopular files. However, the expression [N1−M]+ M + P i>N1 Kpi may become too loose in certain cases (e.g, when N1 < M or M < 3). In those cases, coded caching has little gain, and thus we use uncoded transmissions for all files, which leads to both the second term in (7) and the term [N1−M]+ max(1,M) . Consider the scenario when N1 ≥ M and M ≥ 3, and thus the first term of (7) dominates. Note that increasing N1 by 1 will increase N1 M − 1 + by 1/M, and will reduce P i>N1 Kpi by roughly KpN1 . Thus, by setting pN1 ≈ 1 KM , this index N1 is chosen such that the net effect to the first term of upper bound (7) is approximately zero, and thus the first term in (7) is approximately minimized. This property was the main intuition behind our choice of N1. However, the analysis in the paper will account for all scenarios (not just N1 ≥ M and M ≥ 3). Difference from [13]: Note that the above modification that divides the files into 3 groups in some settings turns out to be crucial for attaining the constant-factor performance gap under arbitrary popularity distributions, especially when the optimal transmission rate is small. The difference from RLFU occurs when N1 < M and when M is not an integer, i.e., when the cache can hold all popular files and the cache size is not a multiple of the file size. In this case, our optimal scheme is to cache all files 1 to ⌊M⌋, cache M − ⌊M⌋ portion of file ⌊M⌋ + 1, and not to cache all other files. To compare the performance difference with RLFU: assuming that there are ⌊M⌋ + 1 files. Let N3 = ⌊M⌋ + 1. If RLFU caches at most ⌊M⌋ files, the average transmission rate is R1 = Θ(KpN3 ) when KpN3 = O(1), which is simply the rate for RLFU to serve file N3 in an uncoded manner when any users request it. On the other hand, if RLFU caches all N3 = ⌊M⌋ + 1 files, the average transmission rate can be lower bounded by R2 = 1 − M N3 = ⌊M⌋+1−M ⌊M⌋+1 , which corresponds to the rate when there is only one file being requested. In contrast, by caching all files 1 to ⌊M⌋ and partially caching file N3, our rate is R3 = KpN3 (⌊M⌋ + 1 − M). We note that, depending on the system setting, R3 can be an arbitrarily small fraction of min{R1, R2}. For example, for any integer H, by letting N = H, M = H− 1 H , and pi = 1 H−1− 1 KH2(H−1) (i=1,...,H− 1), pH = 1 KH2 , we have R1 = Θ( 1 H2 ), R2 = Θ( 1 H2 ) and R3 = Θ( 1 H3 ). Thus, as H goes to infinity, the ratio R3 min{R1,R2} goes to zero. Since our achievable scheme is order optimal, it implies that directly using RLFU is not order-optimal for this case. Hence, this part of dividing files into 3 groups (one group is cached in its entirety, one file is cached partially, other files are not cached) turns out to be critical for the constant-gap result. We acknowledge that the difference may be small under Zipf distribution. However, since we are focusing on arbitrary distribution and non-asymptotic case in this paper, capturing this subtle difference is critical for the overall results. From Theorem 1 and Theorem 2, we will show in Section VI that the gap between the lower bound Rlb and the upper bound Rup is bounded by a multiplicative constant. Corollary 1: With K users independently requesting files in F according to the popularity distribution P, as |F| → +∞, the lower bound Rlb and the upper bound Rup can be bounded by Rup ≤ 55Rlb. (8) Thus, the bounds differ at most by a multiplicative factor of 55. As we discuss in the introduction, although this factor may appear to be large, it is the first result in the literature with a constant-factor gap that is independent of the popularity distributions. In contrast, the gap (between upper- and lower-