On Coded Caching with Heterogeneous Distortion Requirements
Abdelrahman M. Ibrahim Ahmed A. Zewail Aylin Yener








 



Wireless Communications and Networking Laboratory (WCAN)

School of Electrical Engineering and Computer Science

The Pennsylvania State University, University Park, PA 16802.

{ami137,zewail}@psu.edu     yener@engr.psu.edu


On Coded Caching with Heterogeneous Distortion Requirements
    Aylin Yener
    Received: date / Accepted: date
===========================================================




This paper considers heterogeneous coded caching where the users have unequal distortion requirements. The server is connected to the users via an error-free multicast link and designs the users' cache sizes subject to a total memory budget. In particular, in the placement phase, the server jointly designs the users' cache sizes and the cache contents. To serve the users' requests, in the delivery phase, the server transmits signals that satisfy the users' distortion requirements. An optimization problem with the objective of minimizing the worst-case delivery load subject to the total cache memory budget and users' distortion requirements is formulated. The optimal solution for uncoded placement and linear delivery is characterized explicitly and is shown to exhibit a threshold policy with respect to the total cache memory budget. As a byproduct of the study, a caching scheme for systems with fixed cache sizes that outperforms the state-of-art is presented.  











§ INTRODUCTION

Wireless data traffic is increasing at an unprecedented rate due to the demand on video streaming services, which have accounted for 60 percent of total mobile data traffic in 2016 <cit.>. Efficient utilization of network resources is essential in order to accommodate the growth in data traffic. Caching utilizes the cache memories in the network nodes to shift some of the data traffic to off-peak hours. Reference <cit.> has proposed coded caching, where the end-users' cache contents are designed in a way to enable subsequently serving the users using multicast transmissions, reducing the delivery load on the server.



The significant gain achieved by coded caching has motivated studying its fundamental limits in various setups <cit.>. For instance, references <cit.> have studied coded caching in multi-hop networks. Coded caching for device-to-device (D2D) networks has been studied in <cit.>. Caching with security requirements have been studied in <cit.>.


Content delivery networks consists of heterogeneous end-devices that have varying storage, computational capabilities, and viewing preferences. In turn, the effect of heterogeneity in cache sizes on the delivery load has been studied in <cit.>. Additionally, optimizing the users' cache sizes subject to a network-wide total memory budget has been considered in <cit.>.





The heterogeneity in users' preferences for content motivates developing coded caching schemes with different quality-of-service requirements per user. In this realm, coded caching schemes with heterogeneous distortion requirements have been studied in references <cit.>. In particular, reference <cit.> has considered a centralized system where files are modeled as independent and identically distributed (i.i.d.) samples from a Gaussian source. Each file is represented by a number of layers equal to the number of users in the system, and accessing the first k layers guarantees that the kth user's distortion requirement is satisfied. In this setup, reference <cit.> has minimized the squared error distortion for given delivery load, cache sizes, and popularity distribution. Reference <cit.> has studied the problem of minimizing the delivery load in a centralized caching system with heterogeneous distortion requirements and heterogeneous cache sizes at the users. In particular, reference <cit.> has considered a separation approach where the memory allocation over the layers and the caching scheme are optimized separately. 




In this work, like reference <cit.>, we study the problem of minimizing the delivery load given heterogeneous distortion requirements at the users. Different from references <cit.> and <cit.>, we consider that the server not only designs the users' cache contents, but also optimizes their cache sizes subject to a total cache memory budget. In contrast to <cit.>, we jointly design the users cache sizes, the memory allocation over the layers, and the caching scheme in order to minimize the delivery load that achieves certain distortion requirements at the users. Under uncoded placement and linear delivery, we show that the joint optimization problem reduces to a memory allocation problem over the layers which can be solved analytically. In particular, the memory allocation over the layers is obtained using a threshold policy, which depends on the available total cache memory budget and the target distortion requirements at the users. We extend the cut-set bound in <cit.> to systems with total cache memory budget and compare it with the delivery load achieved by the proposed scheme. We observe that the cut-set bound is achievable for large total cache memory budgets.


Although our primary goal in this study is to demonstrate the merit of optimally allocating the cache sizes at different users, we note that the new caching scheme we propose improves on the caching schemes in <cit.> for systems with fixed cache sizes, since we jointly optimize the caching scheme and the memory allocation over the layers. More specifically, the flexibility in our scheme allows us to exploit the multicast opportunities over all layers. Our numerical results confirm the gain attained by our proposed scheme over the two caching schemes presented in <cit.>. Finally, we present a numerical example that shows the suboptimality of exploiting only the intra-layer multicast opportunities without taking into account the inter-layer multicast opportunities.










 


