On the Benefits of Asymmetric Coded Cache
Placement in Combination Networks with End-User
Caches
Kai Wan∗ , Mingyue Ji† , Pablo Piantanida∗ , Daniela Tuninetti‡

arXiv:1802.10474v1 [] 28 Feb 2018

∗ L2S

CentraleSupélec-CNRS-Université Paris-Sud, France, {kai.wan, pablo.piantanida}@l2s.centralesupelec.fr
† University of Utah, Salt Lake City, USA, mingyue.ji@utah.edu
‡ University of Illinois at Chicago, Chicago, USA, danielat@uic.edu

Abstract—THIS PAPER IS ELIGIBLE FOR THE STUDENT
PAPER AWARD. This paper investigates the fundamental tradeoff between cache size and download time in the (H, r, M, N)
combination network, where a server with N files is connected

to H relays (without caches) and each of the K := Hr users
(with caches of size M files) is connected to a different subset
of r relays. Existing schemes fall within two categories: either
use the uncoded symmetric cache placement originally proposed
for the shared-link model and design delivery phase dependent
on the network topology, or effectively divide the combination
network intoH independent shared-link networks each serving
K0 := H−1
users; in either case, the placement phase is
r−1
independent of network topology. In this paper, a novel strategy is
proposed where the coded cache placement is dependent on network
topology. The proposed scheme is shown to be information
theoretically optimal for large cache size. In addition, when
not exactly optimal, the proposed scheme can also outperform
existing schemes.

I. I NTRODUCTION
Caching content at the end-user’s memories smooth the
network traffic. A caching scheme comprises two phases. (i)
Placement phase: during off-peak hours, the server places
parts of its library into the users’ caches without knowledge
of what the users will later demand. When pieces of files are
simply copied into the cache, the cache placement phase is said
to be uncoded; otherwise it is coded. (ii) Delivery phase: each
user requests one file during peak-hour time. According to
the user demands and cache contents, the server transmits the
smallest number of files in order to satisfy the user demands.
Caching was originally studied by Maddah-Ali and Niesen
(MAN) in [1] for shared-link networks, which comprises a
server with N files, K users with a cache of size M files,
and an error-free broadcast link. The MAN scheme uses
uncoded cache placement and a binary linear network code
to deliver coded messages that are simultaneously useful for
t+1 := KM/N+1 users. Coded caching was shown to provide
a multiplicative coded caching/multicast gain of t + 1 over
conventional uncoded caching schemes. In [2], a variation of
the MAN scheme was shown to be information theoretically
optimal to within a factor 2 for shared-link networks.
Since users may communicate with the central server
through intermediate relays, caching in relay networks has
recently been considered. Since it is difficult to analyze general
relay networks, a symmetric network, known as combination

network [3], has received a significant attention. A (H, r, M, N)
combination network comprises a server with N files that is
connected to H relays (withoutcaches) through H orthogonal
links, and each of the K := Hr users (with caches of size M
files) is connected to a different subset of r relays through r
orthogonal links, as shown in Fig. 1.
Past Work (for combination networks): Existing works
use MAN uncoded placement for shared-link networks for the
placement phase (which is agnostic of the network topology)
and then design the delivery phase by leveraging the network
topology [3], [4], [5]; these schemes are symmetric in the
sense that for every file there exists one subfile cached by
each subset of t := KM/N users. The main limitation of the
MAN placement is that the multicasting opportunities (directly
related to the overall coded cahing gain) to transmit the various
subfiles are not “symmetric” across subfiles (because relays
are connected to different sets of users). One way to deal
with this limitation is to divided the combination network into
H independent shared-link network and to precode every file
by an MDS (Maximum Distance Separable) code so that it
becomes irrelevant from which relay a user has received a
coded subfile–as long as enough coded subfiles have been
collected [6]. The limitation of this coded placement is that
the coded
caching gain is now that of a network with K0 :=

H−1
r−1 < K equivalent users, which appears to be suboptimal in
light of known results for shared-link networks (i.e., the coded
caching gain fundamentally scales linearly with the number of
users K).
Contributions: In this paper we propose a novel placement that aims to attain identical “multicasting opportunities”
for each coded subfile, which is then delivered by using a
variation of the scheme proposed in [5]. Interestingly, our
asymmetric placement leads to a “symmetric delivery”–to
be made precise later. The novel scheme is proved to be
.
information theoretically optimal when M ≥ (K−H+r−1)N
K
To the best of our knowledge, this is the very first work
that characterizes the exact memory-download time tradeoff
for combination networks. In addition, when not optimal, the
proposed scheme can also outperform state-of-the-art schemes.
The paper is organized as follows. Section II gives the formal problem definition and states the main results. Section III
contains proofs and numerical evaluations.

Since the max-link load of the uncoded routing scheme in [3]
is Rr = K/H(1 − M/N), we define the coded caching gain g
of a scheme with max-link load R as
K/H(1 − M/N)
Rr
g :=
=
.
(2)
R
R

0
Define that K0 := H−1
r−1 , where K is the number of users
connected to each relay. By the cut-set bound in [3], g ≤ K0 .

