1

Caching with Partial Adaptive Matching
Jad Hachem, Nikhil Karamchandani, Sharayu Moharir, Suhas Diggavi

arXiv:1705.03852v3 [] 12 Dec 2017

Abstract
We study the caching problem when we are allowed to match each user to one of a subset of
caches after its request is revealed. We focus on non-uniformly popular content, specifically when the
file popularities obey a Zipf distribution. We study two extremal schemes, one focusing on coded server
transmissions while ignoring matching capabilities, and the other focusing on adaptive matching while
ignoring potential coding opportunities. We derive the rates achieved by these schemes and characterize
the regimes in which one outperforms the other. We also compare them to information-theoretic outer
bounds, and finally propose a hybrid scheme that generalizes ideas from the two schemes and performs
at least as well as either of them in most memory regimes.

I. I NTRODUCTION
In modern content distribution networks, caching is a technique that places popular content
at nodes close to the end users in order to reduce the overall network traffic. In [3], a new
“coded caching” technique was introduced for broadcast networks. This technique places different
content in each cache, and takes advantage of these differences to send a common coded broadcast
message to multiple users at once. This was shown not only to greatly reduce the network load in
comparison with traditional uncoded techniques, but also to be approximately optimal in general.
In [3] as well as many other works in the literature [4], [5], [6], [7], [8], a key assumption is
that users are pre-fixed to specific caches; see also [9], [10] for a survey of related works. More
precisely, each user connects to a specific cache before it requests a file from the content library.
This assumption was relaxed in [11], [12] where the system is allowed to choose a matching of
users to caches after the users make their requests, while respecting a per-cache load constraint.
In particular, after each user requests a file, any user could be matched to any cache as long
as no cache had more than one user connected to it. In this adaptive matching setup, it was
shown under certain request distributions that a coded delivery, while approximately optimal in
Shorter versions of the results in this paper have appeared in IEEE ISIT 2017 [1] and IEEE ITW 2017 [2].

2

the pre-fixed matching case, is unnecessary. Indeed, it is sufficient to simply store complete files
in the caches, and either connect a user to a cache containing its file or directly serve it from
the server.
The above dichotomy indicates a fundamental difference between the system with completely
pre-fixed matching and the system with full adaptive matching. In this paper, we take a first step
towards bridging the gap between these two extremes. Our contributions are the following.
•

We introduce a “partial adaptive matching” setup in which users can be matched to any
cache belonging to a subset of caches. This can arise when, for instance, only some caches
are close enough to a user to ensure a potential reliable connection. To make matters simple,
we assume that the caches are partitioned into clusters of fixed and equal size, and each
user can be matched to any cache within a single cluster, as illustrated in Fig. 1 and
described precisely in Section II. This setup generalizes both setups considered above: on
one extreme, if each cluster consisted of only a single cache, then the setup becomes the
pre-fixed matching setup of [3]; on the other extreme, if all caches belonged to a single
cluster, then we get back the total adaptive matching setup from [11], [12].

•

Through this setup, we observe a dichotomy between coded caching and adaptive matching
by considering two schemes: one scheme exclusively uses coded caching without taking
advantage of adaptive matching; the other scheme focuses only on adaptive matching and
performs uncoded delivery. We show that the scheme prioritizing coded caching is more
efficient when both the cache memory and the cluster size are small, while the scheme
prioritizing adaptive matching is more efficient in the opposite case (see Theorems 3 and 8).

•

We derive information-theoretic cut-set bounds on the optimal expected rate. These bounds
show that the coded caching scheme is approximately optimal in the small memory regime
and adaptive matching is approximately optimal in the large memory regime (see Theorem 4).

•

For a subclass of file popularities, we propose a new hybrid scheme that combines ideas
from both the coded delivery and the adaptive matching schemes, and that performs better
than both in most memory regimes (see Theorem 5).

In this paper, we consider the relevant case when some files are much more popular than
others. In particular, we consider a class of popularity distributions where file popularity follows
a power law, specifically a Zipf law [13]. This includes the special case when all files are equally

3

Server

W1

· · · WN
files

cache cluster

users

Fig. 1. Illustration of the setup considered in this paper. The squares represent K = 12 caches, divided into three clusters of
size d = 4 caches each, and the circles represent users at these clusters. Dashed arrows represent the matching phase, and solid
arrows the delivery phase. Unmatched users are in gray.

popular, but also encompasses more skewed popularities. We observe a difference in the behavior
of the schemes for two subclasses of Zipf distributions, namely when the Zipf popularities are
heavily skewed (the steep Zipf case) and when they are not heavily skewed (the shallow Zipf
case).
The rest of this paper is organized as follows. Section II precisely describes the problem setup
and introduces the clustering model. Section III provides a preliminary discussion that prepares
for the main results. We divide the main results into Section IV, which focuses on the shallow
Zipf case, and Section V, which focuses on the steep Zipf case. Detailed proofs are given in the
appendices.
II. P ROBLEM S ETUP
Consider the system depicted in Fig. 1. A server holds N files W1 , . . . , WN of size F bits each.
There are K caches of capacity M F bits, equivalently M files, each. The caches are divided
into K/d clusters of size d each, where d is assumed to divide K. For every n ∈ {1, . . . , N }
and every c ∈ {1, . . . , K/d}, there are un (c) users accessing cluster c and requesting file Wn .
We refer to the numbers {un (c)}n,c as the request profile and will often represent the request
profile as a vector u for convenience.
In this paper, we focus on the case where the numbers un (c) are independent Poisson random
variables with parameter ρdpn , where ρ ∈ (0, 1/2) is some fixed constant and p1 , . . . , pN is the
popularity distribution of the files, with pn ≥ 0 and p1 + · · · + pN = 1. Thus pn represents the
probability that a fixed user will request file Wn . We particularly focus on the case where the
files follow a Zipf law, i.e., pn ∝ n−β where β ≥ 0 is the Zipf parameter. Note that the expected
total number of users in the system is ρK.

4

As with standard coded caching setups, a placement phase occurs before the request profile
is revealed during which content related to the files is placed in the caches, and a delivery phase
occurs after the request profile is known during which a broadcast message is sent to all users to
satisfy their demands. In our setup, in addition to the usual placement and delivery phases, there
is an intermediate phase that we call the matching phase. The matching phase occurs before the
delivery phase but after the request profile has been revealed. During the matching phase, each
user is matched to a single cache within its cluster, with the constraint that no more than one
user can be matched to a cache. If there are fewer caches than users in one cluster, then some
users will be unmatched.
For a given request profile u, let Ru denote the rate of the broadcast message required to
deliver to all users their requested files. For any cache memory M , our goal is to minimize
the expected rate R̄ = Eu [Ru ]. Specifically, we are interested in R̄∗ defined as the smallest R̄
over all possible strategies. Furthermore, we assume that there are more files than caches, i.e.,
N ≥ K, which is the case of most interest. We also, for analytical convenience, focus on the
case where the cluster size d grows at least as fast as log K. More precisely, we assume
d ≥ [2(1 + t0 )/α] log K,

(1)

where α = − log(2ρe1−2ρ ) and t0 > 0 is some constant. Note that α > 0. Other than analytical
convenience, the reason for such a lower bound on d is that, when d is too small, the Poisson
request model adopted in this paper is no longer suitable. Indeed, if for example d = 1, then
with high probability a significant fraction of users will not be matched to any cache, leading
to a rate proportional to K even with infinite cache memory.
Finally, we will frequently use the helpful notation [x]+ = max{x, 0} for all real numbers x.
III. P RELIMINARY D ISCUSSION
The setup we consider is a generalization of the pre-fixed matching setup (when d = 1) and
the maximal adaptive matching setup (when d = K). From the literature, we know that different
strategies are required for these two extremes: one using a coded delivery when d = 1, and one
using adaptive matching when d = K.1 Therefore, there must be some transition in the suitable
strategy as the cluster size d increases from one to K.
1

The request model used in the literature when d = 1 is usually not the Poisson model used here. Instead, a multinomial

model is used in which the total number of users is always fixed. As mentioned at the end of Section II, the Poisson model is
not suitable in that case. However, the results from the literature are still very relevant to this paper.

5