Notation: Vectors are represented by boldface letters, ⊕ refers to bitwise XOR operation, |W| denotes size of W, A ∖ B denotes the set of elements in A and not in B, [K] ≜{1,…,K}, ϕ denotes the empty set, ⊊_ϕ [K] denotes non-empty subsets of [K].










§ SYSTEM MODEL



We consider a server connected to K users via an error-free multicast network, see Fig. <ref>. The server has a library of N files, W_1, …, W_N, each file W_j consists of F i.i.d. samples [S_j,1,…,S_j,F] from a uniform discrete source. That is, S_j,i is uniformly distributed over 𝔽_q, Pr(S_j,i=s)=1/q for s ∈𝔽_q. We use Hamming distortion as our distortion measure, i.e., we have 

    d(s,ŝ)= 0,  if  s=ŝ,
    
    1,  if  s≠ŝ.

The rate-distortion function for a uniform discrete source with Hamming distortion is given as <cit.> 

    ρ(D)=log(q)-H(D)-Dlog(q-1),

where 0 ≤ D ≤ 1-1/q. Since a uniform discrete source with Hamming distortion is successively refinable <cit.>, each file can be represented using a scalable layered description that achieves the target rate r_l ≜ρ(D_l) at layer l for distortion requirements D_1 ≥ D_2 ≥…≥ D_K. In particular, layer 1 of each file is a coarse description with size r_1 F bits, while layer l ∈{2,…,K} is a refinement with size (r_l-r_l-1)F bits. In turn, we represent file W_j by W_j^(1),…,W_j^(K), where W_j^(l) denotes layer l of file j. Additionally, we have that D_k is the distortion requirement at user k, i.e., user k needs layers {1,…,k} in order to decode the requested file. Consequently, we define the target rate vector r=[r_1,..,r_K].


The sizes of the users' cache memories are determined by the server. In particular, the server allocates M_k F bits to user k such that ∑_k=1^K M_k F ≤  m_tot N F bits, where m_tot is the cache memory budget normalized by library size NF. We also define m_k=M_k/N, to denote the memory size at user k normalized by the library size N F. We consider the regime where the number of files is greater than or equal the number of users, i.e., N ≥ K, and M_k ∈ [0,N r_k],  ∀ k ∈ [K] which implies m_k ∈ [0,r_k],  ∀ k ∈ [K]. We denote the memory size vector by M =[M_1,…,M_K] and its normalized version by m =[m_1,…,m_K]. 

The system has two operational phases: placement and delivery  <cit.>. In the placement phase, the server assigns the users' cache sizes and the contents of the users' cache memories subject to the distortion requirements D=[D_1,…,D_K] and the cache memory budget m_tot, without the knowledge of the users' demands. In particular, the server places a subset of the library, Z_k, at the cache memory of user k, such that |Z_k| ≤ M_k F bits. In the delivery phase, user k requests the file W_d_k which must be recovered with an average distortion less than or equal to D_k. Equivalently, user k requests layers [k] from file W_d_k. The requested files are represented by the demand vector d=[d_1, …, d_K]. We assume that d consists of identical and independent uniform random variables over the files <cit.>. In order to guarantee the desired distortion requirements at the users, the server needs to deliver the bits that are not cached by the users in each requested layer. In particular, the server sends the signals X_ T,  d to the users in the sets T ⊊_ϕ [K]. User k should be able to decode W^(1)_d_k,…,W^(k)_d_k by utilizing the cached contents Z_k and the transmitted signals X_ T,  d,  T ⊊_ϕ [K]. Formally, we have the following definitions.
 For a given file size F, a caching scheme is defined by the collection of cache placement, encoding, and decoding functions (φ_k(.),ψ_ T,  d(.),μ_ d, k(.)). A cache placement function 

    φ_k: 𝔽_q^F ×…×𝔽_q^F → [2^M_kF],

maps the N files to the cache of user k, i.e., Z_k = φ_k(W_1, W_2,..,W_N). Given a demand vector d, an encoding function 

    ψ_ T,  d: 𝔽_q^F ×…×𝔽_q^F → [2^v_ TF],

maps the requested files to a signal with length v_ T F bits, which is sent to the users in T, i.e., X_ T, d= ψ_ T,  d( W_d_1,..,W_d_K). Finally, a decoding function 

    μ_ d, k: [2^M_kF] × [2^RF] →𝔽_q^F,

with  R ≜∑_ T ⊊_ϕ [K] v_ T, maps Z_k and X_ T,  d, T ⊊_ϕ [K] to Ŵ_d_k, i.e., Ŵ_d_k = μ_ d, k(X_{1},  d,X_{2},  d,…,X_[K],  d, Z_k ). 