Server with
N files (size B bits)
(F1,..., FN )

H relays 1

K users 1
Caches
Z1
(size MB bits)

2

3

4

2

3

4

5

6

Z2

Z3

Z4

Z5

Z6

Fig. 1: A combination network with end-user-caches, with H = 4
relays and K = 6 users, i.e., r = 2.

II. S YSTEM M ODEL AND M AIN R ESULTS
We use the following
 notation convention. A collection
is a set of sets, e.g., {1, 2}, {1, 3} . Calligraphic symbols
denote sets or collections, bold symbols denote vectors, and
sans-serif symbols denote system parameters. We use | · | to
represent the cardinality of a set or the length of a vector;
[a : b] := {a, a + 1, . . . , b} and [n] := [1 : n]; ⊕ represents

bit-wise XOR. We define the set arg maxx∈X f (x) :=  x ∈
X : f (x) = maxx∈X f (x) . Our convention is that xy = 0
if x < 0 or y < 0 or x < y.

B. Main Results
We now state our main results. Thm.1 gives the max-link
load of the novel proposed scheme with coded asymmetric
cache placement and Thm.2 gives the optimality results. Different from the state-of-the-art schemes, which fix the cache
size and compute the load (and thus the coded caching gain), in
the proposed scheme we fix a coded caching gain g ∈ [2 : K0 ]
and then find the minimum needed cache size.
Theorem 1. For an (H, r, M, N) combination network, the
lower convex envelop of the following points
!

K00 −r
K/H(1 − M/N)
q
, (3)
(M, R) = N K00 −r
0 −1 ,
g
+ r Kq−1
q
for (coded caching gain) g ∈ [2 : K0 ], q := K0 − g + 1,
H
00
K0 := H−1
r−1 and K := r−1 , is achievable.
Theorem
2. Under the same assumptions of Thm.1, when

M ∈ (K−H+r−1)N
, N , we have
K
R? = (1 − M/N)/r.

A. System Model
In a (H, r, M, N) combination network, a server has N files,
denoted by F1 , · · · , FN , each composed of B i.i.d uniformly
distributed bits. The server is connected to H relays through H
error-free
orthogonal links. The relays are connected to K :=

H
users
through r K error-free orthogonal links. Each user
r
has a local cache of size MB bits, for M ∈ [0, N], and is
connected to a distinct subset of r relays.
The set of users connected to relay h is denoted by
Uh , h ∈ [H]. The set of relays connected to user k is denoted
by Hk , k ∈ [K]. For each set of relays J ⊆ [H], we denote the
common connected users for the relays in J by PJ . For the
network in Fig. 1, for example, U1 = {1, 2, 3}, H1 = {1, 2}
and P{1,2} = {1}.
In the placement phase, user k ∈ [K] stores information
about the N files in its cache of size MB bits, where M ∈
[0, N]. The cache content of user k ∈ [K] is denoted by Zk ;
let Z := (Z1 , . . . , ZK ). During the delivery phase, user k ∈ [K]
requests file dk ∈ [N]; the demand vector d := (d1 , . . . , dK ) is
revealed to all nodes. Given (d, Z), the server sends a message
Xh of B Rh (d, Z) bits to relay h ∈ [H]. Then, relay h ∈ [H]
transmits a message Xh→k of B Rh→k (d, Z) bits to user k ∈
Uh . User k ∈ [K] must recover its desired file Fdk from Zk and
(Xh→k : h ∈ Hk ) with high probability when B → ∞. The
objective is to determine the optimal max-link load defined as
R? := min

max

max {Rh (d, Z), Rh→k (d, Z)} .

Z k∈Uh ,h∈[H],
d∈[N]K

(1)

(4)

Proof: Converse From the general cut-set outer bound
in [3, Thm.2] with α = 1 and l = 1, we have R? ≥ (1 −
M/N)/r. Between M ∈ (K−H+r−1)N
, N , the outer bound is
K
a straight line. When M = (K−H+r−1)N
, we have
K
H−r+1
1 − (K − H + r − 1)/K
=
.
(5)
r
rK
00
Achievability When q = 1 in Thm.1, we have M = KK−r
=
00
(K−H+r−1)N
Kr
0
and
g
=
K
=
.
Thus
from
(3)
we
have
K
H
R? ≥

K(1 − M/N)
H−r+1
=
,
(6)
Hg
rK
which coincides with (5). The memory sharing is then used
between M = (K−H+r−1)N
and M = N.
K
R? ≤

Remark 1. For the scheme in [6], in order to achieve a coded
caching gain g ∈ [2 : K0 ] jthe minimum
needed cache size is
k
H(g−1)N
H
0
M=
. When K − r−1 + 1 ≤ g ≤ K0 , the minimum
rK
cache size for our scheme in Thm.1 is strictly less than the one
H
in [6]; moreover when r = 2, we have K0 − r−1
+ 1 = 0, and
for any memory size the proposed scheme is better than [6].
The proof can be found in the extended version of this paper.
III. P ROOF OF T HM .1
Uncoded cache placement: If each user directly store
some bits of files in the cache, the placement is uncoded. When
placement is uncoded, each file can be effectively partitioned
as Fi = {Fi,W : W ⊆ [K]} where Fi,W represents the bits of
Fi which are only cached by users in W.