The goal of this paper is to study this transition. To do that, we first adapt and apply the
strategies suitable for the two extremes to our intermediate case. These strategies will exclusively
focus on one of coded delivery and adaptive matching, and we will hence refer to them as “Pure
Coded Delivery” (PCD) and “Pure Adaptive Matching” (PAM). In particular, PCD will perform
an arbitrary matching and apply the coded caching scheme from [5], [6], whereas PAM will
apply a matching scheme similar to [11], [12] independently on each cluster and serve unmatched
requests directly, ignoring any coding opportunities. We then compare PCD and PAM in various
regimes and evaluate them against information-theoretic outer bounds.
Regardless of the value β of the Zipf parameter, we find that PCD tends to perform better
than PAM when the cache memory M is small, while PAM is superior to PCD when M is large.
The particular threshold of M where PAM overtakes PCD obeys an inverse relation with the
cluster size d. Thus when d is small, PCD is the better choice for most memory values, whereas
when d is large, PAM performs better for most memory values. This observation agrees with
previous results on the two extremes d = 1 and d = K, and it is illustrated in Fig. 2 and 4 and
made precise in the theorems that follow.
While most of the analysis assumes general values for K, N ≥ K, d (except for (1)), and
M , it will nevertheless be useful to sometimes compare PCD and PAM under the restriction
that these parameters all scale as powers of K. This can provide some high-level insights into
the different regimes where PCD or PAM dominate, while ignoring sub-polynomial factors such
as log N , thus simplifying the analysis. During this polynomial-scaling-with-K analysis—which
we will call poly-K analysis as a shorthand—we will assume that
N = Kν,

ν ≥ 1;

(2a)

d = Kδ,

δ ∈ (0, 1];

(2b)

M = K µ,

µ ∈ [0, 1].

(2c)

We stress again that our results do not make these assumptions, but that this representation
provides a useful way to understand the results.
To proceed, we will separately consider two regimes for the Zipf popularity: a shallow Zipf
case in which β ∈ [0, 1), and a steep Zipf case where β > 1.2
2

The case β = 1 is a special case that usually requires separate handling. We skip it in this paper, and analyzing it is part of

our on-going work.

6

IV. T HE S HALLOW Z IPF C ASE (β < 1)
A. Comparing PCD and PAM when β < 1
The next theorem gives the rate achieved by PCD.
Theorem 1. When β ∈ [0, 1), the PCD scheme can achieve for all M an expected rate of
o
n
N
+
−t
R̄PCD = min ρK, M
− 1 + K√2π0 .
Theorem 1 can be proved by directly applying any suitable coded caching strategy [5], [6],
[7] along with an arbitrary matching phase. The additional K −t0 term represents the expected
number of users that will not be matched to any cache and must hence be served directly from
the server. The derivation of this term is done in Lemma 1 in Appendix A.
The next theorem gives the rate achieved by PAM.
Theorem 2. When β ∈ [0, 1), the PAM scheme can achieve an expected rate of


ρK
if M = O(N/d);
PAM
R̄
=


min ρK, KM e−zdM/N
if M = Ω(N/d),
where z = (1 − β)ρh((1 + ρ)/2ρ) > 0 with h(x) = x log x + 1 − x.
Theorem 2 can be proved using a similar argument to [11]: the idea is to replicate each file
across the caches in each cluster, and match each user to a cache containing its requested file.
The detailed proof is given in Appendix B.
Notice that PAM can achieve a rate of o(1) when dM > Ω(N log N ). Recall that we have
imposed a service constraint of one user per cache in our setup. If we instead allow multiple
users to access the same cache, then it can be shown that a rate of o(1) can be achieved if and
only if dM > (1 − o(1))N . Consequently, the cache service constraint increases this memory
threshold by at most a logarithmic factor.
The rates of PCD and PAM are illustrated in Fig. 2 for the β ∈ [0, 1) case. We can see that
there is a memory threshold M0 , with M0 = Ω(N/d) and M0 = O((N/d) log N ), such that PCD
performs better than PAM for M < M0 while PAM is superior to PCD for M > M0 . Using
a poly-K analysis, we can ignore the log N term and obtain the following result, illustrated in
Fig. 3.

7

PCD
PAM
HCM
lower bound

R̄
ρK

M
N/d

(N/d) log N

N

Fig. 2. Rates achieved by PCD, PAM, and HCM when β ∈ [0, 1), along with information-theoretic lower bounds. HCM is
a hybrid scheme described in Section IV-C, and the lower bounds are presented in Appendix D. This plot is not numerically
generated but is drawn approximately for illustration purposes.

µ
ν

PAM

µ=ν−δ
(M = N/d)

PCD
ν−1

δ
0

1

Fig. 3. The scheme among PCD and PAM that performs better than the other when β ∈ [0, 1), in terms of polynomial scaling
in K. Here N = K ν , d = K δ , and M = K µ . Notice that the values in the figure are all independent of β; the behavior is
therefore the same for all β < 1.

Theorem 3. When β ∈ [0, 1), and considering only a polynomial scaling of the parameters with
K, PCD outperforms PAM in the regime
µ ≤ ν − δ,
while PAM outperforms PCD in the opposite regime, where N = K ν , d = K δ , and M = K µ .
Note that in some cases PCD and PAM perform equally well, such as when µ = ν. However,
these are usually edge cases and most of the regimes in Theorem 3 are such that one scheme
strictly outperforms the other.
Interestingly, under the poly-K analysis, the memory regime where PAM becomes superior
to PCD is the regime where PAM achieves a rate of o(1), for any d.

8

B. Approximate Optimality
In this section, we compare the achievable rates of PCD and PAM schemes to informationtheoretic lower bounds and identify regimes in which PCD or PAM is approximately optimal,
where approximate optimality is defined below.
Definition 1 (Approximate Optimality). We say that a scheme is approximately optimal if it can
achieve an expected rate R̄ such that
R̄ ≤ C · R̄∗ + o(1),
where R̄∗ is the optimal expected rate and C is some constant.
For β ∈ [0, 1), we show the approximate optimality of PCD in the small memory regime
and that of PAM in the large memory regime. When M > Ω((N/d) log N ), it follows from
Theorem 2 that R̄PAM = o(1), and thus PAM is trivially approximately optimal. The following
theorem states the approximate optimality of PCD when M < O(N/d).
Theorem 4. When β ∈ [0, 1) and M < (1 − e−1 /2)N/2d, and for N ≥ 10, the rate achieved
by PCD is within a constant factor of the optimum,
96
R̄PCD
∆
.
≤C=
∗
(1 − β)ρ(1 − e−1 /2)2
R̄
Note that the constant C is independent of K, d, N , and M .
Theorem 4 can be proved by first reducing the β ∈ [0, 1) case to a uniform-popularities setup,
and then deriving cut-set lower bounds on the optimal expected rate. Proof details are given in
Appendix D.
C. A Hybrid Coding and Matching (HCM) Scheme
So far, we have seen that the two memory regimes M < O(N/d) and M > Ω((N/d) log N )
require very different schemes: the former requires PCD and the latter requires PAM. The PCD
scheme prioritizes coded delivery at the expense of losing the benefits of adaptive matching,
while the PAM scheme leverages adaptive matching but limits itself to an uncoded delivery. In
this section, we introduce a universal scheme that generalizes ideas from both PCD and PAM.
It is a hybrid scheme that combines the benefits of adaptive matching within clusters with the
coded caching gains across clusters. For this reason, we call this scheme Hybrid Coding and
Matching (HCM).

9

The main idea of HCM is to partition files and caches into colors, and then apply a coded
caching scheme within each color while performing adaptive matching across colors. More
precisely, each color consists of a subset of files as well as a subset of the caches of each
cluster. When a user requests a file, the user is matched to an arbitrary cache in its cluster, as
long as the cache has the same color as the requested file. For each color, a coded transmission
is then performed to serve all the matched users requesting a file from said color. Unmatched
users are served directly by the server. This allows us to take advantage of adaptive matching
within each cluster as well as obtain coded caching gains across the clusters.
The rate achieved by HCM is given in the following theorem. It is illustrated in Fig. 2 along
with the rates of PCD and PAM for comparison.
Theorem 5. For any β ∈ [0, 1), HCM can achieve a rate of

