DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

1

Optimization of Heterogeneous Coded Caching

arXiv:1708.04322v1 [cs.IT] 14 Aug 2017

Alexander Michael Daniel and Wei Yu

Abstract—This paper aims to provide an optimization framework for coded caching that accounts for various heterogeneous aspects of practical systems. An optimization theoretic
perspective on the seminal work on the fundamental limits of
caching by Maddah Ali and Niesen is first developed, whereas
it is proved that the coded caching scheme presented in that
work is the optimal scheme among a large, non-trivial family
of possible caching schemes. The optimization framework is
then used to develop a coded caching scheme capable of
handling simultaneous non-uniform file length, non-uniform
file popularity, and non-uniform user cache size. Although the
resulting full optimization problem scales exponentially with the
problem size, this paper shows that tractable simplifications of
the problem that scale as a polynomial function of the problem
size can still perform well compared to the original problem.
By considering these heterogeneities both individually and in
conjunction with one another, insights into their interactions
and influence on optimal cache content are obtained.

papers, however, consider only one type of non-uniformity.
While this is sensible from the viewpoint of understanding
how each heterogeneity affects coded caching systems by
itself, practical systems would have to account multiple types
of non-uniform parameters. Moreover, we cannot in general
expect the effects of these non-uniformities to be additive. It
is thus important to consider combinations of heterogeneities,
which, to the best of our knowledge, only a few recent works
have started to explore: the recent work [19] examines the
achievable rate region for a system serving two users with
two files, where the user cache sizes and file lengths are
not necessarily uniform, while some of the aforementioned
work on caching with non-uniform channel quality exploits
heterogeneous cache size to rectify disparities in channel
quality (see e.g. [33] and references therein).

Index Terms—Coded caching, linear programming, nonuniform popularity, non-uniform cache size, non-uniform file
length

B. Main Contributions

I. I NTRODUCTION
A. Background
Caching technologies stand poised to make an important
contribution to future 5G cellular networks [1]. One such
technique is coded caching, which, roughly speaking, is the
idea of using carefully designed user cache content to enable
content delivery via coded multicast transmissions. (The
cached contents themselves are uncoded.) First introduced
by Maddah-Ali and Niesen in [2], [3], coded caching has
since been the subject of a great number of studies seeking to
extend the original scheme into more practical scenarios. The
coded caching scheme of [2], [3] is developed for a system
in which a central server has complete knowledge of user
numbers and identities, users have identical cache sizes and
make a single download request, transmission occurs over an
error free link, and files are of equal length and popularity.
Subsequent work has since extended the coded caching idea
to the decentralized system [4], and to systems with nonuniform file popularity [5]–[17], non-uniform file length [18],
[19], multiple user requests [20]–[23], non-uniform cache
size [24]–[27], and non-uniform channel quality [28]–[40].
The aforementioned works typically either discuss how the
scheme of [2], [3] should be modified to accommodate the
considered heterogeneity, or develop an entirely new scheme
that enables coded multicast transmissions while accommodating the aforementioned heterogeneity. Most of these
Manuscript prepared on August 16, 2017. This work is supported by
Natural Science and Engineering Research Council (NSERC). The authors
are with the Edward S. Rogers Sr. Department of Electrical and Computer
Engineering, University of Toronto, Toronto, ON M5S 3G4, Canada (emails: alex.daniel@mail.utoronto.ca, weiyu@ece.utoronto.ca).

This paper proposes an optimization theoretic framework
to design caching schemes capable of accommodating nonuniform file length, non-uniform file popularity, and nonuniform user cache size at the same time. More specifically,
we design a caching scheme that uses a generalized version of
the transmission scheme of [4], paired with an optimization
problem designed to yield the optimally coded content.
This optimization problem, although convex, has the number
of variables, constraints, and objective function terms that
scale exponentially with the problem size, so subsequently
this paper develops high-quality simplifications that scale
polynomially with the problem size, yet perform well compared to the original problem. The proposed optimization
approach only yields numerical answers corresponding to
the optimized caching schemes, but also generate practical
insight into the problems considered.
Optimization approaches have been used in the past for
content placement for femtocaching systems [41], [42], but
its use in the coded caching context has only appeared
recently: for instance, [43] uses an information-theory based
optimization problem to help characterize the achievable rate
region for certain numbers of users and files in the case where
all other systems parameters are uniform. More related is
the recent work [27] in which an optimization framework
similar to the one used here is employed to develop a caching
scheme in the case of non-uniform cache size. Crucially,
both approaches design cache content in terms of the subsets
of users who have cached the content (see Section III).
While we directly express our transmission scheme in terms
of that cache content, the approach in [27] is to further
design two sets of variables through which the transmission
scheme is expressed. Moreover, the framework used in [27]

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

does not distinguish between different files beyond designing
a scheme for the worst-case scenario where users request
different files. This prevents their framework from addressing
file heterogeneity, whereas ours allows for it. Finally, while
the optimization problem in [27] suffers from the same
exponential scaling problem that the general problem here
has, they do not present any tractable methods of solution
like we do here.
During the preparation of this paper, we became aware of
independent work [17], which uses an optimization framework essentially the same as the one proposed here to study
the case of non-uniform file popularity. While independently
and simultaneously developed, a number of results in [17]
are echoed in this paper. Specifically, both works develop
the same exponential-order general optimization problem;
then a simplified polynomial-order optimization problem is
developed for the non-uniform popularity case (Section IV-C
of this paper), although the exact formulations are different.
Moreover, both works show that in the special case of
uniform popularity, the caching and delivery scheme of [2],
[3] is the optimal solution (Section III of this paper); however,
the proof in [17] is quite involved, while a much simpler
proof is presented here. Ultimately, the focus of [17] is to
study the case of non-uniform popularity in great depth, while
here, it is only considered as an intermediate step towards the
study of the interactions of several heterogeneities at the same
time. Thus, despite the similarities, both papers develop many
unique insights of practical significance. Indeed, the results
of [27] and [17] taken jointly with the results of this paper
suggest that the optimization framework common to all three
works is likely to be a useful one for coded caching.
C. Notation
The notation [a : b] is used as shorthand for the set of
consecutive integers {a, a + 1, . . . , b − 1, b}, and [b] is used
as an abbreviation of [1 : b]. The symbol ⊕ is used to
denote the bitwise “XOR” operation between two or more
files (i.e. strings of bits). Both l and W (l) are used to refer
to the l-th file under consideration. For an arbitrary file
(l)
W (n) , |W (n) | refers to the length of the file, and WS ,
(l)
called a “subfile” of file W , refers to the portion of file
l stored exclusively on the caches of the users in the set
(l)
S. For notational convenience, notation of the form W123 is
(i)
used instead of W{1,2,3} (for the S = {1, 2, 3} case in this
example), returning only to the latter notation if necessary to
resolve ambiguity. For a set S, P(S) refers to the power set
of S. For a real number t, ⌊·⌋ and ⌈·⌉ denote the floor and
ceiling functions, respectively.

We define the binomial
coefficient nk in the usual way

for 0 ≤ k ≤ n, i.e. nk = n!/(k!(n − k!)), but for n < 0
or k > n, we take nk = 0. Moreover, the notation of the
so-called “multinomial coefficient” is used, defined as:


n
n!
,
=
k1 !k2 ! . . . km !
k1 , k2 , . . . , km
Pb
where k1 +k2 +· · ·+km = n. We use the notation i=a ni in
Pb
the usual way when a ≤ b, and take i=a ni = 0 identically

2

if a > b. More generally, a sum over an empty set of indices
is taken to equal zero. Finally, if a sum over an empty set is
raised to the power of zero, we take the resulting value to be
1; this is simply used for notational convenience.
D. Organization
The organization of the rest of the paper is as follows.
Section II introduces the optimization framework used in this
paper and Section III uses this framework to provide a new
interpretation and understanding of [2]–[4] by showing how
they represent feasible points in the optimization problem.
Sections IV-VI use the framework to develop tractable simplifications of the original problem for different types and
combinations of non-uniformities. Section VII concludes the
paper with a summary and discussion of main results.
II. O PTIMIZATION P ERSPECTIVE

ON

C ODED C ACHING

