A Novel Asymmetric Coded Placement in
Combination Networks with end-user Caches
Kai Wan∗ , Daniela Tuninetti‡ , Mingyue Ji† , Pablo Piantanida∗ ,

arXiv:1802.10481v1 [cs.IT] 28 Feb 2018

∗ L2S

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

Abstract—The tradeoff between the user’s memory size and the
worst-case download time in the (H, r, M, N) combination network
is studied, where a central server communicates with K users
through H immediate relays, and each user has local cache of
size M files and is connected to a different subset of r relays.
The main contribution of this paper is the design of a coded
caching scheme with asymmetric coded placement by leveraging
coordination among the relays, which was not exploited in past
work. Mathematical analysis and numerical results show that the
proposed schemes outperform existing schemes.

I. I NTRODUCTION
Caching is an effective way to smooth out network traffic
by storing some contents in users’ memories during off-peak
times to reduce the required number of transmissions during
peak-traffic times. A caching scheme includes two phases.
In the placement phase, each user stores parts of content in
his cache without knowledge of later demands. If each user
directly stores some bits of the files, the placement is said to
be uncoded. In the delivery phase, each user requests one file.
According to users’ demands and cache contents, the server
aims to transmit the smallest number packets so as to satisfy
the users’ demands, regardless of the demands.
Caching was originally studied by Maddah-Ali and Niesen
(MAN) in [1] for the shared-link network, which comprises
a server with N files, K users with a cache of size M files,
and an error-free broadcast link. An additional multiplicative
coded caching gain was shown to be attainable by coded
caching compared to conventional uncoded caching schemes.
For each M = Nt/K, where t is an integer from 0 to N,
each file is split into Kt non-overlapping equal-size subfiles
that are strategically placed into the user caches. During the
deliver phase, coded multicast messages are sent through the
shared-link so that a single transmission simultaneously serves
t + 1 users. We say that the MAN scheme attains a coded
caching gain of t + 1 for t = KM/N. A slight variation of the
MAN scheme is known to be at most a factor of 2 from an
information theoretical outer bound [2].
Combination networks: In practice, users may communicate with the central server through intermediate relays. Since
it is difficult to analyze general relay networks, a symmetric
network, known as combination network [3], has received
a significant attention recently. A (H, r, M, N) combination
network comprises a server with N files that is connected to
H relays (without caches) 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–see Fig. 1. The goal is to design a two-phase caching
scheme that attains the max-link-load, that is, that minimizes
the maximum number of transmissions among all links, which
is related to the download time.
Past work can be divided into two groups.
Past work for combination networks with uncoded
placement: With MAN placement and MAN multicast message generation, the authors in [3], [4] proposed various
delivery schemes. The scheme in [5] still used MAN placement but proposed a novel way to generate and to deliver
the multicast messages by leveraging the symmetries in the
network topology. Placement Delivery Array (PDA), originally
proposed in [6] to reduce the sub-packetization of the MAN
scheme in the shared-link model, has been recently extended
in [7] to combination network; when r divides H, the scheme
achieves the same load as [8] but with lower sub-packetization
and with uncoded placement.
The main limitation of schemes based on MAN placement is
that, due to the combination network topology, the “multicast
opportunities” (directly related to the overall coded caching
gain) to transmit the various subfiles are different across
subfiles. Hence, even if the placement is symmetric, the
delivery may be asymmetric. Since worst-case performance is
of interest here, asymmetric delivery schemes are not desirable
and they may actually be suboptimal.
Past work for combination networks with coded placement: In [9] we showed that coded placement schemes can
be strictly better than any possible scheme with uncoded
placement. The authors in [8] proposed a caching scheme
where an MDS code is used before (symmetric) placement
so that the delivery phase for the combination network is
equivalent to the delivery phase of H uncoordinated sharedlink networks, each serving H−1
r−1 virtual users.
Our recent results in [9] used asymmetric coded placement
with an MDS precoding to further reduce the max-link load
achieved by [8] when the cache size is large; the MDS code
parameters are not the same in the two papers. The key idea
in [9] is to let the users decode only those subfiles that can be
transmitted with other g − 1 equal-length subfiles in a single
linear combination from a single relay; the main drawback
is that when g (i.e., and thus the cache size) is small some
multicasting opportunities are “overlooked.”