o
n
−t

min ρK, N − χ + K
√
if M ≤ bN/χc;
M
2π
R̄HCM =
−t

K
√
if M ≥ dN/χe,
2π
where χ = bαd/(2(1 + t) log K)c, for any t ∈ [0, t0 ].
While the expression for R̄HCM given in the theorem is rigorous, we can approximate it here
for clarity as
R̄

HCM


≈ min ρK,

h

N
M

−Θ



d
log K

i+


+ o(1) .

The proof of Theorem 5 is given in detail in Appendix E, where we provide a rigorous
explanation of the HCM scheme.
We will next compare HCM to PCD and PAM. Notice from Fig. 2 that HCM is strictly better
than PCD for all memory values. In fact, there is an additive gap between them of about d/ log K
for most memory values, and an arbitrarily large multiplicative gap when M > (N/d) log K
where HCM achieves a rate of o(1). Consequently, HCM is approximately optimal in the regime
where PCD is, namely when M < N/2d.
Furthermore, HCM is significantly better than PAM in the M < N/d regime: there is a
multiplicative gap of up to about K/d between their rates in that regime. Moreover, HCM
achieves a rate of o(1) when M > (N/d) log K. It is thus trivially approximately optimal in that
regime, which includes the regime where PAM is.

10

PCD
PAM

R̄
1

Kβ

M
1

(K/dβ ) β−1

1

min{N, K β−1 }/d

1

min{N, K β−1 }

Fig. 4. Rates achieved by PCD and PAM in the β > 1 case. Again, this plot is not numerically generated but is drawn
approximately for illustration purposes.

V. T HE S TEEP Z IPF C ASE (β > 1)
A. Comparing PCD and PAM when β > 1
When β > 1, we restrict ourselves to the case where d is some polynomial in K for
convenience. The following theorems give the rates achieved by PCD and PAM, illustrated
in Fig. 4.
Theorem 6. When β > 1, the PCD scheme can achieve an expected rate of



K 1/β
if 0 ≤ M < 1;


h
i
+
−t
(KM )1/β
R̄PCD =
−
1
+ K√2π0 if 1 ≤ M < N β /K;
M




 N − 1+ + K√−t0
if M ≥ N β /K.
M
2π
Much like Theorem 1, Theorem 6 follows from directly applying the coded caching strategy
from [5], [6]. Again, the K −t0 term represents the expected number of unmatched users, derived
in Lemma 1 in Appendix A.
Theorem 7. When β > 1, the PAM scheme can achieve an expected rate of
 
o
n
1

K
O min
β
,K
if M = O(N/d);
(dM )β−1
R̄PAM =


N
o(1)
if M = Ω N log
.
d
The proof of Theorem 7, given in Appendix C, follows along the same lines as [12] and
involves a generalization from d = K to any polynomial d = K δ , 0 < δ ≤ 1. The idea is to
replicate the files across the caches in the cluster, placing more copies for the more popular files,
and match the users accordingly.

11

µ
ν

νβ − 1

PAM
µ=ν−δ
(M = N/d)
PCD

µ = (1 − βδ)/(β − 1)

ν−1

δ
0

1 − ν(β − 1)

1/β

1

Fig. 5. The scheme among PCD and PAM that performs better than the other when β > 1 and ν < 1/(β − 1), in terms of
polynomial scaling in K. Here N = K ν , d = K δ , and M = K µ .

As with the β ∈ [0, 1) case, we notice that PCD is the better choice when M is small,
while PAM is the better choice when M is large. In fact, by comparing the rate expressions
in Theorems 6 and 7 using a poly-K analysis, we obtain the following theorem describing the
regimes for which either of PCD or PAM is superior to the other. The theorem is illustrated in
Fig. 5 and proved at the end of this subsection.
Theorem 8. When β > 1, and considering only a polynomial scaling of the parameters with
K, PCD outperforms PAM in the regime
µ ≤ min {ν − δ, (1 − βδ)/(β − 1)} ,
while PAM outperforms PCD in the opposite regime, where N = K ν , d = K δ , and M = K µ .
When comparing Theorems 3 and 8, we notice that the case β > 1 has the added constraint
µ < (1 − βδ)/(β − 1) for the regime where PCD is superior to PAM, indicating that there are
values of d for which PAM is better than PCD for a larger memory regime under β > 1 as
compared to β ∈ [0, 1). This is represented in Fig. 5 by the additional line segment joining
points (1 − ν(β − 1), νβ − 1) and (1/β, 0). As β approaches one from above, this line segment
tends toward the segment joining points (1, ν − 1) and (1, 0). With it, the regime in which PCD
is better than PAM grows until it becomes exactly the regime shown in Fig. 3 for β ∈ [0, 1). In
other words, when β > 1 and as β → 1+ , the regimes in which PCD or PAM are respectively

the better choice become the same regimes as in the β ∈ [0, 1) case. This seemingly continuous
transition suggests that, when β = 1, the system should behave similarly to β ∈ [0, 1), i.e.,

12

Fig. 3, at least under a poly-K analysis.
Proof of Theorem 8: Recall that we are only focusing on a poly-K analysis. We will
define σ PCD and σ PAM to be the exponents of K in R̄PCD and R̄PAM , respectively, i.e., R̄PCD =
Θ(K σ

PCD

) and similarly for PAM. Our goal is to compare σ PCD to σ PAM . We can break the

proof down into two main cases plus one trivial case. It can help the reader to follow these cases
in Fig. 5.
The trivial case is when the total cluster memory dM is large, specifically µ+δ > min{ν, 1/(β−
1)}. From Theorem 7, the PAM rate is then o(1), hence σ PAM = 0. Therefore, PCD cannot
perform better than PAM in this case.
In what follows, we assume µ + δ < min{ν, 1/(β − 1)}. We can write the exponents of the
rates of PCD and PAM as
σ PCD = min {[1 − (β − 1)µ]/β , ν − µ} ;
σ PAM = min {1/β , 1 − (β − 1)(δ + µ)} .
Notice that we always have σ PCD ≤ [1 − (β − 1)µ]/β ≤ 1/β, and hence it is sufficient to
compare σ PCD to the second term in the minimization in σ PAM . In other words,
σ PCD < σ PAM ⇐⇒ σ PCD < 1 − (β − 1)(δ + µ).
Furthermore, we can write σ PCD as


[1 − (β − 1)µ]/β
PCD
σ
=

ν − µ

if µ ≤ νβ − 1;
if µ ≥ νβ − 1.

For this reason, we split the analysis into a small and a large memory regimes, with the threshold
µ ≶ νβ − 1.

Large memory: µ > νβ − 1: This case is only possible when ν < 1/(β − 1) because we

always have µ ≤ ν. Here, PCD achieves σ PCD = ν − µ. The constraints on µ imply:
µ<ν−δ

=⇒ 1 − (β − 1)(δ + µ) > 1 − ν(β − 1);

µ > νβ − 1 =⇒ ν − µ < ν − (νβ − 1) = 1 − ν(β − 1).
Combining the two inequalities yields
1 − (β − 1)(δ + µ) > 1 − ν(β − 1) > ν − µ,
and hence σ PCD < σ PAM .

13

Small memory: µ < νβ − 1: In this case, PCD always achieves σ PCD = [1 − (β − 1)µ]/β.
Using some basic algebra, we can show that [1 − (β − 1)µ] /β < 1 − (β − 1)(δ + µ), i.e.,
σ PCD < σ PAM , if and only if µ < (1 − βδ)/(β − 1).

B. Approximate Optimality
1

