Uncoded Caching and Cross-level Coded Delivery
for Non-uniform File Popularity
Emre Ozfatura and Deniz Gündüz

arXiv:1802.01135v1 [cs.IT] 4 Feb 2018

Department of Electrical and Electronic Engineering
Imperial College London
Email: {m.ozfatura, d.gunduz}@imperial.ac.uk

Abstract—Proactive content caching at user devices and coded
delivery is studied considering a non-uniform file popularity
distribution. A novel centralized uncoded caching and coded
delivery scheme, which can be applied to large file libraries,
is proposed. The proposed cross-level coded delivery (CLCD)
scheme is shown to achieve a lower average delivery rate than
the state of art. In the proposed CLCD scheme, the same subpacketization is used for all the files in the library in order
to prevent additional zero-padding in the delivery phase, and
unlike the existing schemes in the literature, two users requesting
files from different popularity groups can be served by the same
multicast message in order to reduce the delivery rate. Simulation
results indicate significant reduction in the average delivery rate
for typical Zipf distribution parameter values.

I. I NTRODUCTION
Caching and coded delivery can improve the network load
and latency significantly. This is shown in [1] by considering
a server holding N files serving K users, each equipped
with its own cache memory of size M files, over a shared
error-free link. The proposed solution consists of two phases.
In the placement phase, files are divided into sub-files and
each user stores certain sub-files. In the delivery phase, the
server multicasts carefully constructed XORed combinations
of the requested sub-files, and each user recovers its request
from its cache contents and the multicast messages. In the
proposed scheme, the server controls the caching decisions
of the users. The authors showed in [2] that, under certain
assumptions, similar gains can be achieved via coded delivery
with decentralized caching, where users cache randomly. In
[3], the authors introduce a new delivery scheme that utilizes
the common requests in order to further reduce the delivery
rate. These schemes are built on the assumption that user
requests are uniform over the library. However, in on-demand
video streaming networks video popularity statistics are not
homogeneous [4], [5].
The more interesting case of non-uniform demands has been
recently considered in [6]–[11]. The common approach in
[6]–[9] is to group the files according to their popularities,
distribute the available cache memory among the groups, and
then use the coded delivery scheme in [2] to deliver all the
missing files. All the aforementioned works try to achieve the
optimal placement structure according to file popularities. In
This work was supported in part by the Marie Sklodowska-Curie Action
SCAVENGE (grant agreement no. 675891), and by the European Research
Council (ERC) Starting Grant BEACON (grant agreement no. 725731).

particular, it is shown in [9] that the achievable delivery rate
with using two groups of files is at most a constant factor
away from the lower bound. Although the proposed methods
are successful in reducing the delivery rate for non-uniform
demands, they are sub-optimal policies in general.
An optimal content placement strategy for a particular
coded delivery scheme, the one introduced in [1], has been
independently proposed in [10] and [11]. In this scheme, each
file is divided into K + 1 disjoint fragments, and the kth
fragment of each file is cached as in the placement phase
of [1] with parameter t = k − 1. The authors show that the
optimal sizes of these fragments can be obtained by solving
a linear optimization problem. Although this scheme allows
each file to be divided into different size fragments, when the
file library is large, the proposed scheme tends to divide the
library into only a small number of groups, while the sizes of
the fragments in each group are identical. This is because [10]
and [11] optimize the content placement for the delivery phase
in [1], which is, actually, a suboptimal delivery method for
multi-level content placement. In particular, we observe that
the scheme in [10] tends to classify the files into two groups
according to their popularities, where only the popular files are
cached, and this is done in an identical manner. Since the less
popular files are not cached at all, if one of them is requested,
it is delivered via unicast transmission, which increases the
delivery rate significantly. This motivates the proposed crosslevel coded delivery (CLCD) scheme, which codes sub-files
from different placement levels. Our proposed scheme first
optimizes the coded delivery phase according to the given
placement levels, and then optimizes the placement phase
accordingly, i.e, the number of files in each cache level. We
show that the CLCD scheme provides a significant reduction
in the average delivery rate (up to 10%), while also reducing
the complexity of the placement and delivery algorithms.
II. S YSTEM M ODEL
We consider a single content server with a database of N
files, each of size F bits, denoted by W1 , . . . , WN , serving
K users, each with a cache memory of capacity M F bits.
The users are connected to the server through a shared errorfree link. We follow the two-phase model in [1]. Caches are
filled during the placement phase without the knowledge of
particular user demands. User requests are revealed in the
delivery phase, and are satisfied simultaneously.

