￥ 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) >N34 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)