Fundamental Limits of Caching: Improved Bounds For Small Buffer Users

In this work, the peak rate of the caching problem is investigated, under the scenario that the users are with small buffer sizes and the number of users is no less than the amount of files in the server. A novel coded caching strategy is proposed for such a scenario, leading to a lower peak rate compared to recent results in the literature. Furthermore, it is verified that our peak rates coincides with the cut-set bound analytically in an information-theoretic view.


I. INTRODUCTION
Caching, a technique playing a crucial role in combatting the peak hour network traffic congestion, receives increasing attention recently. A natural way to reduce peak hour traffic is to duplicate some contents at the end users. In the literature, there are several works focusing on investigating how to duplicate fractions of files at end users so that the peak rate is minimized and network congestion is reduced. Usually, caching works in two phases. One is the placement phase, which is performed during off-peak times. The other is the delivery phase, performed during rush hours when network resources are scarce. The general model with caching strategy were discussed in [1]- [7] where no coding strategy was applied and the gain comes only from local duplication. However, if each user is equipped with a cache with a small size compared with the amount of the content in the server, this gain is readily observed to be negligible.
In [8], the index coding strategy was discussed. In [10], a new coded caching strategy from an information-theoretic perspective was proposed to achieve a new achievable rate region for general scenarios, where some finite rate-cache pairs were firstly derived and then the lower convex envelope of these points is shown to be achievable by memory sharing. This strategy was shown to enjoy both the local gain from duplication as well as the global gain from coding. This fundamental idea was then extended to [12] where a decentralized coded caching algorithm was presented and to [11] where the nonuniform demand scenario was investigated. In [14], the secure issue with coded caching was investigated.
In this work, however, we investigate the fundamental achievable rate for a special case where all users are equipped with a cache of a small size. In this case, appropriate coded duplication of contents is essential to reduce the delivery rates. To this end, we introduce a new coded caching strategy and it is shown that the rate of this strategy coincides with the lower cut-set bound when the cache size is rather small. With memory sharing, it is shown that our strategy outperforms the strategy proposed in [10] in terms of achievable delivery rates when the cache size is relatively small.

II. PROBLEM SETTING
A system consisting of one server and K users is considered. An error-free link is assumed to be shared by all users connecting the server, where N files are stored for fetching. We also assume that each user is equipped with a cache of size Z k (k = 1, . . . , K) and each user is assumed to request only one full file. The aim is to design a novel coded strategy to achieve a lower peak rate that can guarantee each user obtaining the file requested, compared with the recent results on caching problems in [10]. In this work, we turn our interest on the special case that all users are with small buffer sizes (Z k ≤ 1/K) and K ≥ N, i.e., the amount of users is no smaller than that of the files in the server.
For clarity, we denote the smallest peak rate achieved by our strategy by R(M), i.e., the cache-rate pair (M,R(M)) is on the boundary of the achievable region, where M denotes the cache size of all users. For comparison, we denote the minimum peak rate achieved in [10] by R c (M) and the lower cut-set bound by R * (M).

III. MAIN RESULTS
Theorem 1: For N ∈ N files and K (K = N) users each with cache of size M = 1/N, the cache-rate is achievable.
is achievable.
Theorem 3: For N ∈ N files and K (K = N) users each with cache of size M ≤ 1/N, the achievable rate coincides with the associated cut-set bound.