The request of user k is denoted by dk , dk ∈ [N ] ,
{1, . . . , N }, and the demand vector is denoted by d ,
(d1 , . . . , dK ). The corresponding delivery rate R(d) is defined
as the total number of bits sent over the shared link, normalized
by the file size. We assume that each user requests file Wn
with
PN probability pn , where p1 ≥ p2 ≥ · · · ≥ pN , and
n=1 pn = 1. Let P (d) denote the probability of observing
demand vector d. We want to minimize the average delivery
rate R̄, defined as
X
R̄ ,
P (d)R(d).
(1)
d

A file
 Wn is said to be cached at level t, if it is divided into
K
t non-overlapping sub-files of equal size, and each sub-file
is cached by a distinct subset of t users. Then, each sub-file
can be identified by an index term I, where I ⊆ [K] and
|I| = t, such that sub-file Wn,I is cached by users k ∈ I.
Following a placement phase in which all the files are cached
at level t, as proposed in [1], in the delivery phase, for each
subset S ⊆ [K], |S| = t + 1, all the requests of the users in
S can be served simultaneously by multicasting
M
Wds ,S\{s} .
(2)
s∈S

Thus, with a single multicast message the server can deliver
t + 1 sub-files, and achieve a multicasting gain of t + 1.
III. C ROSS - LEVEL C ODED D ELIVERY
Here, we explain the proposed CLCD scheme. Initially, the
file library is divided into two groups: the most popular Nh
files are called the high-level files, while the remaining N −Nh
files are called the low-level
files. In the placement phase, each

file is divided into Kt sub-files. High-level
 files are cached
K−1
at level t; that is, each user caches t−1 sub-files of each
high-level file, while the low-level files are cached at level
1; that is, each user exclusively caches K−1
t−1 /t sub-files of
each low-level file. We denote this particular case of the CLCD
scheme by CL(t,1), where t and 1 represent the caching levels
of the high and low-level files, respectively. For each lowlevel file, the set of all sub-files are divided into K disjoint
and equal-size subsets1 , so that each user caches the sub-files
in a different subset. Hence, for a given Nh and N the cache
size required for the CL(t, 1) scheme is given by
Nh (t − 1) + N
.
(3)
K
For given M , Nh can be obtained from (3). Hence, the
grouping of the library is directly related to t, M , and N .
Next, we explain the CL(2,1) scheme in detail.
M (Nh , N, t, 1) ,

A. CL(2, 1) Scheme
We first present the achievable delivery rate of the CL(2, 1)
scheme, and then explain the placement and delivery phases

only requirement is that K
should be divisible by K. When K is
t
a prime number this requirement holds for any t.
1 The

User
index of
cached
sub-files

1
{1, 2}
{1, 3}
{1, 4}
{1, 5}
{1, 6}
{1, 7}

2
{1, 2}
{2, 3}
{2, 4}
{2, 5}
{2, 6}
{2, 7}

3
{1, 3}
{2, 3}
{3, 4}
{3, 5}
{3, 6}
{3, 7}

4
{1, 4}
{2, 4}
{3, 4}
{4, 5}
{4, 6}
{4, 7}

5
{1, 5}
{2, 5}
{3, 5}
{4, 5}
{5, 6}
{5, 7}

6
{1, 6}
{2, 6}
{3, 6}
{4, 6}
{5, 6}
{6, 7}

7
{1, 7}
{2, 7}
{3, 7}
{4, 7}
{5, 7}
{6, 7}

TABLE I: Sub-files cached by each user in Example 1.

in detail. For a given demand realization d, the users requesting high-level files are called the high-level users, and
are denoted by Kh . Similarly, users requesting low-level files
are called the low-level users, and are denoted by Kl . Let
k a , |Ka |, a ∈ {l, h}. We will show that for a cache size
of M (Nh , N, t, 1), and demand realization d, the following
delivery rate is achievable by the proposed CL(2, 1) scheme:
 
 h 
k
kh

 ( 3 )+ L(d)−3( 3 ) /2
, if k h ≥ 2 , (4)
R(d) =
(K2 )

 K−1
otherwise
2
where L(d) is the total number of missing sub-files for
demand realization d, and is given by
 2