When β > 1 we know from Theorem 7 that R̄PAM = o(1) is achieved for M > Ω(min{N log N, K β−1 }/d),
and thus PAM is trivially approximately optimal in that regime as per Definition 1.
When the memory is smaller, proving approximate optimality of PCD is more difficult than
in the β ∈ [0, 1) case. Indeed, applying a similar technique here to the shallow-Zipf case is
insufficient. This is partly because the number of distinct requested files is close to the number
of caches K when β < 1, but becomes much smaller than K when β > 1.
A PPENDIX A
E XPECTED N UMBER OF U NMATCHED U SERS
In this appendix, we will derive upper bounds on the expected number of unmatched users
when using PCD, stated in Lemma 1 below. The proof of this lemma requires Lemma 2, also
stated below, which gives a more general result on the number of unmatched users.
Lemma 1. When using PCD, the expected number of unmatched users is no greater than
√
K −t0 / 2π.
Lemma 2. If Y ∼ Poisson(γm) users must be matched with m ≥ 1 caches, where γ ∈ (0, 1),
then the expected number of unmatched users U = [Y − m]+ is bounded by
m
1
E[U ] ≤ √ · m · γe1−γ .
2π
Lemma 2 is proved in Appendix F.
Proof of Lemma 1: In PCD, at each cluster c we are attempting to match a number of users
Y (c) ∼ Poisson(ρd) to exactly d caches. Let U (c) denote the number of unmatched users at
P
cluster c, and let U 0 = c U (c) be the total number of unmatched users. The matching in PCD
is arbitrary, and so any user can be matched to any cache. Consequently, U (c) = [Y (c) − d]+
and we can apply Lemma 2 directly to obtain
0

E[U ] =

K/d
X
c=1

E[U (c)] ≤

d


K
1
1
· √ · d · ρe1−ρ = √ exp log K + d log ρe1−ρ .
d
2π
2π

(3)

14

Note that the function x 7→ xe1−x is strictly increasing for x ∈ (0, 1). Since ρ ∈ (0, 1/2), we
thus get


log ρe1−ρ < log 2ρe1−2ρ = −α < log(1) = 0.
Applying this to (3), we obtain

 (a) 1
1
1
E[U 0 ] ≤ √ exp log K + d log 2ρe1−2ρ ≤ √ exp {log K − (1 + t0 ) log K} = √ K −t0 ,
2π
2π
2π
where (a) uses (1). This concludes the proof.
A PPENDIX B
D ETAILS OF PAM S CHEME FOR β ∈ [0, 1) (P ROOF OF T HEOREM 2)
First, note that it is always possible to unicast from the server to each user the file that it
requested. Since the expected number of users is ρK, we always have R̄PAM ≤ ρK.
In what follows, we focus on the regime M = Ω(N/d). Recall that the number of requests
for file n at cluster c is un (c), a Poisson variable with parameter ρdpn .
In the placement phase, we perform a proportional placement. Specifically, since each cache
can store M files and each cluster consists of d caches, we replicate each file Wn on dn = pn dM
caches per cluster.
In the matching phase, we first construct a fractional matching of users to caches, and then
show that this implies the existence of an integral matching. We construct the fractional matching
by dividing each file Wn into dn equal parts, and then mapping each request for file Wn to dn
requests, one for each of its parts. Each user now connects to the dn caches containing file Wn
and retrieves one part from each cache. This leads to a fractional matching where the total data
served by a cache k in cluster c is less than one file if
X un (c)
≤ 1,
dn
W ∈W
n

(4)

k

where Wk is the set of files stored on cache k. Let h(x) = x log x + 1 − x be the Cramér
transform of a unit Poisson random variable. Using the Chernoff bound and the arguments used
in the proof of [11, Proposition 1], we have that
(
)
X un (c)
Pr
> 1 ≤ e−zdM/N ,
dn
W ∈W
n

k

where z = (1 − β)ρh(1 + (1 − ρ)/2ρ) > 0.

(5)

15

To find a matching between the set of requests and the caches, we serve all requests for files
that are stored on caches for which (4) is violated via the server. For the remaining files, there
exists a fractional matching between the set of requests and the caches such that each request
is allocated only to caches in the corresponding cluster, and the total data served by each cache
is not more than one unit. By the total unimodularity of adjacency matrix, the existence of a
fractional matching implies the existence of an integral matching [14]. We use the Hungarian
algorithm to find a matching between the remaining requests and the caches in the corresponding
cluster.
Let τn be the probability that at least one of the caches storing file Wn does not satisfy (4).
By the union bound, it follows that τn ≤ (KM/N )e−zdM/N . By definition,
R̄

PAM

≤

N
X
n=1

τn ≤ KM e−zdM/N ,

(6)

which concludes the proof of the theorem.
While the above was enough to prove the theorem, we will next provide an additional upper
bound on the PAM rate, thus obtaining a tighter expression.
Let Gc be the event that the total number of requests at cluster c is less than d, and let
T
G = c Gc . Using the Chernoff bound, we have
E[G] ≥ 1 −

K −zd
e ,
d

where z is as defined above. Conditioned on Gc , the number of files that need to be fetched from
the server to serve all requests in the cluster is at most d. The rest of this proof is conditioned
on G.
Let Ec be the event that all caches in cluster c satisfy (4). Using (5) and the union bound, we
have that
Pr{Ec |G} ≥ Pr{Ec } ≥ 1 − de−zdM/N ,
where z is as defined above. Conditioned on Ec , all the requests in cluster c can be served by
the caches. Therefore,
E[R|G] ≤

K/d
X
c=1


d · Pr Ec G ≤ Kde−zdM/N ,

where A denotes the complement of A for any event A.
It follows that
E[R] = E[R|G] Pr{G} + E[R|G] Pr{G} ≤ E[R|G] + N Pr{G} ≤ Kde−zdM/N +

N K −zd
e . (7)
d

16

Using (6) and (7), we obtain
R̄

PAM



N K −zd
−zdM/N
−zdM/N
,
e
≤ min KM e
, Kde
+
d

which is a tighter bound on the PAM rate and implies Theorem 2.
A PPENDIX C
D ETAILS OF PAM S CHEME FOR β > 1 (P ROOF OF T HEOREM 7)
At a high level, the PAM strategy consists in storing complete files in the caches, replicating
the files across different caches, and then matching the users to the cache that contains their
requested file. Users that cannot be matched to a cache containing their file are served directly
from the server.
The above describes PAM strategies very generally; there are many possible schemes for
placement and matching within this class of strategies. In this paper, we adopt for β > 1 a
strategy that performs a knapsack storage (KS) placement phase that is based on the knapsack
problem, and a match least popular (MLP) matching phase in which matching is done for the
least popular files first. We refer to this PAM scheme as KS+MLP.
A. Excess Users
Whatever the strategy, if there are more than d users at a particular cluster, then the excess
users must be unmatched. From Lemma 2, we know that the expected total number of these
excess users across all caches is O(K −t0 ), which is o(1). For the proof of Theorem 7, we will
generally use asymptotic notation for the expected rate. Thus by always serving these users
directly from the server, their contribution to the rate is always o(1). For this reason, we will
make the simplifying assumption in what follows that there are no more than d users at each
cluster.
B. Placement Phase: Knapsack Storage
We split the KS policy into two parts. In the first part, we determine how many copies of each
file will be stored per cluster. In the second part, we determine which caches in each cluster
will store each file.

17

1) KS Part 1: The first part of the knapsack storage policy determines how many caches
in each cluster store each file by solving a fractional knapsack problem. The parameters of the
fractional knapsack problem are a value vn and a weight wn associated with each file Wn , defined
as follows.
•

The value vn of file Wn is the probability that Wn is requested by at least one user in a
cluster,
vn = 1 − (1 − pn )d .

•

The weight wn of file Wn represents the number of caches in which Wn will be stored,
should the policy decide to store it. If we decide to store a file, we would like to make sure
that all requests for that file can be served by the caches, so that it need not be transmitted
by the server. To ensure this, we fix wn to be large enough so that, with probability going
to one as K → ∞, the number of requests for Wn is no larger than wn . We thus choose
the following values for wn :

wn =




d







 1+

if n = 1;

p1
2

ρdpn



d4p1 (log d)2 e






1



if 2 ≤ n ≤ N1 ;
if N1 < n ≤ N2 ;
if N2 < n ≤ N ,

where N1 and N2 are defined as
d1/β
;
N1 =
p1 (log d)2/β

(8a)

N2 = d(1+1/β)/2 .

(8b)

Using the above parameters vn and wn , we solve the following knapsack problem:
maximize
x1 ,...,xN

subject to

N
X

v n xn

n=1
N
X
n=1

wn xn ≤ dM ;

0 ≤ xn ≤ 1, ∀n.

(9)

Then, the number of copies of file Wn that will be present in each cluster is cn = bxn c wn . Note
that cn is hence either zero or wn .