Theorem 4:
For N ∈ N files and K (K ∈ N and K > N) users each with cache of size M ≤ 1/K, the achievable rate coincides with the associated cut-set bound.
Note that in [10], the achievable rate with M = 1/K is on the line connecting the two cache-rate pair points (0, N) and the first non-trivial point (N/K, min ((K − 1)/2, N(K − 1)/K)) 1 and is hence given by, where the inequalities in (5) and (7) follow from the setting that K ≥ N ≥ 1. Note also that the inequality in (7) strictly holds as long as N > 1, which demonstrates the gain achieved by our coding strategy over the strategy designed in [10] for the small cache size scenario.
Furthermore, with our coding strategy, we have Which is an encouraging result. In other words, with a smaller cache size M = 1/K, the designed coding strategy can achieve a rate no smaller than that in [10] with the cache size M = N/K if K ≥ 2N.
Therefore, compared with [10], the rate with the cache size of M < N/K is improved by our results through memory sharing, where the exact expression of the achievable rate with 0 ≤ M ≤ N/K is given on top of next page. For clarity, the cache-rate pair is achieved by memory sharing of the three points (0, N), (1/K, N − K/N) by our results and (N/K, min((K − 1)/2, N(K − 1)/K)) from [10].
It is also noted that our result does not hold for the case K < N, i.e., in this case, the cut-set bound is not achievable for the small buffer size (M ≤ 1/K) scenario. In addition, in our study, our algorithm cannot be applied in the case with relatively higher cache size, which still remains an interesting direction in future on how to achieve the cut-set bound for the case with relatively high cache size.

IV. EXAMPLES
Example 1. In this example, we set N = K = 3, i.e., a system consists of three files in the server and three intended users. Let W 1 = A, W 2 = B and W 3 = C. We would like to show that the (M, R) pair With cache size M = 1/3, we split each file into three subfiles with equal size, i.e., In the placement phase, the cache content of user k is designed , which is an XORed version of three subfiles from different files in the server.
In the delivery phase, let us consider an example that user 1 requires A, user 2 requires B an user 3 requires C. Hence, to obtain the missing files for user 1, we should transmit B 1 and C 1 to obtain A 1 from the XORed subfile in Z 1 as well as A 2 and A 3 for the missing files of A. In a similar manner, for user 2 requesting file B, the server need to transmit B 3 for the missing part of B (B 1 is obtained from the shared link satisfying user 1). In addition, the server transmits C 2 to obtain B 2 (as A 2 has been transmitted and received by user 2). Note that the server has satisfied user 3 since the missing subfiles C 1 and C 2 are already received by it. In addition, with the received A 3 and B 3 from the shared link user Therefore, the server has to transmit (B 1 , C 1 , A 2 , A 3 , B 3 , C 2 ) to satisfy the requests of all users in this example. In a similar manner, all other requests can be satisfied. Since each subfile has rate 1/3, the total rate 2 is achievable.
On the other hand, the cut set bound derived in [10] indicates the minimum rate is R * (1/3) = 3−3/3 = 2 and is identical to the achievable rate. By cache sharing, we conclude that the achievable rate coincides with the cut set bound if 0 ≤ M ≤ 1/N.