K
kl
h
L(d) , (K − 1)
−k −
.
(5)
2
2
In the coded delivery scheme of [1], when all the files are
cached at level t, the delivery rate is K−t
t+1 . Similarly in
(4), when k l = K, there are only low level users and the
delivery rate is K−1
2 . The delivery rate depends only on
k2−1 , [k h , k l ]; rather than the demand vector; hence, the
dependence on d in (4) and (5) can be replaced by k2−1 .
Note that k h and k l are random variables, and their distribution PNh ,N (k2−1 ) depends on Nh , N , and the popularity
distribution. The average load can now be written as follows:
X
R̄ ,
R(k2−1 )PNh ,N (k2−1 ).
(6)
k2−1

B. Placement phase

In the placement phase, file Wk is divided into K
2 subfiles, denoted by Wk,{i,j} , k ∈ [N ], i, j ∈ [K]. If Wk is a
high-level file, Wk,{i,j} is stored by users i and j. Hence,
each user stores K − 1 sub-files for each high-level file. On
the other hand, each user exclusively stores only K−1
sub2
files for each of the low-level files.
Example 1. Consider K = 7 users and N = 7 files. Let
{A, B, C, D, E, F, G} denote the file library with decreasing
popularity, where F and G are low-level, whereas A, B,
 C, D
and E are high-level files. Each file is divided into K
2 = 21
sub-files, and each user stores K − 1 = 6 sub-files of each
= 3 sub-files of each low-level file.
high-level file, and K−1
2
User cache contents after the placement phase is illustrated
in Table I; for each user the sub-files in red are cached for
all the files, whereas the sub-files in blue are cached for only

High-level users
123
124
125
134
135
145
234
235
245
345
Low-level users
67
67
67

Multicast message
A23 ⊕ B13 ⊕ C12
A24 ⊕ B14 ⊕ D12
A25 ⊕ B15 ⊕ E12
A34 ⊕ C14 ⊕ D13
A35 ⊕ C13 ⊕ E13
A45 ⊕ D15 ⊕ E14
B34 ⊕ C24 ⊕ D23
B35 ⊕ C25 ⊕ E23
B45 ⊕ D25 ⊕ E24
C45 ⊕ D35 ⊕ E34
Multicast message
G16 ⊕ F17
G26 ⊕ F27
G67 ⊕ F37

TABLE II: Multicasted messages in the first two steps of the
delivery phase in Example 1.

high-level files.2
C. Delivery phase
Delivery phase of the proposed scheme consists of four
steps, which will be explained on Example 1.
Example 1 continued. Assume that different high-level files
are requested by the first five users, i.e., Kh = {1, 2, 3, 4, 5},
and different low-level files by users 6 and 7, i.e., Kl = {6, 7}.
The delivery phase is carried out in four steps:
1) Intra-high-level delivery: The first step of the delivery
phase is identical to that in (2) for t = 2. The only difference
is that, now we consider only the users in Kh , instead of [K].
2) Intra-low-level delivery: The second step also follows
(2) with t = 1, targeting low-level users in Kl . In Example
1, the messages delivered by the server corresponding to the
first two steps are listed in Table II.
3) Cross-level delivery: This step is the main novelty of
the CLCD scheme. First, note that each high-level user has
(K − 1)/2 sub-files in its cache that are requested by a
low-level user. For instance, in Example 1, user 1 has subfiles {G12 , G13 , G14 } that are requested by user 7. Let Hi,j
denote the set of sub-files stored at high-level user i that are
requested by low-level user j, e.g., H1,7
 , {G12 , G13 , G14 }.
Similarly, let Γi,j be the set of K−2
= K − 2 sub-files
1
stored by low-level user j, that are requested by high-level
user i, e.g., Γ1,7 , {A27 , A37 , A47 , A57 , A67 } in Example 1.
We note that sub-files {A27 , A37 , A47 , A57 } are also cached
by a high-level user, but sub-file A67 is cached by only lowlevel users. At this point we introduce the set Ωi,j ⊆ Γi,j
of the sub-files that are requested by high-level user i, and
cached by low-level user j as well as by a high-level user,
e.g., Ω1,7 , {A27 , A37 , A47 , A57 }. Further, we introduce the
set Λi , i ∈ Kh , of the sub-files that are requested by high-level
user i and cached by only low-level users, e.g., Λ1 = {A67 }.
In the third step our aim is to deliver all the sub-files
requested by the low-level users and the sub-files requested by
2 In Example 1, we use a systematic placement for the low-level files;
that is, sub-file Wk,{i,j} is cached by either user i or j. This systematic
placement enables dynamic cache replacement when a low-level (high-level)
file becomes a high-level (low-level) file.