For given normalized cache sizes m, distortion requirements D_1 ≥ D_2 ≥…≥ D_K, and r_l =ρ(D_l), the delivery load R( m,  r) is achievable if there exists a sequence of caching schemes such that lim_F →∞1F∑_i=1^F d(S_d_k,i,Ŝ_d_k,i) ≤ D_k, ∀ k ∈ [K], ∀ d_k ∈ [N]. Furthermore, the infimum over all achievable delivery loads is denoted by R^*( m,  r). 

In this work, we consider the class of cache placement schemes, 𝔄, in which user k cache uncoded pieces of layers [k] of the files, and the class of delivery schemes, 𝔇, where the multicast signals are formed using linear codes. Note that the uniform demands assumption implies that each user should cache the same number of bits from all files, i.e., user k dedicates m_k F bits to each file.
 For given normalized cache sizes m and target rates r, 
the worst-case delivery load under an uncoded placement scheme in 𝔄, and a linear delivery policy in 𝔇, is defined as 

    R_𝔄, 𝔇( m,  r) ≜max_ d ∈ [N]^K  R_ d,𝔄, 𝔇  =  ∑_ T ⊊_ϕ [K] v_ T.

Furthermore, by taking the infimum over 𝔄 and all possible delivery policies, we get R^*_𝔄( m,  r).

The trade-off between the delivery load and the total cache memory budget is defined as follows.
 For given normalized cache memory budget m_tot and target rate vector r, the infimum over all achievable worst-case delivery loads is given as

    R^*(m_tot,  r)= inf_ m ∈ M(m_tot,  r) R^*( m,  r),

where M(m_tot,  r)={ m |  0 ≤ m_k ≤ r_k,  ∑_k=1^K m_k = m_tot}. Furthermore, we have

    R^*_𝔄(m_tot,  r)= inf_ m ∈ M(m_tot,  r) R^*_𝔄( m,  r).






§ A NOVEL CACHING SCHEME

Given the layered description of the files explained in Section <ref>, the problem of designing the users' cache contents, under the uncoded placement assumption, can be decomposed into K placement problems, each of which corresponds to one of the layers <cit.>. In particular, the cache memory at user k is partitioned over layers [k] and m_k^(l) denotes the normalized cache memory dedicated to layer l at user k. In turn, the placement problem of layer l is equivalent to the placement problem with K-l+1 users and unequal cache memories m^(l)=[m_l^(l),…,m_K^(l)] addressed in <cit.>. By contrast, in the delivery phase, decoupling over the layers is suboptimal. That is, we need to jointly design the multicast signals over all layers, in order to utilize all multicast opportunities. Next, we explain the cache placement and delivery schemes in detail.







 §.§ Placement Phase

Under uncoded placement, the placement phase is decomposed into K layers. In particular,  layer l of each file is partitioned over users {l,…,K}. That is, W^(l)_j is divided into subfiles, W̃^(l)_j, S,  S ⊂{l,…,K}, which are labeled by the set of users S exclusively storing them. We assume that |W̃^(l)_j, S|= a^(l)_ S F bits ∀ j ∈ [N], i.e., we have symmetric partitioning over the files and the allocation variable a^(l)_ S∈ [0,r_l-r_l-1] defines the size of W̃^(l)_j, S. In turn, the set of feasible placement schemes for layer l is defined by 

    𝔄^(l)( m^(l), r)    =   { a^(l)|∑_ S ⊂{l,…,K}   a^(l)_ S =r_l-r_l-1, 
       ∑_ S ⊂{l,…,K}:   k ∈ S  a^(l)_ S ≤ m_k^(l), ∀ k ∈{l,…,K}},

where a^(l) is the vector representation of { a^(l)_ S}_ S. Note that the first constraint follows from the fact that the lth layer of each file is partitioned over the sets S ⊂{l,…,K}, while the second constraint represents the cache size constraint at layer l for user k. Therefore, the cache content placed at user k is given by

    Z_k = ⋃_l ∈ [k] ⋃_j ∈ [N] ⋃_ S ⊂{l,…,K}:   k ∈ S W̃^(l)_j, S.







 §.§ Delivery Phase

In order to deliver the missing subfiles, the server sends the sequence of unicast/multicast signals X_ T,  d, T ⊂ [K]. In particular, the multicast signal to the users in T is defined by  

    X_ T,  d= ⊕_j ∈ T ⋃_l=1^L W^(l), T_d_j,