We begin by providing an optimization perspective on the
coded caching schemes of Maddah-Ali and Niesen for both
the centralized [2], [3] and the decentralized [4] cases. The
transmission scenario consists of a server with a set of N
files, F = {1, 2, . . . , N } = [N ], serving a set of K users,
U = {1, 2, . . . , K} = [K], over a shared, error-free link. For
full generality, we allow each file l to have a distinct length
of Fl bits and a distinct probability pl of being requested,
and allow each user k to have arbitrary cache size of Mk
bits.
Central to the coded caching scheme of [2]–[4] is the
(l)
partitioning of each file l ∈ F into subfiles WS , indexed
by all subsets of S ⊆ U. (No two subfiles have a nonempty intersection; together the subfiles jointly reconstruct
the original file.) In the caching phase, each user k caches
[
(l)
WS∪k
(1)
l,S∈P(U \{k})

without coding. In the content delivery phase, given the set of
user requests d = [d1 , . . . , dK ], where dk denotes the index
of the file requested by user k, the server transmits
M (d )
k
(2)
WS\{k}
k∈S

over the shared link with zero-padding if necessary, for each
S ∈ P(U) \ ∅, so that together with uncoded content stored
a priori in each user’s local cache, all users are guaranteed
to be able to reconstruct the entirety of their requested files.
Any coded caching scheme (with coded transmission and
uncoded cache) can be described using this “subset partitioning” representation [4]. Different caching strategies differ
in their partitioning of the subfiles. But instead of thinking
of the above as a way of labelling the cache contents, we
can also use this to design the cache content, and regard the
(l)
size of each subfile WS as design variables. Consequently,
instead of designing cache contents by assigning discrete bits
to sets, the problem can be simplified by designing only the
(l)
(l)
(l)
sizes of the subfiles: if we have |W∅ | = b∅ , |W1 | =
(l)
(l)
(l)
(l)
b1 , . . . , |WU | = bU , then the first b∅ Fl bits of W (l) are

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

(l)

(l)

3

(l)

assigned to W∅ , the next b1 Fl bits to W1 , and so on,
(l)
(l)
assigning the final bU Fl bits to WU . (Formally, this requires
(l)
that bS ∈ {0, 1/Fl , . . . (Fl − 1)/Fl , 1}, but for large Fl , this
(l)
can be relaxed to bS ∈ [0, 1] without any significant loss.)
For example, consider the centralized scenario wherein the
numbers and identities of users are known in advance, so the
server has the ability to design the cache content of each user.
The coded caching scheme of [2], [3] (assuming uniform file
length, cache size and uniform popularity) sets |WS | to be
non-zero for only the S’s with |S| = t = KM/N . In the
decentralized setting of [4], all subfiles have non-zero sizes
due to the use of random cache content. More generally,
(l)
|WS | can be explicitly designed.
The design of coded caching in this way imposes some
natural constraints on the subfile sizes. First, the subfiles
together must contain the entire file, i.e.
X
(l)
|WS | = Fl , ∀l ∈ F .
(3)
S∈P(U )

Second, denoting the amount of cache dedicated to file l
by user k as µk,l , the amount of a file cached by a user is
expressed as
X
(l)
|WS∪k | ≤ µk,l , ∀k ∈ U, ∀l ∈ F ,
(4)
S∈P(U \{k})

where

N
X

µk,l = Mk , ∀k ∈ [K].

(5)

l=1

Finally, the subfiles cannot have a negative size:
(l)

|WS | ≥ 0,

∀S ∈ P(U),

∀l ∈ F .

(6)

In the transmission defined in (2), zero-padding is neeeded
whenever the subfiles do not have the same length, so the
length of a single transmission is determined by the largest
subfile in the transmission. For a vector of user requests d,
the number of bits sent to satisfy user requests given in d is
thus
o
n
X
(dk )
|
(7)
max |WS\{k}
Rd =
S∈P(U )\∅

k∈S
(l)

The set of choices of |WS | define a broad family of
caching schemes. To find the most efficient caching strategy
among this family of schemes that minimize the expected
delivery rate over all demand requests, we can formulate the
following optimization problem:
o
n
X
X
(dk )
|
max |WS\{k}
minimize E[Rd ] =
p(d)
d∈F K

subject to

(3)-(6).

S∈P(U )\∅

k∈S

(8)
(9)

We note before continuing that the transmission scheme
described above is the same for all possible user requests,
which may be suboptimal if there is repetition in the users’
requests, i.e. the same file is requested by more than one
user. However, it can readily be shown that the probability

of each user requesting a distinct file goes to one as N → ∞
of a fixed K. Since it is likely that N ≫ K in practice, the
optimization formulation (8) can be therefore be used without
fear of significant loss.
The optimization problem (8)-(9) is convex in the |WS |
variables. However, there are N 2K variables, N K (2K − 1)
summands in the objective function, and N 2K + KN + N +
K constraints, making it impractical to solve for large-scale
problems. The rest of this paper is dedicated to developing
simplifications of (8)-(9) that allow for high quality (and even
optimal) solution while maintaining a tractable problem size.
III. H OMOGENEOUS C ODED C ACHING
Consider the special case of problem (8)-(9) with uniform
file lengths, Fl = F, ∀l ∈ [N ], uniform file popularities, pl =
1/N, ∀l ∈ [N ], and uniform cache sizes Mk = M, ∀k ∈ [K];
this is the same system originally considered in [2], [3]. The
symmetry of the resulting problem can be exploited to reduce
the computational complexity of optimization. Specifically,
define vj such that vj = |WS | for all S such that |S| = j
and for all files W ; this reduces the number of optimization
variables from an exponential number in K to a linear
number in K. Since the file length, file popularity and cache
size are all homogeneous, there is symmetry across both the
users and the files, and so we would expect the solution to
(8)-(9) for this uniform case to have this form, i.e., any two
subfiles have the same size if their respective user sets are
the same size. The summands of the objective function now
simplify as
o
n
(k′ )
(k)
max |WS\{k} | = |WS\{k′ } | = v|S|−1
k∈S

where k ′ is any user in the set S \ {k}, because each subfile
in a given transmission is the same size. Since the files are
equally popular, every request vector is equally likely, and
since every transmission scheme requires the same number
of bits to satisfy the requests, the average does not need to be
taken across all the N K possible demands as in (8). Finally,
since vj F bits are sent to any subset of j + 1 users, and
K
there are j+1
subsets of j + 1 users, the objective function
becomes
K−1
X K 
E[Rd ] =
vj F,
(10)
j+1
j=0

Note that the number of terms in the objective function now
scales linearly in K instead of exponentially in K, because
each term in (10) accounts for a combinatorial number of
transmissions.
The constraints simplify as well. Since all files are of equal
length, only one file reconstruction
constraint is required.

Then, because there are Kj subsets of size j, the file
reconstruction constraint becomes
K  
X
K
vj = F.
(11)
j
j=0
Moreover, since the cache sizes are uniform, only one cache
constraint is needed, and since all file are homogeneous, an

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

4

equal amount of memory is allocated to each. The cache
constraint thus simplifies to

K 
X
K −1
vj ≤ M F/N,
(12)
j−1
j=1

because there are K−1
subsets of size j that contain the
j−1
index k. As a final step, we follow [2], [3] and normalize
the file length F = 1 in (10)-(12). This yields the following
linear programming problem with K + 1 variables, K + 3
constraints, and K terms in the objective function:
K−1
X K 
vj
(13)
minimize
j+1
j=0
K  
X
K
vj = 1,
(14)
subject to
j
j=0

K 
X
K −1
vj ≤ M/N,
(15)
j−1
j=1
vj ≥ 0, ∀j ∈ U.

(16)

Note that the reduction to an optimization problem that scales
as a linear function of K and as a constant function of N
is possible because of the symmetry created by the uniform
file length, file popularity, and cache size. Later in this paper,
cases when one or more of these parameters are non-uniform
are treated; but the reduction from the exponential order will
no longer be without loss of generality.
Note also that the schemes of [2], [3] and [4] are all
feasible points of this problem. In particular, assuming that
t = KM/N is an integer, the caching scheme of [2],
[3] sets vt = 1/ Kt and vj = 0 if j 6= t, while the
decentralized scheme of [4] sets the variables to be of the
form vj = (M/N )j (1 − M/N )K−j for all j. For the noninteger t case, a similar scheme is also stated in [2], [3]. The
following theorem shows that the caching scheme of [2], [3]
is, in fact, the optimal scheme among the broad family of
schemes discussed above. The theorem works for the cases
of integer or non-integer t. We note that while a similar result
for the integer t case exists in [17], the proof used here
uses a novel reformulation over the probability simplex. It
is considerably simpler and lends additional insight into the
problem.
Theorem 1. Assume M ≤ N . The unique, optimal solution
to (13)-(16) is:
• For t = KM/N ∈ Z:
(

1/ Kt
if j = t,
∗
vj =
(17)
0
if j 6= t
•

For t = KM/N ∈
/ Z:


K

s/ ⌊t⌋
vj∗ = (1 − s)/


0

where s = ⌈t⌉ − t.

if j = ⌊t⌋
K
⌈t⌉



if j = ⌈t⌉
else

Proof:
First, we make a change of variables: aj =

vj / K
;
after
some mild algebra, the original problem (13)j
(16) can be reformulated as:
minimize

K
X
K−j
j=0

subject to

K
X

j+1

aj

(19)

jaj ≤ t

(20)

aj = 1

(21)

j=0

K
X
j=0

aj ≥ 0,

∀j ∈ [0 : K].

(22)

In this form, the optimization problem is more easily understood. Constraints (21) and (22) restrict the feasible space to
the probability simplex. The key features of the formulation
is that the coefficients of the objective function K−j
j+1 are
decreasing in j with decreasing second differences, while
the cache constraint (20) now has coefficients that increase
linearly in j. Intuitively, the optimal solution would involve
placing as much “probability mass” in high-j aj variables in
order to lower the objective function, but not so high as to
violate the cache constraint. This results in the optimal aj to
concentrate around at most two consecutive j’s close to t.
To complete the argument, we first observe that at the
optimal solution a∗ of (19)-(22), the cache constraint (20)
must be tight, when M ≤ N . This is because if it were
not, one can always shift some of the weight of aj to a
higher indexed aj+1 without violating the constraints while
lowering the objective function. In the practical context, this
means that the optimal caching strategy does not waste any
cache space.
Second, for a similar reason, we can show that if a feasible
solution a = [a0 , . . . , aK ]T to (19)-(22) has two non-zero
variables ai1 6= 0 and ai2 6= 0 such that i2 − i1 ≥ 2,
then a cannot be an optimal solution of (19)-(22). This is
because for any such a, we can always construct a better
feasible solution ā = [ā0 , . . . , āK ]T in the following way.
For some small ∆, set āi1 = ai1 − ∆, āi1 +1 = ai1 +1 + ∆,
āi2 = ai2 − ∆, āi2 −1 = ai2 −1 + ∆, and āj = aj for all other
j values. (If i1 + 1 = i2 − 1, then set āi2 −1 = ai2 −1 + 2∆.)
Note that such ā remains on the probability
simplex;
PK the
PK
cache constraint remains satisfied as j=0 jāj = j=0 jaj ,
while the objective function decreases strictly, because the
coefficients of aj in the objective, K−j
j+1 is a decreasing
function of j with decreasing second differences.
The above two observations imply that the optimal solution
has either only one non-zero variable, or two non-zero
variables that have adjacent indices, i.e. some j and j + 1. In
this case, the constraints for the optimal solution to (19)-(22)
reduce to

(18)

jaj + (j + 1)aj+1 = t,

(23)

aj + aj+1 = 1.

(24)

and

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

This system of equations has a unique solution. Indeed, due to
(24) and the positivity constraints, (23) implies that t must be
a convex combination of j and j+1. If t ∈
/ Z, the only integer
possibility for j is j = ⌊t⌋ and j + 1 = ⌈t⌉; representing
t = s⌊t⌋ + (1 − s)⌈t⌉ for some s ∈ (0, 1), it becomes clear
that the unique solution to (23)-(24) is aj = s, aj+1 = 1 − s
for j = ⌊t⌋ and s = ⌈t⌉ − t. If t ∈ Z, then we can set j = t,
then the unique solution to (23)-(24) is aj = 1, aj+1 = 0.
Using the change of variables vi = ai / Ki , this gives the
optimal solution to (13)-(16) as stated by (17)-(18).
As a final remark for this section, we acknowledge that
there exist stronger results about optimal coded caching
schemes than Theorem 1 in the literature, for instance, [44]
shows that a slightly modified version of the scheme in [2],
[3] is the optimal coded caching scheme among all schemes
with uncoded cache content using information theoretical
upper bounds. The optimization theoretic perspective of this
paper is nevertheless worthwhile in that it easily begets
extensions to more practical non-uniform scenarios, which
is the focus of the rest of this paper.
IV. C ODED C ACHING

WITH

H ETEROGENEOUS F ILES

We now move onto the coded caching problem with heterogeneous parameters. Although the optimization problem
(8)-(9) is already capable of accounting for non-uniform file
popularity, file length, and cache size, the problem size scales
exponentially in system parameters, hence the optimization
problem is intractable for practical system sizes. The main
contributions of this and the next section are to develop
simplifications to (8)-(9) that reduce the computational complexity of the problem while maintaining high-quality performance. Each non-uniformity is considered both individually
and in conjunction with the others in order to gain insight
into the interactions of their respective effects. We begin by
examining the effect of non-uniform file popularity and nonuniform file length, but for now keep the cache sizes uniform
across the users.
The procedure for each case is roughly as follows: first a
new set of variables are defined that are intended to capture
some structural feature of the problem, e.g. the vj variables of
the simplified homogeneous problem (13)-(16). Next, certain
conditions, referred to as memory inequality constraints, are
imposed on the new variables (see e.g. (35)), which forces
feasible solutions to dedicate more cache memory to certain
kinds of files, e.g. more popular files. While no a priori
justification for the use of these variable and constraints
is given, subsequent numerical results justify their use a
posteriori.
These memory inequality constraints then allow the simplification of the objective function (8). First, the max function
can be eliminated from (8), since the memory inequality
constraints are sufficient to determine a priori which subfiles
will be the maximum given some request vector d. This
in turn allows the expected rate to computed precisely in
terms of the largest file requested, the second largest file
requested, and so on, instead of in terms of the N K possible
request vectors. Since there are K files requested, and N

5

possibilities for each file, this ultimately reduces the scaling
of the objective function from exponential to polynomial,
although the objective function does not necessarily scale
with N K precisely.
A. Prior Work
The effect of non-uniform file popularity, also referred
to as non-uniform demands, on coded caching has been
explored in a number of papers [5]–[16]. In [5], [6], Niesen
and Maddah-Ali modify their decentralized scheme from [4]
by first grouping users according to the popularity of their
respective file requests, and then transmitting to the groups
sequentially using the scheme from [4]. The authors of [7]–
[11] develop an order-optimal scheme using random caching
with a graph-based algorithm to design coded multicast
transmissions, with [9] focusing specifically on the application of video delivery. In [10], [11], both the popularity of
the files and their request correlation are considered when
designing the caching and transmission scheme, while in
[12]–[15], a heterogeneous network structure is considered,
with file popularity organized in discrete levels. Using a
novel random caching-based scheme, [16] is able to show
order-optimality with a constant that is independent of the
popularity distribution. Finally, we repeat earlier comments
that [17] uses the same optimization framework that is used to
study non-uniform popularity in great depth; we nevertheless
show our (similar) work for the sake of exposition.
The literature on the effects of non-uniform file length is,
however, comparatively scarce. To the best of our knowledge,
Zhang et al [18] provide the only scheme designed to
accommodate non-uniform file length for a general number of
users. A scheme is provided that uses random caching with a
transmission scheme similar to the one used in this paper, and
upper and lower bounds on system performance are derived.
In particular, [18] explores a random caching scheme where
files are cached with a probability proportional to size of
the file. Non-uniform file size is also explored in the recent
letter [19], in which the achievable rate region for both nonuniform file size and non-uniform cache size is characterized,
but only for the case of K = 2 users and N = 2 files.
Note that it can be argued that if files are indeed different
sizes, they can be broken up into smaller packets of a constant
size F ′ bits, and then treated as separate files. While this
is a reasonable assumption while investigating other aspects
of a coded caching scheme, there are two issues that need
be addressed in practice. First, if a file is broken up into
multiple pieces, then a user who seeks to to download the
entire file must make multiple (correlated) requests to the
server - a fact that should be accounted for in subsequent
system design. The second practical issue comes from the
fact that it is unclear how to set the common file size F ′ :
efficiency demands that F ′ be as large as possible so that any
required headers represent a small proportion of the entire
download, while at the same time, F ′ should also be small
enough to divide files without significant remainder.
We therefore contend that heterogeneous file length is an
important parameter that a practical system must capable

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

6

of accommodating in one way or another. The approach to
handling non-uniform files sizes discussed above may indeed
have some merit; some work has been done to analyze the
case of multiple requests from users, see e.g. [20]–[23], and
so an approach based on this technique may be viable. This
paper, however, uses a different approach: files are not broken
up into smaller files of equal lengths, and so the cache
content is designed to accommodate their different lengths.
The possibility of comparing the performance of the different
approaches is left to future work.
To the best of our knowledge, there has been no work
exploring the relationship between file length and popularity
and the resulting effect on cache content. In the literature
discussed above, it is noted (roughly) that more popular files
should be allocated more cache memory, but also that larger
files should be allocated more cache memory. Given that,
in general, file lengths and popularity may not have any
correlation, it is not clear how these non-uniformities jointly
affect optimal cache content. These interactions are explored
in the following.

Pr[Ym = i] =

!K−m
!K−m 


N
N
X
X
K


−
pl
pl
K −m
l=i
l=i+1
!m K−2 min {m−1,K−2−k}
i−1
X
X
X
+
pl





K
p2+k
2 + k, b, K − 2 − k − b i
i−1
X
l=1

pl

!b

N
X

l=i+1

pl

!K−2−k−b 

where the final expression is for i ∈ [2 : N ].

(l)

Lemma 1 (Chu-Vandermonde Convolution). For N, N1 , N2 ,
and n positive integers, with N1 + N2 = N and n ≤ N ,


  X
n 
N2
N
N1
(25)
=
n−k
k
n
k=0

Lemma 2. Consider K independent multinomial random
trials with N possible outcomes per trial, with probabilities
{p1 , p2 , . . . , pN }, denoted by Z ∈ [N ]K , i.e., Zi , the i-th
element of Z, is the outcome of the i-th trial. Let the random
vector Y be a sorted version of Z, but with index shifted by
1, so that Y0 is the smallest element of Z, Y1 is the second
smallest element, and so on. The probability mass function
of Ym is given by
!K
!K
N
N
X
X
,
(26)
pl
Pr[Y0 = i] =
−
pl
i+1

l=i



Pr[Y1 = i] = Pr[Y0 = i] + K 
−

i
X

pl

l=1

!

and for m ∈ [2 : K − 1],
K−m−1
X 
k=0

i−1
X
l=1

pl

!

N
X
l=i

pl

!K−1

!K−1 
N
X
,
pl

(27)

l=i+1

K
m+1+k



p1m+1+k (1 − p1 )K−m−1−k

(28)

(29)

The first step in reducing the exponential number of
variables in (8)-(9) is the definition of a new set of (K +1)N
variables as
vl,j = |WS |, ∀S s.t. |S| = j, ∀l ∈ [N ].

First, we introduce two lemmas. The first one is a classic
result about binomial coefficients, while the second lemma
is used to determine the probability that the file n is the k-th
largest file requested; the proof of the latter is contained in
Appendix A.



C. Optimization Formulation

B. Preliminaries

Pr[Ym = 1] =

k=0 b=max {0,m−1−k}

l=1



(30)

similar to the vj variables used in Section III, except now
there is a set of vj variables for each file to capture the
difference in length and popularity between files. Such a
(l)
reduction enforces |WS | to depend only on the cardinality
of S, which is a reasonable thing to do and in fact can be
proved to be without loss of generality for the special case
of non-uniform file popularity alone but with uniform file
length [17]. The effect of this reduction in the general case
is numerically evaluated later in the section.
The simplification of the general constraints in (9) follows
similar reasoning used to obtain the constraints (11)-(12) in
Section III, except now there are arbitrary file lengths Fl and
popularities pl ; this gives
K  
X
K
vl,j = Fl , ∀l ∈ [N ]
(31)
j
j=0
as the file reconstruction constraints, and

K 
X
K −1
vl,j ≤ µl , ∀l ∈ [N ]
j−1
j=1

(32)

for the cache constraint. The other two constraints,
vl,j ≥ 0, ∀l ∈ [N ], ∀j ∈ [0 : K],
and

N
X

µl ≤ M

(33)

(34)

l=1

have more obvious modifications.
To express the objective function in polynomial number of
terms, we now need to impose certain memory inequality conditions in order to simplify the max operator in the objective.
We propose two different approaches called the popularityfirst approach and the length-first approach respectively for
handling the non-uniform file popularity and file length.

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

7

1) Popularity-First Approach: In the popularity-first approach, files are labelled in decreasing over of popularity, i.e.
such that p1 ≥ · · · ≥ pN . Then, motivated by the idea that
more popular files ought to have more cache space dedicated
to them, a memory inequality condition is imposed on the
cache content as
vl1 ,j ≥ vl2 ,j , ∀l1 , l2 ∈ [N ] s.t. l1 < l2 , j ∈ [K].

Proposition 1. Consider the case of non-uniform file popularity and uniform file length. Let the variables defined in (30)
be subject to condition (35) with files labelled in decreasing
order of popularity. Then the objective function (8) simplifies
exactly as

E

X

S∈P(U )\∅

(d )



N 
K−1
XX
X K−1


K −1−i
Pr[Yi = l]vl,j
j

j=1 i=0 l=1

+

K−1
N
XX

+

Pr[YK−i−1 = l]vl,0 , (36)

i=0 l=1

where Yi is the random variable representing the (i + 1)-th
smallest index in a random request vector d.
The proof of Proposition 1 is contained in Appendix B.
Note that the probabilities Pr[Yi = l] can be obtained directly
from Lemma 2: since the files are labelled in decreasing order
of popularity, the probability that l is the (i + 1)-th smallest
file requested in d is equivalent to the probability that l is the
(i + 1)-th smallest index in Z. The optimization problem for

K−1
N
XX

Pr[YK−i−1 = l]vl,0

(37)

i=0 l=1

subject to

(31)-(35),

(38)

Note that this is a linear program, with a number of
summands in the objective function that scales K 2 N , and
exactly KN variables and N (K + 3) + K(N (N − 1))/2 + 1
constraints.
If the files are also of non-uniform length, further work is
required, but a similar optimization problem can nonetheless
be developed. The details are omitted here both for the sake
of brevity and because numerical results suggest that the
popularity-first approach does not perform as well as the
length-first approach in the general case when both popularity
and file lengths are non-uniform.
2) Length-First Approach: In the length-first approach,
files are labelled in decreasing order of length, i.e. such that
F1 ≥ F2 ≥ · · · ≥ FN . Then, motivated by the idea that
longer files ought to have more cache space dedicated to
them, the following memory inequality condition is imposed:
vl1 ,j ≥ vl2 ,j , ∀l1 , l2 ∈ [N ] s.t. l1 < l2 , j ∈ [0 : K − 1]. (39)
Using similar reasoning as Proposition 1, it is straightforward to show that
Proposition 2. Consider the case of non-uniform file length
with either uniform or non-uniform popularity. Let the variables defined in (30) be subject to condition (39) with files
labelled in decreasing order of length. Then the objective
function (8) simplifies exactly as