the high-level users that are cached by only low-level users,
via multicast messages, each destined for one high-level and
one low-level user. More formally, we want low-level user j,
j ∈ Kl , to recover all the sub-files in ∪i∈Kh Hi,j , and we want
high-level user i, i ∈ Kh , to recover all the sub-files in Λi .
Now, we introduce the sets Fi,j ⊆ Γi,j for all i ∈ Kh and
j ∈ Kl , which satisfy the following constraints
|Hi,j | = |Fi,j |, ∀i ∈ Kh , ∀j ∈ Kl ,

(7)

h

Λi ⊆ ∪j Fi,j , ∀i ∈ K ,

(8)
h

l

Fi,j ∩ Fi,k = ∅, ∀i ∈ K and j, k ∈ K .

(9)

Let us first assume that sets Fi,j satisfying (7)-(9) exist for
all i ∈ Kh and j ∈ Kl . From (7), one can observe that it
is possible to construct a one-to-one mapping between the
elements of Hi,j and Fi,j .
The proposed coded delivery procedure for the third step
works as follows: first, for each i ∈ Kh and j ∈ Kl the
sub-files in sets Hi,j and Fi,j are paired via a one-to-one
mapping, and the server multicasts the XOR of the paired
sub-files. We remark that the sub-files in Hi,j are requested by
low-level user j, and are available at high-level user i, while
the sub-files in Fi,j are requested by high-level user i, and
are available at low-level user j. Hence, with each multicast
message both high-level user i and low-level user j receives
one sub-file of their respective requests. Since all the sub-files
in ∪i∈Kh ,j∈Kl Hi,j are delivered via multicast messages, the
low-level users collect all their missing sub-files. Furthermore,
(8) ensures that each high-level user collects its missing subfiles that are available only in the caches of the low-level users.
As a final remark, (9) guarantees that high-level users do not
receive the same sub-file multiple times.
Next, we show how to construct the sets Fi,j , i ∈ Kh ,
j ∈ Kl . In order to ensure (8) and (9), Λi is partitioned into
subsets {Λi,j }j∈K l with approximately uniform cardinality,
i.e., |Λi,k | − |Λi,j | ≤ 1, ∀j, k ∈ Kl , j 6= k, and such that
Λi,j ⊆ Γi,j holds for all i ∈ Kh and j ∈ Kl . Further details of
this approximately uniform partitioning are provided in [12].
We note that, if Λi,j ⊆ Fi,j , then (8) holds. We also assume
that the same partitioning is applied to all Λi ’s. Partitions of
Λi ’s for Example 1 are illustrated in Table III. For given Ωi,j
and Λi,j , Fi,j can be constructed as follows; Fi,j = Λi,j ∪
{Ωi,j \ ∆i,j }, for some ∆i,j ⊆ Ωi,j . From the construction,
one can easily verify that (9) holds. Finally, in order to ensure
(7), we need to show that it is possible to construct ∆i,j ,
i ∈ Kh , j ∈ Kl , which satisfy the following equality
|Hi,j | = |Λi,j | + |Ωi,j | − |∆i,j |.

(10)

We note that, if the following inequality holds
|Λi,j | ≤ |Hi,j | ≤ |Λi,j | + |Ωi,j |,

(11)

then, ∆i,j satisfying (10) can be always found.
From the construction, we know that |Hi,j | = K−1
2 ;
however, |Ωi,j | and |Λi,j | depend on the realization
of
l l mthe
user demands, i.e., |Ωi,j | = k h − 1 and |Λi,j | = k 2−1 or

Λi,j

∆i,j

Fi,j

Hi,j

(1,6)

{A26 , A36 , A46 , A56 }

∅

{A46 }

{A26 , A36 , A56 }

{F12 , F13 , F14 }

(1,7)

{A27 , A37 , A47 , A57 }

{A67 }

{A27 , A47 }

{A67 , A37 , A57 }

{G12 , G13 , G14 }

(2,6)

{B16 , B36 , B46 , B56 }

∅

{B56 }

{B16 , B36 , B46 }

{F23 , F24 , F25 }

(2,7)