MAN placement: For M = t N
where t ∈ [0 : K], each file
K 
Fi where i ∈ [N] is divided into Kt non-overlapping subfiles
of length BK bits; Fi = {Fi,W : W ⊆ [K], |W| = t}.
(t)
With MAN placement, a delivery scheme to create multicast
messages by leveraging the symmetries in the topology was
proposed in [5]; in Section III-A, we revisit it. In Section III-B,
we describe the proposed scheme to achieve coded caching
gain g = K0 . In Section III-C, we generalize the scheme to
any coded caching gain g ∈ [2 : K0 ].

Besides the relays in Y, each of these three users is connected
to a different relay other than the two relays in Y. For one
user k ∈ Y, we assume user k is connected to relay h where
h ∈ Hk \ Y; since relay h is connected to only one user (user
k) in PY , we have ([K]\PY )∩Uh = Uh \{k}. 1 This motivates
H
the following placement, which considers all the K00 := r−1
subsets of relays with cardinality r − 1.
Placement phase: We divide each Fi into K00 = 10 nonoverlapping and equal-length pieces and denote

A. Separate Relay Decoding delivery Scheme (SRDS) [5]

Fi = (Fi,[K]\PY : Y ⊆ [H], |Y| = r − 1)

= Fi,[10]\{1,2,3} , Fi,[10]\{1,4,5} , Fi,[10]\{2,4,6} , Fi,[10]\{3,5,6} ,

In the delivery phase, user k ∈ [K] should recover Fdk ,W
for all W ⊆ [K] \ {k}. For each such subfile Fdk ,W , we find
Sk,W := maxh∈Hk |Uh ∩ W| (i.e., the set of relays Sk,W ⊆
Hk each relay in which is connected to the largest number
of users in W). We partition Fdk ,W into |Sk,W | equal-length
|Sk,W |
pieces and denote Fdk ,W = (Fdk ,W,h
: h ∈ Sk,W ). For each
|S

|

k,W
h
h
relay h ∈ Sk,W , we add Fdk ,W,h
to Tk,W∩U
; here Tk,W∩U
h
h
represents the set of bits needed to be recovered by user k (first
entry in the subscript) from relay h (superscript) and already
known by the users in W ∩ Uh (second entry in the subscript)
who are also connected to relay h (superscript).
The next step is to generate multicast messages. For each
relay h ∈ [H] and each set J ⊆ Uh , the server forms the
multicast messages

h
WJh := ⊕ Tk,J
\{k} ,

(7)

k∈J

where we used the same convention as that in the literature
when it comes to ‘summing’ sets. The message WJh is sent to
relay h, which then forwards it to the users in J .
The main limitation of SRDS with MAN placement is that
the delivery of some subfiles, due to the network topology,
needs more bits than than others–see Example 2 later on. In
the next subsection, we propose a novel placement so that
all multicast messages need the same amount of transmitted
bits to be delivered to the intended users, in other words, all
multicast messages have the same “multicasting opportunities”
and thus the delivey phase is “symmetric”.
B. Novel Caching Scheme for g = K0
We start by describing by way of an example to achieve the
maximal coded caching gain g = K0 ; in this case, the coded
multicast gain g equals the number of users connected to a
relay.
Example 1 (H = 5, r = 3, N = 10, g = 6). In this example,
we have N = K = 10 and
U1 = [6], U2 = {1, 2, 3, 7, 8, 9}, U3 = {1, 4, 5, 7, 8, 10},
U4 = {2, 4, 6, 7, 9, 10}, U5 = {3, 5, 6, 8, 9, 10}.
We aim to achieve coded caching gain g = 6, that is, every
multicast message is simultaneously useful for g = 6 users.
Since r = 3 (each user is connected to three relays), we cansee
that every r − 1 = 2 relays (denoted by Y) have H−(r−1)
=
r−(r−1)
H − r + 1 = 3 common connected users (denoted by PY ).

Fi,[10]\{1,7,8} , Fi,[10]\{2,7,9} , Fi,[10]\{3,8,9} , Fi,[10]\{4,7,10} ,
Fi,[10]\{5,8,10} , Fi,[10]\{6,9,10} .
It can
 be00 seen that the required memory size is M = N 1 −