where L ≜min_i ∈ T i and W^(l), T_d_j denotes a subset of W^(l)_d_j which is delivered to user j via X_ T,  d. W^(l), T_d_j is constructed using the side-information available at the users in T ∖{j}. That is, if W_d_j, S^(l), T denotes the subset of W^(l), T_d_j cached by the users in S, then we have

    W^(l), T_d_j = ⋃_ S ⊂{l,…,K}∖{j}:   T ∖{j}⊂ S W_d_j, S^(l), T.

Additionally, we denote |X_ T,  d|=∑_l=1^L |W^(l), T_d_j|= v_ T F bits ∀ j ∈ T and |W_d_j, S^(l), T|= u^(l), T_ S F bits. That is, the transmission variable v_ T∈ [0,r_L] and the assignment variable u^(l), T_ S∈ [0,a^(l)_ S] determine the structure of the signal X_ T,  d. Furthermore, the unicast signal X_{k},  d delivers the missing pieces of ⋃_l=1^k W^(l)_d_k to user k, i.e., the pieces that had not been delivered by multicast signals and are not cached by user k. We assume |X_{k},  d|= ∑_l=1^k v_{k}^(l) F bits.

Next, we explain that all linear delivery schemes under uncoded placement can be described by the following linear constraints on the transmission and assignment variables. In particular, for given allocation { a^(l)}_l, the set of linear delivery schemes, 𝔇( a^(1),…, a^(K), r), is defined by

    v_ T = ∑_l=1^L∑_ S ∈ B^(l), T_j u^(l), T_ S,  ∀ T ⊂ [K]  s.t.  | T| ≥ 2, ∀ j ∈ T, 
         v_{k}^(l) +∑_ T ⊂{l,…,K} :  k ∈ T, | T|≥ 2∑_ S ∈ B^(l), T_k u^(l), T_ S + ∑_ S ⊂{l,…,K} :  k ∈ S  a_ S^(l)≥
                      r_l  -  r_l-1, ∀ l ∈ [K],  ∀ k ∈{l,…,K}, 
       ∑_ T ⊂{l,…,K} :   j ∈ T,  T ∩ S ≠ϕ u^(l), T _ S≤ a_ S^(l), ∀ l ∈ [K], ∀ j ∉ S, ∀ S ∈ A^(l), 
        0 ≤ u_ S^(l), T≤ a_ S^(l),∀ l ∈ [K], ∀ T ⊊_ϕ{l,…,K}, ∀ S ∈ B^(l), T,

where 

    B^(l), T_j   ≜{ S ⊂{l,…,K}∖{j}:   T ∖{j}⊂ S },
     A^(l)   ≜{ S ⊂{l,…,K} : 2 ≤ | S| ≤ K-l },

and B^(l), T≜⋃_j ∈ T B^(l), T_j.




The structural constraints in (<ref>) follows from the structure of the multicast signals in (<ref>) and (<ref>). The delivery completion constraints in (<ref>) guarantee that the unicast and multicast signals complete the lth layer of the requested files, and the redundancy constraints in (<ref>) prevent the transmission of redundant bits to the users. For example, for K=3, the structural constraints are defined as


    v_{1,2}   =  u^(1),{1,2}_{2} +  u^(1),{1,2}_{2,3} =  u^(1),{1,2}_{1} +  u^(1),{1,2}_{1,3}, 
    
    v_{1,3}   =  u^(1),{1,3}_{3} +  u^(1),{1,3}_{2,3} =  u^(1),{1,3}_{1} +  u^(1),{1,3}_{1,2}, 
    
    v_{2,3}   =  u^(1),{2,3}_{3} + u^(1),{2,3}_{1,3} + u^(2),{2,3}_{3}, 
       = u^(1),{2,3}_{2} +  u^(1),{2,3}_{1,2} +  u^(2),{2,3}_{2}, 
     v_{1,2,3}   =  u^(1),{1,2,3}_{2,3} =  u^(1),{1,2,3}_{1,3} =  u^(1),{1,2,3}_{1,2},

 
the delivery completion constraints for user 3 are defined as


    v_{3}^(1) + ( u^(1),{1,3}_{1} +  u^(1),{1,3}_{1,2})  + ( u^(1),{2,3}_{2} +  u^(1),{2,3}_{1,2})  + 
       u^(1),{1,2,3}_{1,2} + ( a_{3}^(1) +  a_{1,3}^(1) + a_{2,3}^(1) + a_{1,2,3}^(1)) ≥ r_1, 
       v_{3}^(2)  +  u^(2),{2,3}_{2}  +  a_{3}^(2)  +  a_{2,3}^(2)≥  r_2  - r_1, 
       v_{3}^(3) + a_{3}^(3)≥ r_3  -  r_2,