{B17 , B37 , B47 , B57 }

{B67 }

{B17 , B57 }

{B67 , B37 , B47 }

{G23 , G24 , G25 }

(3,6)

{C16 , C26 , C46 , C56 }

∅

{C46 }

{C16 , C26 , C56 }

{F34 , F35 , F36 }

(3,7)

{C17 , C27 , C47 , C57 }

{C67 }

{C47 , C57 }

{C67 , C17 , C27 }

{G34 , G35 , G36 }

(4,6)

{D16 , D26 , D36 , D56 }

∅

{D36 }

{D16 , D26 , D56 }

{F45 , F46 , F47 }

(4,7)

{D17 , D27 , D37 , D57 } {D67 }

{D17 , D37 }

{D67 , D27 , D57 }

{G45 , G46 , G47 }

(5,6)

{E16 , E26 , E36 , E46 }

∅

{E26 }

{E16 , E36 , E46 }

{F15 , F56 , F57 }

(5,7)

{E17 , E27 , E37 , E47 }

{E67 }

{E27 , E37 }

{E67 , E17 , E47 }

{G15 , G56 , G57 }

(i,j)

Ωi,j

Multicasted messages
A26 ⊕ F12 , A36 ⊕ F13 ,
A56 ⊕ F14
A67 ⊕ G12 , A37 ⊕ G13 ,
A57 ⊕ G14
B16 ⊕ F23 , B36 ⊕ F24 ,
B46 ⊕ F25
B67 ⊕ G23 , B37 ⊕ G24 ,
B47 ⊕ G25
C16 ⊕ F34 , C26 ⊕ F35 ,
C56 ⊕ F36
C67 ⊕ G34 , C17 ⊕ G35 ,
C27 ⊕ G36
D16 ⊕ F45 , D26 ⊕ F46 ,
D56 ⊕ F47
D67 ⊕ G45 ,
D27 ⊕ G46 ,D57 ⊕ G47
E16 ⊕ F15 , E36 ⊕ F56 ,
E46 ⊕ F57
E67 ⊕ G15 , E17 ⊕ G56 ,
E47 ⊕ G57

TABLE III: Sets Ωi,j , Λi,j , ∆i,j , Fi,j , Hi,j and the multicasted messages in step 3 of the delivery phase for Example 1.
j l k
|Λi,j | = k 2−1 due to the approximately uniform partitioning. Accordingly,


K − 1 kh − 2
+
, or
(12)
|Ωi,j | + |Λi,j | =
2
2


K − 1 kh − 2
|Ωi,j | + |Λi,j | =
+
.
(13)
2
2
One can observe that, when k h ≥ 2, in both cases |Ωi,j | +
h
|Λi,j | ≥ K−1
2 . Hence, from now on we assume k ≥ 2, and
h
if k = 1, then in the delivery phase, the high-level file is
considered as a low-level file, thus the achievable rate becomes
(K − 1)/2. One can also observe that |Λi,j | ≤ |Hi,j |, since
k l ≤ K. Let ni,j be the required cardinality for the set ∆i,j
according to (10), i.e., ni,j , |Ωi,j | + |Λi,j | − |Hi,j |, then we
can consider any subset of Ωi,j with cardinality ni,j as ∆i,j to
construct Fi,j . We note that all the sub-files in ∪i∈Kh ,j∈Kl ∆i,j
will be delivered in the fourth step of our scheme. Hence, ∆i,j
are chosen in order to minimize the number of transmitted
messages in the last step. To clarify, in Example 1, if the server
transmits E26 ⊕B56 in the last step of the delivery phase, then
this implies that B56 ∈ ∆2,6 and E26 ∈ ∆5,6 . Therefore,
we need to construct the multicast messages that will be
transmitted in the last step while satisfying the constraint
∆i,j = ni,j , ∀ i ∈ Kh , j ∈ Kl . We will address this issue in
Section IV. Once ∆i,j is known, Fi,j can be constructed easily
as illustrated in Table III, which also lists all the multicasted
messages in this step.
4) Intra-high-level delivery with multicasting gain of two:
In the last step, the server multicasts the messages
B = {C46 ⊕ D36 , E26 ⊕ B56 , A27 ⊕ B17 , D17 ⊕ A47
C57 ⊕ E37 , C47 ⊕ D37 , B57 ⊕ E27 } ,

(14)