By the inclusion-exclusion principle [10, Theorem 10.1]

r  
X
H Kn
|Zt | =
(−1)n−1 ,
(5)
n
t
n=1

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

H relays 1

K users 1
Caches
Z1
(size MB bits)

2

3

and moreover, from the definition of Ki in (1), we have


r  
t|Zt | X H Kn Kn − 1
=
(−1)n−1
K0
K
t
−
1
n
0
n=1

r  
X
r
Kn − 1
=
(−1)n−1 .
n
t
−
1
n=1

4

2

3

4

5

6

Z2

Z3

Z4

Z5

Z6

(6)

For the network in Fig. 1, we have

Fig. 1: A combination network with H = 4 relays and K = 6

U1 = {1, 2, 3}, U2 = {1, 4, 5},

users, i.e., r = 2.

Contributions: In this paper we design an asymmetric
coded placement so that the delivery by the H relays can be
“coordinated”–to be made precise later. We also prove that the
proposed schemes strictly
 lower the max-link-load compared
to [8] when g ≤ H−2
r−2 + 1. Numerical evaluations show that
the proposed schemes outperform existing schemes.
Paper Organization: The paper is organized as follows.
Section II gives the formal problem definition and some
related results. Section III states the main results. Section IV
concludes this paper.
II. S YSTEM M ODEL AND R ELATED R ESULTS
A. Notation
We shall use the following notation convention in the study
of the (H, r, M, N) combination network, where a server with
N files communicates with the users through H immediate
relays, and each user has local cache of size M files and is
connected to a different subset of r relays. We let


H−i
Ki :=
, i ∈ [0 : r],
(1)
r−i
where K0 = K is the number of users in the system, K1 is the
number of users connected to each relay, and Ki represents the
number of users that are simultaneously
connected to i relays.

Our convention is that xy = 0 if x < 0 or y < 0 or x < y.
The subset of users connected to relay h ∈ [H] is denoted by
Uh , and the subset of relays connected to user k ∈ [K] by Hk .
For a subset of users W ⊆ [K], the set of relays simultaneoulsy
connected to all the users in W is denoted by
RW := {h ∈ [H] : W ⊆ Uh }.

and thus, for instance, R{1,2} = {1}, U{2,3} = U2 ∩U3 = {4},
and Z1 contains all the 1-subsets of [6], while Z2 contains all
the 2-subsets of [6] with the exception of {1, 6}, {2, 5}, {3, 4}.
Moreover, calligraphic symbols denote sets or collections
(i.e., set of sets), bold symbols denote vectors, and sans-serif
symbols denote system parameters. We use | · | to represent
the cardinality of a set or the absolute value of a real number;
[a : b] := {a, a + 1, . . . , b} and [n] := [1 : n]; ⊕ represents
bit-wise XOR.
B. 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 :=
K0 users through r K error-free orthogonal links. Each user has
a local cache of size MB bits, for M ∈ [0, N], and is connected
to a distinct r-subset of relays.
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 max-link load R? is
R? := min max {R1 (d, Z), R2 (d, Z)} ,

(2)

For a subset of relays J ⊆ [H], the set of users who are
simultaneously connected to all the relays in Y is denoted by
UY := {k ∈ [K] : k ∈ ∩h∈J Uh }.

U3 = {2, 4, 6}, U4 = {3, 5, 6}.

(3)

Note that U{h} = Uh . For a given integer t, the t-subsets of
users for which there exists at least one relay connected to all
the users in this subset is denoted as

Zt := W ⊆ [K] : |W| = t, RW 6= ∅ .
(4)

d∈[N]K

Z

R1 (d, Z) := max {Rh (d, Z)},
h∈[H]

R2 (d, Z) :=

max
k∈Uh ,h∈[H]

{Rh→k (d, Z)},

(7)
(8)
(9)

where R1 in (8) is the largest load from the server to the relays,
and R2 in (9) is the largest load from the relays to the users.
We say that a scheme with max-link load R attains a coded
caching gain of g if
R=