X
(d
)
k
|}
max{|WS\{k}
E
S∈P(U )\∅

k
|} =
max{|WS\{k}

k∈S

l=1

(35)

This memory inequality constraint is adopted to help reduce
the complexity of the problem; as previously discussed, this
constraint (and others like it later in the paper) allow the max
function in (8) to be eliminated in favour of a linear function
of the variables, which in turn allows for the expected rate to
be computed in a polynomial number of operations, instead
of the exponential number required by (8).
The popularity-first approach is most appropriate for the
special case of non-uniform file popularity alone, but with
uniform file length. The following proposition shows explicitly the effect that (35) has on the objective function in this
case. Note that in this special case of uniform file length,
(35), which holds for j = 1, . . . , K, becomes reversed for
j = 0. To see this, consider two files l1 and l2 with l1 < l2 ,
that satisfy (35); if both have length F , i.e. satisfy (31) with
Fl! = Fl2 = F , then vl1 ,0 ≤ vl2 ,0 because every other subfile
of l1 is larger than every other subfile of l2 .
As mentioned earlier, this special case of non-uniform
file popularity alone with uniform file length has already
been considered in independent work [17]. But the problem
formulation of [17] does not account for the difference in
the lengths of subfiles within the max operator, thus may
result in loss of optimality. The expression below is an exact
accounting of the expected delivery rate.



the case of non-uniform file popularity, uniform file length,
and uniform cache size can now be written as

K−1
N 
X K−1
XX
K −1−i
minimize
Pr[Yi = l]vl,j
j
j=1 i=0

=

k∈S

N 
K−1
XX
X K−1
j=0 i=0 l=1


K −1−i
Pr[Yi = l]vl,j
j

(40)

where Yi is the random variable representing the (i + 1)-th
smallest index in a random request vector d.
The length-first optimization problem for non-uniform file
popularity, non-uniform file length, and uniform cache size
is obtained as

K−1
N 
X K−1
XX
K −1−i
minimize
Pr[Yi = l]vl,j (41)
j
j=0 i=0
l=1

subject to

(31)-(34), (39)

(42)

which is a linear program with K 2 N summands in the
objective function, KN variables, and N (K +3)+K(N (N −
1))/2 + 1 constraints.

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

8

4.5

4.5
Optimal Solution, Polynomial Problem
Optimal Solution, Exponential Problem
Random Caching

Random Caching
Optimal Solution, Polynomial Problem
Optimal Solution, Exponential Problem

4

3.5

3.5

3

3

Expected Rate, R

Expected Rate, R

4

2.5
2

2.5
2

1.5

1.5

1

1
0.5

0.5

0

0
0

1

2

3

4

5

0

6

1

2

3

4

5

6

Memory Size, M

Memory Size, M

Fig. 1. A comparison of the performance of the solution obtained from
(8)-(9) to the solution obtained by (37)-(38), with reference to a baseline
random caching scheme, for the case of non-uniform file popularity only

Fig. 2. A comparison of the performance of the solution obtained from
(8)-(9) to the solution obtained by (41)-(42), with reference to a baseline
random caching scheme, for the case of non-uniform file length only.

D. Numerical Results

T HE FILE

TABLE I

To evaluation the effect of the simplified problem formulation, we consider a case with K = 4 users with equal
cache sizes of M , and N = 6 files. When the files are
of uniform length, the value F = 1 is used, and when
they are of non-uniform length, the values {F1 , . . . , F6 } =
{9/6, 8/6, 7/6, 5/6, 4/6, 3/6} are used. Similarly, when the
files are of uniform popularity, the value pl = 1/N is used for
all l ∈ [N ], but when the files have non-uniform popularity,
the distribution is given by a Zipf distribution with parameter
s, which has been observed empirically to be reasonable
model for user demands; a parameter of s = 0.56 is used
in this paper (see e.g. [42]). When both the file lengths and
popularities are non-uniform, the relationship between length
and popularity is specified explicitly.
Fig. 1 compares the rate-memory tradeoff curve for the
original problem (8)-(9) and the simplified problem (37)(38) for the non-uniform popularity and uniform length case.
A baseline random caching scheme is also included for
reference. This random caching scheme is essentially the
decentralized scheme of [4] but with file n allocated µn F
bits of cache memory instead of M F/N bits; initially, the
value
P is obtained as µn = min{M pn , 1} for all n ∈ [N ], and
if N
n=1 µn < M after that, the remaining cache memory is
allocated to each file sequentially until the remaining memory
runs out.
Conversely, Fig. 2 compares the rate-memory tradeoff
curves of (8)-(9) and the simplified problem (41)-(42) for the
non-uniform length and uniform popularity case. The random
caching baseline scheme used here is essentially equivalent
to the one proposed in [18].
Both figures show that the performance of the general
problem and the two simplified problems is identical for the
respective cases considered here. Indeed, when the numer-

LABELLING AND LENGTH - POPULARITY PAIRINGS USED IN THE
NON - UNIFORM FILE POPULARITY AND LENGTH CASE .

Length-First (LF) and Popularity-First (PF) Labelling
LF File Index
PF File Index
Length
Popularity
1
5
9/6
0.1176
2
3
8/6
0.1566
3
2
7/6
0.1965
4
6
5/6
0.1062
5
1
4/6
0.2897
6
4
3/6
0.1333

ical solutions of (8)-(9) for these two cases are examined
explicitly, it is clear that the memory constraint conditions
are indeed satisfied, and so the optimal solutions in these
cases are attainable by the respective simplified problems.
Next, Fig. 3 compares the performance of the original
problem (8)-(9) to both the length-first and popularity-first
simplified problems for the case of non-uniform file length
and popularity. The specific pairings of length and popularities used and their associated labels are listed in Table I.
Although somewhat arbitrary, these file length and popularity combinations are intended to simulate a practical scenario
where file popularity and length are relatively uncorrelated.
While examining this individual case is not sufficient for
determining general patterns, it is enough to gain some
important insight about the tension between file length and
popularity.
Fig. 3 shows that in this case, the length-first scheme yields
much better results than the popularity-first scheme. Indeed,
the length-first scheme obtains the same performance as the
original problem for all M considered except M = 1. The
reason for this divergence can be seen from Table II which
shows the optimal solution to the original problem (8)-(9) in
(l)
the M = 1 case. The value of |WS | is shown in the l-th
column of the row labelled with S, and the files are ordered

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

9

popularity and file length are kept uniform; the case with
all parameters being non-uniform is treated in the subsequent section. For the case of non-uniform cache size, a
decentralized coded caching scheme is developed in [24]
and subsequently improved upon in the K > N case by
[25], [26]. As previously discussed, [27] uses an optimization
framework similar to the one used in this paper to generate a
scheme for the centralized case. For the sake of completion,
we note again the work [19] in which the rate region for both
non-uniform cache and file size is characterized for K = 2
users and N = 2 files, but the optimal scheme is not yet
known for the general case.

4
Optimal File-First Caching, Polynomial Problem
Optimal Probability-First Caching, Polynomial Problem
Optimal Caching, Exponential Problem
Random Caching

3.5

Expected Rate, R

3

2.5

2

1.5

1

0.5

A. Optimization Formulation

0
0

1

2

3

4

5

6

Memory Size, M

Fig. 3. A comparison of the performance of the solution obtained from (8)(9) to the solutions obtained by (41)-(42) and a popularity-first optimization
problem, with reference to a baseline random caching scheme, for the case
of non-uniform file length and popularity.
TABLE II
O PTIMAL SUBFILE SIZES AND MEMORY ALLOCATION FOR THE GENERAL
PROBLEM (8)-(9) WITH K = 4, N = 6, M = 1, AND FILE LENGTHS AND
POPULARITIES GIVEN IN TABLE I ( USING LENGTH - FIRST INDEXING ),
WITH VALUES ROUNDED TO THREE DECIMAL PLACES .
Subset
∅
{1}
{2}
{3}
{4}
{1, 2}
...
{1, 2, 3, 4}
Total memory:

1
0.833
0.167
0.167
0.167
0.167
0

2
0.583
0.188
0.188
0.188
0.188
0

0
0.167

0
0.188

File Index
3
4
0.417
0.167
0.188
0.167
0.188
0.167
0.188
0.167
0.188
0.167
0
0
...
0
0
0.188
0.167

5
0
0.167
0.167
0.167
0.167
0

6
0
0.125
0.125
0.125
0.125
0

0
0.167

0
0.125

using the length-first labelling of Table I. It is clear that file 1,
the largest file but fifth-most popular, has been allocated less
cache memory than files 2 and 3, which are the third and
second most popular files respectively. Thus the memoryinequality constraint (39) is violated and so the length-first
simplified problem cannot attain the optimal solution of (8)(9). Despite this, the optimal value to the simplified problem
is only about 10−4 larger than the optimal value of (8)(9), and so the difference is not significant. It would thus
appear that, while probability cannot be completely ignored
in theory, a length-first approach to caching can yield very
good results in practice. This insight is later used in Section
VI-A, but first the problem of non-uniform cache size must
be studied on its own first; this is done next.
V. C ODED C ACHING

WITH H ETEROGENEOUS
S IZES

C ACHE

We next consider simplifying the optimization formulation
for the case with non-uniform cache sizes. For now, file

We first consider a simple case where there are only two
cache sizes, “large” and “small”, represented by ML and MS
respectively. The variable KL is used to represent the number
of users with large caches, and KS is used to represent the
number of users with small caches, such that KL +KS = K.
Note that file lengths and popularities are fixed as uniform,
i.e. p1 = · · · = pN = 1/N and F1 = · · · = FN = F = 1
respectively.
Since files here are equally popular and of the same size,
we have symmetry across files, but now the symmetry across
users is broken by the non-uniform cache size. However,
certain user symmetry still exists, i.e., symmetry among
members of the same cache size group. We therefore define
three sets of variables for j ∈ [0 : K], denoted vj,S , vj,L , and
vj,M , as follows. For a subset of users S with a size |S| = j,


vj,S if S contains only small-cache users,
(l)
|WS | = vj,L if S contains only large-cache users,


vj,M otherwise,
(43)
for all files l ∈ [N ].
This definition suggests some natural constraints. First,
since there are only KS small-cache users, there cannot be
a group of j small-cache users if j > KS , so we set
vj,S = 0, ∀j > KS .

(44)

Similarly, for large-cache users,
vj,L = 0, ∀j > KL .

(45)

A similar constraint is required for the v1,M . Since there
cannot be a subset of size one with both large- and smallcache users, we require
v1,M = 0;

(46)

Moreover, since the j = 0 variables correspond to subsets of
size 0, it it not particularly meaningful to discuss whether or
note this corresponds to a small, large, or mixed subset. To
avoid any further complications, we simply set
v0,S = v0,L = v0,M = v0 ,

(47)

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

To understand the file reconstruction condition, note that,
for j ≥ 2, there are KjS groups of small-cache users, KjL
groups of large-cache users, and


j−1 
X
KL
KS
i=1

i

j−i

mixed groups, because each mixed group must have at least
one small-cache users and at least one-large cache user. By
adding and subtracting the i = 0 and i = j terms and using
Lemma 1, we can rewrite this as


j 
X
KL
KS
i=0

i

   
KS
KL
−
−
j
j
j−i
     
KS
K
KL
,
−
=
−
j
j
j

and so the total portion of the file cached by subsets of size
j ≥ 2 is
 
 
 
K
KS
KL
(vj,S − vj,M ) +
vj,M .
(vj,L − vj,M ) +
j
j
j
(48)

For j = 1, there are KL = K1L large users and KS = K1S
small users. Moreover, since v1,M = 0, it is easy to see that
(48) also holds for j = 1. Finally, consider the j = 0 case.
Here we only need to add v0 to capture the portion of the
file not cached by any user. However, note that if we set
j = 0 in (48) and apply constraint (47), the first two terms
become 0, while the last term reduces to v0,M = v0 . Thus
(48) applies for all j, and so we can conveniently express
the file reconstruction constraint as

 
K 
X
KS
KL
(vj,S − vj,M )
(vj,L − vj,M ) +
j
j
j=0
 
K
+
vj,M = 1. (49)
j
Similar reasoning is used to obtain the cache memory
constraints. A small cache user caches every subfile labelled
with a subset in which he is contained as a member, and
so necessarily caches only subfiles of size vj,S and vj,M .
S −1
Specifically, a small-cache user is a member of Kj−1
small
groups of size j, and
K−2
X KS − 1 KL 
(50)
j−1−i
i
i=0
mixed groups. Using Lemma 1 once again, the cache memory
constraint for the small user is obtained as



K 
X
KS − 1
K −1
(vj,S − vj,M ) +
vj,M = MS /N.
j−1
j−1
j=1

(51)

Note that the j = 1 expression reduces to KL0−1 (v1,S −0)+
0 = v1,S , as desired. Note also that each file is allocated an
equal MS /N of the cache because the files are equally sized

10

and equally popular. Using similar reasoning for large-cache
users, we obtain



K 
X
KL − 1
K −1
(vj,L − vj,M ) +
vj,M = ML /N.
j−1
j−1
j=1
(52)

As always, it is required that all subfiles be of nonnegative
size:
vj,S ≥ 0, vj,L ≥ 0, vj,M ≥ 0, ∀j ∈ {0, . . . , K}.

(53)

Finally, the memory inequality constraints for this problem
are introduced. In general, we would expect the subfiles that
large users have cached to be longer than the ones cached by
small users. This is codified in the problem explicitly with
vj,L ≥ vj,M , j ∈ [2 : KL ]
vj,M ≥ vj,S , j ∈ [2 : KS ]

(54)
(55)

vj,L ≥ vj,S , j ∈ [1 : KL ].

(56)

Again note that there is some redundancy in these constraints,
but they are nonetheless included for clarity of exposition.
Note also that the first two inequalities hold from j = 2 to
j = KL and j = KS respectively; the j = 1 is already
constrained by (46), while the j = 0 is constrained by (47),
and the j > KL and j > KS cases are governed by (45) and
(44) respectively.
As Proposition 3 shows, the memory inequality constraints
allow us to greatly simplify the original objective function
(8).
Proposition 3. Assuming uniform file length and popularity
but two different user cache sizes, and with variables as
defined in (43) and satisfying (44)-(47) and (53)-(56), the
objective function (8) simplifies exactly as


X
(dk )
|}
max{|WS\{k}
E
S∈P(U )\∅

=

k∈S

K−1
X




K
Ks
(vj,S − vj,M ) +
vj,M +
j+1
j+1
j=0
   

KL
KS
KL
(vj,L − vj,M ) (57)
+
j
1
j+1

The proof of Proposition 3 is in Appendix C. The simplified optimization problem can then be written as


K−1
X  Ks 
K
(vj,S − vj,M ) +
vj,M +
minimize
j+1
j+1
j=0
   

KL
KS
KL
(vj,L − vj,M )
+
j
1
j+1
(58)
subject to (44)-(47), (49), (51)-(56).
(59)
This is a linear program that has a number of variables,
constraints, and objective function summands that scale linearly in K.

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

11

TABLE III
O PTIMAL SUBFILE SIZES AND MEMORY ALLOCATION FOR THE GENERAL
PROBLEM (8)-(9) WITH K = 4, N = 6, KS = 2, MS = 3.2 AND
ML = 4.8, WITH VALUES ROUNDED TO THREE DECIMAL PLACES .

4.5
Optimal Caching, Polynomial Problem
Optimal Caching, Exponential Problem
Wang et al., Random Caching Scheme

4

3.5

Expected Rate, R

3

2.5

2

1.5

1

0.5

0
0

1

2

3

4

5

6

Memory Factor, M

Fig. 4. A comparison of the performance of the solution obtained from
(8)-(9) to the solution obtained by (58)-(59) for KS = 2.

Finally, we remark that only two cache sizes were considered in this paper. While a practical system would likely have
more than two cache sizes, it is reasonable to expect that only
a small number of cache sizes will be used, e.g. cell phones
with 8,16, 32 or 64 GB of cache memory. The reasoning
used here for two cache sizes could then be extended to
accommodate these additional cache sizes as needed.
B. Numerical Results
Consider a case where there are N = 6 files, uniform in
popularity and length, and K = 4 users. Define a ”memory
factor” M ∈ [0 : N ]; there are KS small users with a cache
size of MS = 0.8M , and KL large users with a cache
size of ML = 1.2M . Fig. 4 compares the corresponding
solution of the general problem (8)-(9) to the solution of
the simplified problem (58)-(59) when there are KS = 2
small users. The random caching scheme of [24] is included,
but the centralized scheme of [27] (which has exponential
complexity) is not. The purpose here is not to determine
the best caching scheme for the heterogeneous cache case,
but to, first, demonstrate the implicit performance-tractability
tradeoff of using the simplified problem (58)-(59) over the
general problem, and second, to demonstrate that it is worth
the effort of developing and using these problems to design
cache content (rather than caching randomly) when the
engineering context allows for it. Nevertheless, we expect the
performance of the problem in [27] to be very similar, if not
identical, to the exponential problem developed here, even
though the two optimization frameworks are not identical
themselves. Table III also shows the optimal cache content
obtained from the general problem in the KS = 2, M = 4
case.
Fig. 4 shows that in the KS = 2 case, while the simplified
problem tracks the optimal scheme for small cache size

Subset
∅
...
{4}
{1, 2}
{1, 3}
{1, 4}
{2, 3}
{2, 4}
{3, 4}
{1, 2, 3}
{1, 2, 4}
{1, 3, 4}
{2, 3, 4}
{1, 2, 3, 4}
Mem. (L):
Mem. (S):

1
0

2
0

0
0.056
0.056
0.056
0.056
0.056
0.056
0.033
0.033
0.300
0.300
0
0.800
0.533

0
0.056
0.056
0.056
0.056
0.056
0.056
0.033
0.033
0.300
0.300
0
0.800
0.533

File Index
3
4
0
0
...
0
0
0.056
0.056
0.056
0.056
0.056
0.056
0.056
0.056
0.056
0.056
0.056
0.056
0.033
0.033
0.033
0.033
0.300
0.300
0.300
0.300
0
0
0.800
0.800
0.533
0.533

5
0

6
0

0
0.056
0.056
0.056
0.056
0.056
0.056
0.033
0.033
0.300
0.300
0
0.800
0.533

0
0.056
0.056
0.056
0.056
0.056
0.056
0.033
0.033
0.300
0.300
0
0.800
0.533

(M ≤ 3), it performs worse than even the random caching
scheme for large M values. Table III reveals why this is
the case. Here, users 1 and 2 are the small users, and
users 3 and 4 are the large users. The variable definitions
in (43) specify one variable for all mixed subsets of the
same size, but consider the subfile sizes for the size-three
subsets: the subsets with 2 small users have smaller subfiles
than the subsets with 2 large users. Thus using only one
M
vl,j
variable for these four subsets results in a loss in
performance. In principle, one could introduce more variables
to accommodate this, albeit at a cost of a more complicated
objective function.
VI. C ODED C ACHING

WITH H ETEROGENEOUS F ILES AND
C ACHE S IZES

The natural final step in this program is to develop
a tractable optimization problem that accommodates nonuniformity in cache size, file size, and popularity at the same
time. To the best of our knowledge, there has yet to be a
caching scheme proposed that handles heterogeneity in all
three of these domains.
A. Optimization Formulation
We begin by defining a new set of variables that, in a
sense, combines the functionality of the variables defined in
(30) and (43). Let

S

vl,j if S contains only small-cache users,
(l)
L
|WS | = vl,j
if S contains only large-cache users,

 M
vl,j otherwise,
(60)
for a subset of users S such that |S| = j and all files l ∈ [N ].
The symmetry across users is broken by the heterogeneity of
the user cache size, and the symmetry across files is broken
by a the heterogeneity of files in both length and popularity.
Nevertheless, we can still exploit the symmetry across subsets

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

12

of users of the same size (j) and type (i.e. small, large, mixed)
for a particular file (l) to reduce the complexity of the original
problem (8)-(9) while still accounting for the aforementioned
heterogeneity.
Many of the constraints used in the non-uniform cache size
case can be converted to their equivalents for this new case.
If j > KS , there cannot be a subset of j small cache users,
so
S
vl,j
= 0, ∀j > KS , ∀l ∈ [N ],
(61)

where it must be the case that
N
X

A similar pair of equations holds for large users:
µL
l =

(62)

Since there cannot be a subset of size 1 containing both large
and small users, the l = 1 variable is constrained as
M
vl,1

= 0, ∀l ∈ [N ],

(64)

The cache size-based memory inequalities should still hold,
giving, for a fixed file l,
L
M
vl,j
≥ vl,j
, j ∈ [2 : KL ], ∀l ∈ [N ],

(65)

M
S
vl,j
≥ vl,j
, j ∈ [2 : KS ], ∀l ∈ [N ],

(66)

L
vl,j

(67)

≥

and
N
X

j ∈ [1 : KL ], ∀l ∈ [N ].

vlL1 ,j ≥ vlL2 ,j , j ∈ [0 : K − 1], ∀l1 , l2 s.t. l1 < l2

(68)

vlM
1 ,j
S
vl1 ,j

j ∈ [0 : K − 1], ∀l1 , l2 s.t. l1 < l2

(69)

j ∈ [0 : K − 1], ∀l1 , l2 s.t. l1 < l2 .

(70)

≥
≥

The remaining conditions are formed using identical reasoning to the non-uniform cache case, but occur on a fileby-file basis as needed. The file reconstruction constraint
remains the same, with the minor change that the file must
add up not to the common file length 1, but to Fl , the actual
length of the file as expressed below:
Fl =


 
K 
X
KS
KL
S
M
L
M
(vl,j
− vl,j
)
(vl,j
− vl,j
)+
j
j
j=0
 
K M
+
vl,j ,
∀l ∈ [N ] (71)
j

The cache memory constraints are modified similarly,
except instead of giving an equal amount MS /N to each
file, an amount µSl is allocated to file l, yielding
µSl


K 
X
KS − 1
S
M
(vl,j
− vl,j
)
=
j
−
1
j=1


K−1 M
+
v ,
j − 1 l,j

µL
l = ML .

(75)

l=1

L
S
M
vl,j
≥ 0, vl,j
≥ 0, vl,j
≥ 0, ∀j ∈ [0 : K], l ∈ [N ]

vlL1 ,j ≥ vlM
, j ∈ [2 : KL ], ∀l1 , l2 ∈ [N ]
2 ,j

(77)

vlM
1 ,j
vlL1 ,j

j ∈ [2 : KS ], ∀l1 , l2 , ∈ [N ]

(78)

j ∈ [1 : KL ], ∀l1 , l2 ∈ [N ].

(79)

≥
≥

vlS2 ,j ,
vlS2 ,j ,

In words, this means that subfiles for any file stored on a
larger cache type should be larger than the subfiles of any file
stored on a smaller cache type, independent of which files
are involved. The following proposition gives the objective
function of the simplified optimization problem.
Proposition 4. Define the following functions of the integer
parameters n, m, j and i:


KS − m
ν1 (n, m, j, i) =
K −n+1



KS − m − 1 KL − n + 1 + m
,
i
j−i


KL − n + 1 + m
ν2 (n, m, j, i) =
K −n+1



KS − m KL − n + m
,
i
j−i
and
ν(n, j) =

∀l ∈ [N ], (72)

(76)

Finally, another set of memory inequality constraints are
required to break ties between small-index, small-cache
subfiles and large-index, large-cache subfiles. Leaving the
justification and discussion of this choice to later sections,
we develop a caching scheme under the constraints

We also import conditions from the non-uniform file size
and popularity problem. As seen earlier, it is better to
prioritize file length rather than popularity, and so we label
the files in decreasing order of file length. This gives
vlM
,
2 ,j
S
vl2 ,j ,

∀l ∈ [N ], (74)

The subfiles are also required to be positive in size, as always:

M
S
L
= vl,0
= vl,0
= vl,0 , ∀l ∈ [N ].
vl,0

S
vl,j
,


K 
X
KL − 1
L
M
(vl,j
− vl,j
)
j
−
1
j=1


K −1 M
+
v ,
j − 1 l,j

(63)

and for convenience, we set

(73)

l=1

and similarly
L
vl,j
= 0, ∀j > KL , ∀l ∈ [N ].

µSl = MS .

n−1
X

m=0
j−2
X
i=1

KS
m



KL
n−1−m

K
n−1



ν1 (n, m, j, i) +

j−1
X
i=2

!

ν2 (n, m, j, i)

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

13

Then for the variables defined in (60) satisfying (61)-(79),
the objective function (8) simplifies exactly as


X
(d )
max{|W k |}
E
=

K−1
N
XX

M
Pr[Yi = l]vl,0
i=0 l=1
KX
N 
L −1 X
L −1 K
X
KL


−1−i
L
Pr[YiL = l]vl,j
j
i=0 l=1
j=1

KX
N 
S −1 X
S −1 K
X
KS − 1 − i
S
Pr[YiS = l]vl,j
+
j
j=1 i=0 l=1

KL KX
N 
S −1 X
X
KL
L
Pr[YiS = l]vl,j
+
j
j=1 i=0 l=1
 
KX
N 
S −1 X
S −1 K
X
KS − 1 − i KL
M
Pr[YiS = l]vl,j
+
1
j
j=2 i=0 l=1

K−1
K−1
N 
X
XX
K −1−i
M
+
Pr[Yi = l]vl,j
j
i=0
+

j=max{KS ,KL }+1

+

max{KS ,KL } K N
X
XX
j=3

Optimal Caching, Polynomial Problem
Optimal Caching, Exponential Problem
Random Caching

3.5

S\{k}

k∈S

l=1

M
Pr[Yn−1 = l]ν(n, j)vl,j

2.5

2

1.5

1

0.5

0
0

1

2

3

4

5

6

Memory Factor, M

Fig. 5. A comparison of the performance of the solution obtained from
(8)-(9) to the solution obtained by (81)-(82), with reference to a baseline
random caching scheme, for the case of non-uniform file size, file popularity,
and cache size.

(80)

n=1 l=1

Proposition 4 is proved in Appendix D. Although visually
complicated, (80) simplifies the original objective function
(8) by using only 3(K + 1)N variables and having a number
of terms that scales with K 2 N rather than (2N )K . The number of constraints described by (61)-(79) scales with KN 2 ,
and so the following optimization problem is a tractable
method of obtaining a caching scheme that accommodates
heterogeneity in cache size, file size, and file popularity:
minimize (80)
subject to (61) − (79)

3

Expected Rate, R

S∈P(U )\∅

4

(81)
(82)

simplified problem still achieves good performance compared
to the general problem in this regime. For large M , we see
that the expected rate of the simplified scheme does not
drop as quickly as the general problem solution, and is even
eclipsed by the random caching scheme. This occurs for the
same reason we saw in Section V in the KS = 2 case (Fig. 4).
To compare the relative performance of the three schemes in
general, Fig. 6 shows the percent increase in expected rate
if the random caching scheme is used over the general and
simplified schemes respectively. The significant increase in
rate when using random caching make it clear that designing
the cache content can be worthwhile when the engineering
context allows for it.

B. Numerical Results
To demonstrate that this simplified optimization problem
performs well when compared to the general problem (8)-(9),
we again consider K = 4 users (KS = 2 of which are smallcache users) and N = 6 files, with all of the non-uniformities
used thus far: file labels and popularity/size pairs as given in
Table I, and cache sizes of MS = 0.8M and ML = 1.2M
for M ∈ [0 : N ]. Fig. 5 compares the simplified and general
problems with a naive random caching baseline.
We see that the simplified problem yields a scheme that
closes mirrors, although does not match exactly, the performance of the scheme obtained from the general problem for
small and intermediate M values. Table IV shows the optimal
solution to the general problem for the M = 2 case; we see
several violations of the memory inequality constraints that
explain why the simplified problem could not achieve as good
a performance as the general problem: the “true” optimal
solution lies outside of its feasible space. Nevertheless, the

C. Further Extensions
We first echo the earlier comments about heterogeneous
cache sizes: we consider only two different cache sizes here,
but it is possible to use the same reasoning to develop a
tractable optimization problem for a practical system having
more (but not many more) cache sizes.
The primary focus in this section, however, is on the
memory inequality constraints (77)-(79) used in developing
the simplified problem (81)-(82) of this section. Recall that
these constraints require, among other things, that (roughly
L
variables for all files l
speaking) for a fixed index j, the vl,j
S
be larger than the vl,j variables for all files. Thus the largeuser subfile for the smallest file is larger than the smalluser subfile for the largest file. This restriction was required
to allow us to write the simplified problem, and numerical
results show that the simplified problem still performed
well compared to the general problem for the considered

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

14

TABLE IV
O PTIMAL SUBFILE SIZES AND MEMORY ALLOCATION FOR THE GENERAL
PROBLEM (8)-(9) WITH K = 4, N = 6, KS = 2, MS = 1.6, ML = 2.4
AND FILE POPULARITY / SIZE PAIRS GIVEN BY TABLE I, WITH VALUES
ROUNDED TO THREE DECIMAL PLACES .
Subset
∅
{1}
{2}
{3}
{4}
{1, 2}
{1, 3}
{1, 4}
{2, 3}
{2, 4}
{3, 4}
{1, 2, 3}
...
{1, 2, 3, 4}
Mem. (L):
Mem. (S):

1
0
0.178
0.178
0.178
0.178
0
0.090
0.090
0.090
0.090
0.431
0

2
0
0.178
0.178
0.178
0.178
0.077
0.090
0.090
0.090
0.090
0.188
0

0
0.788
0.357

0
0.554
0.434

File Index
3
4
0
0
0.178
0.178
0.178
0.178
0.178
0.178
0.178
0.178
0.008
0
0.090
0.008
0.090
0.008
0.090
0.008
0.090
0.008
0.090
0.090
0
0
...
0
0
0.446
0.284
0.365
0.194

5
0
0.165
0.165
0.165
0.165
0
0
0
0
0
0.008
0

6
0
0.085
0.085
0.085
0.085
0
0
0
0
0
0
0

0
0.173
0.165

0
0.165
0.085

VII. S UMMARY

0.4
Random v.s. Exponential Program
Random v.s. Polynomial Program

0.35

Percent Increase in Rate, %/100

0.3
0.25
0.2
0.15
0.1
0.05
0
-0.05
-0.1
0

1

2

3

4

5

larger-user subfile variable vlL2 ,j if file l1 is larger than file l2 .
While the simplified optimization problem that would result
from this constraint is not explored in this paper, it should
be possible to construct such a problem using the same kind
of reasoning used here.
Indeed, there may also be other memory inequality constraints that prove to yield useful simplified optimization
problems for other parameter sets. The appeal of the tractability of these models is that a server, knowing the relevant
parameters for its system, could easily compute the performance of these schemes and choose the best among them;
any discussion of the specifics of such schemes, however, is
left to future work.

6

Memory Factor, M

Fig. 6. The percent increase in expected rate due to random cache content
when compared to the simplified problem (81)-(82) and general problem
(8)-(9) optimal solutions.

parameters. While a full investigation of the performance
of the simplified problem across all parameter values would
be labourious, it is still possible to estimate the behaviour
for certain parameter regimes. We should expect (77)-(79) to
result in a good simplification when the disparity between
the large and small cache sizes is big, and when there are
small numbers of files, because the large cache users will
likely store much larger subfiles than the small cache users,
irrespective of the length of the file. Conversely, we should
expect the performance of (81)-(82) to be relatively poor
when the cache sizes are comparable and there are large
numbers of files. In this case, it may make more sense to use
something like the “opposite” memory inequality constraint:
a small-user subfile variable vlS1 ,j should be larger than any

AND

C ONCLUSIONS

The two primary goals of this paper are to advance a
certain optimization theoretic approach to coded caching
problems, and to use that framework to derive both specific
caching schemes and general insight for system models containing multiple heterogeneities that have yet to be considered
in the literature. An exponentially-scaling optimization problem corresponding to a caching scheme capable of handling
non-uniform file size, popularity, and cache size is developed.
It is shown that the original scheme of Maddah-Ali and
Niesen in [2], [3] is the optimal solution of that problem
for the special case of uniform file length, popularity, and
cache size.
Tractable problems are then developed to handle various
combinations of heterogeneous system parameters. The consideration of these special cases also permitted the observation of the effects that these non-uniformities have on the
optimal cache content. When considering non-uniform file
popularity and size jointly, it is shown that while popularity
may in general have some influence on the optimal cache
allocation, file size can be a much stronger influence; indeed,
very good performance is obtained in the case considered by
ignoring file popularity altogether. Finally, with the insights
obtained from the previously-explored special cases, we
developed a tractable optimization problem corresponding
to a caching scheme capable of accommodating all three of
the aforementioned heterogeneities, and showed numerically
that it performs well compared to the original exponentiallyscaling problem.
A PPENDIX
A. Proof of Lemma 2
We begin with the proof of the expression of Pr[Y0 = i],
for which we use induction on i for i = 1, . . . , N . We begin
first with the i = 1 case. Let Z ∈ [N ]K denote the sequence
of outcomes from the N trials, e.g. if for K = 3 and N
= 4, trial 1 obtains outcome 2, trial 2 obtains outcome 4,
and trial 3 obtains outcome 1, we have Z = [2, 4, 1]T . Let
Xn denote the random variable representing the number of
times the outcome n occurs in the K trials (i.e. the number of
times it appears in Z), and stack the Xn variables in a vector
X ∈ [K]N ; the example above would yield X = [1, 1, 0, 1]T .

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

15

Then the smallest element of Z is 1 (i.e. Y0 = 1) if and only
if X1 >= 1; in other words, since 1 is the smallest possible
outcome, if it occurs anywhere in Z then it is the smallest
element. Thus we have

obtain from (84), after some mild algebraic manipulation,
!K
PN
l=i pl
Pr[Y0 = i] = Pr[Y0 = i − 1] PN
l=i−1 pl
K
P
N
l=i−1 pl
Pr[Y0 = 1] = Pr[X1 ≥ 1] = 1 − Pr[X1 = 0]

K

P
!K
!K
K
PN
N
N
N
X
X
−
p
p
l=i−1 l
l=i l
= 1 − (1 − p1 )K =
−
,
pl
pl
P
K P
K
N
N
l=1
l=2
p
−
p
l
l
l=i
l=i+1
K
P
N
which is indeed the formula (26) with i = 1, as desired.
l=i pl
For an arbitrary i such that 2 ≤ i ≤ N − 1, we note that
K P
K
P
N
N
if the smallest element of Z is i, (i.e. Y0 = i), then there
−
l=i pl
l=i+1 pl
cannot be any values smaller than i, and there must be at
= Pr[Y0 = i − 1] 
K P
K .
PN
N
least one i in Z; in other words:
−
p
p
l=i−1 l
l=i l

(86)

Pr[Y0 = i] = Pr[Xi ≥ 1, Xi−1 = 0, . . . X1 = 0]

= Pr[X1 = 0]Pr[X2 = 0|X1 = 0] · · ·
Pr[Xi−1 = 0|Xi−2 = · · · = X1 = 0]
Pr[Xi ≥ 1|Xi−1 = · · · = X1 = 0]
= Pr[X1 = 0]Pr[X2 = 0|X1 = 0] · · ·

Now by the inductive hypothesis, Pr[Y0 = i − 1] is precisely
equal to the denominator of (86), and so we obtain
!K
!K
N
N
X
X
Pr[Y0 = i] =
−
,
(87)
pl
pl
l=i

Pr[Xi−1 = 0|Xi−2 = · · · = X1 = 0]
(1 − Pr[Xi = 0|Xi−1 = · · · = X1 = 0]) .
(83)
Now, comparing the expression (83) for Y0 = i to the same
expression with Y0 = i − 1, it is easy to show that
Pr[Y0 = i] = Pr[Y0 = i − 1]


Pr[Xi−1 = 0|Xi−2 = · · · = X1 = 0]
1 − Pr[Xi−1 = 0|Xi−2 = · · · = X1 = 0]
(1 − Pr[Xi = 0|Xi−1 = · · · = X1 = 0]) .
(84)

as desired.
Although the Pr[Y0 = N ] formula was covered in the
preceding paragraph, we discuss it in further detail here
because (26) above may not appear sensible in the i = N
case. Note that if N is the smallest value in the multinomial
vector Z, then it must be the case that every element of Z is
equal to N , otherwise some element not equal to N would
be the smallest value. Thus we have
Pr[Y0 = N ] =
=

Pr[XN = K, XN −1 = 0, . . . , X1 = 0]
pK
N

=

N
X

l=N

It is possible to compute these conditional probabilities
directly:
K

(j)
,
Pr[Xj = 0|Xj−1 = · · · = X1 = 0] = 1 − pj

(85)

Pr[Y1 = i] =

pj

= PN

l=j

−

N
X

l=N +1

pl

!K

,

N
X

Pr[Y1 = i, Y0 = j]

(88)

j=1

pl

is the probability of outcome j occurring in a trial conditioned on the knowledge that outcomes 1 through j − 1 have
(j)
not occurred in that trial. From the definition of pj , we can
rewrite (85) as

Pr[Xj = 0|Xj−1 = · · · = X1 = 0] =

pl

!K

which is the formula
P (26) with i = N , noting that we use
the definition that bl=a nl = 0 when a > b.
Next, we proceed to the m = 1 case. Here we will directly
compute Pr[Y1 = i] by first deriving Pr[Y1 = i, Y0 = j], and
then obtaining the desired quantity from the sum

where
(j)
pj

l=i+1

PN

l=j+1 pl
PN
l=j pl

!K

.

Evaluating this expression for j = i and j = i − 1, we can

Clearly the second smallest element of Z is no smaller than
the smallest element of Z, so there are two cases to consider:
i > j, and i = j. If i > j, we write
Pr[Y1 = i, Y0 = j]
= Pr[Xi ≥ 1, Xi−1 = 0, . . . , Xj = 1,
Xj−1 = · · · = X1 = 0]
= Pr[Xi−1 = 0, . . . , Xj = 1, Xj−1 = · · · = X1 = 0]
− Pr[Xi = 0, Xi−1 = 0, . . . , Xj = 1,
Xj−1 = · · · = X1 = 0]

(89)

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

16

To compute the difference (89), note that we can form a (K,
4) sequential vector of outcomes Z̃(m, n), indexed by two
integers m and n, from the original (K, N ) sequential vector
of outcomes Z in the following way: for a single trial, the first
outcome of Z̃(m, n) occurs if any of the first n−
outcomes
P1n−1
of Z occur, and so it has the probability p̃1 = l=1 pj ; the
second outcome of Z̃(m, n) occurs if the n-th outcome of
Z occurs, and so it has a probability of p̃2 = pn ; the third
outcome of Z̃(m, n) occurs if any outcomes of ZP
from n + 1
m
to m occurs, and so it has a probability of p̃3 = l=n+1 pl ;
and the fourth outcome of Z̃(m, n) occurs if any of the last
N −m
P outcomes of Z occur, and so it has a probability
p̃4 = N
l=m+1 pl . If we define X̃j as the number of times
outcome
occurred in Z̃(m, n), thenPwe consequently have
Pjn−1
m
X̃1 = l=1 Xl , X̃2 = Xn , X̃3 = l=n+1 Xl , and X̃4 =
PN
1
l=m+1 Xl . We can then rewrite (89) using vectors X̃(i, j)
and X̃(i − 1, j) as
Pr[Y1 = i, Y0 = j]

is not unique. This gives

Pr[Y1 = i, Y2 = i]
= (p̃4 )K − (p̃4 )K − K p̃2 (p̃4 )K−1
!K
!K
N
N
X
X
=
−
pl
− Kpi
pl
l=i

=

N
X

Pr[Y1 = i, Y0 = j]

i−1
X

Pr[Y1 = i, Y0 = j] + Pr[Y1 = i, Y0 = i] + 0

j=1

where the first term is computed with respect to X̃(i − 1, j),
and the second with respect to X̃(i, j). Using the probabilities
defined earlier, this gives

i−1
X
j=1

+





Pr[Y1 = i, Y0 = j]

= Kpj 

N
X
l=i

− K p̃2 (p̃4 )
!K−1

pl

−

N
X

l=i+1

(90)
pl

!K−1 


N
X

N
X
l=i

(91)
+K

pl

pl

!K

!K

N
X

−K

N
X

l=i+1

−

N
X

−K

N
X

l=i+1

− Pr[Xi = 1, Xi−1 = · · · = X1 = 0]
= Pr[X̃4 = K, X̃3 = X̃2 = X̃1 = 0]
− Pr[X̃4 = K, X̃3 = X̃2 = X̃1 = 0]
(92)

Here, the first term in (92) is computed with respect to X̃(i−
1, i − 2), the second with respect to X̃(i, i − 1), and the third
with respect to X̃(i, i−1), although this choice of X̃ variables
1 Note that the X̃ variables lose the (m, n) indices of the original variable
X̃(m, n). This is done for notational convenience, but will result in an abuse
of the notation when multiple X̃(m, n) are involved. We will therefore be
careful to indicate which X̃ variables belong to which X̃(m, n) vectors.

pl

l=i+1
N
X

pl



X
j=1

−

l=i+1

!K

!K

N
X

− Kpi

!K−1 

pl
N
X

pl

l=i+1

− Kpi

N
X

l=i+1



pl

!K−1

!K−1

pj 

!K−1  i−1 
X

pj 
pl
j=1

N
X
l=i

= Pr[Xi ≥ 2, Xi−1 = · · · = X1 = 0]
= Pr[Xi−1 = · · · = X1 = 0] − Pr[Xi = 0 = · · · = X1 = 0]

!K−1

l=i+1
!K−1  i−1

= Pr[Y0 = i] + K

Pr[Y1 = i, Y2 = i]

pl

l=i

−

pl

l=i

where, again, the terms in (90) are computed with respect to
X̃(i − 1, j), and X̃(i, j) respectively.
Similar reasoning yields the value of the joint probability
when i = j:

− Pr[X̃4 = K − 1, X̃3 = 1, X̃2 = X̃1 = 0].

=

N
X

Kpj 

l=i

= K p̃2 (p̃4 )


(93)

j=1

=

K−1

.

Pr[Y1 = i]

− Pr[X̃4 = K − 1, X̃3 = 0, X̃2 = 1, X̃1 = 0]

K−1

pl

l=i+1

!K−1

We can now evaluate (88) as

=

= Pr[X̃4 = K − 1, X̃3 = 0, X̃2 = 1, X̃1 = 0]

l=i+1

N
X

!K−1  i−1 
X

pj 
pl
j=1


!K−1  i
X

pj  ,
pl

(94)

j=1

which is the desired formula. Note that, although we refer
to Pr[Y0 = i] in the formula for Pr[Y1 = i], this is only for
notational simplicity; we do not wish to suggest some sort
of interpretation relating the two quantities in this way.
Finally, we must compute Pr[Ym = i] for m = 2, . . . , K −
1. We take an approach similar to the Pr[Y1 = i] case, and
derive Pr[Ym = i] using the joint probabilities Pr[Ym =
i, Ym−1 = j]. As before, there are two cases, i > j, and
i = j, as the m-th smallest element of Z cannot be smaller
than the (m−1)-th element of Z, and so Pr[Ym = i, Ym−1 =
j] = 0 if i < j.

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

17

In the case where i > j, we have
Pr[Ym = i, Ym−1 = j]
m
X
Pr[Xi ≥ 1, Xi−1 = · · · = Xj+1 = 0,
=
k=1

Xj = k, Xj−1 + · · · + X1 = m − k]
m
X
Pr[Xi−1 = · · · = Xj+1 = 0, Xj = k,
=
k=1

Xj−1 + · · · + X1 = 0] − Pr[Xi = · · · = Xj+1 = 0,
Xj = k, Xj−1 + · · · + X1 = m − k]

= (Pr[Xi−1 = · · · = Xj+1 = 0, Xj + · · · + X1 = m]
− Pr[Xi−1 = · · · = Xj = 0, Xj−1 + · · · + X1 = m])
− (Pr[Xi = · · · = Xj+1 = 0, Xj + · · · + X1 = m]
− Pr[Xi = · · · = Xj = 0, Xj−1 + · · · + X1 = m]) .
(95)
Now we recast the four terms of (95) in terms of X̃(i−1, j +
1), X̃(i − 1, j), X̃(i, j + 1), and X̃(i, j) respectively:
Pr[Ym = i, Ym−1 = j]

= Pr[X̃4 = K − m, X̃3 = 0, X̃2 = 0, X̃1 = m]

− Pr[X̃4 = K − m, X̃3 = 0, X̃2 = 0, X̃1 = m]

− Pr[X̃4 = K − m, X̃3 = 0, X̃2 = 0, X̃1 = m]

− Pr[X̃4 = K − m, X̃3 = 0, X̃2 = 0, X̃1 = m] .




K
K
K−j
j
=
(p̃4 )
(p̃1 ) +
(p̃4 )K−j (p̃1 )j
K −m
K −m




K
K
+
(p̃4 )K−j (p̃1 )j +
(p̃4 )K−j (p̃1 )j
K −m
K −m

!K−m
!m


j
N
X
X
K

=
pl
pl
K −m
l=i

N
X

−

pl

l=i

N
X

−

l=i+1

+

N
X

l=i+1

=

!K−m

pl

j−1
X

pl

l=1

!K−m

pl

l=1

!K−m

j
X
l=1

j−1
X
l=1

!m

pl


!K−m

N
X
K

−
pl
K −m
l=i
!m
!m !
j
j−1
X
X
−
.
pl
pl



l=1

Pr[Ym = i, Ym−1 = i 6= 1]
=

K−2
X min{m−1,K−2−k}
X
k=0 b=max{0,m−1−k}

Pr[Xi = 2 + k, Xi−1 + · · · + X1 = b]
=

K−2
X min{m−1,K−2−k}
X
k=0 b=max{0,m−1−k}

!m

!m 

pl

We know that Ym = i and Ym−1 = i, but that leaves k Y
variables “adjacent” to Ym and Ym−1 that must also have a
value of i. Let nl denote the number of variables Ym′ that are
equal to i and have m′ > m, and ns denote the number of
variables Ym′ that are equal to i and have m′ < m − 1. Then
nl +ns = k and the following must be true: there are at most
K −1−m variables Ym′ with m′ > m, because there are only
K − 1 total Ym′ variables, and so nl ≤ K − 1 − m; moreover
there are only m − 2 variables Ym′ with m′ < m − 1, and so
ns ≤ m − 2. We will use these inequalities to place bounds
on b as a function of k.
We first consider an upper bound on b. We have already
seen that b ≤ m − 1 in general, but the inequality on nl
induces a second upper bound on b that is sometimes stricter
than the first. Note that b = m−1 only if Ym−1 is the first Ym′
variable with the value i; if Xi = 2 + k, then we must have
nl = k, and therefore k ≤ K −1−m. Thus if k > K −1−m,
then b < m − 1, where the maximum possible b decreases by
one every time k increases by one. Indeed, the upper limit on
b is imposed by (m−1)−(k −(K −1−m)) = K −k −2; the
general upper limit on be is then b ≤ min{m−1, K −k −2}.
The lower limit on b is obtained through similar reasoning,
but we first note that the trivial lower limit on b is 0, which
occurs when the number i constitutes (at least) the first m
smallest values of Z; in this case k ≥ m − 1. If k < m − 1,
then not all Ym′ with m′ < m can have values of i. In
general, k + 2 + b ≥ m+ 1, which implies that b ≥ m− 1 − k.
Then general lower bound on b is therefore b ≥ max{0, m −
1 − k}.
We are therefore now in a position to write

Pr[X̃4 = K − k − 2 − b, X̃3 = 0, X̃2 = 2 + k, X̃1 = b]
(97)
where the X̃ variables in (97) are with reference to X̃(i, i).
This can be computed as
N
X

l=i+1

pl

!K−j 

(96)

l=1

In the case where i = j, there are two sub-cases to
consider: i = j 6= 1 and i = j = 1. In the former sub-case,
we must have Xi ≥ 2, and Xi−1 + · · · + X1 = b ≤ m − 1.
Suppose that Xi = 2+k for some integer k ∈ {0, . . . , K−2}.

Pr[X̃4 = K − k − 2 − b, X̃3 = 0, X̃2 = 2 + k, X̃1 = b]


K
=
(p̃4 )K−k−2 (p̃2 )2+k (p̃1 )b
K − k − 2 − b, b, 2 + k


K
=
K − k − 2 − b, b, 2 + k
!b
!K−k−2−b
i−1
N
X
X
(98)
pl
(pi )2+k
pl
l=i+1

l=1

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

When i = j = 1, we simply have

of size j + 1, and in the outer summation, we sum over all
j from 0 to K − 1, giving
X
(dk )
|}
max{|WS\{k}

Pr[Ym = 1, Ym−1 = 1]
= Pr[X1 ≥ m + 1]
=
=

K−1−m
X

S∈P(U )\∅

Pr[X1 = j + 1 + k]

K
(p1 )m+1+k (1 − p1 )K−m−1−k
m+1+k
(99)

k=0

Pr[Ym = i, Ym−1 = j]

j=1

i−1
X

Pr[Y − m = i, Y − m − 1 = j]

j=1

+ Pr[Ym = i, Ym−1 = i]

!K−m
!K−m 


N
N
X
X
K


=
−
pl
pl
K −m
l=i
l=i

!m
!m 
j
j−1
i−1
X X
X


−
pl
pl
j=1

l=1

l=1

+ Pr[Ym = i, Ym−1 = i]

!K−m
!K−m 


N
N
X
X
K


=
−
pl
pl
K −m
l=i
l=i+1
!m !
i−1
X
+ Pr[Ym = i, Ym−1 = i]
(100)
pl
l=1

Combing (100) with (98) and (100) yields the desired
result. This completes the proof.

We wish to show that


X
(dk )
|}
max{|WS\{k}
E
S∈P(U )\∅

k∈S

K−1
N 
X K−1
XX
j=1 i=0 l=1

+


K −1−i
Pr[Yi = l]vl,j
j

K−1
N
XX

Pr[YK−i−1 = l]vl,0

(d )

k
|} (102)
max{|WS\{k}

j=0 S∈P(U )\∅:|S|=j+1

k∈S

Replacing the |WS | variables with the appropriate vl,j
variables, (102) becomes
X

max{vdk ,j }.
k∈S

(103)

For a fixed j ≥ 1, we note that we send one transmission to
K
each of the j+1
subsets of size j + 1. For a fixed d, let
ki denote the user requesting the i-th most popular file, i.e.
the file i-th smallest index. Then k1 has requested the most
popular file, and so by the memory inequality (35), vdk1 ,j is
the largest variable for any transmission to a subset
 of which
k1 is a member. Since k1 is a member of K−1
subsets of
j
size j+1 that contain k1 as a member, the inner summation of
(103) will have K−1
terms with the value vdk1 ,j . Similarly,
j
user k2 has requested the second most popular file, and so
vdk2 ,j will be the largest subfile for all subsets that contain

k2 but don’t contain k1 . This constitutes K−2
subsets of
j
size j + 1.
This reasoning can be extended until all subsets are
characterized in terms of their maximum vl,j variable. User
ki requests the i-th most popular file, and so vdki ,j will
be the largest element sent in any subset containing ki but
not containing k1 , k2 , . . . , ki−1 . Since there are K − i users
who are not users k1 , . . ., ki , and user ki is already in
the subset, there are K−i
subsets that contain ki but not
j
k1 , k2 , . . . , ki−1 . We can therefore eliminate the max{} term
from the inner sum of (103) to obtain, for j = 1, . . . , K − 1,

K 
X
K −i
vdki ,j .
(104)
j
i=1
As noted earlier, the memory inequality reverses for j = 0,
so the least popular files take up the most memory in that
case; the reasoning is the same as in the above, but we instead
obtain

K
K 
X
X
K −i
(105)
vdkK+1−i ,0 ,
vdkK+1−i ,0 =
0
i=1
i=1

B. Proof of Proposition 1

=

X

j=0 S∈P(U )\∅:|S|=j+1

Pr[Ym = i]

=

K−1
X

K−1
X

Finally, we compute Pr[Ym = i] as

=

k∈S

=

k=0
K−1−m
X 

N
X

18

(101)

i=0 l=1

if the memory inequality condition holds for the vl,j variables. We begin with an examination of the left hand side of
the equation. Inside the expectation, we sum over all subsets
S of the set of users U. This can be rewritten as a double
summation: in the inner summation, we sum over all subsets

All that remains is to compute the expectation of these
terms with respect to the demand vectors. Using the linearity
of expectation and the results of (102)-(105), the left hand
side of (101) reduces to

K
K 
K−1
X
XX
K −i
E[vdkK+1−i ,0 ] (106)
E[vdki ,j ] +
j
i=1
j=1 i=1

To compute the expected value of the vdki ,j variables
(j = 1, . . . , K − 1), we note that it has N possible values,
v1,j , v2,j , . . . , vN,j , and the probability of each outcome can

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

be obtained from Lemma 2 in the following way. We have
vdki ,j = vl,j if l is the i-th most popular file in the request
vector d; since the files are labelled in terms of decreasing
order of popularity, the i-th most popular file requested
is represented by the i-th smallest index in d. Thus the
probability that dki = l is equivalent to the probability that l
is the i-th smallest index in d, and so by Lemma 2, we have
N
X

E[vdki ,j ] =

l=1
N
X

=

Pr[dki = l]vl,j
Pr[Yi−1 = l]vl,j .

(107)

l=1

For j = 0, the size ordering is reversed, so we are concerned
with the largest indices of d. However, as has been noted
already, the i-th largest index of d must necessarily be the
K + 1 − i-th smallest index of d, which gives
E[vdkK+1−i ,0 ] =
=

N
X

l=1
N
X

Pr[dkK+1−i = l]vl,0
Pr[YK−i = l]vl,0 .

(108)

l=1

Combing (107)-(108), we see that (106) is equal to
 N
K −i X
Pr[Yi−1 = l]vl,j
j

K−1
K 
XX
j=1 i=1

l=1

+

K X
N
X

Pr[YK−i = l]vl,0 . (109)

i=1 l=1

We complete the proof through a cosmetic change of variables i′ = i − 1 to obtain the desired expression on the
right-hand side of (101).
C. Proof of Proposition 3
We follow reasoning similar to what we have already seen
in the previous proof, where users are divided into subsets
that require the same amount of data to be sent to them,
and then count how many such subsets there are. For this
proof, however, we instead divide the various subsets into
subsets containing only small-cache users, subsets containing
only large-cache users, and subsets containing both large- and
small-cache users.
But first, we note that since the files are all the same size
and length, the transmission length will be independent of
the request vector d, and so we have


X
(d )
max{|W k |}
E
S∈P(U )\∅

k∈S

S\{k}

=

X

S∈P(U )\∅

(d )

k
|}. (110)
max{|WS\{k}

k∈S

As discussed above, the sum in the above expression is
over all S ∈ P(U) \ ∅, which we can separate into small,

19

large, and
subset
size of j + 1, there
 mixed sets. For a fixed

KS
KL
are j+1
sets of small users, j+1
sets of large users, and

j 
X
KS
i=1

i


KL
j +1−i

(111)

groups of at least one small user and at least one large user.
For a set of j + 1 small users, every subfile in a single
coded transmission is cached by j small users, and so has
the size vj,S . Similarly, for any set of j + 1 large users, the
transmission has the size vj,L .
For the mixed subset case, we must consider three cases.
First, when there are at least 2 small users and 2 large users
in the subset of j + 1 users, then since every subfile sent
is cached on j of the j + 1 users, there must be at least
1 small user and 1 large users among those j users, and
so every subfile must be of size vj,M . However, if there is
only one small user in the subset of j + 1 users, then the
subfile requested by the small user will have been stored on
the caches of j large users, and so will have size vj,L . The
length of the entire transmission will therefore also be of size
vj,L . The third case occurs when there is only one large users
in the subset of j + 1 users. Then the subfile requested by
the large user will be store on the caches of j small user and
so will be of size vj,S , while every other subfile is cached
on a mixed set of j users and so will be of size vj,M ; the
2
entire transmission will therefore
 be of length vj,M .
KL
So, in addition to the j+1 transmissions of size vj,L
sent for groups
consisting of entirely large users,

 entirely
there are K1S KjL transmissions of the same size for those
mixed subsets with only one small user. The total number
of transmissions of size vj,M can then be simplified using
Lemma 1 as


j 
X
KL
KS
j+1−i
i
i=2

 


j+1
X
KS
KL
KS
−
=
j+1
j+1−i
i
i=0

   
KL
KL
KS
−
−
j+1
j
1


 
K
KS
=
−
j+1
j+1

   
KL
KL
KS
(112)
−
−
j+1
j
1
Altogether, (110) reduces to
K−1
X
j=0




K
Ks
(vj,S − vj,M ) +
vj,M
j+1
j+1
   

KL
KS
KL
(vj,L − vj,M ),
+
+
j
1
j+1

which is what we aimed to show. We make a special note
that the formula is indeed sensible for j = 0: the j = 0 term
2 In the case where a subset of size 2 contains one large user and one
small user, obviously the entire transmission is of length v1,L .

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING


reduces to K
1 v0,M = Kv0 , as needed for the individual
transmissions to the K users.
D. Proof of Proposition 4
We derive the terms of (80) in the order that they appear.
In general, we do this using the following steps. First, we
identify a certain group of subsets that have similar user
composition; then for that group, we determine the number
of transmissions that the largest subfile will be in, the number
of transmissions that the second largest subfile will be in, and
so on. Finally, we compute the expected size of the maximum
subfile, the second largest subfile, and so on. This approach
will be familiar from previous proofs, but we nevertheless
repeat it here due to the complexity of (80).
The groups of subsets that the seven terms of (80) correspond to are, in order: subsets of size one, subsets of size
greater than one containing only large users, subsets of size
greater than one containing only small users, mixed subsets
containing more than one user but only one small user,
mixed subsets containing only one large user but more than
one small user, subsets containing greater than or equal to
max{KS , KL } + 2 users, and subsets containing at least two
small and two large users that are less than max{KS , KL }+2
users. We label these sets of subsets S1 , . . . , S7 respectively.
The following lemma shows these sets form a partition (in
the loose sense of the word discussed earlier) of P(U) \ ∅,
and so the sum over all S ∈ P(U) \ ∅ at the beginning of
(80) can equivalently be done over all subsets in S1 , then
all subsets in S2 , and so on, so that all subsets of users in
P(U) \ ∅ will have been accounted for precisely once.
Lemma 3. For the sets S1 , . . . , S7 described above,
P(U) \ ∅ =

7
[

Si ,

(113)

20

S ⊆ P(U)\∅ thus falls into one and only one set Si , proving
the lemma.
We remark before continuing that, given the specific values
of KS , KL , some of the above subsets may be empty. As per
the notation adopted in this paper, a sum over an empty set
is identically zero, and so this will not affect our subsequent
calculations. In terms of the expressions
below, this will

correspond to binomial coefficients nk with
 n < 0 or k > n,
both of which, by our notation, gives nk = 0.
So per the above discussion, we can change the summation
over all subsets of P(U) \ ∅ into seven summations over one
of the Si each:


E

X

S∈P(U )\∅



(dk )
|}
max{|WS\{k}
k∈S

=

7 X
X

E

i=1 S∈Si



(dk )
|}
max{|WS\{k}
k∈S



(114)

This allows us to analyze each subset of subsets separately.
We begin with the analysis of S1 , i.e. to broadcasts of
individual users. Since each transmission is to only one
person, we get
X

S∈S1

E



(d )
max{|W∅ k |}
k∈S



=

K
X

k=1

K
i X
h
(d )
E [vdk ,0 ]
E |W∅ k | =
k=1

The above sum is over all users from k = 1 to k = K, i.e. in
lexicographic order. But we can instead sum over all users by
adding the user requesting the largest subfile, then the user
requesting the second largest subfile, and so on. Using the
index i to indicate the user requesting the (i + 1)-th largest
subfile, we can write the expectation E[vdk ,0 ] in terms of the
random variable Yi as defined in Lemma 2 to obtain

i=1

and the Si are mutually disjoint.
S
Proof: That 7i=1 Si ⊆ P(U) \ ∅ is trivial: for any i, any
set in Si is a non-empty subset of users, and so S
must be
7
contained in P(U) \ ∅. To show that P(U) \ ∅ ⊆ i=1 Si ,
consider the number of users in an arbitrary subset of users
S ∈ P(U) \ ∅: if it is one, then S ⊆ S1 and if it is greater
than or equal to max{KS , KL } + 2, then it must be mixed
because there are not enough of any one type of user to
comprise the entire group, and so is must be that S ⊆ S6 .
Otherwise, suppose 1 < |S| < max{KS , KL } + 1, consider
the number of small users, kS , in S. If kS = 0, then S is
contains only large users, and so S ⊆ S2 . If kS = 1, then
we have S ⊆ S4 . If 1 < kS < |S|, then either the number of
large users is either one, or more than one; if it is one, then
S ⊆ S5 , while if it is more than one, then S ⊆ S7 . Finally, if
kS = |S|, there are only S
small users, and so S ⊆ S3 , proving
7
that indeed P(U) \ ∅ ⊆ i=1 Si . The mutual disjointedness
is obvious once it is noted that a subset containing only one
large/small user or no large/small users cannot exceed a size
of max{KS , KL } or max{KS , KL } + 1 respectively. Each

K
X

k=1

E [vdk ,0 ] =

K−1
X
i=0

N
XX

 K−1
Pr[Yi = l]vl,0 ,
E vfd (i+1),0 =
i=0 l=1

(115)

M
as per
which is the first term of (80), with vl,0 = vl,0
constraint (64). Here, fd (i) denotes the index of the i-th
largest file in the request vector d (recall that f (i) was used
earlier to denote the i-th largest file in the set of all files).
We next consider S2 , the set of user subsets with more
than one user containing only large-cache users. There are
KL
user subsets of size j + 1 in S2 , for j values ranging
j
from 1 to KL −1; we cannot have a subset of only large users
that contains more members than there are large users. Since
there are only large users in these subsets, the subfiles sent
will stored on j large users caches, and so only subfiles of
L
are sent. As we saw in earlier proofs, the largest
size vj,l
subfile requested (i.e. corresponding to the file with the
smallest index), will be sent to KLj−1 subsets, the second

largest subfile is the largest subfile for KLj−2 subsets, and

in general, the i-th largest subfile sent will be sent in KLj−i

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

We use fdS (i) to denote the index of the i-th largest file
requested by a small-user. Consequently, the second sum in
(118) is over all small cache users, in decreasing order of
the file size they requested. This allows us to compute the
expectation in (118) using the YiS variables in the following
way:

X 
(dk )
|}
E max{|WS\{k}

subsets, giving

X 
(dk )
E max{|WS\{k} |}
k∈S

S∈S2

KL 
KX
L −1 X

 h
i
KL − i
E vfLL (i),j
d
j
j=1 i=1
 N
KL 
KX
L −1 X
KL − i X
L
L
Pr[Yi−1
= l]vl,j
=
j
j=1 i=1
l=1

KX
−1
N
L −1 K
L
X X KL − i + 1
L
,
=
Pr[YiL = l]vl,j
j
j=1
i=0

=

21

S∈S4

=

(116)

S∈S3

=

k∈S

KX
N 
S −1 X
S −1 K
X
j=1

i=0

l=1


KS − i + 1
S
Pr[YiS = l]vl,j
j

(117)

which is the third term of (80). Here, Pr[YiS = l] is the
probability that file l is the i + 1-th largest file requested
among all small users. This can also be computed using
Lemma 2, but with N outcomes and KS trials.
Next, we consider S4 , the set of mixed subsets containing
more than one user but only one small user. We saw in the
non-uniform cache memory case that the coded transmissions
to these kinds of groups will consist almost entirely of
M
subfiles whose size is described by mixed variables vl,j
,
because the subfiles are stored on a mixed subset of users’
caches, save for one subfile whose size is described by a
L
large variable vl,j
, because that subfile is stored only on large
user caches. Due the memory inequality constraints (77)-(79)
that prioritize cache size over file size, the one large variable
(corresponding to the file requested by the one small user)
will necessarily be the maximum value.
The size of the transmissions sent to these kinds of subsets
will therefore depend on what files are requested by the
small-cache users. Each small cache user will be in KjL
many of these subsets for a subset size of j + 1, where j
takes values from 1 to KL ; if j was any larger, there would
have to be more than one small user. We therefore have
 h
 X
KS 
KL X
i
X 
KL
(dk )
E vfLS (i),j
|} =
E max{|WS\{k}
d
k∈S
j
j=1 i=1
S∈S4

(118)

 N
KS 
KL X
X
KL X
j=1 i=1

l=1

where the last line is obtained by rearranging the terms and
using a minor change of variable for the index of summation
i. This is the second term of (80). Here we use fdL (i) to
refer to the i-th largest file requested within the set of large
users, and by Pr[YiL = l], we mean the probability that file
l is the i + 1th largest file requested within the set of large
users. We can compute Pr[YiL = l] using Lemma 2 with N
files (outcomes) and KL users (trials). The change from the
second to third lines above then follows immediately from
the definition of expectation (see Appendix B).
Using identical reasoning for S3 , the set of user subsets of
size greater than 1 with only small users, we can obtain

X 
(dk )
E max{|WS\{k} |}

k∈S

=

j

l=1

KL KX
N 
S −1 X
X
j=1 i=0

l=1

S
L
Pr[Yi−1
= l]vl,j


KL
L
Pr[YiS = l]vl,j
.
j

(119)

The final step is once again attained with a rearranging of
terms and a change of variable for the i index of summation.
This gives the fourth term in (80).
The fifth term is obtained using similar reasoning. This
term corresponds to S5 , the set of mixed user subsets containing exactly one large user and more than one small user.
Here, the transmitted subfiles will all be stored on the caches
of a mixed subset of users, except for the subfile requested
by the large user, which will be stored on the caches of
every other user in the subset, i.e. all small users. The large
user’s requested subfile will have a size described by a small
S
, and so due to the memory inequality constraints
variable vl,j
(77)-(79), will never be the largest subfile transmitted; once
again, it is the small-cache user requests that determine the
largest subfile. The largest subfile
 KL requested by a small user
S −1
will be transmitted to Kj−1
subsets of size j + 1; the
1
second largest subfile requested among small users will be the
largest subfile transmitted when the largest subfile requested
is not also being transmitted
to that subset, and so will be
 KL 
S −2
transmitted Kj−1
times.
In general, the i-th largest
1
subfile requested among small users will be transmitted only
when the previous i − 1 largest subfiles
 Kare
 not also being
S −i
L
transmitted, and so will be sent Kj−1
times.
1
There are subsets of size 3 through KS + 1 in S5 , so
indexing subset size with j + 1 yields

X 
(dk )
|}
E max{|WS\{k}
S∈S5

k∈S

 
KS KX
S −1 
X
KS − i KL
E[vfMS (i),j ]
=
d
1
j
−
1
j=2 i=1
!

  X
KS KX
N
S −1
X
KS − i KL
S
M
Pr[Yi−1
= l]vl,j
=
1
j
−
1
j=2 i=1
l=1
 
KS KX
N 
S −2 X
X
KS − 1 − i KL
M
Pr[YiS = l]vl,j
.
=
1
j
−
1
j=2 i=0
l=1

(120)

The last line is once again obtained through rearranging terms
and doing a change of variables for the index of summation
i. This is the fifth term of (80).

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

The sixth term of (80) contains the terms for S6 , the set of
user subsets with more than max{KS , KL } + 1 users. These
subsets are precisely large enough that they are all mixed
and have at least two of each user type in them. Thus only
subfiles stored on the caches of mixed subsets of users will be
sent, and so they will have a size given by a mixed variable
M
vl,j
. The only factor that determines the largest subfile for
a given subset will therefore be the file index. There are no
restrictions on subset composition, and so we find ourselves
in a familiar situation: the largest
 subfile requested will be
the largest file sent for K−1
subsets, the second largest
j

subfile requested will be the largest subfile sent for K−2
j
subsets, and so on, such that
 the i-th largest subfile is the
largest subfile sent for K−i
subsets. This gives
j

X 
(dk )
|}
E max{|WS\{k}
S∈S6

=

k∈S

K−1
X

j=max{KS ,KL }+1

=

K−1
X

 h
K 
i
X
K −1−i
E vfMd (i),j
j
i=1
K−1
X

j=max{KS ,KL }+1 i=0


K −1−i
M
Pr[Yi = l]vl,j
,
j

22

for S7 demands it.
S7
The Rd,j
(n) quantity can be further decomposed: the
number of bits sent in this case is equal to the product of
the number of transmission sent in this case, denoted by
T (n), and the number of bits transmitted per transmission,
M
which is given buy the appropriate vl,j
variable. We can then
compute the S7 term of (80) using conditional expectation
in the following way:



max{KS ,KL } K
X 
X
X
(d )
E max{|W k |} = E 
RS7 (n)
d,j

n=1

j=3

=

max{KS ,KL } K
X
X
j=3

n=1

h
i
S7
E Rd,j
(n)

(122)

For a fixed j value, we compute the expectation conditional
on the fact that the n-th largest file is file l, i.e. Yn−1 = l:
K
X

n=1

=

(121)

the sixth term of (80).
The seventh and final term of (80) is by far the most
complicated term. It corresponds to S7 , the set of subsets
with at least two large-cache and two small-cache users, but
less than max{KS , KL } + 2 users. Here, every subfile sent
will be stored on the caches of a mixed subset of users and so
M
. The difficulty
will have a size given by a mixed variable vl,j
arises when we try to characterize the number of transmissions for each of the largest subfile requested, second largest
subfile requested, and so on - these numbers are dependent
on whether the file was requested by a large user or by a
small user. An example will illustrate this fact: consider the
third largest file requested among all users and transmissions
to subsets of 5 users. If a large-cache user has requested
the largest subfile, and another large-cache user requests
the second largest subfile, then the number of transmissions
where the thirdPlargest subfile
requested
is the largest subfile
 K

2
S
transmitted is n=1 KLn−3 4−n
if the subfile is requested


P3
KL −2 KS −1
if it is
by a large-cache user, and
n=2
n
4−n
requested by a small-cache user. These two number are
clearly not equal in general, and so the cache size of the
user making the request matters.
Nevertheless, it is possible to compute the expected rate
with a number of terms that scales as a polynomial function
Si
of N and K. To this end, let Rd,j
(n) denote the number of
bits sent to subsets in Si of size j + 1 as part of the transmissions required to satisfy the request d, when the n-th largest
file in d is the largest subfile transmitted
in P
that subset. By
P7 PK−1
K
Si
this definition, we have Rd = i=1 j=0
n=1 Rd,j (n).
These values have been implicitly computed for S1 through
S6 earlier in this appendix; we only introduce this opaque
notation now because the complexity of the accounting done

S\{k}

k∈S

S∈S7

=
=

h
i
S7
E Rd,j
(n)

K X
N
X

n=1 l=1
K X
N
X
n=1 l=1
K X
N
X

h
i
S7
E Rd,j
(n)|Yn−1 = l Pr[Yn−1 = l]
h
i
E vfMd (n),j T (n)|Yn−1 = l Pr[Yn−1 = l]
M
vl,j
E [T (n)|Yn−1 = l] Pr[Yn−1 = l].

(123)

n=1 l=1

The last line (123) is obtained because, given that Yn−1 =
l, it follows immediately that fd (n) = l, and so we have
M
, which is no longer a random quantity.
vfMd (n),j = vl,j
Comparing (123) to the form of (80) in the statement
of the proposition, we see that all that remains is to
show that E [T (n)|Yn−1 = l] = ν(n, j). First, we note
that E [T (n)|Yn−1 = l] = E [T (n)], since the number of
transmissions in which the n-th largest subfile requested is
the largest subfile sent to the subset depends only on the index
n but not the identity of the n-th largest subfile. Next, letting
S(n) denote the number of small users in the set of users
who requested the n − 1 largest files we further decompose
the expectation using conditional expectation:
E [T (n)] =

n−1
X

E [T (n)|S(n) = m] Pr[S(n) = m]. (124)

m=0

And further, if DS (n) = 1 represents the event that a
small user requested the n-th largest file and DS (n) = 0
representing the event that a large user did it, we have
E [T (n)] =
=

n−1
X

E [T (n)|S(n) = m] Pr[S(n) = m]

m=0
n−1
1
XX

E [T (n)|S(n) = m, DS (n) = r]

m=0 r=0

Pr[DS (n) = r|S(n) = m]Pr[S(n) = m] (125)

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

Now with (123)-(125), we have finally expressed the original
expectation in (122) in terms of quantities that can be
computed directly.
We begin with Pr[S(n) = m], the probability that there are
m small-cache users in the set of users who have the n − 1
largest files among all files requested. Since all users have the
same preferences, these probabilities are simply determined
by the relative numbers of large and small users. Indeed S(n)
has a hypergeometric distribution: the probability that m of
the n − 1 largest files requested are requested by small users
(and thus n − 1 − m of these files are requested by large
users) is given by
 KL 
KS
Pr[S(n) = m] =

m

n−1−m

K
n−1

.

(126)

Next we consider Pr[DS (n) = r|S(n) = m], which is
obtained with similar reasoning. Once again, since the large
and small users have the same preferences, only their relative
numbers will determine the probabilities. Since n − 1 users
have already been accounted for, there are K − (n − 1) users
left to choose from, and if m of them are small users, there
are KS − m small users left and KL − (n − 1 − m) large
users left. This gives
KS − m
K −n+1

(127)

KL − n + 1 + m
K −n+1

(128)

Pr[DS (n) = 1|S(n) = m] =
and
Pr[DS (n) = 0|S(n) = m] =

Finally, we compute E [T (n)|S(n) = m, DS (n) = r]; the
number of transmissions T (n) is deterministic given the
values of S(n) and DS (n), so no probabilities will be
involved in the calculation. First, if r = 1, i.e. a small user has
the n-th largest file request. In this case, the corresponding
subfile is the largest subfile transmitted for any transmission
to a subset with at least one other small user and two large
users, but not the users responsible for the n − 1 larger
requested files. This number is obtained as
E [T (n)|S(n) = m, DS (n) = 1]


j−2 
X
KS − m − 1 KL − n + 1 + m
=
(129)
i
j−i
i=1
for a subset size of j + 1. The equivalent number for r = 0,
i.e. a large user has the n-th largest file request, is
E [T (n)|S(n) = m, DS (n) = 0]


j−1 
X
KS − m KL − n + m
. (130)
=
i
j−i
i=2
Substituting the expressions in (126)-(130) into the appropriate places in (123) - (125) yields the desired term, i.e. the
seventh and final term of (80), which concludes the proof.

23

R EFERENCES
[1] F. Boccardi, R. W. Heath, A. Lozano, T. L. Marzetta, and P. Popovski,
“Five disruptive technology directions for 5G,” IEEE Commun. Mag.,
vol. 52, no. 2, pp. 74–80, February 2014.
[2] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,”
in IEEE Int. Symp. Inf. Theory, July 2013, pp. 1077–1081.
[3] ——, “Fundamental limits of caching,” IEEE Trans. Inf. Theory,
vol. 60, no. 5, pp. 2856–2867, May 2014.
[4] ——, “Decentralized coded caching attains order-optimal memory-rate
tradeoff,” IEEE/ACM Trans. Netw., vol. 23, no. 4, pp. 1029–1040, Aug
2015.
[5] U. Niesen and M. A. Maddah-Ali, “Coded caching with nonuniform
demands,” in IEEE Conf. Computer Commun. Workshops, April 2014,
pp. 221–226.
[6] ——, “Coded caching with nonuniform demands,” IEEE Trans. Inf.
Theory, vol. 63, no. 2, pp. 1146–1158, Feb 2017.
[7] M. Ji, A. M. Tulino, J. Llorca, and G. Caire, “Order-optimal rate of
caching and coded multicasting with random demands,” IEEE Trans.
Inf. Theory, vol. 63, no. 6, pp. 3923–3949, 2017.
[8] ——, “On the average performance of caching and coded multicasting
with random demands,” in 11th Int. Symp. Wireless Commun. Systems,
Aug 2014, pp. 922–926.
[9] A. S. Cacciapuoti, M. Caleffi, M. Ji, J. Llorca, and A. M.
Tulino. (2016, May) Speeding up Future Video Distribution via
Channel-Aware Caching-Aided Coded Multicast. [Online]. Available:
https://arxiv.org/abs/1605.05026.
[10] P. Hassanzadeh, A. Tulino, J. Llorca, and E. Erkip. (2016, Sep.)
Correlation-Aware Distributed Caching and Coded Delivery. [Online].
Available: https://arxiv.org/abs/1609.05836.
[11] ——. (2016, Sep.) Cache-Aided Coded Multicast for Correlated
Sources. [Online]. Available: https://arxiv.org/abs/1609.05831.
[12] J. Hachem, N. Karamchandani, and S. Diggavi, “Content caching
and delivery over heterogeneous wireless networks,” in IEEE Conf.
Computer Commun., April 2015, pp. 756–764.
[13] J. Hachem, N. Karamchandani, and S. N. Diggavi, “Coded caching for
multi-level popularity and access,” IEEE Trans. Inf. Theory, vol. 63,
no. 5, pp. 3108–3141, May 2017.
[14] J. Hachem, N. Karamchandani, and S. Diggavi, “Multi-level coded
caching,” in IEEE Int. Symp. Inf. Theory, June 2014, pp. 56–60.
[15] ——, “Effect of number of users in multi-level coded caching,” in
IEEE Int. Symp. Inf. Theory, June 2015, pp. 1701–1705.
[16] J. Zhang, X. Lin, and X. Wang, “Coded caching under arbitrary
popularity distributions,” in Inf. Theory and Applications Workshop,
Feb 2015, pp. 98–107.
[17] S. Jin, Y. Cui, H. Liu, and G. Caire. (2017, Jul.) Structural properties of uncoded placement optimization for coded delivery. [Online].
Available: https://arxiv.org/abs/1707.07146.
[18] J. Zhang, X. Lin, C. C. Wang, and X. Wang, “Coded caching for files
with distinct file sizes,” in IEEE Int. Symp. Inf. Theory, June 2015, pp.
1686–1690.
[19] C. Li, “On rate region of caching problems with non-uniform file and
cache sizes,” IEEE Commun. Letters, vol. 21, no. 2, pp. 238–241, Feb
2017.
[20] A. Sengupta, R. Tandon, and T. C. Clancy, “Improved approximation
of storage-rate tradeoff for caching via new outer bounds,” in IEEE
Int. Symp. Inf. Theory, June 2015, pp. 1691–1695.
[21] A. Sengupta and R. Tandon, “Improved approximation of storage-rate
tradeoff for caching with multiple demands,” IEEE Trans. Commun.,
vol. 65, no. 5, pp. 1940–1955, May 2017.
[22] M. Ji, A. Tulino, J. Llorca, and G. Caire. (2015, Nov.) CachingAided Coded Multicasting with Multiple Random Requests. [Online].
Available: https://arxiv.org/abs/1511.07542.
[23] M. Ji, A. M. Tulino, J. Llorca, and G. Caire. (2014, Feb.) Caching
and Coded Multicasting: Multiple Groupcast Index Coding. [Online].
Available: https://arxiv.org/abs/1402.4572.
[24] S. Wang, W. Li, X. Tian, and H. Liu. (2015, Apr.) Coded
Caching with Heterogenous Cache Sizes. [Online]. Available:
https://arxiv.org/abs/1504.01123.
[25] M. M. Amiri, Q. Yang, and D. Gunduz. (2016, Nov.) Decentralized
Coded Caching with Distinct Cache Capacities. [Online]. Available:
https://arxiv.org/abs/1611.01579.
[26] M. M. Amiri, Q. Yang, and D. Gndz, “Decentralized coded caching
with distinct cache capacities,” in 50th Asilomar Conf. Signals, Systems
and Computers, Nov 2016, pp. 734–738.

DANIEL, YU: OPTIMIZATION OF HETEROGENEOUS CODED CACHING

[27] A. M. Ibrahim, A. A. Zewail, and A. Yener, “Centralized coded caching
with heterogeneous cache sizes,” in IEEE Wireless Commun. and Netw.
Conf., March 2017, pp. 1–6.
[28] S. Saeedi Bidokhti, M. Wigger, and R. Timo. (2016, May) Noisy
Broadcast Networks with Receiver Caching. [Online]. Available:
https://arxiv.org/abs/1605.02317.
[29] R. Timo and M. Wigger. (2015, May) Joint Cache-Channel
Coding over Erasure Broadcast Channels. [Online]. Available:
https://arxiv.org/abs/1505.01016.
[30] S. S. Bidokhti, M. Wigger, and R. Timo, “Erasure broadcast networks
with receiver caching,” in IEEE Int. Symp. Inf. Theory, July 2016, pp.
1819–1823.
[31] ——, “An upper bound on the capacity-memory tradeoff of degraded
broadcast channels,” in 9th Int. Symp. Turbo Codes and Iterative Inf.
Processing, Sept 2016, pp. 350–354.
[32] J. Zhang and P. Elia. (2016, Jun.) Wireless Coded Caching: A Topological Perspective. [Online]. Available: https://arxiv.org/abs/1606.08253.
[33] S. Saeedi Bidokhti, M. Wigger, and A. Yener. (2017, Feb.) Benefits
of Cache Assignment on Degraded Broadcast Channels. [Online].
Available: https://arxiv.org/abs/1702.08044.
[34] A. Ghorbel, M. Kobayashi, and S. Yang, “Content delivery in erasure
broadcast channels with cache and feedback,” IEEE Trans. Inf. Theory,
vol. 62, no. 11, pp. 6407–6422, Nov 2016.
[35] M. M. Amiri and D. Gunduz. (2017, Feb.) Cache-Aided Data
Delivery over Erasure Broadcast Channels. [Online]. Available:
https://arxiv.org/abs/1702.05454.
[36] A. Destounis, M. Kobayashi, G. Paschos, and A. Ghorbel.
(2017, Jan.) Alpha Fair Coded Caching. [Online]. Available:
https://arxiv.org/abs/1701.07730.
[37] A. Ghorbel, K.-H. Ngo, R. Combes, M. Kobayashi, and S. Yang. (2017,
Feb.) Opportunistic Content Delivery in Fading Broadcast Channels.
[Online]. Available: https://arxiv.org/abs/1702.02179.
[38] L. Zheng, Q. Yan, Q. Chen, and X. Tang. (2016, Nov.) On the Coded
Caching Delivery Design over Wireless Networks. [Online]. Available:
https://arxiv.org/abs/1611.04853.
[39] W. Huang, S. Wang, L. Ding, F. Yang, and W. Zhang. (2015, Apr.) The
Performance Analysis of Coded Cache in Wireless Fading Channel.
[Online]. Available: https://arxiv.org/abs/1504.01452.
[40] A. S. Cacciapuoti, M. Caleffi, M. Ji, J. Llorca, and A. M. Tulino,
“Speeding up future video distribution via channel-aware cachingaided coded multicast,” IEEE J. Sel. Areas Commun., vol. 34, no. 8,
pp. 2207–2218, Aug 2016.
[41] N. Golrezaei, K. Shanmugam, A. G. Dimakis, A. F. Molisch, and
G. Caire, “Femtocaching: Wireless video content delivery through
distributed caching helpers,” in IEEE Conf. Computer Commun., March
2012, pp. 1107–1115.
[42] K. Shanmugam, N. Golrezaei, A. G. Dimakis, A. F. Molisch, and
G. Caire, “Femtocaching: Wireless content delivery through distributed
caching helpers,” IEEE Trans. Inf. Theory, vol. 59, no. 12, pp. 8402–
8413, Dec 2013.
[43] C. Tian. (2016, Oct.) Symmetry, Outer Bounds, and Code Constructions: A Computer-Aided Investigation on the Fundamental Limits of
Caching. [Online]. Available: https://arxiv.org/abs/1611.00024.
[44] Q. Yu, M. A. Maddah-Ali, and A. Salman Avestimehr. (2016, Sep.) The
Exact Rate-Memory Tradeoff for Caching with Uncoded Prefetching.
[Online]. Available: https://arxiv.org/abs/1609.07817.

24

