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≤j2 [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