Rrouting
, for
g

(10)

Rrouting :=

K(1 − M/N)
K1 (1 − M/N)
=
from [3].
H
r

(11)

By the cut-set bound [3] we have g ≤ K1 = rK/H (recall that
K1 is the number of users connected to each relay).
C. Caching Scheme in [8, Theorem 1]
We state here the state-of-the-art scheme in [8] for the case
of no cache at the relays; the scheme uses MDS-based coded
placement so as the delivery from each relay is equivalent
to that of a shared-link network serving K1 virtual users and
where the operations of the H virtual shared-link network are
not coordinated. In particular, each file is divided into r nonoverlapping and equal-length pieces that are encoded by an
(H, r) MDS code. The h-th MDS-coded symbol is denoted by
shi and must be delivered by relay h ∈ [H] to the users in Uh
following the MAN scheme [1]. This is done as follows.
Placement: Fix g ∈ [1 : K1 ]. The MDS-coded symbol
K1
shi is partitioned into g−1
non-overlapping and equal-length
h
h
subfiles as si = {si,W : W ⊆ Uh , |W| = g − 1} (recall
|Uh | = K1 for all h ∈ [H]). There are in total


K1
n=H
[subfiles per file].
(12)
g−1
User k ∈ [K] caches shi,W if k ∈ W from all h ∈ Hk (recall
|Hk | = r for all users), for a total of


K1 − 1
[subfiles per file].
(13)
k1 = r
g−2
Delivery: The MAN-like multicast coded message
h
wJ

= ⊕
k∈J

shdk ,J \{k} ,

∀J ⊆ Uh : |J | = g, h ∈ [H],

(14)

Note that there are
 
K1
[subfiles],
g

(16)

multicast coded messages in (14), each of the size of a subfile,
that are delivered from the server to the relays.
Performance:
Each user eventually knows k1 + k2 =

K1
r g−1
subfiles of its desired file (either cached or delivered),

K1
which suffices to recover all the n = H g−1
subfiles of
its desired file because of the (H, r) MDS encoding before
placement, where k1 , k2 and n are defined in (13), (15)
and (12), respectively. Since each multicast coded message
in (14) is simultaneously useful for g users, a coded caching
gain of g is achieved and the required memory size is
M=N

g−1
k1 H
· =N
=: M[8] (g),
n r
K1

k1
M
=
(memory occupancy per file),
N
k1 + k2


k2
M
rR2 =
= 1−
(total load to a user),
k1 + k2
N
k3
Hk3
HR1 =
=
Rrouting (load to the relays),
k1 + k2
Kk2
Kk2
⇐⇒ g =
(coded caching gain),
k3

(18)
(19)
(20)
(21)

where R1 and R2 were defined in (8) and (9), respectively;
notice that Kk2 represents the total number of subfiles decoded
by the users and k3 is the number of subfiles actually sent.
Limitation: In [8], the operations at the H relays are
uncoordinated. Indeed, consider the network in Fig. 1 for
g = 2. The scheme in [8] uses an (H, r) = (4, 2) MDS code,
1
2
and the MDS-coded symbols shi,W
and shi,W
are treated as two
“independent” subfiles if h1 6= h2 . For example, among the
MDS subfiles s1i,{1} , s1i,{2} , s1i,{3} , s2i,{1} , s2i,{4} and s2i,{5} ,
each of length is B/6, user 1 caches s1i,{1} and s2i,{1} , which
requires M/N = 2/6. However, s1i,{1} and s2i,{1} can be treated
as a single subfile known / cached by user 1. This observation
is key for the design of the novel proposed schemes.
III. M AIN R ESULT

is delivered from the server to relay h, who then forwards it
to the users in J . User k ∈ [K], thanks to its cache content
and the received multicast coded messages from the relays in
Hk , recovers


K1 − 1
k2 = r
[subfiles per file].
(15)
g−1

k3 = H