r
= 7. Note that, compared to MAN placement, not
r−1 /K
all subfiles Fi,W where |W| = 7 are present.
Delivery phase: Assume d = (1 : 10). We use SRDS
to let each user k recover Fdk ,W where k ∈
/ W. For
example, user 1 should recover F1,[10]\{1,2,3} , F1,[10]\{1,4,5}
and F1,[10]\{1,7,8} . For F1,[10]\{1,2,3} = F1,[4:10] , we can see
that relay 1 is connected to users [1 : 6] ∩ [4 : 10] = {4, 5},
relay 2 is connected to users {1, 2, 3, 7, 8, 9} ∩ [4 : 10] =
{7, 8, 9} while relay 3 is connected to users {1, 4, 5, 7, 8, 10}∩
[4 : 10] = {4, 5, 7, 8, 10} and thus we have S1,[4:10] =
arg maxh∈H1 |Uh ∩ [4 : 10]| = {3}. Therefore F1,[4:10] ∈
3
2
T1,{4,5,7,8,10}
. Similarly, F1,[10]\{1,4,5} ∈ T1,{2,3,7,8,9}
and
1
F1,[10]\{1,7,8} ∈ T1,{2,3,4,5,6}
. After considering all the subfiles
demanded by all users, for relay h = 1 (and similarly for all
other relays) we have


1
1
= F2,[10]\{2,7,9} ,
T1,{2,3,4,5,6}
= F1,[10]\{1,7,8} ,T2,{1,3,4,5,6}


1
1
= F4,[10]\{4,7,10} ,
T3,{1,2,4,5,6}
= F3,[10]\{3,8,9} ,T4,{1,2,3,5,6}


1
1
T5,{1,2,3,4,6}
= F6,[10]\{6,9,10} .
= F5,[10]\{5,8,10} ,T6,{1,2,3,4,5}
For each relay h ∈ [H], we create the multicast messages
WUhh as in (7) to be sent to relay h and then forwarded to the
users in Uh . Notice that in this example, by the novel placement, each subfile is multicasted with other 5 subfiles and thus
the coded caching gain is g = 6. The achieved max-link load
is 1/10, which coincides with the cut-set outer bound in [3];
the max-link load in [6] is 0.118. In this example, the proposed
placement is uncoded and is information theoretically optimal.
We now generalize the scheme in Example 1 to achieve the
maximal coded caching gain g = K0 .
00
Placement phase: Each file Fi is divided into K :=
H
r−1 non-overlapping and equal-length pieces denoted by
Fi = (Fi,[K]\PY : Y ⊆ [H], |Y| = r − 1). Fi,W , i ∈ [N],
is cached by user
M =
 k if k ∈ W, which requires
H−(r−1)
r
(since
|P
|
=
=
N 1 − r−1
/K00 = (K−H+r−1)N
Y
K
r−(r−1)
H − r + 1).
1 For example, if Y = {1, 2}, we have P
{1,2} = {1, 2, 3}; let us focus on
user 1, who is also connected to relay 3; we can see ([K] \ P{1,2} ) ∩ U3 =
{4, 5, 7, 8, 10} = U3 \ {1}.

Delivery phase: User k should recover Fdk ,[K]\PY where
Y ⊆ [H] with |Y| = r − 1 and k ∈ PY . It can be seen that
if and only if Y ⊆ Hk , we have k ∈ PY . So we need to
consider each user k ∈ [K] and each set of relays Y ⊆ Hk
with cardinality |Y| = r − 1. We can see that |Hk \ Y| = 1
and let h ∈ Hk \ Y. Besides Y, each user in PY is connected
to a different relay other than the relays in Y. Hence, PY ∩
Uh = {k} and thus ([K] \ PY ) ∩ Uh = Uh \ {k}. Each relay
h0 ∈ (Hk \ {h}) is connected to |PY | = H − r + 1 users in PY
and thus |([K] \ PY ) ∩ Uh0 | = |Uh0 | − |PY |. So for Fdk ,[K]\PY ,
h
we have Sk,[K]\PY = {h} and put it in Tk,U
.
h \{k}
For each relay h ∈ [H], the server forms the multicast
messages as in (7) and transmits it to relay h, which then
forwards it to users in Uh .
Max-link load: Each demanded subfile is multicasted
with other K0 − 1 subfiles and thus g = K0 . As a result, the
max-link load is as in (3).
C. Generalization to g ∈ [2 : K0 ]
We now extend the scheme in Section III-B to any g ∈ [2 :
K0 ]. The novel ingredient here is an additional ‘precoding’ of
the files before placement, i.e., in other words, the design of a
coded placement based on the topology of the network instead
of uncoded placement. We start with an example.
Example 2 (H = 4, r = 2, N = 6, g = 2). In Example 1,
for each collection Q of q subsets of relays with cardinality
r − 1 each, we have one corresponding subfile. Similar to
Example 1, for each set of r − 1 = 1 relay, in this example
we also determine the set of common connected users, in this
case P{h} = Uh , i.e., P{1} = {1, 2, 3}, P{2} = {1, 4, 5},
P{3} = {2, 4, 6}, and P{4} = {3, 5, 6}. In addition, we have
q = K0 − g + 1 = 2. Before introducing the additional MDS
precoding, we show that, if we proceed as for the previous
example, not all the subfiles are sent in a linear combination
involving the same number of subfiles, in other words, not all
subfiles have the same “multicasting opportunities.”
Consider q = 2 subsets of relays each with cardinality
r − 1 = 1, e.g., Y1 = {1} and Y2 = {3}. Since besides
relay 1, each user in PY1 is connected to a different relay
other than relay 1, we have |PY1 ∩ U2 | = 1. Similarly, we
have |PY2 ∩ U2 | = 1. It can also be checked that PY1 ∩ U2 6=
PY2 ∩U2 . Hence, we have |(PY1 ∪PY2 )∩U2 | = q = 2 and thus
| [K] \ (PY1 ∪ PY2 ) ∩ U2 | = |U2 | − q = 1. Hence with SRDS,
for user 1 we can transmit Fd1 ,[K]\(PY1 ∪PY2 ) = Fd1 ,{5} and
Fd5 ,{1} simultaneously in one linear combination. Similarly,
it can be seen that the subfiles Fd1 ,[K]\(P{1} ∪P{4} ) = Fd1 ,{4} ,
Fd1 ,[K]\(P{2} ∪P{3} ) = Fd1 ,{3} and Fd1 ,[K]\(P{2} ∪P{4} ) =
Fd1 ,{2} demanded by user 1 have the same “multicasting
opportunities” as Fd1 ,{4} .
However, consider the following q = 2 subsets of relays
each with cardinality r − 1 = 1: Y3 = {1} and Y4 = {2}. For
user 1 who does not know Fd1 ,[K]\(PY3 ∪PY4 ) = Fd1 ,{6} , since
H1 ⊆ Y3 ∪ Y4 , we can see that for each h ∈ H
 1 we have
