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