where in (17) the factor Hr is the inverse of the rate of the
MDS code used before placement.
In general, the used MDS code has parameters (n, k1 + k2 )
because each users must be able to recover n subfiles from the
available k1 + k2 subfiles; therefore for a scheme where the
delivery is symmetric across users and relays we have

(17)

In this section, we describe the proposed scheme that aims
to overcome the limitation of [8, Theorem 1] as discussed in
the previous section. We have:
Theorem 1. For an (H, r, M, N) combination network, a coded
caching gain g ∈ [1 : K1 ] is achievable with a memory
requirement of


Pr
r Ka −1
a−1
a=1 a
g−2 (−1)
M = N Pr
=: M[Th.1] (g).
(22)
 Ka 
r
a−1
a=1 a g−1 (−1)
Proof: We aim to achieve coded caching gain g. In
other words, every multicast coded message send through the
network is simultaneously useful for g users and each subfile
is cached by at least g − 1 other users.
Placement: We consider the elements of Zg−1 defined
in (4), that is, those subsets of users with cardinality g − 1
(from a ground set of cardinality K1 ) for which there exists at
least one relay connected to all of them. We aim to partition
each MDS-coded file into
n = |Zg−1 | [subfiles per file]

(23)

equal-length subfiles, i.e., fi = (fi,W : W ∈ Zg−1 ), i ∈ [N],
where subfile fi,W is cached by the users in W. Therefore,
each user caches
g−1
k1 =
|Zg−1 | [subfiles per file],
(24)
K

since each subfile is cached by g − 1 users and all users cache
the same amount of subfiles. This placement is considered to
be asymmetric because not all subfiles fi,W for W ⊆ [K] of
cardinality |W| = g − 1 are present.
Delivery: We should create a multicast coded message
similarly to (14) for each subset of users J of the form

1.1

1

0.9

(25)

however, only those J ∈ Zg are such that all users in J
have at least one common connected relay; in order to have
a symmetric delivery scheme from the relays to the users,
we aim to deliver only those multicast coded messages for
J ∈ Zg and consider those for J 6∈ Zg as “erased”, i.e.,
k3 = |Zg |. Therefore, each user eventually decodes
g|Zg |
[subfiles per file],
(26)
k2 =
K
More precisely, for each set J ∈ Zg , we generate the MANlike multicast message
WJ = ⊕ fdk ,J \{k} .

Ratio

0.8

J = W ∪ {k} : W ∈ Zg−1 , k ∈ [K], k 6∈ W;

0.7

0.6
R([9])/R([8])
R[Th. 1]/R([8])
Outer bound
R([2])/R([8])

0.5

0.4

0

5

We then divide WJ into |RJ | non-overlapping and equallength pieces WJ = {WJh : h ∈ RJ }; the server transmits
WJh to relay h ∈ RJ , which then forwards it to users in
J . A user must be able to recover all the n subfiles of its
desired file from the k1 +k2 subfiles that were either cached or
received; this is possible if we divide each file into k1 +k2 nonoverlapping and equal-length pieces and use an (n, k1 + k2 )
MDS code to generate the subfiles before placement, where
k1 , k2 and n are defined in (24), (26) and (23), respectively.
Performance: By the above construction, each multicast
coded message is simultaneously useful for g users, thus a
coded caching gain of g is achieved with cache size (see (18))
M[Th.1] (g)
k1
(g − 1)|Zg−1 |
=
=
,
(28)
N
k1 + k2
(g − 1)|Zg−1 | + g|Zg |


a −1
a −1
By using (6) in (28), and the identity Kg−2
+ Kg−1
=

Ka
g−1 , we obtained the claimed cache size in (22).
A. Comparison between Theorem 1 and [8, Theorem 1]
In the following we show that our scheme in Theorem 1 is
no worse than the scheme in [8]. In general we have:
Corollary 1. For an (H, r, M, N) combination network with
coded caching gain g ∈ [K1 ], M[Th.1] (g) ≤ M[8] (g) with
equality if and only if g ≥ K2 + 2.
Proof: The proof uses the fact that Kr < Kr−1 . . . < K1 .
Indeed, M[Th.1] (g) in (28) is no larger than M[8] (g) in (17) if
|Zg |
K1 −g+1
, which is always true because
|Zg−1 | ≤
g
 