|(PY3 ∪ PY4 ) ∩ Uh | = 3 and so | [K] \ (PY3 ∪ PY4 ) ∩ Uh | = 0.
In other words, with SRDS to transmit Fd1 ,{6} , we cannot
transmit other subfiles in the same combination.

Hence, the main idea of our proposed scheme is to let user
1 recover Fd1 ,{2} , Fd1 ,{3} , Fd1 ,{4} and Fd1 ,{4} in the delivery
phase, and ignore Fd1 ,{6} which has less “multicasting opportunities”. Notice that the subfile Fd1 ,[K]\(P{3} ∪P{4}) = Fd1 ,{1}
is cached by user 1. This motivates the following placement.
Placement phase: Each file Fi is divided into 1 + 4 =
5 non-overlapping and equal-length pieces, which are then
encoded by using a (6, 5) MDS code (not the (H, r) = (4, 2)
MDS code as in [6]). Each MDS coded symbol of Fi is cached
by one user k ∈ [K] and is denoted by fi,{k} , which contains
B/5 bits. So the cache size needs to be M = 6/5.
Delivery phase: Assume d = (1 : 6). We use SRDS
to let each user k ∈ [K] recover fdk ,[K]\(PY1 ∪PY2 ) where
k∈
/ [K] \ (PY1 ∪ PY2 ) and Hk * (Y1 ∪ Y2 ), such that from
placement and delivery phases, each user can obtain 5 MDS
coded symbols of file Fdk and is thus able to recover Fdk .
For example, user 1 must recover f1,{2} , f1,{3} , f1,{4} , and
f1,{5} ; those, together with the cached MDS coded symbol
f1,{1} , allows him to recover F1 . For f1,{2} , we can see that
relay 1 is connected to user {2}∩{1, 2, 3} = {2}, while relay 2
is connected to user {2} ∩ {1, 4, 5} = ∅, and thus we have
1
S1,{2} = arg maxh∈H1 |Uh ∩ {2}| = {1} and f1,{2} ∈ T1,{2}
.
After considering all the subfiles demanded by all the users,
for relay h = 1 (and similarly for all other relays) we have
1
1
1
T1,{2}
= {f1,{2} }, T1,{3}
= {f1,{3} }, T2,{1}
= {f2,{1} },
1
1
1
T2,{3}
= {f2,{3} }, T3,{1}
= {f3,{1} }, T3,{2}
= {f3,{2} }.

We then create the multicast messages as in (7) for each
J ⊆ Uh where |J | = g = 2. For example, the server
1
1
1
transmits to relay 1 W{1,2}
= T1,{2}
⊕ T2,{1}
= f1,{2} ⊕
1
1
1
1
f2,{1} , W{1,3} = T1,{3} ⊕ T3,{1} = f1,{3} ⊕ f3,{1} , W{2,3}
=
1
1
T2,{3} ⊕ T3,{2} = f2,{3} ⊕ f3,{2} , which are then forwarded to
the demanding users. The achieved max-link load is 3/5, while
that of [6] is 9/10. The outer bound idea used in [3], which
leverages the cut-set bound from [1], can be straightforwardly
extended to leverage the tighter outer bound from [2]; by doing
so, for this example we obtain as outer bound 3/5; therefore,
our proposed scheme is optimal. In this example, thanks to the
novel placement, each MDS coded symbol is multicasted with
another one and thus the coded caching gain is g = 2.
Notice that the outer bound under the constraint of uncoded
placement in [4, Thm.4] is 157/255 ≈ 0.616, that is, in this
example using uncoded cache placement is strictly suboptimal.
We now present our novel scheme that attains g ∈ [2 : K0 ].
Placement phase: Recall q = K0 − g + 1, K0 = H−1
r−1

H
and K00 := r−1
. Each file Fi , i ∈ [N], is divided into