Example 2.
In this example, we consider a system with a server of 4 files and 4 users, i.e., N = K = 4.
The four files are termed as W 1 = A, W 2 = B, W 3 = C and W 4 = D.
Consider the case with the cache size M = 1/4. In this example, we split each file into four parts of equal In the placement phase, we let user i caches the XORed subfile In the delivery phase, for instance, consider that user i requires W i , i.e., user 1 requests A, user 2 requests B, user 3 requests C and user 4 requests D. We can satisfy all requests of different users by . It is observed that with this transmission subfile list, all missing subfiles can be received by intended users. In addition, it is readily verified that the intended subfile which is XORed in the cache of each user is also obtained by XORing the three other XORed subfiles. For example, for user 1, it receives B 1 , C 1 and D 1 , hence A 1 is also fetched by In a similar manner, user 2, user 3 and user 4 can also obtain B 2 , C 3 and D 4 respectively. Therefore, by sending these subfiles, all user requests are satisfied with rate 3, as the rate of each subfile is 1/4.
Similarly, we can realize any possible requests with rate 3 with the cache size M = 1/4. Hence, the cache-rate pair (1/4, 3) is achievable and can be verified to coincide with the cut-set bound, which is Akin to Example 1 and 2, the cache-rate pair (1/N,N − 1) is achievable for an arbitrary number of files N in the server with the same number of users as that of the files in the server, i.e., K = N. The proof for this general case is left to the next section.
Example 3. Consider a system with N = 3 files and K = 4 users. We term each file as W 1 = A, W 2 = B and W 3 = C. Consider the case with cache size M = 1/4. We split each file into 12 parts of equal size, i.e., A = (A 1 , · · · , A 12 ), B = (B 1 , · · · , B 12 ) and C = (C 1 , · · · , C 12 ). Each cache can therefore store three subfiles. In the placement phase, we let user i caches the three XORed subfiles as Hence one user caches 9 exclusive subfiles in an XORed version and any subfiles partitioned in the server can be found in the cache of one and only one user.
In the transmissions phase, let us assume that user 1 needs A, user 2 needs B, user 3 needs C and user 4 needs A. To fully exploit the coded caching strategy, we then delivery the subfiles (B 1 , C 1 , B 2 , C 2 , B 3 , C 3 ) for user 1 to XOR A 1 , A 2 and A 3 . By delivering of these subfiles, B 1 , B 2 are received by user 2 and C 1 , C 2 are received by user 3. Similarly, we deliver (A 4 , C 4 , A 5 , C 5 , A 6 , C 6 ) for user 2 to obtain B 4 , B 5 and B 6 . (A 7 , B 7 , A 8 , B 8 , A 9 , B 9 ) for user 3 to obtain C 7 , C 8 and C 9 . (B 10 , C 10 , B 11 , C 11 , B 12 , C 12 ) for user 4 to obtain A 10 , A 11 and A 12 .
Hence, by delivering these 24 subfiles, user 2 receive the complete file B and user 3 receive the entire file C. However, user 1 still lacks the subfiles (A 10 , A 11 , A 12 ) and user 4 is in need of the subfiles . To exploit the side information at the caches, we hence delivery (A 1 ⊕ A 10 , A 2 ⊕ A 11 and  parts of equal size, i.e., A = (A 1 , · · · , A 15 ), B = (B 1 , · · · , B 15 ) and C = (C 1 , · · · , C 15 ) and each cache can store three subfiles. In the placement phase, we let user i caches the three XORed subfiles as Each user then stores 9 exclusive subfiles in an XORed version and each subfile can be found in the cache of one and only one user.
In the transmissions phase, let us assume that user 1 needs A, user 2 needs B, user 3 needs C, user 4 needs A and user 5 requests B. Similar to Example 3, we deliver the subfile list (  It is worth pointing out that, the cut-set bound at the point M = 1/5 is R * (1/5) = 3 − 3/5 = 12/5 and equals the achievable rate R(1/5). By memory sharing, the cut-set bound is therefore achievable in the interval M ∈ [0, 1/5] in this example.

V. PROOF OF THEOREMS
We now present the achievable scheme for an arbitrary number of users with K ≥ N. We shall show that with the cache size of M ≤ 1/ max(N, K), the delivery rates presented in Theorem 1-2 are achievable and the cut-set bound is met for such points with cache size M ≤ 1/ max(N, K).

A. Proof of Theorem 1
Here we prove Theorem 1 for the case with an equal number of files and users, i.e., N = K. We prove it in two folds. Firstly, we verify that the point (1/N,N − 1) is achievable by a constructed coded caching scheme. Secondly, we show that any points with M < 1/N can achieve a rate of N − NM by memory sharing.
In the placement phase, the cache of user j is designed to be Z j = W 1j ⊗ . . . ⊗ W N j , an XORed version of subfiles, which contains one and only one subfile from all files. With this coded placement scheme, each user caches some exclusive part of all files.
In the delivery phase, if the users request L ≤ N − 1 files, we can simply transmit these requested files and the delivery rate is L files. We then move to the case that the users request N files, i.e., each user requests a different file. Due to symmetry, we only need to study the case that user i requests file W i .
The transmission algorithm is therefore presented as follows.
As for each file (N − 1)/N fraction of it is delivered, we totally deliver N − 1 files.
With this transmission, we argue that each user can obtain the files requested. For instance, for the ith user requesting W i , it can obtain all subfiles except W ii from the delivery of W i directly. In addition, user i receives all W ki (j = i) subfiles from file W k . Hence it can obtain the subfile W ii by

B. Proof of Theorem 2
Here we prove Theorem 2 for the case with N < K. The files are defined by W i (i = 1, . . . , N) and we split each file into NK subfiles, i.e., W i = (W i,1 , . . . , W i,N K ).
In the placement phase, the cache of user i is designed to store N XORed version of subfiles, which are, With this coded placement scheme, each user caches some exclusive part of all files and the union set of the caches comprises all N files in the server.
In the delivery phase, if all users request L (L ≤ N − 1) distinct files in total, we can simply transmit these requested files one by one and the total amount of files delivered is L files and the associated rate is less than N − N/K. We then move to the case that all N files are requested. Suppose user i requests the file W d i and correspondingly the subfile W i is requested by totally k i users. By definition, we hence The transmission procedure can be divided into two steps as follows.
2) In the second step, for the rest subfiles requested by users, we apply the following algorithm by firstly grouping the users requesting the same file and then applying coding strategy to reduce transmissions. The details are presented as follows. ii) If u = 1, deliver the N coded subfiles, W i,N (K 1 −1)+j ⊕ W i,N (K 2 −1)+j (j = 1, . . . , N) and set u ← u + 1.
iv) If u < k i − 1 go to Step iii), otherwise terminate the delivery of subfiles of W i .
Note that in step 2), a) follows from two facts. The first is that the ith user obtains W d i ,N (i−1)+j (j = 1, . . . , N) via coded delivery. The second is that it receives directly W d i ,N (k−1)+j (k = i and j = 1, . . . , N) in the first step because they are delivered for other users for XORing. Therefore, the ith user can reconstruct the full file W d i directly after Step 1).
Similarly for the case that W i is requested by more than one users (k i > 1) in b) of Step 2), the fact that each user requesting W i needs (k i − 1)N follows also from two facts. The first is that it receives N subfiles via coded delivery in Step 1). The second is that it directly receives N(K − k i ) subfiles for the users requesting other files in Step 1). Therefore, only NK − N − N(K − k i ) = N(k i − 1) subfiles is requested by each of the users requesting W i .
In the following, we shall show that the sub-algorithm in b) in Step 2) can help all users requesting W i receive all the residue files.
Note that for user K m requesting W i , it receives the subfile list (W i,N (Km−1)+j ⊕ W i,N (K m+1 −1)+j ) (m = 1, . . . , k i −1, j = 1, . . . , N). It can firstly obtain W i,N (K m−1 −1)+j and W i,N (K m+1 −1)+j (j = 1, . . . , N) from the m−1th and the m delivery of subfiles via XORing. It can then recursively obtain W i,N (K m−k −1)+j (k = 2, . . . , m − 1) and W i,N (K m+k −1)+j (k = 2, . . . , k i − m). Hence, user K m can obtain the complete file W i . In a similar manner, we can verify that any other users in the same group requesting W i can receive the complete file W i .
As W i is an arbitrary file in the server, we conclude that all users can obtain the requested file by our algorithm and in the following we shall derive the achievable rate for M = 1/K by applying the algorithm above. We first denote C i as the amount of subfiles delivered in Step i) and n k i as the amount of the XORed version of subfiles delivered for W i in Step 2). In Step 1), it is observed that the total amount of subfiles delivered is given by, As designed in Step 2) for file W i , the total amount of the remaining transmissions is Therefore, the total amount of subfiles delivered in the second step is The total amount of subfile deliveries in these two steps is given by The associated delivery rate therefore is and we can claim that (1/K, R(1/K)) = (1/K, N(1 − 1/K) is an achievable cache-rate pair. In addition, regarding the trivial cache-rate pair (0, N), for any M ≤ 1/K, the rate pair (M, N(1 − M)) is achievable by memory sharing. Theorem 2 is hence proved.

C. Proof of Theorem 3 and Theorem 4
Here we show that the achieved rate given in Theorem 3 and Theorem 4 for the scenario with N ≤ K and M ≤ 1/K coincides with the lower cut-set bound.
From [10], the cut-set lower bound is given by, From the above derivation, it is hence concluded that for the scenario N ≤ K and M ≤ 1/K, the lower cut-set bound is achievable. Theorem 3 and Theorem 4 are therefore verified.

VI. CONCLUSION
In this work, we studied the caching problem when all users are with a small buffer size and the number of users is no less than the amount of files in the server. A novel coded caching scheme was proposed to achieve the cut-set bound rate for such a scenario.