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-