and the redundancy constraints are defined as


    u^(1),{1,3}_{1,2}  +  u^(1),{2,3}_{1,2}  +  u^(1),{1,2,3}_{1,2}   ≤   a^(1)_{1,2}, 
    
    u^(1),{1,2}_{1,3}+u^(1),{2,3}_{1,3}+u^(1),{1,2,3}_{1,3}   ≤ a^(1)_{1,3}, 
    
    u^(1),{1,2}_{2,3}+u^(1),{1,3}_{2,3}+u^(1),{1,2,3}_{2,3}   ≤ a^(1)_{2,3}.


We denote the vector representation of the transmission variables { v_ T}_ T, {v_{k}^(l)}_k,l and the assignment variables { u^(l), T_ S}_l, T,  S by v and u, respectively.







§ FORMULATION



In this section, we demonstrate that the problem of minimizing the worst-case delivery load by optimizing over the users' cache sizes, uncoded placement, and linear delivery, can be formulated as a linear program. In particular, given the target rate vector r, the total memory budget m_tot, and N ≥ K, the minimum worst-case delivery load under uncoded placement and linear delivery, R^*_𝔄,𝔇(m_tot, r), is characterized by 
 

    O1:       min_ a^(l), u , v, m^(l)      ∑_ T ⊊_ϕ [K]  v_ T
       subject to       a^(l)∈𝔄^(l)( m^(l), r), ∀ l ∈ [K]
              ( u,  v) ∈𝔇( a^(1),…, a^(K), r),
             ∑_k=1^K∑_l=1^k m_k^(l) = m_tot,


where 𝔄^(l)( m^(l), r) is the set of uncoded placement schemes in layer l defined in (<ref>) and 𝔇( a^(1),…, a^(K), r) is the set of feasible linear delivery schemes defined by (<ref>)-(<ref>).

We can also solve the problem of designing the caching scheme and the memory allocation over the layers for systems with fixed cache sizes as in <cit.>. In particular, for fixed cache sizes m, the minimum worst-case delivery load under uncoded placement and linear delivery, R^*_𝔄,𝔇( m, r), is characterized by
 

    O2:       min_ a^(l), u , v, m^(l)      ∑_ T ⊊_ϕ [K]  v_ T
       subject to       a^(l)∈𝔄^(l)( m^(l), r), ∀ l ∈ [K]
              ( u,  v) ∈𝔇( a^(1),…, a^(K), r),
             ∑_l=1^k m_k^(l) = m_k, ∀ k ∈ [K].


In contrast to the formulation in reference <cit.>, observe that in (<ref>), we jointly design the caching scheme and the memory allocation over the layers, and exploit multicast opportunities over different layers. 




§ OPTIMAL CACHE ALLOCATION

In this section, we first characterize the solution to the optimization problem in (<ref>), i.e., we find the achievable worst-case delivery load assuming uncoded placement and linear delivery. Then, we present a lower bound on the trade-off between the minimum worst-case delivery load under any caching scheme and the cache memory budget.


Given the target rate vector r, N ≥ K, and the total memory budget m_tot= ∑_l=1^K t_l f_l, where f_1 ≜ r_1, f_l ≜ r_l-r_l-1 for l>1, t_l ∈{0,1,…,K-l+1} and t_l+1≤ t_l ≤ t_l-1, the minimum achievable worst-case delivery load under uncoded placement is given by

    R^*_𝔄,𝔇(m_tot, r)= R^*_𝔄( r,m_tot)  = ∑_l=1^K(K-l+1)-t_l1+t_lf_l.

Furthermore, for general m_tot∈ [0,∑_k=1^Kr_k], R^*_𝔄,𝔇( r,m_tot) is defined by the lower convex envelope of these points.

 In Appendix <ref>, we show that the optimal solution to the optimization problem in (<ref>) achieves the lower convex envelope of the delivery load points in (<ref>). In particular, for m_tot= ∑_i=1^K t_i f_i where t_l ∈{0,1,…,K-l+1} and t_l+1≤ t_l ≤ t_l-1, the optimal memory allocation is defined as m_k^(l)=t_l f_l/(K-l+1) for k ∈{l,…,K}, i.e., the users are assigned equal cache sizes in each layer. In turn, we apply the MaddahAli-Niesen caching scheme in each layer, i.e., in layer l the placement phase is defined by

    |W̃^(l)_j, S|   =  f_l/K-l+1t_l F,  for  | S| =t_l,
    
    0,  otherwise.

and the multicast signals are defined by ⊕_j ∈ TW̃^(l)_d_j, T ∖{j} for T ⊂{l,…,K} and | T| =t_l+1.