each of which is destined for two high-level users. This step
is completed with unicasting the sub-file A46 . In the next
section, we will explain how the multicast messages in (14)
are constructed.

IV. S MART SET CONSTRUCTION PROCEDURE
In this section, we will explain the procedure for constructing the set of multicast messages, B. The main concern of
this procedure is to satisfy the constraint |∆i,j | = ni,j 3 for
all i ∈ Kh and j ∈ Kl , while constructing set B. In the
construction procedure, we consider the two cases, where k h
is even and odd, separately.
A. Even number of high-level users
Before presenting the algorithm for the even number of
high-level users, we will briefly explain how set partitioning
can be used for the construction of multicast messages. Consider Kh = {1, 2, 3, 4, 5, 6} and a partition of Kh into subsets
h
of size two, e.g., P K = {{1, 2} , {3, 4} , {5, 6}}. Then, for
h
a particular j ∈ Kl each {i, k} ∈ P K can be converted
into the following multicast message: Wdi ,{k,j} ⊕ Wdk ,{i,j} .
h
For instance, for the specified partition set P K , following
multicast messages will be constructed: Wd1 ,{2,j} ⊕Wd2 ,{1,j} ,
Wd3 ,{4,j} ⊕Wd4 ,{3,j} and Wd5 ,{6,j} ⊕Wd6 ,{5,j} . Note that, for
h
a particular j ∈ Kl , if P K is used to construct the multicast
messages as illustrated above, then exactly one sub-file is
added to the set ∆i,j for each i ∈ Kh . Hence, for a particular
h
h
j ∈ Kl , if we have nj disjoint partitions P1K , . . . , PnKj to construct multicast messages, then the constraint |∆i,j | = nj is
h
satisfied for all i ∈ Kh . Therefore, we use Qnj = ∪i=1:nj PiK
to construct multicast messages in Algorithm 1. We note that
Qn can be considered as a set of user pairings, where each
user appears in exactly n pairings. Details on the construction
h
h
of disjoint partition sets P1K , . . . , PnK are given in [12].
B. Odd number of high level users
In Section IV-A, we first constructed a set of node pairings
Qnj for each j ∈ Kl , and then generated the multicast
messages using the node pairings. In the construction of Qnj ,
3 Since the same partitioning is applied to all Λ ’s, ∀i ∈ Kh , n
i
i,j = nj
for all i ∈ Kh .

Algorithm 1: Set construction for the case of even k h

1
2
3
4
5
6
7
8
9
10

Input : Kh , {nj }j∈Kl
Output: {∆i,j }i∈Kh ,j∈Kl , B
∆i,j ← {} for all i ∈ Kh , j ∈ Kl ;
B ← {};
for all j ∈ Kl do
construct Qnj , then;
for all {i, k} ∈ QnSj do
∆i,j ← ∆i,j
W
;
S  di ,{k,j}
∆k,j ← ∆k,j
Wdk ,{i,j} ;
S
B←B
Wdi ,{k,j} ⊕ Wdk ,{i,j} ;
end
end

h

we use the partition sets P K . However, when k h is an odd
number, it is not possible to partition Kh into subsets of
cardinality two. Note that, if k h is an odd number, k l must
be an even number, which means that for k l /2 low-level
users, nj will be an odd number nodd , and for the remaining
l
low-level users, nj will be an even number neven . Let Kodd
l
and Keven be the subset of low-level users with nodd and
l
l
denote
neven , respectively. Furthermore, let kodd
and keven
l
l
the cardinality of the sets Kodd and Keven , respectively.
For the case of neven , we introduce a new method, Algorithm 2, to construct Qneven for each j ∈ Kl . We note that,
l
(ind) and P(ind)
in Algorithm 2 we use the notation Keven
4
to denote the elements with index ind in the given sets. We
also want to remark that partition sets5 used in Algorithm 2
h
h
are disjoint, i.e., P K \{i} ∩ P K \{k} = ∅, where i, k ∈ Kh ,
and i 6= k. Hence, one can easily observe that, each high-level
h
user appearsSexactly in one pairing in P K \{i} , except i, and
h
h
in P K \{i} P K \{k} ∪ {i, k} each high-level user appears
exactly in two pairings. Eventually, in Qneven each high-level
user appears exactly in neven pairings. Hence, as in Algorithm
1, Qneven can be used to construct sets ∆i,j as well the set
of multicast messages B.
l
the same set of node pairings Qneven is
For each j ∈ Keven
used to construct the multicast messages B; hence, the process
l
is identical for each j ∈ Keven
. However, it is not possible
nodd
l
to construct set B.
to have a single Q
for each j ∈ Kodd
Nevertheless, we follow a similar procedure to construct the
l
multicast messages for the low-level users in Kodd
. Our goal
in this paper is to highlight the fundamental aspects of the
CLCD scheme, while the complete algorithm for odd number
of high-level users is provided in [12]. With the proposed set
construction algorithms we are ensuring that in the third and
fourth steps of the delivery phase all the sub-files are delivered
with a multicasting gain of two6 , which explains the achievable
delivery rate.
l
Although we use index for the sets Keven
, P, Algorithm 2 does not
require a particular ordering for these sets
5 Due to limited space we omitted the construction procedure of the
partitions sets, for further details please refer to [12].
6 When | ∪
i∈Kh ,j∈Kl ∆i,j | is odd, exactly one sub-file is unicasted, while
the remaining sub-files achieve a multicasting gain of two, as in Example 1.
4