0
K00 −r
−1
+ r Kq−1
non-overlapping and equal-length pieces,
q
 00  00 

0
−1
which are then encoded by using a Kq , K q−r + r Kq−1
MDS code. For each collection Q including q subsets of
relays with cardinality r − 1 each, there is an MDS coded
symbol fi,[K]\ ∪ PY cached by users in [K] \ ∪ PY . The
Y∈Q
Y∈Q
required memory
size to store these MDS coded symbols is
K00 −r
(
)
M = N K00 −r q K0 −1 . After the placement phase, since there
( q )+r( q−1 )

K00
q



collections of q subsets of relays each of cardinality
00 
r − 1, each file Fi has Kq MDS coded symbols. For each
user k, we divide the collections Q into 3 classes.
1) Class 1: if there is no Y ∈ Q such that Y ⊆ Hk , we
have k ∈ [K]\ ∪ PY and thus the symbol fi,[K]\ ∪ PY
Y∈Q

2.5

Y∈Q

is cached by user k where i ∈ [N]. The number of
00
collections of Class 1 is K q−r .
2) Class 2: if k ∈
/ [K] \ ∪ PY and Hk * ∪ Y,
Y∈Q

Y∈Q

we transmit the symbol fdk ,[K]\ ∪ PY to user k in
Y∈Q
one combination including other g − 1 symbols in the
delivery phase. Furthermore, if and only if at least
one Y ∈ Q is a subset of Hk , we can see that
k ∈
/ [K] \ ∪ PY . Recall that each Y ∈ Q has r − 1
relays. So if Hk *

1.5

1

0.5

0

Y∈Q

∪ Y, at most one Y ∈ Q is a

0

5

10

15

M

Y∈Q

subset of Hk . As a result, if and only if Hk * ∪ Y
Y∈Q
and there exists only one Y ∈ Q such that Y ⊆ Hk ,
one has k ∈
/ [K] \ ∪ PY and Hk * ∪ Y. Hence,
Y∈Q

Fig. 2: Memory-load tradeoff for the combination network
with H = 6, r = 2 and K = N = 15.

Y∈Q

the number of symbols to be recovered by user k in the
 (H−1)−1

0
r
−1
r−1
delivery phase is r−1
= r Kq−1
.
q−1
3) Class 3: if k ∈
/ [K] \ ∪ PY and Hk ⊆ ∪ Y, for each
Y∈Q

Y∈Q

h ∈ Hk we have |([K]\ ∪ PY )∩Uh | ≤ K0 −(H−r+1).
Y∈Q

Hence, we let user k ignore the symbol fdk ,[K]\

∪ PY .

Y∈Q

Delivery phase: In the delivery phase, we let each user
k ∈ [K] recover the MDS coded symbols in Class 2. We focus
on each user k ∈ [K], each relay h ∈ Hk , and each set of users
J ⊆ Uh where |J | = g and k ∈ J . Besides relays in Hk \{h},
each user in PHk \{h} is connected to a different relay other
than the relays in Hk \ {h}. So we have that PHk \{h} ∩ Uh =
{k}. Let M := Uh \ J . For each user k 0 ∈ M, we can
find a set of relays Hk0 \ {h}. We can similarly prove that
PHk0 \{h} ∩ Uh = {k 0 }. Hence, we construct the collection


Q0 = Hk0 \ {h} : k 0 ∈ M ∪ Hk \ {h}
(8)
and we have ([K] \

[6, Zewail and Yener, ISIT 17]
[4, Wan et al, Allerton 17]
[5, Wan et al, ICC 18]
Proposed scheme in (3)
Enhanced cut−set outer bound
in [3, Yu et al, ISIT 17]

2

Max link−load

are

∪ PY ) ∩ Uh = J \ {k}. By this

Y∈Q0
0

construction, we have |Q | = K0 − g + 1 = q. In addition,
since (Hk \ {h}) ∈ Q0 and there is no set in Q0 containing
relay h, we have that Hk \ {h} is the only set in Q0 which
is a subset of Hk and that Hk * ∪ 0 Y. So fdk ,[K]\ ∪ PY
Y∈Q

Y∈Q0

h
should be recovered by user k and be put in Tk,J
\{k} . As a
result, for each relay h ∈ Hk and each set of users J ⊆ Uh
where |J | = g and k ∈ J , we consider a different symbol of
Fdk demanded by user k. With |Uh | = K0 and q = K0 − g + 1,
we can0 prove
inthe delivery
 that
 phase, we consider all of
0
−1
−1
K0 −1
the r Kg−1
=r K
=
r
0
q−1 symbols which are needed
K −q
to be recovered by user k.
For each relay h ∈ [H] and each set J ⊆ Uh where |J | = g,
the server forms the multicast messages WJh as in (7) and
transmit it to relay h, who then forwards it to each user k ∈ J .
Notice
that when g0 = K0 , we have q = K0 − g + 1 = 1. So

K00
K00 −r
−1
=
+ r Kq−1
= K00 and thus we need not MDS
q
q
precoding procedure. Hence, the above scheme is equivalent
to the scheme in Section III-B.