In general, any m_tot∈ [0, ∑_i=1^Kr_i] can be represented as ∑_i=1^K t_i f_i where t_i=x, for i=[y], t_y=x-1+α, t_i=x-1, for i={y+1,…,K-x+1}, t_i=K-i+1, for i={K-x+2,…,K}, for some x∈ [K], y ∈ [K-x+1] and 0<α<1. In particular, we have 

    x ≜1,  0 < m_tot≤∑_i=1^Kf_i, 
    ⋮
    
    j, (j-1)∑_i=1^K-j+1 f_i +∑_i=K-j+2^K(K-i+1)f_i  < m_tot≤ j∑_i=1^K-j f_i 
    ⋮                               +∑_i=K-j+1^K(K-i+1)f_i, 
    
    K,   (K-1)f_1 +∑_i=2^K(K-i+1)f_i  < m_tot≤∑_i=1^K r_i.

and for a given x, we have y=b if 

    x∑_i=1^b-1f_i   +(x-1)∑_i=b^K-x+1f_i+∑_i=K-x+2^K(K-i+1)f_i < m_tot≤
       x∑_i=1^bf_i+(x-1)∑_i=b+1^K-x+1f_i+∑_i=K-x+2^K(K-i+1)f_i.


In turn, any m_tot∈ [0,∑_k=1^Kr_k] can be represented as 

    m_tot   =  x ∑_l=1^y-1  f_l+(x- 1+α)f_y +(x-1) ∑_l=y+1^K-x+1f_l + 
          ∑_l=K-x+2^K  (K-l+1)f_l,

and the corresponding minimum worst-case delivery load under uncoded placement and linear delivery is given by

    R^*_𝔄,𝔇(m_tot, r)  = ∑_l=1^y-1K-l-x+1x+1f_l + ∑_l=y+1^K-x+1K-y-x+2xf_l+ 
             (2(K-y)-x+3x+1-(K-y+2)(x-1+α)x(x+1))f_y.



For example, for K=3, the corner points of the delivery load cache budget trade-off under uncoded placement in (<ref>) are defined as follows













    R^*_𝔄,𝔇(m_tot, r)  = r_1+r_2+r_3, for  m_tot=0, 
    
    r_2+r_3-r_1, for  m_tot = r_1, 
    
    r_1/2+r_3-r_2/2, for  m_tot = r_2, 
    
    r_1/2+r_2/2, for  m_tot = r_3, 
    
    r_2/2-r_1/6, for  m_tot = r_1+r_3, 
    
    r_1/3, for  m_tot = r_2+r_3, 
    
    0, for  m_tot = r_1+r_2+r_3,

which are illustrated in Fig. <ref>, for r=[0.5,   0.7,   1].





























Next, we extend the lower bound on the delivery load for systems with fixed cache sizes in <cit.> to systems with cache memory budget.

 (Extension of <cit.>)
Given N ≥ K, the target rate vector r, and the total memory budget m_tot∈ [0,∑_k=1^Kr_k], the infimum over all achievable delivery loads R^*(m_tot, r) is lower bounded by

    min_ m ∈ M(m_tot,  r){max_ U ⊂ [K]{∑_k ∈ U r_k -N ∑_k ∈ Um_k⌊ N/| U|⌋}},

where M(m_tot,  r)={ m |  0 ≤ m_k ≤ r_k,  ∑_k=1^K m_k = m_tot}. 

For the three-user case, the cut-set bound can be simplified as follows. 
 Given K=3, N ≥ 3, the target rate vector r, and the total memory budget m_tot∈ [0,∑_k=1^Kr_k], the infimum over all achievable delivery loads R^*(m_tot, r) is lower bounded by

    max{∑_l=1^3 r_l - N⌊ N/3⌋ m_tot,  ⌊ N/2⌋ (r_1 +r_2)+ N r_3 N+ ⌊ N/2⌋- 
                   NN+⌊ N/2⌋ m_tot,  13( ∑_l=1^3 r_l - m_tot) }.






















§ DISCUSSION AND NUMERICAL RESULTS

In this section, we first consider systems with total cache memory budget and present numerical examples that illustrate the optimal solution of (<ref>). Then, we consider systems with fixed cache sizes and illustrate the gain achieved by our caching scheme compared to the schemes proposed in <cit.>.




 §.§ Systems with Total Cache Memory Budget