Algorithm 2: Construction of Qneven for odd k h

1

Input : Kh , neven
Output: Qneven
for ind = 1 : neven n
/2 do

o
Kh \ Kh (kh )

{i, k} ← P
(ind);
S
S
h
h
Qneven ← Qneven P K \{i} P K \{k} ∪ {i, k};

2
3
4

end

V. CL(t, 1, 0) SCHEME
We can generalize the CL(t, 1) scheme to the CL(t, 1, 0)
scheme, in which some of the files are not cached at all. We
present this generalized scheme for the special case of t = 2.
A. CL(2, 1, 0) Scheme
In the CL(2, 1) scheme, we grouped the files according to
their popularities. For a given cache size M , we can choose
not to cache a certain number of least popular files, Nr , at all,
in order to increase the number of high-level files Nh .
In the delivery phase, the users requesting files that are not
cached are treated as virtual high-level users. To clarify, for a
given demand realization d, let k2−1−0 , [k h , k l , k r ], where
k r is the total number of users requesting one of the uncached
files. If the users requesting these files are considered as virtual
high-level users, the delivery phase becomes identical to the
delivery phase of CL(2, 1) scheme for k2−1 = [k h + k r , k l ].
Then, the sub-files of the uncached files are unicasted. We
note that, in the first step of the delivery phase, the server does
not need to send the multicast messages that are destined for
only the virtual high-level users. Hence, the delivery rate for
a demand realization k2−1−0 is given by

kr
R(k2−1−0 ) = R(k2−1 ) + k r −

3
.
K
2

Recall that the average delivery rate is
X
R̄ ,
R(k2−1−0 )PNh ,N,Nr (k2−1−0 ).

(15)

(16)

k2−1−0

Thus, to minimize the average delivery rate we search for the
optimal value of Nr , Nr? . We note that Nrmax ≥ Nr? ≥ Nrmin ,
where Nrmax and Nrmin are defined as the number of files that
are not cached in order to cache all the remaining files at level
t = 2 and t = 1, respectively. Hence, to find the optimal value
of Nr? , average delivery rate R̄ is calculated for each possible
value of Nr within the interval [Nrmin , Nrmax ]. We remark
that, for each value of Nr , P (k2−1−0 ) must be calculated for
each possible realization of k2−1−0 . Hence, the optimization
of the placement phase has a complexity of O(N K 2 ).
VI. N UMERICAL R ESULTS
In this section, we compare the performance of the proposed
CLCD scheme with that of the conventional centralized coded
delivery scheme for two different content placement schemes.
The first content placement scheme is called naive memory
sharing, introduced in [1], in which all the files are cached
identically according to a single parameter t = M K/N .

3

3

Average delivery rate

2.8

2.6

2.4

2.2

2

1.8

1.6
140

naive memory sharing
optimal memory sharing [10]
CL(2,1,0)
CL(3,1,0)

2.8

Average delivery rate

naive memory sharing
optimal memory sharing [10]
CL(2,1,0)
CL(3,1,0)

2.6

2.4

2.2

2

1.8

160

180

200

220

240

260

280

Cache size (number of files)

1.6
140

160

180

200

220

240

260

280

Cache size (number of files)

Fig. 1: γ = 0.7.

Fig. 2: γ = 0.75.