18

Algorithm 1 The Match Least Popular (MLP) matching policy for a fixed cluster.
Require: Number of requests un for file Wn , for each n, at the cluster
Ensure: Matching of users to caches
1:

Set Kn ⊆ {1, . . . , d} to be the set of caches containing file Wn , for each n

2:

Loop over all files from least to most popular:

3:

for n ← N, N − 1, . . . , 1 do

4:

Loop over all requests for file n:

5:

for v ← 1, . . . , un do

6:

if Kn 6= ∅ then

7:

Pick k ∈ Kn uniformly at random

8:

Match a user requesting file Wn to cache k

9:

Cache k is no longer available:
for all n0 ∈ {1, . . . , N } do

10:

Kn0 ← Kn0 \ {k}

11:

end for

12:
13:
14:
15:

end if
end for
end for

2) KS Part 2: The second part of the knapsack storage policy is to determine which caches
store each file. We will focus on one arbitrary cluster, but the same placement is done in each
cluster. To do that, define the multiset S containing exactly cn copies of each file index n. Let us
order the elements of S in increasing order, and call the resulting ordered list (n1 , . . . , nbdM c ).
Then, for each r, we store file Wnr in cache ((r − 1) mod d) + 1 of the cluster.
C. Matching and Delivery Phases: Match Least Popular
In the matching phase, we use the Match Least Popular (MLP) policy, the key idea of which
is to match users to caches starting with the users requesting the least popular files. Algorithm 1
gives the precise description of MLP.
At the end of Algorithm 1, some users will be unmatched, particularly those for which the
condition on line 6 fails. Any file requested by an unmatched user will be broadcast directly
from the server.

19

D. Expected Rate Achieved by KS+MLP
Lemma 3. Let X be a Poisson random variable with mean µ, and let  ∈ (0, 1) be arbitrary.
Then,
Pr {X ≥ (1 + )µ} ≤ e−µh(1+) ,
where h(x) = x log x + 1 − x.
Proof: The lemma follows from the Chernoff bound.
Lemma 4. Recall that un (c) denotes the number of users requesting file Wn from cluster c.
Consider an arbitrary cluster c. Let E1 denote the event that

p1 
un (c) ≤ 1 +
dpn for all 1 ≤ n ≤ N1 ; and
4
un (c) ≤ 2p1 (log d)2
for all N1 < n ≤ N2 ,
where N1 and N2 are as defined in (8). Then,
2

Pr {E1 } = 1 − N e−Ω((log d) ) .
Proof: In what follows, we will ignore for simplicity the index c when it is clear from the
context, e.g., we will write un = un (c). Recall that un is a Poisson random variable with mean
ρdpn .
•

For n ≤ N1 , we have dpn ≥ p1 (log d)2 . Therefore, using Lemma 3, we have for n ≤ N1
o
n

p1 
2
dpn ≤ e−Ω(dpn ) ≤ e−Ω((log d) ) .
Pr un > 1 +
4

•

For N1 < n ≤ N2 , we have dpn < p1 (log d)2 . By defining ũ to be a Poisson variable with

parameter ρp1 (log d)2 > ρdpn , we obtain

(b)


(a)
2
Pr un > 2p1 (log d)2 < Pr ũ > 2p1 (log d)2 ≤ e−Ω((log d) ) ,

In the above, (a) uses the fact that the function λ 7→ Pr{X(λ) > a} defined on λ ∈ [0, a),
where X(λ) is a Poisson variable with parameter λ, is an increasing function of λ, and (b)
follows from Lemma 3.
The statement of the lemma is then obtained by a union bound over all the files.

20

Lemma 5. Let R = {n : xn = 1}, where xn is the solution to the fractional knapsack problem
solved in Appendix C-B1. Let E2 denote the event that, in a given cluster, the MLP policy
matches all requests for all files in R to caches. Then,
2

Pr{E2 } = 1 − N e−Ω((log d) ) .
Proof: Since the MLP policy matches requests to caches starting from the least popular
files, we first focus on requests for files less popular than file WN2 . Because the files follow a
Zipf distribution, we can write
pN2 = p1 N2−β =

p1
.
(β+1)/2
d

Every file less popular than N2 is stored at most once across all the caches in the cluster.
Therefore, under MLP, a request for a file n > N2 will remain unmatched only if the cache
storing that file is matched to another request for another file n0 > N2 . Under the KS placement
policy, the cumulative popularity of all files no more popular than file N2 stored on a particular
cache is less than


β+1
pN2 + pN2 +d + pN2 +2d + · · · = O p1 d− 2 .
Each unmatched request for file n > N2 corresponds to the event that there are at least two
requests for the M files less popular than WN2 stored on a cache. Therefore, by the Chernoff
bound (Lemma 3), the probability that a particular request for a file n > N2 remains unmatched
is at most e−Ω(d) . By the union bound, the probability that at least one request for file n ∈ R
such that n > N2 is not matched by the MLP policy is at most de−Ω(d) .

Next, we focus on the files n ∈ {2, . . . , N2 }. Note that if the KS policy decides to store file
n, it stores it on wn caches. Therefore,
N2
X
n=2

xn w n ≤

N1 l
X
n=2
N1 h
X

N2
m
X


p1 
dpn +
4p1 (log d)2
1+
2
n=N +1
1

N2
i
X


p1 
≤
1+
dpn + 1 +
4p1 (log d)2 + 1
2
n=2
n=N1 +1


p1
≤ 1+
d(1 − p1 ) + 4p1 (log d)2 N2 + N2
2


p1 
≤ 1+
d(1 − p1 ) + Θ d(1+1/β)/2 (log d)2
2
≤ d,

21

for d large enough. Therefore, if files are stored according to KS Part 2, each cache stores at
most one file from the set {2, . . . , N2 }.
Let Kn be the set of caches storing file n in a given cluster. Let E3,k be the event that cache
k ∈ Kn is matched to a user requesting a file n > N2 . A cache will be matched to a user
requesting a file less popular than N2 only if at least one of the files that it stores, among those
that are less popular than N2 , is requested at least once. Since there are at most M such files
on each cache,
Pr{E3,k } ≤ 1 − 1 − O d−(β+1)/2

d

.

For a given constant 0 <  < 1, there exists a d() such that Pr{E3,k } ≤  for all d ≥ d().

For each file n, N1 < n ≤ N2 , let E4,n denote the event that more than 2p1 (log d)2 of the

d4p1 (log d)2 e caches in Kn are matched to users requesting some file n0 > N2 . By the Chernoff
bound for negatively associated random variables [14],
2

Pr{E4,n } = e−Ω((log d) ) .
2

From Lemma 4, we know that with probability at least 1 − N e−Ω((log d) ) , there are less
than (1 + p1 /4)dpn requests for each file 2 ≤ n ≤ N1 . Therefore, with probability at least
2

1 − N e−Ω((log d) ) , all requests for files in R such that 2 ≤ n ≤ N1 are matched to caches by the
MLP policy.
Finally, we now focus on the requests for the most popular file W1 . Recall that if the KS
policy decides to store this file, it will be stored on all caches in each cluster. Since we are
assuming that the total number of requests at each cluster is no greater than d, then even if all
the users requesting files other than W1 are matched, the remaining caches can still be used to
serve all requests for W1 .
E. Expected Rate
2