In Fig. <ref>, we compare the achievable worst-case delivery load R^*_𝔄(m_tot,  r) defined in Theorem <ref> with the lower bound on R^*(m_tot,  r) defined in Proposition <ref>, for K=N=3 and the target rates r =[0.5,   0.7,   1]. In particular, for K=3 the corner points of the achievable delivery load are defined in (<ref>) and the cut-set bound in (<ref>) for N=3 is 

    max{∑_l=1^3 r_l - 3 m_tot, r_1  +  r_2  +  3 r_3 -  3 m_tot4, 1/3(∑_l=1^3 r_l  -  m_tot) } .


We observe that for large memory budget, ∑_l=2^K r_l ≤ m_tot≤∑_l=1^K r_l, the cut-set bound can be achieved and the delivery load R^*(m_tot,  r)= 1/K( ∑_l=1^K r_l  -  m_tot).



Recall the notation f_l=(r_l-r_l-1) and r_0=0. Fig. <ref> shows the optimal allocation for the users' cache sizes that correspond to the achievable delivery load in Fig. <ref>. From Fig. <ref>, we observe the optimal memory allocation follows a threshold policy. In particular, we have 


  * If m_tot = α f_1 and α∈ [0,1], then m = [α f_1/3,  α f_1/3,  α f_1/3].

  * If m_tot=f_1  + α f_2 and α∈ [0,1], then m = [f_1/3,   f_1/3+α f_2/2,   f_1/3+α f_2/2].

  * If m_tot=f_1  +  f_2  + α f_3 and α∈ [0,1], then m = [f_1/3,   f_1/3+f_2/2,   f_1/3+f_2/2  + α f_3].

  * If m_tot=(1+α)f_1  +  f_2  +  f_3 and α∈ [0,1], then m = [(1+α)f_1/3,   (1+α)f_1/3+f_2/2,   (1+α)f_1/3+f_2/2  +  f_3].

  * If m_tot=2f_1  +  (1+α)f_2  +  f_3 and α∈ [0,1], then m = [2f_1/3,   2f_1/3+(1+α)f_2/2,   2f_1/3+(1+α)f_2/2  +  f_3].

  * If m_tot=(2+α)f_1  +  2f_2  +  f_3 and α∈ [0,1], then m = [(2+α)f_1/3,   (2+α)f_1/3+f_2,   (2+α)f_1/3+f_2  +  f_3].







 §.§ Systems with Fixed Cache Sizes


For systems with fixed cache sizes, we compare the delivery load achieved by our scheme which performs joint design of the memory allocation over the layers and the caching scheme, with the two separation based schemes in <cit.>. In reference <cit.>, the memory allocation over the layers follows one of the following heuristic methods:


  * Proportional cache allocation (PCA), where user k cache size for layer l is defined as m_k^(l)=f_l m_k / r_k. 

  * Ordered cache allocation (OCA), where user k allocates all of its cache to the first b layers if r_b-1< m_k < r_b. 

In turn, in layer l, we have a caching system that consists of K-l+1 users with fixed cache sizes m^(l). Reference <cit.> has proposed designing the caching scheme in each layer separately, i.e., the multicast signals utilize the side-information from one layer. In particular, in layer l, the cache sizes m^(l) are further divided into sublayers of equal size and the MaddahAli-Niesen scheme is applied on each sublayer. Additionally, reference <cit.> has formulated an optimization problem in order to identify the optimal distribution of f_l over the sublayers. We refer to this scheme as the layered scheme. 




Fig. <ref> shows the delivery load obtained from (<ref>), the delivery load achieved by PCA/OCA combined with the layered scheme, and the cut-set bound in <cit.>, for K=N=3, r =[0.5,   0.8,   1], and m_k=0.8   m_k+1. We observe that the delivery load achieved by (<ref>) is lower than the one achieved by the schemes in <cit.>. This is attributed to the fact that we not only jointly optimize the memory allocation over the layers and the caching scheme, but also exploit the multicast opportunities over all layers. However, the performance improvement comes at the expense of higher complexity, since the dimension of the optimization problem in (<ref>) grows exponentially with the number of users.

The next example illustrates the suboptimality of exploiting the multicast opportunities in each layer separately.


For m=[0.1,   0.2,   0.6] and r =[0.2,   0.3,   0.8], the optimal solution of (<ref>) is as follows Placement phase: 


  * Layer 1: W^(1)_j is divided into subfiles W̃^(1)_j,{3} and W̃^(1)_j,{1,2}, such that a^(1)_{3}=a^(1)_{1,2}=0.1.

  * Layer 2: W^(2)_j is stored at user 2, i.e., a^(2)_{2}=0.1.

  * Layer 3: W^(3)_j is stored at user 3, i.e., a^(3)_{3}=0.5.