Pr
H Kn
n−1
|Zg |
n=1 n
g (−1)
= Pr
(29)


H
Kn
n−1
|Zg−1 |
n=1 n g−1 (−1)


Pr
H Kn −g+1 Kn
n−1
n=1 n
g
g−1 (−1)
=
(30)


Pr
H
Kn
n−1
n=1 n g−1 (−1)

15

20

Fig. 2: Performance comparison for the combination network
with H = 6, r = 3 and K = N = 20.
Pr

(27)

k∈J

10
M

H K1 −g+1 Kn
n−1
n=1 n
g
g−1 (−1)


Pr
H
Kn
n−1
n=1 n g−1 (−1)

≤
=



K1 − g + 1
.
g



(31)
(32)

Moreover equality holds in (31) if and only if the summations
contain only one term, which is the case if and only if K2 <
K2
g − 1 (i.e., g−1
= 0) as claimed.
B. Numerical Results
In Fig. 2, we compare the performance of the proposed
schemes to those of the schemes with coded cache placement
in [8] and [9]. As an outer bound, we use the same cut-set
idea of [3] (which used the cut-set bound for the shared-link
model originally proposed in [1]) but with the enhanced cutset for the shared-link model in [2]; we denote this outer
bound as R(out)
[2] . In Fig. 2, we plot the ratios R[9] /R[8] (red
line), R[Th.1] /R[8] (blue line), and R(out)
[2] /R[8] (magenta dotted
line), and where R[9] and R[8] are the achievable max-link load
by the schemes in [9] and in [8], respectively. We plot the ratio
of max-link loads as otherwise their difference would not be
clearly visible on a small figure. It can be noted from Fig. 2
that the blue curve, which represents our proposed scheme in
Theorem 1, is never below one, that is, it is never inferior
in performance to the baseline scheme in [8]; however, it is
strictly worse than the performance of our past work in [9]
for M > 12.5 (which is information theoretically optimal for
M ≥ 16). Our proposed scheme in Theorem 1 is information
theoretically optimal for M ≥ 18 and has the same max-link
load as the scheme in [8].
From Fig. 2 we observe a general fenomenon: our scheme
in Theorem 1 (blue line) improves on the scheme in [8] for
small value of g, while our scheme in [9] (red line) improves
on the scheme in [8] for large value of g. Part of our ongoing
work is to design a scheme that combines the advantages
of both Theorem 1 and [9]. In Corollary 1 we proved that

Theorem 1 is equivalent to the scheme in [8] for g ≥ K2 + 2;
this suggests that an improved scheme should consider the
multicasting coding opportunities for groups of K2 users or
more.
Finally, numerical evaluations suggest that the ratio
R(out)
[2] /R[Th.1] is increases as H increases. An interesting open
question is thus if any of the known achievable schemes is to
within a constant factor of a known outer bound.
IV. C ONCLUSIONS
This paper proposed a novel asymmetric coded cache placement scheme for combination networks with end-user-caches,
which aim to create multicasting opportunities across relays.
The proposed schemes were shown to be achieve a max-link
load no larger than the best scheme known in the literature.
ACKNOWLEDGMENT
This work was supported in parts by NSF 1527059 and
Labex DigiCosme.

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] Q. Yan, M. Cheng, X. Tang, and Q. Chen, “On the placement delivery
array design in centralized coded caching scheme,” IEEE Trans. Infor.
Theory, vol. 63, no. 9, pp. 5821–5833, Sep. 2017.
[7] Q. Yan, M. Wigger, and S. Yang, “Placement delivery array design for
combination networks with edge caching,” arXiv:1801.03048, Jan. 2018.
[8] 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.
[9] K. Wan, M. Ji, P. Piantanida, and D. Tuninetti, “On the benefits of
asymmetric coded cache placement in combination networks with enduser caches,” submitted to IEEE Int. Symp. Inf. Theory, Jan. 2018.
[10] J. H. V. Lint and R. M. Wilson, “A course in combinatorics (second
edition),” Cambridge University Press, ISBN 9780521803403, 2001.