From Lemma 5, we know that, for d large enough, with probability at least 1 − N e−Ω((log d) ) ,
in a given cluster all requests for the files cached by the KS+MLP policy are matched to caches.
e be the number of files not in R (i.e., that are not cached) that are requested at least once.
Let N
By the union bound over the K/d clusters,
2
2
e ] + K (1 − Pr{E2 }) ≤ E[N
e ] + N K e−Ω((log d)2 ) .
R̄PAM ≤ E[N
d
d

22

After solving the fractional knapsack problem, defined in (9), as a function of N , K, d, β,
and M , we can determine the set R. For a given R, we then have
X

e] =
E[N
1 − (1 − pn )K .
n∈R
/

We hence obtain the following bound on the expected rate:

 !
−β K
X
n
N K 2 −Ω((log d)2 )
R̄PAM ≤
1− 1−
e
.
+
AN
d
n∈R
/

When N and d are polynomial in K, then the second term is o(1), and solving the fractional
knapsack problem yields the result of Theorem 7.
A PPENDIX D
A PPROXIMATE O PTIMALITY (P ROOF OF T HEOREM 4)
In this section, we focus on the case β ∈ [0, 1) to prove Theorem 4. The key idea here is to
show that this case can be reduced to a uniform-popularities case. We will therefore first derive
lower bounds for the uniform-popularities setup (β = 0), and then use that result to derive
bounds for the more general case.
A. The Uniform-Popularities Case (β = 0)
When β = 0, we have the following lower bounds.
Lemma 6. Let s ∈ {1, . . . , K/d}. If N ≥ 10, we have the following lower bound on R̄∗ :


e−1 sdM
1
∗
−
.
R̄ ≥ ρsd 1 −
4
2
N
Before we prove Lemma 6, notice that the lower bounds that it gives are very similar to the
ones in [3]. In fact, by writing the inequality of Lemma 6 as


ρ(1 − e−1 /2)
sdM
∗
R̄ ≥
d · max s 1 −
,
s∈[K/d]
4
(1 − e−1 /2)N
we can use the same argument as in [3] to show


ρ(1 − e−1 /2)
1
(1 − e−1 /2)N
K
R̄ ≥
d·
min
− 1,
4
12
dM
d


ρ(1 − e−1 /2)
(1 − e−1 /2)N
=
min
− d, K .
48
M
∗

(10)

Proof of Lemma 6: First, consider the following hypothetical scenario. Let there be a single
cache of size M 0 , and suppose that a request profile u is issued from users all connected to

23

this one cache. Moreover, assume that we allow the designer to set the cache contents after the
request profile is revealed; thus both the placement and delivery take place with knowledge of
u. If we send a single message to serve those requests, and denote its rate by R0 (M 0 , u), then
a cut-set bound shows that
R0 (M 0 , u) + M 0 ≥ γ(u),

(11)

where γ(u) is the total number of distinct files requested in u.
Since all users share the same resources, if a file can be decoded by one user then it can be
decoded by all. Thus the number of requests for each file is irrelevant for (11), as long as it is nonzero. Furthermore, since both the placement and the delivery are made after the request profile
is revealed, the identity of the requested files is irrelevant. Indeed, if R0 (M 0 , u1 ) > R0 (M 0 , u2 )
for some u1 and u2 such that γ(u1 ) = γ(u2 ), then a simple relabling of the files in u1 can make
it equivalent to u2 , and thus the same rate can be achieved. Consequently, (11) can be rephrased
using only the number of distinct requested files,
e 0 , y) + M 0 ≥ y,
R(M

(12)

e 0 , y) is the rate required to serve requests for y distinct files from one cache of
where R(M
e 0 , γ(u)) for all u. Additionally, it can be seen that
memory M 0 . Note that R0 (M 0 , u) = R(M
e 0 , y) increases as y increases: if y1 < y2 , then we can always add y2 − y1 users to request
R(M
e 0 , y1 ) ≤ R(M
e 0 , y2 ).
new files, and thus achieve a rate of R(M

Let us now get back to our original problem. For convenience, define R̄y = Eu [Ru |γ(u) = y]
for every y. Suppose we choose s ∈ {1, . . . , K/d} different clusters, and we observe the system
over B instances. Over this period, a certain number of users will connect to these clusters and
request files; all other users are ignored. If we denote the resulting request profiles as u1 , . . . , uB ,
P
then the rate required to serve all requests is B
i=1 Rui .
Suppose we relax the problem and allow the users to co-operate. Suppose also that we allow the
placement to take place after all B request profiles are made. This can only reduce the required
rate. Furthermore, this is now an equivalent problem to the hypothetical scenario described at the
beginning of the proof. Therefore, if we denote by ūB the request profile cumulating u1 , . . . , uB ,
we have

B
X
i=1

e
Rui ≥ R0 (sdM, ūB ) = R(sdM,
γ(ūB )).

24

By averaging over the cumulative request profile, we obtain the following bound on any achievable expected rate R̄:
h
i
h
h
ii
e
e
B R̄ ≥ EūB R(sdM,
γ(ūB )) = EYsB EūB R(sdM,
γ(ūB )) γ(ūB ) = YsB
h
i
e
= EYsB R(sdM,
YsB ) ,

(13)

where YsB is a random variable denoting the number of distinct files requested after B instances
at s clusters. Since (13) holds for all achievable rates R̄, it also holds for R̄∗ .
Let us choose B = dN/ρsde. Using Chernoff bounds, we obtain some probabilistic bounds
on the number of requested files YsB . These bounds are given in the following lemma for
convenience; the lemma is proved in Appendix F.
Lemma 7. If Y denotes the number of distinct requested files by users at s clusters over
B = dN/ρsde instances, then, for all  > 0,

−1
−1
Pr Y ≤ (1 − e−1 − )N ≤ e−N D(e +||e ) .
e = (1 − e−1 − )N .
We will now use Lemma 7 to obtain bounds on the expected rate. Define N
From (13), we have
N
h
i X
e
e
Pr{YsB = y} · R(sdM,
y)
YsB ) =
dN/ρsde R̄∗ ≥ EYsB R(sdM,
y=1

≥

N
X
e
y=N

(a)

Pr{YsB

e
e
e)
= y} · R(sdM,
y) ≥ R(sdM,
N

N
X

Pr{Y = y}

e
y=N

(b)


 (c)

e
e ) 1 − e−N D(e−1 +||e−1 ) ≥ (1 − o(1)) (1 − e−1 − )N − sdM ,
≥ R(sdM,
N

e
where (a) uses the fact that R(sdM,
y) can only increase with the number of requested files y,
(b) follows from Lemma 7, and (c) is due to (12).
For a fixed , the 1 − o(1) factor approaches 1 as N grows. More generally, we can lower-

bound it by some constant for a large enough N . For example, if  = e−1 /2, then the term is
larger than 1/2 as long as N ≥ 10. Therefore, we have


−1


1 − e 2 N − sdM
1
e−1 sdM
∗
≥ ρsd 1 −
−
R̄ ≥
2 dN/ρsde
4
2
N
as long as N ≥ 10. More generally, we can approach


1
sdM
(1 − e−1 ) N − sdM
∗
−1
R̄ ≥
≥ ρsd 1 − e −
,
dN/ρsde
2
N
if we allow N to be sufficiently large.

25

B. The General Shallow Zipf Case (β ∈ [0, 1))
First, notice that the popularity of each file is
pn ≥ p N =

N −β (a) (1 − β)N −β
1−β
≥
,
=
1−β
AN
N
N

(14)

where AN is defined in Lemma 8 stated below, and (a) follows from the lemma.
Lemma 8. Let m ≥ 1 be an integer and let β ∈ [0, 1). Define Am =

Pm

n=1

n−β . Then,

m1−β − 1 ≤ (1 − β)Am ≤ m1−β .
Lemma 8 is proved in Appendix F.
Consider now the following relaxed setup. Suppose that, for every file n, there are ũn (c) users
requesting file n from cluster c, where

ũn (c) ∼ Poisson

(1 − β)ρd
N


.

Since (1 − β)ρd/N ≤ pn ρd for all n by (14), the optimal expected rate for this relaxed setup can
only be smaller than the rate from the original setup. Indeed, we can retrieve the original setup
by simply creating Poisson ((pn − (1 − β)/N )ρd) additional requests for file n at each cluster.
Our relaxed setup is now exactly a uniform-popularities setup except that ρ is replaced by
ρ0 = (1 − β)ρ, which is still a constant. Consequently, the information-theoretic lower bounds
obtained in Lemma 6, and inequality (10) that follows it, can be directly applied here, giving
the following lemma.
Lemma 9. When N ≥ 10, the optimal expected rate R̄∗ can be lower-bounded by


(1 − e−1 /2)N
(1 − β)ρ(1 − e−1 /2)
∗
min
− d, K .
R̄ ≥
48
M
When M < (1 − e−1 /2)N/2d, the bound in Lemma 9 can be further lower-bounded by


(1 − β)(1 − e−1 /2)2 ρ
N
∗
R̄ ≥
· min
, ρK .
(15)
96
M
Furthermore, the rate achieved by PCD is upper-bounded by




K −t0
N
N
PCD
−1+ √
≤ min ρK,
.
R̄
≤ min ρK,
M
M
2π
Consequently, combining (15) with (16) gives us the result of Theorem 4.

(16)

26

A PPENDIX E
D ETAILS OF HCM S CHEME (P ROOF OF T HEOREM 5)
In this section, we are mostly interested in the case where K is larger than some constant.
Specifically, we assume
log K ≥ 2gα,

(17)

where g = (31−β − 1)/41−β > 0 is a constant. In the opposite case, we can achieve a constant
rate by simply unicasting to each user the file that it requested.
Let t ∈ [0, t0 ], and let χ = bαgd/(2(1 + t) log K)c. We will partition the set of files into χ
colors. For each color x ∈ {1, . . . , χ}, define Wx as the set of files colored with x. We choose
to color the files in an alternating fashion. More precisely, we choose for each x ∈ {1, . . . , χ}
Wx = {Wn : n ≡ x (mod χ)} .
Notice that |Wx | = bN/χc or dN/χe. We can now define the popularity of a color x as
P
Px =
Wn ∈Wx pn . The following proposition, proved in Appendix F, gives a useful lower
bound for Px .
Proposition 1. For each x ∈ {1, . . . , χ}, we have Px ≥ g/χ.
The significance of the above proposition is that the colors will essentially behave as though
they are all equally popular.
Next, we partition the caches of each cluster into the same χ colors. We choose this coloring
in such a way that the number of caches associated with a particular color is proportional to
the popularity of that color. Specifically, exactly bdPx c caches in every cluster will be colored
with x. This will leave some caches colorless; they are ignored for the entirety of the scheme
for analytical convenience.
We can now describe the placement, matching, and delivery phases of HCM. Consider a
particular color x. This color consists of |Wx | files and bdPx c K/d caches in total. The idea
is to perform a Maddah-Ali–Niesen scheme [3], [15] on each color separately, while matching
each user to a cache of the same color of its requested files. The scheme can be described more
formally with the following three steps.
•

In the placement phase, for each color x we perform a Maddah-Ali–Niesen placement of
the files Wx in the caches colored with x.

27

•

In the matching phase, each user is matched to a cache in its cluster of the same color
as the file that the user has requested. Thus if the user is at cluster c and requests a file
from Wx , it is matched to an arbitrary cache from cluster c colored with color x. For each
cluster-color pair, if there are more users than caches, then some users must be unmatched.

•

In the delivery phase, for each color x we perform a Maddah-Ali–Niesen delivery for the
users requesting files from Wx . Next, each unmatched user is served with a dedicated
unicast message. The resulting overall message sent from the server is a concatenation of
the messages sent for each color as well as all the unicast messages intended for unmatched
users.

Suppose that the broadcast message sent for color x has a rate of Rx . Suppose also that the
number of unmatched users is U 0 . Then, the total achieved expected rate will be
(
)
χ
X
R̄HCM = min ρK,
E[Rx ] + E[U 0 ] ,

(18)

x=1

since ρK can always be achieved by simply unicasting to every user its requested file.
From [15], we know that we can always upper-bound the rate for color x by
+

|Wx |
−1 ,
Rx ≤
M
for all M > 0. Because |Wx | = bN/χc or dN/χe for all x, we obtain


N

−1
if M ≤ bN/χc;

M


X
Rx ≤ 0
if M ≥ dN/χe;




x


(N mod χ) dN/χe − 1
otherwise.
M

(19)

All that remains is to find an upper bound for E[U 0 ]. Let Y (c, x) represent the number of
users at cluster c requesting a file from color x. Since there are bdPx c caches at cluster c with

color x, then exactly U (c, x) = [Y (c, x) − bdPx c]+ users will be unmatched. Thus we can write
U 0 as

0

U =

K/d χ
X
X

U (c, x).

c=1 x=1

Before we proceed, it will be helpful to state the following two results, proved in Appendix F.
Proposition 2. If Y is a Poisson variable with parameter λ, then, for all integers m ≥ 1, the
function λ 7→ Pr{Y = m} is increasing in λ as long as λ < m.

28

Proposition 3. Let Y be a Poisson random variable with parameter λ, and let m ≥ λ. Define
U = [Y − m]+ , i.e., U = 0 if Y < m and U = Y − m if Y ≥ m. Then, E[U ] ≤ m Pr{Y = m}.
Notice that Y (c, x) ∼ Poisson(ρd · Px ), and that the Y (c, x) users must be matched to bdPx c.
e = [Ye (c, x) − bdPx c]+ . Since
For convenience, we define Ye (c, x) ∼ Poisson(2ρ · bdPx c) and U
we have
ρdPx ≤ 2ρ bdPx c ,
i.e., the Poisson parameter of Ye (c, x) is at least the Poisson parameter of Y (c, x), then
∞
∞
X
(a) X
e (c, x)],
E[U (c, x)] =
y · Pr{Y (c, x) = y} ≤
y · Pr{Ye (c, x) = y} = E[U
y=bdPx c

y=bdPx c

where (a) uses Proposition 2.
e (c, x) in order to upper-bound the
This allows us to apply Proposition 3 on Ye (c, x) and U
expectation of U (c, x) by

e (c, x)] ≤ √1 · bdPx c · 2ρe1−2ρ bdPx c .
E[U (c, x)] ≤ E[U
2π
0
Consequently, we get the upper bound on E[U ],
0

E[U ] =

K/d χ
X
X
c=1

K/d χ
X
X 1
bdPx c
√ bdPx c 2ρe1−2ρ
E[U (c, x)] ≤
2π
x=1
c=1 x=1

χ
χ

bdPx c
1 XK
1 X
1−2ρ bdPx c
=√
· bdPx c 2ρe
≤√
Px · K 2ρe1−2ρ
.
2π x=1 d
2π x=1

Isolating part of the term in the sum,
bdPx c


K 2ρe1−2ρ
= exp log K + log 2ρe1−2ρ bdPx c = exp {log K − α bdPx c}




αdg
αdPx (a)
≤ exp log K −
≤ exp log K −
2
2χ


(b)
αdg 2(1 + t)
≤ exp log K −
·
log K = exp {log K − (1 + t) log K}
2
αdg
= K −t ,
where (a) uses Proposition 1, and (b) uses the definition of χ combined with byc ≤ y. We obtain
the final upper bound on the expected number of unmatched users,
χ
1 X
K −t
0
E[U ] ≤ √
Px K −t = √ .
2π x=1
2π

(20)

Finally, we combine (19) and (20) in (18) to obtain the rate expression in Theorem 5, thus
completing its proof.

29

A PPENDIX F
E XTRA P ROOFS
Proof of Lemma 2: Before we prove Lemma 2, we need the following result that pertains
to Poisson variables in general, proved later in the appendix.
Proposition 4. If Y is a Poisson variable with parameter λ, then for all integers m ≥ 1,
E [Y |Y ≥ m] = m Pr{Y = m|Y ≥ m} + λ.
We can now prove Lemma 2. By using Proposition 3 (stated in Appendix E) with λ = γm,
we have
E[U ] ≤ m Pr{Y = m} = m ·

(γm)m e−γm
.
m!

Using Stirling’s approximation, we have
√
√
1
m! ≥ 2πmm+ 2 e−m ≥ 2πmm e−m ,
which yields

m
1
(γm)m e−γm
√
= √ · m · γe1−γ ,
E[U ] ≤ m ·
2πmm e−m
2π

thus concluding the proof.
Proof of Proposition 1: Choose any x ∈ {1, . . . , χ}. Starting with the definition of Px , we
have
Px =

X
Wn ∈Wx

|Wx |−1
|Wx |−1
|Wx |−1
1 X
1 X
χ−β X
−β
−β
pn =
(kχ + x) ≥
(kχ + χ) =
(k + 1)−β
AN k=0
AN k=0
AN k=0

A|Wx | (a) −β |Wx |1−β − 1 (b) −β (N/χ − 1)1−β − 1
≥χ ·
≥χ ·
AN
N 1−β
N 1−β
"


1−β 
1−β #
1
χ 1−β  χ 1−β (c) 1
gα
gα
= · 1−
−
≥
1−
−
χ
N
N
χ
2 log K
2 log K
"
#
1−β  1−β
(d) 1
1
1
g
≥
1−
−
= ,
χ
4
4
χ
= χ−β ·

where (a) uses Lemma 8, (b) uses the fact that |Wx | ≥ bN/χc ≥ N/χ − 1 for all x, (c) uses
the definition of χ as well as N ≥ d and t ≥ 0, and (d) uses (17).
Proof of Proposition 2: Define fm (λ) = Pr{Y = m} when Y is Poisson with parameter
λ, i.e., fm (λ) = λm e−λ /m!. Then,
0
fm
(y) =

 λm−1 e−λ
1
mλm−1 e−λ − λm e−λ =
(m − λ) .
m!
m!

30

0
Consequently, fm
(y) > 0 if and only if λ < m, and hence Pr{Y = m} increases with λ as long

as λ < m.
Proof of Proposition 3: Define V such that V = 0 if Y < m and V = 1 if Y ≥ m. Using
the tower property of expectation,
E[U ] = E [E [U |V ]] = Pr{V = 0}E [U |V = 0] + Pr{V = 1}E [U |V = 1]
(a)

= 0 + Pr{V = 1}E [Y − m|V = 1] = Pr{Y ≥ m}E [Y − m|Y ≥ m]
(b)

= Pr{Y ≥ m} (E[Y |Y ≥ m] − m) = Pr{Y ≥ m} (m Pr{Y = m|Y ≥ m} + λ − m)

(c)

≤ Pr{Y ≥ m} · m Pr{Y = m|Y ≥ m} = m Pr{Y = m},
where (a) uses the definition of U given the different values of V , (b) uses Proposition 4, and
(c) uses λ ≤ m.
Proof of Proposition 4: First notice that
λ Pr{Y = m − 1} = λ ·

λm e−λ
λm−1 e−λ
=
· m = m Pr{Y = m}.
(m − 1)!
m!

(21)

We can now write the conditional expectation as
E [Y |Y ≥ m] =

∞
X
y=m

y·

∞
X
Pr{Y = y}
1
λy e−λ
=
y·
Pr{Y ≥ m}
Pr{Y ≥ m} y=m
y!

∞
X
1
λy−1 e−λ
1
=
λ
=
λ · Pr{Y ≥ m − 1}
Pr{Y ≥ m} y=m (y − 1)!
Pr{Y ≥ m}

λ Pr{Y = m − 1} + λ Pr{Y ≥ m} (a) m Pr{Y = m} + λ Pr{Y ≥ m}
=
Pr{Y ≥ m}
Pr{Y ≥ m}
= m Pr{Y = m|Y ≥ m} + λ,
=

where (a) uses (21)
Proof of Lemma 7: Recall that we are considering s clusters and B = dN/ρsde instances
of the problem. Let Un denote the number of requests for file n by users in these clusters across
the B instances. We can see that Un is a Poisson variable with parameter


ρd
ρsd
N
λ=
· sB =
·
.
N
N
ρsd
Note that λ ≥ 1.
Let Zn be equal to one if Un ≥ 1, i.e., if file n was requested at least once, and equal to zero

otherwise. Thus Zn is a Bernoulli variable with parameter Pr{Un ≥ 1} = 1 − e−λ . Then, the
P
total number of distinct requested files can be written as Y = n Zn .

31

Let  > 0 be arbitrary, and define η = 1 − e−1 − . We can now use the Chernoff bound to
write, for every t > 0,
Pr {Y ≤ ηN } ≤ e

tηN



−tY

·E e



=e

tηN

·

N
Y



E e−tZn .

n=1

The expression inside the product is


E e−tZn = e−λ · 1 + (1 − e−λ ) · e−t = e−λ (1 − e−t ) + e−t
≤ e−1 (1 − e−t ) + e−t = e−1 + e−t (1 − e−1 ),
where the inequality is due to λ ≥ 1 and the fact that the function λ 7→ e−λ (1 − e−t ) decreases
as λ increases, for all t > 0. Consequently,

N
Pr {Y ≤ ηN } ≤ etη · e−1 + e−t (1 − e−1 )
.
By choosing t such that
et =

1 − e−1
e−1 + 
·
,
e−1
1 − (e−1 + )

we get
h
iN
−1
−1
−1
−1
Pr {Y ≤ ηN } ≤ e−D(e +||e ) = e−N D(e +||e ) ,
which concludes the proof.
Proof of Lemma 8: To prove the lemma, we will relate the sum Am =

P

n

n−β with the

corresponding integral, which can be evaluated as a closed-form expression.
Let f be any decreasing function defined on the interval [k, l] for some integers k and l. Then,
we can bound the integral of f by
l
X
n=k+1

f (n) ≤

Z

l

k

f (x) dx ≤

l−1
X

f (n).

n=k

Rearranging the inequalities, we get the equivalent statement that
Z l
Z l
l
X
f (l) +
f (x) dx ≤
f (n) ≤ f (k) +
f (x) dx.
k

Recall that Am =

Pm

n=1

−β

n

(22)

k

n=k

. Thus we can apply (22) with f (x) = x−β , k = 1, and l = m.

Since we know that
Z
1

m

x−β dx =

m1−β − 1
,
1−β

32

this implies, using (22),
m−β +

m1−β − 1
m1−β − 1
≤ Am ≤ 1 +
1−β
1−β
1−β
1−β
m
m
−1
≤ Am ≤
,
1−β
1−β

which concludes the proof.
R EFERENCES
[1] J. Hachem, N. Karamchandani, S. Moharir, and S. Diggavi, “Coded caching with partial adaptive matching,” in 2017 IEEE
International Symposium on Information Theory (ISIT), June 2017, pp. 2423–2427.
[2] ——, “Caching with partial matching under Zipf demands,” in 2017 IEEE Information Theory Workshop (ITW), October
2017.
[3] M. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” IEEE Trans. Inf. Theory, vol. 60, no. 5, pp. 2856–2867,
May 2014.
[4] U. Niesen and M. A. Maddah-Ali, “Coded caching with nonuniform demands,” IEEE Transactions on Information Theory,
vol. 63, no. 2, pp. 1146–1158, Feb 2017.
[5] M. Ji, A. M. Tulino, J. Llorca, and G. Caire, “On the average performance of caching and coded multicasting with random
demands,” in Proc. IEEE ISWCS, Aug. 2014.
[6] J. Zhang, X. Lin, and X. Wang, “Coded caching under arbitrary popularity distributions,” in Proc. ITA, Feb. 2015.
[7] J. Hachem, N. Karamchandani, and S. N. Diggavi, “Coded caching for multi-level popularity and access,” IEEE Transactions
on Information Theory, vol. 63, no. 5, pp. 3108–3141, May 2017.
[8] ——, “Multi-level coded caching,” in Proc. IEEE ISIT, Jun. 2014.
[9] M. A. Maddah-Ali and U. Niesen, “Coding for caching: fundamental limits and practical challenges,” IEEE Communications
Magazine, vol. 54, no. 8, pp. 23–29, August 2016.
[10] G. Paschos, E. Bastug, I. Land, G. Caire, and M. Debbah, “Wireless caching: technical misconceptions and business
barriers,” IEEE Communications Magazine, vol. 54, no. 8, pp. 16–22, August 2016.
[11] M. Leconte, M. Lelarge, and L. Massoulié, “Bipartite graph structures for efficient balancing of heterogeneous loads,”
SIGMETRICS Perform. Eval. Rev., vol. 40, no. 1, pp. 41–52, Jun. 2012.
[12] S. Moharir and N. Karamchandani, “Content replication in large distributed caches,” arXiv:1603.09153 [cs.NI], Mar. 2016.
[13] L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker, “Web caching and Zipf-like distributions: evidence and implications,”
in Proc. IEEE INFOCOM, 1999, pp. 126–134.
[14] A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency.

Springer, 2003.

[15] M. A. Maddah-Ali and U. Niesen, “Decentralized coded caching attains order-optimal memory-rate tradeoff,” IEEE/ACM
Trans. Netw., vol. 23, no. 4, pp. 1029–1040, Aug 2015.

