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

arXiv:1802.10073v1 [cs.IT] 27 Feb 2018

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

Abstract—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.

I. I NTRODUCTION
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
[1]. 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 [2] 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 [2]–
[28]. For instance, references [7]–[11] have studied coded
caching in multi-hop networks. Coded caching for device-todevice (D2D) networks has been studied in [12]–[14]. Caching
with security requirements have been studied in [9], [15]–[17].
Content delivery networks consists of heterogeneous enddevices 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 [14], [18]–
[22]. Additionally, optimizing the users’ cache sizes subject
to a network-wide total memory budget has been considered
in [23]–[26].
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 [27]–[29]. In particular, reference [27] 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 [27]
has minimized the squared error distortion for given delivery
load, cache sizes, and popularity distribution. Reference [28]
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 [28] has considered a separation approach
where the memory allocation over the layers and the caching
scheme are optimized separately.
In this work, like reference [28], we study the problem of
minimizing the delivery load given heterogeneous distortion
requirements at the users. Different from references [27] and
[28], 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 [28], 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 [28] 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 [28] for systems with fixed
cache sizes, since we jointly optimize the caching scheme

Fig. 1. Caching system with heterogeneous distortion requirements D1 ≥
D2 ≥ · · · ≥ DK .

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 [28]. 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 nonempty subsets of [K].
II. S YSTEM M ODEL
We consider a server connected to K users via an errorfree multicast network, see Fig. 1. The server has a library
of N files, W1 , . . . , WN , each file Wj consists of F i.i.d.
samples [Sj,1 , . . . , Sj,F ] from a uniform discrete source. That
is, Sj,i is uniformly distributed over Fq , P r(Sj,i = s) = 1/q
for s ∈ Fq . We use Hamming distortion as our distortion
measure, i.e., we have
(
0, if s = ŝ,
d(s, ŝ) =
(1)
1, if s 6= ŝ.
The rate-distortion function for a uniform discrete source with
Hamming distortion is given as [30]
ρ(D) = log(q) − H(D) − D log(q − 1),

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 = [r1 , .., rK ].
The sizes of the users’ cache memories are determined by
the server. InP
particular, the server allocates Mk F bits to user
K
k such that k=1 Mk F ≤ mtot N F bits, where mtot is the
cache memory budget normalized by library size N F . We
also define mk = Mk /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 Mk ∈ [0, N rk ], ∀k ∈ [K] which
implies mk ∈ [0, rk ], ∀k ∈ [K]. We denote the memory size
vector by M = [M1 , . . . , MK ] and its normalized version by
m = [m1 , . . . , mK ].
The system has two operational phases: placement and
delivery [26]. 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 = [D1 , . . . , DK ]
and the cache memory budget mtot , without the knowledge of
the users’ demands. In particular, the server places a subset
of the library, Zk , at the cache memory of user k, such that
|Zk | ≤ Mk F bits. In the delivery phase, user k requests the
file Wdk which must be recovered with an average distortion
less than or equal to Dk . Equivalently, user k requests layers
[k] from file Wdk . The requested files are represented by the
demand vector d = [d1 , . . . , dK ]. We assume that d consists
of identical and independent uniform random variables over
the files [2]. 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 XT ,d to the users
in the sets T (φ [K]. User k should be able to decode
(1)
(k)
Wdk , . . . , Wdk by utilizing the cached contents Zk and the
transmitted signals XT ,d , T (φ [K]. Formally, we have the
following definitions.
Definition 1. 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
F
Mk F
ϕk : FF
],
q × · · · × Fq → [2

maps the N files to the cache of user k, i.e., Zk =
ϕk (W1 , W2 , .., WN ). Given a demand vector d, an encoding
function

(2)

where 0 ≤ D ≤ 1 − 1/q. Since a uniform discrete source
with Hamming distortion is successively refinable [31], each
file can be represented using a scalable layered description that
achieves the target rate rl , ρ(Dl ) at layer l for distortion
requirements D1 ≥ D2 ≥ · · · ≥ DK . In particular, layer 1
of each file is a coarse description with size r1 F bits, while
layer l ∈ {2, . . . , K} is a refinement with size (rl − rl−1 )F
(K)
(1)
bits. In turn, we represent file Wj by Wj , . . . , Wj , where
(l)
Wj denotes layer l of file j. Additionally, we have that Dk

(3)

F
vT F
ψT ,d : FF
],
q × · · · × Fq → [2

(4)

maps the requested files to a signal with length vT F
bits, which is sent to the users in T , i.e., XT ,d =
ψT ,d (Wd1 , .., WdK ). Finally, a decoding function
µd,k : [2Mk F ] × [2RF ] → FF
q ,

(5)

with R , T (φ [K] vT , maps Zk and XT ,d , T (φ [K] to

Ŵdk , i.e., Ŵdk = µd,k X{1},d , X{2},d , . . . , X[K],d , Zk . 
P

Definition 2. For given normalized cache sizes m, distortion

requirements D1 ≥ D2 ≥ · · · ≥ DK , and rl = ρ(Dl ), the
delivery load R(m, r) is achievable if there exists a sequence
F
1 P
d(Sdk ,i , Ŝdk ,i ) ≤
of caching schemes such that lim
F →∞ F i=1
Dk , ∀k ∈ [K], ∀dk ∈ [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, A, in which user k cache uncoded pieces of layers
[k] of the files, and the class of delivery schemes, D, 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 mk F bits to each file.
Definition 3. For given normalized cache sizes m and target
rates r, the worst-case delivery load under an uncoded
placement scheme in A, and a linear delivery policy in D,
is defined as
X
vT .
(6)
RA,D (m, r) , max Rd,A,D =
d∈[N ]K

T (φ [K]

Furthermore, by taking the infimum over A and all possible
∗
delivery policies, we get RA
(m, r).

The trade-off between the delivery load and the total cache
memory budget is defined as follows.

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

X (l)
(l)
(l)
aS = rl − rl−1 ,
A (m , r) = a(l)
S⊂{l,...,K}

(l)
aS ≤
S⊂{l,...,K}: k∈S

X

(l)
mk , ∀k


∈ {l, . . . , K} , (9)
(l)

where a(l) is the vector representation of {aS }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
[ [
[
(l)
W̃j,S .
(10)
Zk =
l∈[k] j∈[N ] S⊂{l,...,K}: k∈S

Definition 4. For given normalized cache memory budget
mtot and target rate vector r, the infimum over all achievable
worst-case delivery loads is given as
∗

R (mtot , r) =
where M(mtot , r) =
Furthermore, we have

inf

m∈M(mtot ,r)

∗

R (m, r),

(7)

o
n
K
P
mk = mtot .
m 0 ≤ mk ≤ rk ,

∗
RA
(mtot , r) =

k=1

inf

m∈M(mtot ,r)

∗
RA
(m, r).

(8)


III. A N OVEL C ACHING S CHEME
Given the layered description of the files explained in
Section II, 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 [28]. In particular, the cache memory at user k
(l)
is partitioned over layers [k] and mk 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
(l)
(l)
m(l) = [ml , . . . , mK ] addressed in [22], [26]. 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.

B. Delivery Phase
In order to deliver the missing subfiles, the server sends
the sequence of unicast/multicast signals XT ,d , T ⊂ [K]. In
particular, the multicast signal to the users in T is defined by
XT ,d = ⊕j∈T

L
[

(l),T

Wdj

,

(11)

l=1
(l),T

where L , mini∈T i and Wdj

(l)

denotes a subset of Wdj
(l),T

is constructed
which is delivered to user j via XT ,d . Wdj
using the side-information available at the users in T \ {j}.
(l),T
(l),T
cached by the
That is, if Wdj ,S denotes the subset of Wdj
users in S, then we have
[
(l),T
(l),T
Wdj ,S .
(12)
=
Wdj
S⊂{l,...,K}\{j}: T \{j}⊂S

Additionally, we denote |XT ,d | =
(l),T
|Wdj ,S

PL

(l),T
uS

l=1

(l),T

|Wdj

| = vT F

bits ∀j ∈ T and
| =
F bits. That is, the
transmission variable vT ∈ [0, rL ] and the assignment variable
(l)
(l),T
∈ [0, aS ] determine the structure of the signal XT ,d .
uS
Furthermore, the unicast signal X{k},d delivers the missing
Sk
(l)
pieces of l=1 Wdk to user k, i.e., the pieces that had not
been delivered by multicast signals and are not cached by
Pk
(l)
user k. We assume |X{k},d | = l=1 v{k} 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, D(a(1) , . . . , a(K) , r), is defined by
vT =

L
X

(l),T

X

uS

, ∀T ⊂ [K] s.t. |T | ≥ 2, ∀j ∈ T ,

(13)

l=1 S∈B(l),T
j

(l)

X

v{k} +

X

(l),T

uS

T ⊂{l,...,K}:k∈T ,|T |≥2 S∈B(l),T
k

X

+

(l)

aS ≥

S⊂{l,...,K}:k∈S

rl −rl−1 , ∀l ∈ [K], ∀k ∈ {l, . . . , K},
(l),T
(l)
uS
≤ aS , ∀l ∈ [K], ∀j 6∈ S, ∀S ∈ A(l) ,
T ⊂{l,...,K}: j∈T ,T ∩S6=φ
X

(l)
(l),T
0 ≤ uS ≤ aS , ∀l ∈ [K], ∀T

(φ {l, . . . , K}, ∀S ∈ B

(14)

(l),T

(1),{1,2}
(1),{1,2}
(1),{1,2}
(1),{1,2}
+u{1,3} ,
+u{2,3} = u{1}
v{1,2} = u{2}
(1),{1,3}
(1),{1,3}
(1),{1,3}
(1),{1,3}
+u{1,2} ,
+u{2,3} = u{1}
v{1,3} = u{3}
(2),{2,3}
(1),{2,3}
(1),{2,3}
,
+ u{1,3} + u{3}
v{2,3} = u{3}
(2),{2,3}
(1),{2,3}
(1),{2,3}
,
+u{1,2} +u{2}
= u{2}
(1),{1,2,3}
(1),{1,2,3}
(1),{1,2,3}
,
= u{1,2}
= u{1,3}
v{1,2,3} = u{2,3}

(17a)
(17b)
(17c)
(17d)
(17e)

the delivery completion constraints for user 3 are defined as
(1),{2,3} 
(1),{2,3}
(1),{1,3} 
(1),{1,3}
(1)
+
+u{1,2}
+ u{2}
+u{1,2}
v{3} + u{1}

(1)
(1)
(1)
(1)
(1),{1,2,3}
+ a{3} +a{1,3} + a{2,3} + a{1,2,3} ≥ r1 , (18a)
u{1,2}
(2)

(2),{2,3}

(3)

(3)

(2)

(2)

+ a{3} + a{2,3} ≥ r2 − r1 ,

v{3} + a{3} ≥ r3 −r2 ,

(18b)
(18c)

and the redundancy constraints are defined as
(1),{1,3}

u{1,2}

(1),{1,2}
u{1,3}
(1),{1,2}
u{2,3}

(1),{2,3}

+ u{1,2}
+
+

(1),{2,3}
u{1,3}
(1),{1,3}
u{2,3}

+
+

(1)

(1),{1,2,3}

≤ a{1,2} ,

(1),{1,2,3}
u{1,3}
(1),{1,2,3}
u{2,3}

(1)
a{1,3} ,
(1)
a{2,3} .

+ u{1,2}

≤
≤

(19a)
(19b)
(19c)

We denote the vector representation of the transmission
(l)
variables {vT }T , {v{k} }k,l and the assignment variables
(l),T

{uS

}l,T ,S by v and u, respectively.

IV. F ORMULATION
In this section, we demonstrate that the problem of minimizing the worst-case delivery load by optimizing over the users’

T (φ [K]

a(l) ∈ A(l) (m(l) , r), ∀l ∈ [K] (20b)

(u, v) ∈ D(a(1) , . . . , a(K) , r), (20c)
K X
k
X

, (16)



v{3} + u{2}

subject to

(l),T

, S ⊂ {l, . . . , K} \ {j} : T \ {j} ⊂ S ,

A , S ⊂ {l, . . . , K} : 2 ≤ |S| ≤ K − l ,
S
(l),T
.
and B (l),T , j∈T Bj
The structural constraints in (13) follows from the structure
of the multicast signals in (11) and (12). The delivery completion constraints in (14) guarantee that the unicast and multicast
signals complete the lth layer of the requested files, and the
redundancy constraints in (15) prevent the transmission of
redundant bits to the users. For example, for K = 3, the
structural constraints are defined as
(l)

a(l) ,u,v,m(l)

(15)

where
Bj

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 mtot , and N ≥ K, the
minimum worst-case delivery load under uncoded placement
∗
and linear delivery, RA,D
(mtot , r), is characterized by
X
vT
(20a)
O1:
min

(l)

mk = mtot ,

(20d)

k=1 l=1

where A(l) (m(l) , r) is the set of uncoded placement schemes
in layer l defined in (9) and D(a(1) , . . . , a(K) , r) is the set
of feasible linear delivery schemes defined by (13)-(16).
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 [28]. In particular, for fixed
cache sizes m, the minimum worst-case delivery load un∗
der uncoded placement and linear delivery, RA,D
(m, r), is
characterized by
X
vT
(21a)
O2:
min
a(l) ,u,v,m(l)

subject to

T (φ [K]

a(l) ∈ A(l) (m(l) , r), ∀l ∈ [K] (21b)

(u, v) ∈ D(a(1) , . . . , a(K) , r), (21c)
k
X

(l)

mk = mk , ∀k ∈ [K].

(21d)

l=1

In contrast to the formulation in reference [28], observe that
in (21), we jointly design the caching scheme and the memory
allocation over the layers, and exploit multicast opportunities
over different layers.
V. O PTIMAL C ACHE A LLOCATION
In this section, we first characterize the solution to the
optimization problem in (20), i.e., we find the achievable
worst-case delivery load assuming uncoded placement and
linear delivery. Then, we present a lower bound on the tradeoff between the minimum worst-case delivery load under any
caching scheme and the cache memory budget.
Theorem 1. Given the target rate
P vector r, N ≥ K, and
the total memory budget mtot = K
l=1 tl fl , where f1 , r1 ,
fl , rl − rl−1 for l > 1, tl ∈ {0, 1, . . . , K − l + 1} and
tl+1 ≤ tl ≤ tl−1 , the minimum achievable worst-case delivery
load under uncoded placement is given by
∗
∗
RA,D
(mtot , r) = RA
(r, mtot ) =

K
X
(K − l + 1) − tl
l=1

1 + tl

fl . (22)

P
∗
Furthermore, for general mtot ∈ [0, K
k=1 rk ], RA,D (r, mtot )
is defined by the lower convex envelope of these points. 

Proof. In Appendix A, we show that the optimal solution to
the optimization problem in (20) achieves the lower convex
envelope ofPthe delivery load points in (22). In particular,
K
for mtot = i=1 ti fi where tl ∈ {0, 1, . . . , K − l + 1} and
tl+1 ≤ tl ≤ tl−1 , the optimal memory allocation is defined
(l)
as mk = tl fl /(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
(

fl / K−l+1
F, for |S| = tl ,
(l)
t
l
|W̃j,S | =
(23)
0, otherwise.
(l)

and the multicast signals are defined by ⊕j∈T W̃dj ,T \{j} for
T ⊂ {l, . . . , K} and |T | = tl + 1.
PK
In general, any mtot ∈ [0, i=1 ri ] can be represented as
PK
i=1 ti fi where ti = x, for i = [y], ty = x − 1 + α, ti =
x − 1, for i = {y + 1, . . . , K − x + 1}, ti = K − i + 1, for
i = {K − x + 2, . . . , K}, for some x ∈ [K], y ∈ [K − x + 1]
and 0 < α < 1. In particular, we have

K
P


fi ,
1,
0
<
m
≤

tot


i=1



..


.




K−j
K−j+1
K

P
P
P
x , j, (j−1) i=1 fi + (K−i+1)fi < mtot ≤ j i=1 fi (24)
i=K−j+2



K
.
P

..

(K−i+1)fi,
+



i=K−j+1



K
K
P
P


K, (K−1)f1 + (K−i+1)fi < mtot ≤ ri .
i=1

i=2

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

b−1
X

K−x+1
X

fi + (x−1)

i=1

fi +

i=b

x

b
X

K−x+1
X

fi +

K
X

(K−i+1)fi.

PK

k=1 rk ]

fl + (x − 1 + α)fy + (x − 1)

K−x+1
X

fl +

(26)

l=K−x+2

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

K−x+1
X K −y −x+2
K −l−x+1
fl +
fl +
x+1
x
l=1
l=y+1


2(K −y)−x+3 (K −y +2)(x−1+α)
fy . (27)
−
x+1
x(x+1)

∗
RA,D
(mtot , r) =

Proposition 1. (Extension of [28, Theorem 2]) Given N ≥ K,
theP
target rate vector r, and the total memory budget mtot ∈
[0, K
k=1 rk ], the infimum over all achievable delivery loads
R∗ (mtot , r) is lower bounded by
P



mk 
N

X
k∈U
,
(29)
min
max
rk −
⌊N/|U|⌋ 
m∈M(mtot ,r)U ⊂[K]
k∈U

o
n
K
P
where M(mtot , r) = m 0 ≤ mk ≤ rk ,
mk = mtot . 
k=1

For the three-user case, the cut-set bound can be simplified
as follows.

Corollary 1. Given K = 3, N ≥ 3, the target
PKrate vector
r, and the total memory budget mtot ∈ [0, k=1 rk ], the
infimum over all achievable delivery loads R∗ (mtot , r) is
lower bounded by
X
3
N
⌊N/2⌋(r1 + r2 ) + N r3
rl −
max
mtot ,
−
⌊N/3⌋
N + ⌊N/2⌋
l=1

3

1 X
N
mtot ,
rl − mtot . (30)
N + ⌊N/2⌋
3


l=y+1

(K − l + 1)fl ,

which are illustrated in Fig. 2, for r = [0.5, 0.7, 1].
Next, we extend the lower bound on the delivery load for
systems with fixed cache sizes in [28, Theorem 2] to systems
with cache memory budget.

l=1

can be represented as

l=1

K
X

(25)

i=b+1 i=K−x+2

In turn, any mtot ∈ [0,
mtot = x

(K−i+1)fi < mtot ≤

i=K−x+2

fi + (x−1)

i=1

y−1
X

K
X

For example, for K = 3, the corner points of the delivery
load cache budget trade-off under uncoded placement in (22)
are defined as follows


r1 +r2 +r3 , for mtot = 0,



r2 +r3 −r1 , for mtot = r1 ,





r1 /2+r3 −r2 /2, for mtot = r2 ,
∗
RA,D
(mtot , r) = r1 /2+r2/2, for mtot = r3 ,
(28)



r2 /2−r1/6, for mtot = r1 +r3 ,





r

1 /3, for mtot = r2 +r3 ,


0, for mtot = r1 +r2 +r3 ,

VI. D ISCUSSION

AND

N UMERICAL R ESULTS

In this section, we first consider systems with total cache
memory budget and present numerical examples that illustrate
the optimal solution of (20). Then, we consider systems with
fixed cache sizes and illustrate the gain achieved by our
caching scheme compared to the schemes proposed in [28].
A. Systems with Total Cache Memory Budget
In Fig. 2, we compare the achievable worst-case delivery
∗
load RA
(mtot , r) defined in Theorem 1 with the lower bound
on R∗ (mtot , r) defined in Proposition 1, for K = N = 3 and
the target rates r = [0.5, 0.7, 1]. In particular, for K = 3 the

1

2.5

1.5
1
0.5
0

0

0.5 0.7

1 m
tot

1.5 1.7

m1
m2
m3

0.8

Achievable delivery load
Cut-set bound

Users’ cache sizes

Delivery load

2

0.6
0.4
0.2
0

2.2

0

0.5 0.7

1 mtot

1.5 1.7

2.2

Fig. 2. Comparing the delivery load R∗A (mtot , r) in Theorem 1 with the
cut-set bound in Proposition 1, for K = N = 3, and r = [0.5, 0.7, 1].

Fig. 3. The memory allocation corresponding to the delivery load in Theorem
1 for r = [0.5, 0.7, 1].

corner points of the achievable delivery load are defined in
(28) and the cut-set bound in (30) for N = 3 is
(3
)
3
X

r1 +r2 +3r3 −3mtot 1 X
max
rl −3mtot ,
,
rl −mtot . (31)
4
3

2) Ordered cache allocation (OCA), where user k allocates
all of its cache to the first b layers if rb−1 < mk < rb .
In turn, in layer l, we have a caching system that consists
of K − l + 1 users with fixed cache sizes m(l) . Reference
[28] has proposed designing the caching scheme in each
layer separately, i.e., the multicast signals utilize the sideinformation 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 [28] has formulated an optimization
problem in order to identify the optimal distribution of fl over
the sublayers. We refer to this scheme as the layered scheme.
Fig. 4 shows the delivery load obtained from (21), the
delivery load achieved by PCA/OCA combined with the
layered scheme, and the cut-set bound in [28, Theorem 2],
for K = N = 3, r = [0.5, 0.8, 1], and mk = 0.8 mk+1 . We
observe that the delivery load achieved by (21) is lower than
the one achieved by the schemes in [28]. 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 (21) grows exponentially with the number of users.
The next example illustrates the suboptimality of exploiting
the multicast opportunities in each layer separately.

l=1

l=1

Remark
1. We observe
that for large memory budget,
PK
PK
r
,
the cut-set bound can be achieved
r
≤
m
≤
l
l
tot
l=1
l=2

1 PK
and the delivery load R∗ (mtot , r) = K
l=1 rl −mtot . 
Recall the notation fl = (rl − rl−1 ) and r0 = 0. Fig. 3
shows the optimal allocation for the users’ cache sizes that
correspond to the achievable delivery load in Fig. 2. From
Fig. 3, we observe the optimal memory allocation follows a
threshold policy. In particular, we have
• If mtot
= αf1 and α ∈ [0, 1], then m =
[αf1 /3, αf1 /3, αf1 /3].
• If mtot = f1+αf2 and α ∈ [0, 1], then m = [f1 /3, f1 /3+
αf2 /2, f1 /3+αf2 /2].
• If mtot = f1 + f2 + αf3 and α ∈ [0, 1], then m =
[f1 /3, f1 /3+f2/2, f1 /3+f2/2+αf3 ].
• If mtot = (1+α)f1 +f2 +f3 and α ∈ [0, 1], then m =
[(1+α)f1 /3, (1+α)f1 /3+f2/2, (1+α)f1 /3+f2/2+f3].
• If mtot = 2f1 +(1+α)f2 +f3 and α ∈ [0, 1], then m =
[2f1 /3, 2f1 /3+(1+α)f2/2, 2f1 /3+(1+α)f2/2+f3].
• If mtot = (2+α)f1 +2f2 +f3 and α ∈ [0, 1], then m =
[(2+α)f1 /3, (2+α)f1 /3+f2, (2+α)f1 /3+f2 +f3 ].

B. 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 [28]. In reference
[28], the memory allocation over the layers follows one of the
following heuristic methods:
1) Proportional cache allocation (PCA), where user k cache
(l)
size for layer l is defined as mk = fl mk /rk .

Example 1. For m = [0.1, 0.2, 0.6] and r = [0.2, 0.3, 0.8],
the optimal solution of (21) is as follows
Placement phase:
(1)
(1)
is divided into subfiles W̃j,{3} and
• Layer 1: Wj
(1)

(1)

(1)

W̃j,{1,2} , such that a{3} = a{1,2} = 0.1.
•

(2)

Layer 2: Wj

(3)

(2)

is stored at user 2, i.e., a{2} = 0.1.
(3)

Layer 3: Wj is stored at user 3, i.e., a{3} = 0.5.
Delivery phase: We have two multicast transmissions X{1,3},d
and X{2,3},d , such that
•

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 [2], which is equivalent
to equal distortion requirements at the users [28].

2.5
Our scheme
PCA + Layered scheme
OCA + Layered scheme
Cut-set bound

Delivery load

2

Lemma 1. For a caching system with K users, N ≥ K files,
and cache memory budget mtot ∈ [0, K], the minimum worstcase delivery load under uncoded placement


2K − j + 1 (K + 1)mtot
∗
, (32)
−
RA
(mtot ) = max
j+1
j(j + 1)
j∈[K]

1.5
1
0.5
0

which is achieved by uniform memory allocation and the
MaddahAli-Niesen caching scheme [2].
0

0.2

0.4

m3

0.6

0.8

1

R∗A,D (m, r)

obtained from (21), the
Fig. 4. Comparing the delivery load
delivery load achieved by the two schemes in [28], and the cut-set bound
[28, Theorem 2], for K = N = 3, r = [0.5, 0.8, 1], and mk = 0.8 mk+1 .

Proof. For any memory allocation m = [m1 , . . . , mK ],
∗
RA
(m) ≥ max

λ0 ∈R,λk ≥0

subject to λ0 +
•

(1),{1,3}

X{1,3},d = Wd1 ,{3}
(1)

(1)

(1),{2,3}

X{2,3},d = Wd2 ,{3}
(1)
a{3}

(2)
a{2}

(2),{2,3}

⊕ Wd2 ,{2}

, where v{2,3} =

= 0.1.
=
The optimal solution of (21) achieves the delivery load
∗
RA,D
(m, r) = 0.2 compared to 0.2167 which is achieved
by exploiting only the intra-layer multicast opportunities. 
VII. C ONCLUSION
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 [28] by exploiting the interlayer multicast opportunities and jointly designing the cache
contents and the partitioning of the caches over the layers.

mk λk

(33a)

X

λk +

K −|S|
≥ 0, ∀S ⊂ [K], (33b)
|S|+1

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


K −j
∗
− λ(j − mtot ) , (34)
RA (mtot ) ≥ max min
λ≥0 j∈{0,...,K} j + 1


2K − j + 1 (K + 1)mtot
= max
,
(35)
−
j∈[K]
j+1
j(j + 1)
PK
where mtot = k=1 mk .
Building on Lemma 1, given r and any memory allocation
m(1) , . . . , m(K) , the minimum worst-case delivery load under
∗
uncoded placement, RA
(m(1) , . . . , m(K) , r) satisfies
∗
RA
(m(1) , . . . , m(K) , r) ≥

K
X

(rl − rl−1 )

l=1

K
P
(l)

(K −l+2) mk 
2(K −l+1)−j +1
k=l
max
. (36)
−
j∈[K−l+1]
j+1
j(j + 1)

Furthermore, this lower bound is achievable if we consider
(l)
mk = m(l) , ∀k ∈ {l, . . . , K} and apply the MaddahAliNiesen caching scheme [2] on each layer. In turn, the
optimization problem in (20) simplifies to the problem of
allocating the memory over the layers, which is defined as

A PPENDIX A
P ROOF OF T HEOREM 1
In order to prove that the optimal solution of (20) achieves
the delivery load in Theorem 1, we first show the optimality of
(l)
uniform cache allocation in each layer, i.e., mk = m(l) , ∀k ∈
{l, . . . , K}. Then, we show that the optimal memory allocation over the layers follows the threshold policy defined by
(24)-(26).

K
X

k=1

k∈S

(1),{1,3}

⊕ Wd3 ,{1,2} , where v{1,3} =

a{3} = a{1,2} = 0.1.
•

− λ0 −

min

t1 ,...,tK

subject to

K
X

χl f l

(37a)

tl fl ≤ mtot ,

(37b)

0 ≤ tl ≤ K − l + 1,

(37c)

l=1
K
X
l=1

where m(l) = tl fl /(K − l + 1) and


2(K −l+1)−j +1 (K −l+2)tl
. (38)
−
χl, max
j+1
j(j + 1)
j∈[K−l+1]
Finally, we can show that the optimal solution to (37) achieves
the delivery load in Theorem 1, by solving the dual of the
linear program in (37).
R EFERENCES
[1] Cisco, Cisco VNI Forecast and Methodology, 2015-2020, Jun. 2016.
[2] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,”
IEEE Trans. Inf. Theory, vol. 60, no. 5, pp. 2856–2867, Mar. 2014.
[3] ——, “Coding for caching: Fundamental limits and practical challenges,” IEEE Commun. Mag., vol. 54, no. 8, pp. 23–29, Aug. 2016.
[4] K. Wan, D. Tuninetti, and P. Piantanida, “On the optimality of uncoded
cache placement,” in Proc. IEEE ITW, 2016.
[5] Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “The exact rate-memory tradeoff for caching with uncoded prefetching,”
arXiv:1609.07817, 2016.
[6] ——, “Characterizing the rate-memory tradeoff in cache networks
within a factor of 2,” in Proc. IEEE ISIT, 2017.
[7] N. Karamchandani, U. Niesen, M. A. Maddah-Ali, and S. N. Diggavi,
“Hierarchical coded caching,” IEEE Trans. Inf. Theory, vol. 62, no. 6,
pp. 3212–3229, Apr. 2016.
[8] M. Ji, M. F. Wong, A. M. Tulino, J. Llorca, G. Caire, M. Effros, and
M. Langberg, “On the fundamental limits of caching in combination
networks,” in Proc. IEEE SPAWC, 2015.
[9] A. A. Zewail and A. Yener, “Combination networks with or without
secrecy constraints: The impact of caching relays,” arXiv:1712.04930,
2017.
[10] K. Wan, M. Ji, P. Piantanida, and D. Tuninetti, “Combination networks
with caches: Novel inner and outer bounds with uncoded cache placement,” arXiv:1701.06884, 2017.
[11] ——, “Caching in combination networks: Novel multicast message generation and delivery by leveraging the network topology,”
arXiv:1710.06752, 2017.
[12] M. Ji, G. Caire, and A. F. Molisch, “Fundamental limits of caching in
wireless D2D networks,” IEEE Trans. Inf. Theory, vol. 62, no. 2, pp.
849–869, Feb. 2016.
[13] A. A. Zewail and A. Yener, “Fundamental limits of secure device-todevice coded caching,” in Proc. IEEE Asilomar, 2016.
[14] A. M. Ibrahim, A. A. Zewail, and A. Yener, “Device-to-device coded
caching with heterogeneous cache sizes,” in Proc. IEEE ICC, 2018.
[15] V. Ravindrakumar, P. Panda, N. Karamchandani, and V. Prabhakaran,
“Fundamental limits of secretive coded caching,” in Proc. IEEE ISIT,
2016.
[16] A. Sengupta, R. Tandon, and T. C. Clancy, “Fundamental limits of
caching with secure delivery,” IEEE Trans. Inf. Forensics Security,
vol. 10, no. 2, pp. 355–370, Feb. 2015.
[17] A. A. Zewail and A. Yener, “Coded caching for resolvable networks
with security requirements,” in Proc. IEEE CNS Workshops, 2016.
[18] S. Wang, W. Li, X. Tian, and H. Liu, “Coded caching with heterogenous
cache sizes,” arXiv:1504.01123, 2015.
[19] M. M. Amiri, Q. Yang, and D. Gündüz, “Decentralized coded caching
with distinct cache capacities,” arXiv:1611.01579, 2016.
[20] A. Sengupta, R. Tandon, and T. C. Clancy, “Layered caching for
heterogeneous storage,” in Proc. IEEE Asilomar, 2016.
[21] A. M. Ibrahim, A. A. Zewail, and A. Yener, “Centralized coded caching
with heterogeneous cache sizes,” in Proc. IEEE WCNC, 2017.
[22] ——, “Coded caching for heterogeneous systems: An optimization
prespective,” in preparation.
[23] S. S. Bidokhti, M. Wigger, and A. Yener, “Gaussian broadcast channels
with receiver cache assignment,” Proc. IEEE ICC, 2017.
[24] ——, “Benefits of cache assignment on degraded broadcast channels,”
in Proc. IEEE ISIT, 2017.
[25] ——, “Benefits of cache assignment on degraded broadcast channels,”
arXiv:1702.08044, 2017.
[26] A. M. Ibrahim, A. A. Zewail, and A. Yener, “Optimization of heterogeneous caching systems with rate limited links,” in Proc. IEEE ICC,
2017.

[27] P. Hassanzadeh, E. Erkip, J. Llorca, and A. Tulino, “Distortion-memory
tradeoffs in cache-aided wireless video delivery,” in Proc. IEEE Allerton, 2015.
[28] Q. Yang and D. Gündüz, “Coded caching and content delivery with
heterogeneous distortion requirements,” arXiv:1608.05660, 2016.
[29] R. Timo, S. S. Bidokhti, M. Wigger, and B. C. Geiger, “A rate-distortion
approach to caching,” to appear in IEEE Trans. Inf. Theory, 2018.
[30] T. M. Cover and J. A. Thomas, Elements of information theory. John
Wiley & Sons, 2006.
[31] W. H. Equitz and T. M. Cover, “Successive refinement of information,”
IEEE Trans. Inf. Theory, vol. 37, no. 2, pp. 269–275, 1991.