Note that, when the parameter t is not integer, we can apply
memory-sharing [1] by dividing the files in the library into two
disjoint fragments, and these fragments are cached according
to parameters btc and dte, respectively.
The second benchmark scheme is the optimal memory sharing scheme proposed in [10], which is shown to outperform
other coded delivery techniques under non-uniform demand
distributions. In this scheme, each file is divided into K + 1
disjoint fragments, and the kth fragment, 1 < k, is cached
according to parameter t = k − 1, while the first fragment
is not cached. Thus, the overall system can be considered
as a combination of K + 1 sequential coded delivery phases
with different multicasting gains, i.e., the kth delivery phase
is executed with multicasting gain of k + 1. The sizes of the
fragments are obtained via a linear program.
In general, the popularity of video files for on-demand
streaming applications approximately fits a Zipf distribution
with parameter 1 > γ > 0.65 [4], [5]. Hence, in our simulations we consider γ = 0.7 and γ = 0.75. In realistic scenarios,
number of files in the video library is considered to be on the
order of 104 . However, due to the complexity of the optimal
memory sharing scheme of [10], we assume N = 1000 and
K = 7. In the simulations, the cache size M varies from 140 to
280, which corresponds to 1 < t < 2. The delivery rates of the
naive memory sharing, the optimal memory sharing scheme,
CL(2, 1, 0) and CL(3, 1, 0)7 schemes are illustrated in Fig. 1
and Fig. 2, for γ = 0.7 and γ = 0.75, respectively. We observe
that the proposed CLCD scheme reduces the average delivery
rate especially for moderate cache capacities. While the gain
from the CL(2, 1, 0) scheme reduces as the Zipf parameter
increases, the gain provided by CL(3, 1, 0) increases.

Due to space limitations, we presented a special case of our
scheme, called CL(2, 1, 0), which divides the library into three
groups, and uses different levels of caching for the first two
groups, while the last group of the least popular files are not
cached at all. The delivery rate is presented in closed form as
a function of the number of users requesting files from each
group. Numerical simulations show that the proposed scheme
can provide up to 10% reduction in the average delivery rate.

VII. C ONCLUSIONS
We introduced a novel centralized coded delivery scheme
with uncoded caching for non-uniform demand distributions.
7 The CL(3, 1, 0) scheme can be constructed similarly to CL(2, 1, 0);
however, the details are skipped due to page limitation.

R EFERENCES
[1] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,”
IEEE Trans. Inf. Theory, vol. 60, no. 5, May 2014.
[2] ——, “Decentralized coded caching attains order-optimal memory-rate
tradeoff,” IEEE/ACM Trans. Netw., vol. 23, no. 4, Aug 2015.
[3] Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “The exact ratememory tradeoff for caching with uncoded prefetching,” in 2017 IEEE
Int. Symp. on Inf. Theory (ISIT), June 2017, pp. 1613–1617.
[4] X. Cheng, C. Dale, and J. Liu, “Statistics and social network of youtube
videos,” in 2008 16th Int. Workshop on Quality of Service, June 2008.
[5] M. Cha, H. Kwak, P. Rodriguez, Y. Y. Ahn, and S. Moon, “Analyzing
the video popularity characteristics of large-scale user generated content
systems,” IEEE/ACM Trans. Netw., vol. 17, no. 5, Oct 2009.
[6] J. Hachem, N. Karamchandani, and S. Diggavi, “Coded caching for
multi-level popularity and access,” IEEE Trans. Inf. Theory, vol. 63,
no. 5, May 2017.
[7] U. Niesen and M. A. Maddah-Ali, “Coded caching with nonuniform
demands,” IEEE Trans. Inf. Theory, vol. 63, no. 2, Feb 2017.
[8] 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, June 2017.
[9] J. Zhang, X. Lin, and X. Wang, “Coded caching under arbitrary
popularity distributions,” in Inf. Theory and Appl. Works., Feb 2015.
[10] S. Jin, Y. Cui, H. Liu, and G. Caire, “Structural properties of uncoded
placement optimization for coded delivery,” CoRR, vol. abs/1707.07146,
2017.
[11] A. M. Daniel and W. Yu, “Optimization of heterogeneous coded
caching,” CoRR, vol. abs/1708.04322, 2017.
[12] E. Ozfatura and D. Gündüz, “Uncoded caching and cross-level coded
delivery for non-uniform file popularity,” 2018, in preparation.