Max-link load: Each demanded subfile is multicasted
with other g − 1 subfiles such that the coded caching gain
is g. As a result, the max-link load is as in (3).
Remark 2. From (8), since (Hk \ {h}) ∈ Q0 , for each h0 ∈
Hk \ {h}, we have |([K] \ ∪ 0 PY ) ∩ Uh0 | ≤ K0 − (H − r + 1).
Y∈Q

Hence, when g > K0 − (H − r + 1) + 1, we have |([K] \
∪ 0 PY ) ∩ Uh | = g − 1 > K0 − (H − r + 1). In conclusion,
Y∈Q

{h} = arg maxh1 ∈Hk |([K]\ ∪ 0 PY )∩Uh1 | and the multicast
Y∈Q
message generation is identical to SRDS. However, when g ≤
K0 − (H − r + 1) + 1, h may not be the relay connected to the
largest number of users in the considered subset and the coded
caching gain may be reduced. So the future work includes the
improvement for g ≤ K0 − (H − r + 1) + 1.
Example 3 (H = 6, r = 2, N = 15). In Fig. 2, we compare
the performance of the proposed scheme with that of [6], [5],
[4] and the enhanced cut-set outer bound based on [2] as
described in Example 2. Notice that the proposed scheme is
exactly optimal for 10 ≤ M ≤ 15.
IV. F URTHER I MPROVEMENT FOR T HM .1
We can further improve the asymmetric coded placement
proposed in Section III-C.
It is stated in Section III-C that for each collection Q where
|Q| = p and each element in Q includes r − 1 relays, we can
generate one MDS symbol fi,[K]\ ∪ PY . Recall that, for each
Y∈Q
user k, the MDS symbols can be divided into 3 classes: the
symbols which are cached by user k, the symbols which are
needed to be recovered by user k in the delivery phase and the
symbols which are ignored by user k in the delivery phase.
Moreover, when Hk ⊆ ∪ Y, the MDS symbol fdk ,[K]\ ∪ PY
Y∈Q

Y∈Q

is in Class 3. So if ∪ Y = [H], there is no user who needs
Y∈Q

to recover the MDS symbol fdk ,[K]\

∪ PY

Y∈Q

in the delivery

phase. As a result, we need not to generate the MDS symbol
fi,,[K]\ ∪ PY for the collections Q where ∪ Y = [H].

It is equivalent to prove

Y∈Q

Y∈Q

x−

In Appendix, we prove the following lemma.
Lemma 1. For each user k ∈ [K], the number of collections Q
where ∪ Y =
6 [H] and there is no Y ∈ Q such that Y ⊆ Hk
Y∈Q
is
G :=

H−1
X

(X1 + Y1 + Z1 )(−1)H−a+1 ,

Since

H
H−r+1

<

r+q−1
q−1 ,



Theorem 3. For an (H, r, M, N) combination network, the
lower convex envelop of the following points
!
K/H(1 − M/N)
G
,
(13)
(M, R) = N
0 −1 ,
g
G + r Kq−1
0

0

for (coded caching gain) g ∈ [2 : K ], q := K − g + 1 and
K0 := H−1
r−1 is achievable.
A PPENDIX A
P ROOF OF R EMARK 1
We give the outline of the proof.j Wekaim to prove that
H
for a coded caching gain g ≥ K0 − r−1
+ 1 meaning that
j
k
H
q ≤ r−1
, the needed minimum memory size of the proposed
scheme is less than the one in [6], i.e.,

K00 −r
H(g − 1)N
q
N K00 −r
.
(14)
<
K0 −1
rK
+
r
q
q−1
It is equivalent to prove

0
−1

H
r Kq−1
0
1 − K00 −r
<
K
−
q

0
−1
rK
+ r Kq−1
q
= (K − Hq/r)/K = 1 − Hq/rK. (15)
It is equivalent to prove
1
Hq
−
> 0,
(16)
x/(qr) + 1
rK


K00 − r × · · · × K00 − r − q + 1

 .
where x =
K0 − 1 × · · · × K0 − q + 1

we have

q−1
H
H−r+1
q−1
H
00
<K
H−r+1
q
H
0
.
=K
H−r+1

(9)

It can be computed that the number of collections Q where
Hk ⊆ ∪ Y and there is only one set Y ∈ Q where Y ⊆ Hk
Y∈Q

0
−1
is also r Kq−1
. For each of such collections Q, user k needs to
recover the MDS symbol fdk ,[K]\ ∪ PY . Hence, we can derive
Y∈Q
the following theorem.

(17)



x < K00 − r

a=r−1

 a 

H−r
−r
r−1
X1 :=
,
(10)
a−r
q

 a 

H−r
r−1 − 1 ,
Y1 := r
(11)
a−r+1
q
 

 
  a 
H
H−r
H−r
r−1
Z1 :=
−r
−
. (12)
a
a−r+1
a−r
q

Kr2
+ qr = x − K0 r + qr < 0.
H

Hence, it is sufficient to prove
K0
Since

qr
K0

q
H
− K0 r + qr < 0.
H−r+1

