as the smallest integer such that unpopular files is about普≈克o·logv.Note KM N1+hi that depending on the relationship between N and K,the term 1 p防之KM, (33) due to unpopular files may be larger or smaller than the term j=N1+h:-1+1 due to popular files.For instance,if we keep N fixed and let Koo,then the term due to unpopular files will be and the replace files热r试，BN,+by one file, dominated by the term due to popular files.Such a setting whose popularity is vpIn this way,each has been studied in Corollary 1 of [131.However,in general non-empty file's popularity satisfies 1/KM vi<2/KM N/(KM)could be large,and thus the unpopular files may for all 1<i<N2.Note that after the merging steps finish, dominate.In that case,if we did not use the characterization there could be some files unmerged whose sum popularity is in this subsection,we would be unable to obtain the sharper smaller than Hence,we have iN Kpi<N2K+ results in this paper. K,which can turn into N2> ∑>NP-1 (34)E.Further Refining the Lower Bound 2/KM. -2 In (38),we have established the first term of(6).However, Since N2 is an integer,we must have the first term of(6)may becomes zero when N+N2 M. 1 In that case.the first term of(6)will be too loose to be a lower N2≥ ∑2NP 2/KM, 2 +1 bound for the average transmission rate.What happens is that (35) the cache space M is abundant,and hence more than N1+N2 ∑i>N1Pi files can be accommodated in the cache.Intuitively,we should 2/KM, "relax"the threshold N for"popular files",so that a larger number of files can be considered for caching.Towards this In the following,we will only take +到 of these end,we now take pN as the popularity threshold.There are N files with popularity no smaller than pN.. merged files,i.e.,let N2 ∑>NP4 2泣+ Let this new Lemma 9:With K users requesting files independently in system be (K,F4,P4). F according to the corresponding popularity distribution P. By applying Lemma 8 iteratively,we can show that the lower bound on the expected transmission rate is given by 1 R(K,F3:P3)>R(K,FA:P). (36) RK,F,P)≥i立KpN.(N:-MO, (39) Define乃-L-',,}over file seta万. 1 for any N satisfying PN.KM In other words,the first file (which corresponds to the empty This lemma can be obtained by reducing the popularity of file)is requested with probability 1 and the other files Fi(1 <i<N)in the original file-set F to pN and (N+N2)files are requested with probability each. applying Proposition 1.We note that the use of N here is Similar to Lemma 2,we can prove that similar to the use of I in Theorem 2 of [13],which allows a larger number of files to be considered for caching.However, R(K,F P)>R(K,F4;Ps). (7)the use of Ny introduced below again accounts for files less Now,note that the system(K,F,P5)is of the same form popular than pN.which is not reported in [13]. as the system(K,F1,P2):all non-empty files are requested Then,if we apply the merging technique introduced in sub- with a common probability that is greater than or equal section D,we can construct Ny files with popularity pN.from to i (this is also of the form of the "System 2"that files FN.+1.FN+2...FN,where Ny= 2/PN we referred to in Sections III-A and IV-A).With System Applying Proposition 1,we have the following lemma. (K,F4,Ps),we can directly apply Proposition 1 and obtain Lemma 10:With K users requesting files independently in R(K,FA,Ps)≥1W+-M+ (38) Faccording to the corresponding popularity distribution P, the lower bound on the expected transmission rate is given by Remark:We believe that the above characterization for the R(K,F,P)KpN.(N:+Ny(N)-M). (40) unpopular files is crucial for obtaining the improved constant- factor results that hold for arbitrary distributions and system for any N satisfying PN.<KM settings.Again take Zipf distribution with a =1 as an Combining Equations(38)and(40),the result of Theorem example.Suppose that the number of files N is large.As 1 then follows. we discussed at the beginning of this subsection,it is easy to see that p and thus the threshold is N log N On the other hand,the number of virtual files merged from V.UPPER BOUND ON EXPECTED TRANSMISSION RATE log N-log N the unpopular files is about N2 -()From In this section,we show that,by combing RLFU with our earlier results,the lower bound due to popular files is another scheme that divides the files into 3 groups,we can (1)-1),while the lower bound due to obtain a tight achievable bound.Recall the following statement12 as the smallest integer such that N X1+hi j=N1+hi−1+1 pj ≥ 1 KMr (33) and then replace files FN1+hi−1+1, ..., FN1+hi by one file Vi , whose popularity is vi = PN1+hi j=N1+hi−1+1 pj . In this way, each non-empty file’s popularity satisfies 1/KMr ≤ vi ≤ 2/KMr for all 1 ≤ i ≤ N2. Note that after the merging steps finish, there could be some files unmerged whose sum popularity is smaller than 1 KMr . Hence, we have P i>N1 Kpi < N2· 2 KMr + 1 KMr , which can turn into N2 > P i>N1 pi 2/KMr − 1 2 . (34) Since N2 is an integer, we must have N2 ≥ P i>N1 pi 2/KMr − 1 2  + 1 = P i>N1 pi 2/KMr + 1 2  . (35) In the following, we will only take P i>N1 pi 2/KMr + 1 2  of these merged files, i.e., let N2 = P i>N1 pi 2/KMr + 1 2  . Let this new system be (K, F4,P4). By applying Lemma 8 iteratively, we can show that R(K, F3,P3) ≥ R(K, F4,P4). (36) Define P5 = {1 − N1+N2 KMr , 1 KMr , ..., 1 KMr } over file set F4. In other words, the first file (which corresponds to the empty file) is requested with probability 1 − N1+N2 KMr , and the other (N1 + N2) files are requested with probability 1 KMr each. Similar to Lemma 2, we can prove that R(K, F4,P4) ≥ R(K, F4,P5). (37) Now, note that the system (K, F4,P5) is of the same form as the system (K, F1,P2): all non-empty files are requested with a common probability that is greater than or equal to 1 KMr (this is also of the form of the “System 2” that we referred to in Sections III-A and IV-A). With System (K, F4,P5), we can directly apply Proposition 1 and obtain R(K, F4,P5) ≥ 1 11Mr [N1 + N2 − M]+. (38) Remark: We believe that the above characterization for the unpopular files is crucial for obtaining the improved constant￾factor results that hold for arbitrary distributions and system settings. Again take Zipf distribution with α = 1 as an example. Suppose that the number of files N is large. As we discussed at the beginning of this subsection, it is easy to see that pi ≈ 1 i log N , and thus the threshold is N1 ≈ KM log N . On the other hand, the number of virtual files merged from the unpopular files is about N2 = Θ( log N−log N1 log N 2/KM ). From our earlier results, the lower bound due to popular files is 1 11 ( N1 M − 1) ≈ 1 11 ( K log N − 1), while the lower bound due to unpopular files is about 1 11 N2 M ≈ 1 22 K log N · log N log N KM . Note that depending on the relationship between N and K, the term due to unpopular files may be larger or smaller than the term due to popular files. For instance, if we keep N fixed and let K → ∞, then the term due to unpopular files will be dominated by the term due to popular files. Such a setting has been studied in Corollary 1 of [13]. However, in general N/(KM) could be large, and thus the unpopular files may dominate. In that case, if we did not use the characterization in this subsection, we would be unable to obtain the sharper results in this paper. E. Further Refining the Lower Bound In (38), we have established the first term of (6). However, the first term of (6) may becomes zero when N1 + N2 ≤ M. In that case, the first term of (6) will be too loose to be a lower bound for the average transmission rate. What happens is that the cache space M is abundant, and hence more than N1+N2 files can be accommodated in the cache. Intuitively, we should “relax” the threshold N1 for “popular files”, so that a larger number of files can be considered for caching. Towards this end, we now take pNx as the popularity threshold. There are Nx files with popularity no smaller than pNx . Lemma 9: 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 KpNx (Nx − M), (39) for any Nx satisfying pNx ≤ 1 KMr . This lemma can be obtained by reducing the popularity of files Fi (1 ≤ i ≤ Nx) in the original file-set F to pNx and applying Proposition 1. We note that the use of Nx here is similar to the use of l in Theorem 2 of [13], which allows a larger number of files to be considered for caching. However, the use of Ny introduced below again accounts for files less popular than pNx , which is not reported in [13]. Then, if we apply the merging technique introduced in sub￾section D, we can construct Ny files with popularity pNx from files FNx+1,FNx+2,...,FN , where Ny = P i>Nx pi 2/pNx + 1 2  . Applying Proposition 1, we have the following lemma. Lemma 10: 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 KpNx (Nx + Ny(Nx) − M), (40) for any Nx satisfying pNx ≤ 1 KMr . Combining Equations (38) and (40), the result of Theorem 1 then follows. V. UPPER BOUND ON EXPECTED TRANSMISSION RATE In this section, we show that, by combing RLFU with another scheme that divides the files into 3 groups, we can obtain a tight achievable bound. Recall the following statement