Delivery phase: We have two multicast transmissions X_{1,3},  d and X_{2,3},  d, such that


  * X_{1,3},  d= W^(1),{1,3}_d_1,{3}⊕ W^(1),{1,3}_d_3,{1,2}, where v_{1,3}=a^(1)_{3}=a^(1)_{1,2}=0.1.

  * X_{2,3},  d= W^(1),{2,3}_d_2,{3}⊕ W^(2),{2,3}_d_2,{2}, where v_{2,3}=a^(1)_{3}=a^(2)_{2}=0.1.

The optimal solution of (<ref>) achieves the delivery load R^*_𝔄,𝔇( m, r) =0.2 compared to 0.2167 which is achieved by exploiting only the intra-layer multicast opportunities. 







































§ CONCLUSION

In this paper, we have studied coded caching systems with heterogeneous distortion requirements. In addition to designing the caching scheme, the server allocates the sizes of the cache memories at the end users, subject to a total cache budget constraint over the set of all users. Assuming uncoded placement and linear delivery policies, we have shown that the problem of minimizing the worst-case delivery load can be formulated as a linear program. 


The optimal memory allocation has been shown to follow a threshold policy. Furthermore, we have observed that our solution matches the cut-set bound in the large total cache memory budget region. As a byproduct, we have proposed a novel caching scheme which, for fixed cache sizes, outperforms the state-of-art schemes <cit.> by exploiting the inter-layer multicast opportunities and jointly designing the cache contents and the partitioning of the caches over the layers.  

  

























§ PROOF OF THEOREM <REF> 


In order to prove that the optimal solution of (<ref>) achieves the delivery load in Theorem <ref>, we first show the optimality of uniform cache allocation in each layer, i.e., m_k^(l)=m^(l), ∀ k ∈{l,…,K}. Then, we show that the optimal memory allocation over the layers follows the threshold policy defined by (<ref>)-(<ref>). 

Next lemma shows the optimality of allocating equal cache sizes in a caching system where the users request the same number of bits from the desired files <cit.>, which is equivalent to equal distortion requirements at the users <cit.>.

For a caching system with K users, N ≥ K files, and cache memory budget m_tot∈ [0,K], the minimum worst-case delivery load under uncoded placement

    R^*_𝔄(m_tot)= max_j ∈ [K]{2K-j+1j+1-(K+1)m_totj(j+1)},

which is achieved by uniform memory allocation and the MaddahAli-Niesen caching scheme <cit.>.


For any memory allocation m=[m_1,…,m_K], 


    R^*_𝔄( m) ≥   max_λ_0∈ℝ,λ_k≥ 0       -λ_0 - ∑_k=1^K m_k λ_k
       subject to      λ_0   + ∑_k ∈ Sλ_k   + K - | S|| S| + 1≥ 0,  ∀ S ⊂ [K],


which is obtained by considering the average cut in the lower bound under uncoded placement in <cit.>. In turn, by considering λ_k= λ,  ∀ k ∈ [K], we get

    R^*_𝔄(m_tot)    ≥max_λ≥ 0min_j ∈{0,…,K}{K-jj+1 - λ(j  -  m_tot) }, 
       =max_j ∈ [K]{2K-j+1j+1-(K+1)m_totj(j+1)},

where m_tot= ∑_k=1^K m_k.

Building on Lemma <ref>, given r and any memory allocation m^(1), …, m^(K), the minimum worst-case delivery load under uncoded placement, R^*_𝔄( m^(1), …,  m^(K), r) satisfies

    R^*_𝔄(  m^(1), …,  m^(K), r) ≥∑_l=1^K (r_l -r_l-1) 
       max_j ∈ [K-l+1]{2(K-l+1)-j+1j+1 - (K-l+2) ∑_k=l^K m^(l)_kj(j+1)} .

Furthermore, this lower bound is achievable if we consider m_k^(l)=m^(l), ∀ k ∈{l,…,K} and apply the MaddahAli-Niesen caching scheme <cit.> on each layer. In turn, the optimization problem in (<ref>) simplifies to the problem of allocating the memory over the layers, which is defined as
 

    min_ t_1,…,t_K      ∑_l=1^Kχ_l f_l
       subject to      ∑_l=1^K t_l f_l ≤ m_tot, 
              0≤ t_l ≤ K-l+1,


where m^(l)= t_l f_l/(K-l+1) and

    χ_l ≜max_j ∈ [K-l+1]{2(K-l+1)-j+1j+1-(K-l+2)t_lj(j+1)}.

Finally, we can show that the optimal solution to (<ref>) achieves the delivery load in Theorem <ref>, by solving the dual of the linear program in (<ref>).


IEEEtran