< 1, it is sufficient to prove
q
H
− r + 1 < 0.
H−r+1

Since q ≤

j

H
r−1

k
, it is sufficient to prove

H/(r−1)
H
− (r − 1) < 0.
H−r+1
Let r − 1 = u. We can see that H ≥ u + 2. It is equivalent to
prove
H H/u
− u < 0.
H−u
H/u
H
Let G(H, u) = H−u
− u. We then compute the partial
derive of G(H, u) with respect to H denoted by ∂G(H,u)
,
∂H
H H/u
1
H 
∂G(H, u)
=
− u + (H − u) log(
) .
∂H
H−u
u(H − u)
H−u
By Taylor series, we can prove that
ey >

H H−u
,
H−u

where e is the Euler’s number. Hence ∂G(H,u)
< 0 and
∂H
thus G(H, u) is monotonically decreasing with respect to H.
Similarly by the partial derive of G(H, u) with respect to u,
we can see that for any H0 and u0 , if G(H0 , u0 ) < 0, we
have G(H0 , u) < G(H0 , u0 ) where u > u0 . From these two
monotonic results, we can have
1) When u = 7, we have G(u+2, u) < 0. So for any u ≥ 7
and any H/gequ + 2, we have G(H, u) < 0. So we can
prove the proposed scheme is strictly better than [6].
2) When u < 7, we can find the minimum value vu where
G(u+vu , u) < 0. Thus for any H ≥ u+vu , G(H, u) < 0
and we can prove our results. For H < u + vu , we can
directly compute and show (14) is true.
In conclusion, we prove (14).

A PPENDIX B
P ROOF OF L EMMA 1
We focus on one integer a ∈ [r − 1, H − 1] and one user
k ∈ [K]. We can divide collections Q where | ∪ Y| = a and
Y∈Q
there is no Y ∈ Q such that Y ⊆ Hk into 3 groups:
1) |Hk ∩ ∪ Y| = r. The number of set S ⊆ [H] where
Y∈Q

|S| = a and Hk ⊆ S is H−r
a−r . For each of thus sets S,
we want to choose one collection Q where |Q| = q and
for each Y ∈ Q we have Y ⊆ S and Y * Hk . It can be
computed that the number of such collections for each

a
set S is (r−1q)−r . Hence, the number of collections Q
in this group is X1 .
2) |Hk ∩ ∪ Y| = r − 1. The number of set S ⊆ [H] where
Y∈Q
 H−r 
r
|S| = a and |S ∩ Hk | = r − 1 is r−1
a−r+1 . For each
of thus sets S, we want to choose one collection Q
where |Q| = q and for each Y ∈ Q we have Y ⊆ S and
Y 6= (S ∩ Hk ). It can be computed that the number of

a
such collections for each set S is (r−1q)−1 . Hence, the
number of collections Q in this group is Y1 .
3) |Hk ∩ ∪ Y| < r − 1. The number of set S ⊆ [H]
Y∈Q


where |S| = a and |S ∩ Hk | < r − 1 is Ha − H−r
a−r −


r
H−r
r−1 a−r+1 . For each of thus sets S, we want to
choose one collection Q where |Q| = q and for each
Y ∈ Q we have Y ⊆ S. It can be computed that the
a 
) .
number of such collections for each set S is (r−1
q
Hence, the number of collections Q in this group is Z1 .
Hence, by the inclusion-exclusion principle [7, Theorem 10.1],
we prove Lemma 1.
R EFERENCES
[1] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” IEEE
Trans. Infor. Theory, vol. 60, no. 5, pp. 2856–2867, May 2014.
[2] Q. Yu, M. A. Maddah-Ali, and S. Avestimehr, “Characterizing the ratememory tradeoff in cache networks within a factor of 2,” in IEEE Int.
Symp. Inf. Theory, Jun. 2017.
[3] M. Ji, M. F. Wong, A. M. Tulino, J. Llorca, G. Caire, M. Effros, and
M. Langberg, “On the fundamental limits of caching in combination
networks,” IEEE 16th Int. Workshop on Sig. Processing Advances in
Wireless Commun., pp. 695–699, 2015.
[4] K. Wan, M. Ji, P. Piantanida, and D. Tuninetti, “Novel outer bounds and
inner bounds with uncoded cache placement for combination networks
with end-user-caches,” inner bounds in 55th Allerton Conf. Commun.,
Control, Comp. , outer bounds in IEEE Inf. Theory Workshop 2017,
available at arXiv:1701.06884v5, Oct. 2017.
[5] ——, “Caching in combination networks: Novel multicast message generation and delivery by leveraging the network topology,” accepted to
IEEE Intern. Conf. Commun (ICC 2018), available at arXiv:1710.06752.
[6] A. A. Zewail and A. Yener, “Coded caching for combination networks
with cache-aided relays,” in IEEE Int. Symp. Inf. Theory, pp. 2438–2442,
June 2017.
[7] J. H. V. Lint and R. M. Wilson, “A course in combinatorics (second
edition),” Cambridge University Press, ISBN 9780521803403, 2001.

