1

Coded Load Balancing in Cache Networks
Mahdi Jafari Siavoshani, Member, IEEE, Farzad Parvaresh,
Ali Pourmiri, Seyed Pooya Shariatpanahi

arXiv:1707.09757v1 [] 31 Jul 2017

Abstract
We consider a cache network consisting of storage-enabled servers forming a distributed content delivery
scenario. Each incoming content request, arriving uniformly at random to these servers, will be redirected to one
or more responsible servers for that request. While assigning each request to its nearest available replica seems to
be a reasonable solution, specifically in terms of communication cost, it will result in overloaded servers. Thus,
alternatively, we investigate a coded scheme which will address this problem. In this scheme, coded chunks of
original files are stored in servers based on the files popularity distribution, which we consider to be Zipf. Then,
upon each request arrival, by delivering enough coded chunks to the request origin, the request can be decoded.
Specifically, we show that if n requests are assigned to n servers based on the proposed coded scheme, the
maximum load of servers will be Θ(1), while in the nearest replica strategy the maximum load is Θ(log n). More
surprisingly, this coded scheme will have the same communication cost performance as the nearest replica strategy,
asymptotically. Finally, our numerical results show that the coded scheme surpasses the uncoded one even in
non-asymptotic regimes.

Keywords
Distributed Caching Servers, Content Delivery Networks, Request Routing, Load Balancing, Communication Cost, Balls-into-Bins, Randomized Algorithms.
I. I NTRODUCTION
The main objective of a Content Delivery Network (CDN) is fulfilling customers content requests by
forwarding these requests to distributed caching servers. This will relieve congestion from the original
servers of the contents, especially during flash crowds. Achieving this goal requires careful load balancing
in request assignment strategies so that none of the distributed caching servers becomes overloaded. This
issue, i.e., load balancing in CDNs, has been the focus of many research works such as [1]–[6].
Load Balancing in CDNs can be managed either in a centralized manner by an authority which has
access to full network state information, or in a distributed way where the assignment is done in the client
side. While centralized schemes have good performance in terms of load balancing and communication
cost, they are not scalable and are prone to single node failures [7]. Thus, distributed schemes have
attracted much more attention both in industry and academia [1], [8]–[10].
Every load balancing scheme should manage two metrics when assigning requests to caching servers.
The first metric is the communication cost which is the distance of the assigned server to the request
origin. Obviously, in terms of this metric alone, the best scheme is the one which assigns each request
to the nearest server that has cached the content. We call this scheme as the nearest replica strategy.
The second metric is the maximum load incurred to the servers. Since in the Nearest Replica strategy the
current load of servers is not considered when assigning requests, this will result in overloaded servers. On
the other hand, if on each assignment, the request is assigned to less loaded servers, this may incur high
The authors’ names appear in alphabetical order.
M. Jafari Siavoshani is with the Department of Computer Engineering, Sharif University of Technology, Tehran, Iran (email: mjafari@sharif.edu).
F. Parvaresh is with the Department of Electrical Engineering, University of Isfahan, Isfahan, Iran (email: f.parvaresh@eng.ui.ac.ir) and
also School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box:1395-5746, Tehran, Iran. F. Parvaresh was
supported by a grant from IPM (No. 95680425).
A. Pourmiri is with the Department of Computer Engineering, University of Isfahan, Isfahan, Iran. (email: a.pourmiri@comp.ui.ac.ir).
S. P. Shariatpanahi is with the School of Computer Science, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran (email:
pooya@ipm.ir).

2

communication cost. Thus, managing this fundamental trade-off is a core issue in load balancing schemes
[11]–[13]. The authors in [14] follow a theoretical framework to analyze this trade-off and propose a load
balancing scheme benefiting from the power of two choices. Also, in [15], a queuing model has been
proposed to investigate the above trade-off for several proximity-aware schemes.
In all the above works no form of coding is exploited in the cache content placement or content delivery
phases. In other words, in above schemes, each file is cached and delivered in its raw uncoded form. In
contrast, in this paper we propose to cache coded chunks of each file in distributed caching servers to
improve load balancing performance of the network. This coded chunks can consist of random linear
combinations of the original file chunks, or can be constructed via more sophisticated fountain codes. In
the delivery phase each request is distributed among a number of close servers which have cached the
corresponding coded chunks. Then the requester can decode the whole file if it receives enough coded
chunks.
√
√
In particular, we consider the network topology to be a n × n Grid. In this setup, we show that our
proposed coded scheme will result in asymptotically the same communication cost as the Nearest Replica
strategy under the Zipf file popularity distribution, in large networks. Surprisingly, we prove that this
scheme will reduce the maximum load of servers from Θ(log n) in the Nearest Replica strategy to O(1)
if each file is divided into Θ(log n) chunks. This means that in the delivery phase every request should
be satisfied by Θ(log n) servers, each providing a coded chunk to the requester.
Related Work
Using coding in content delivery scenarios has been proposed in previous works as following. The
authors in [16] and [17] consider the benefit of using network coding in a P2P based scenario and
VANETs, respectively. Also, [18] uses LT1 codes to reduce cache pollution which improves network
performance. Moreover, [19] considers the effect of coding on the multiple multicast problem. Interested
reader can also see [20] which is a good review on the role of network coding for multimedia delivery.
On another line of research, the in-network caching idea has been proposed to relieve network congestion. The authors in [21] investigate optimal coded/uncoded cache content placement for minimizing
delivery delay in wireless content delivery scenarios. Also, the pioneering work [22] introduces the concept
of coded content delivery from an information theoretic perspective.
In contrast to all aforementioned researches, our paper is the first analytical work which analyzes the
role of coding in load balancing scenarios. We derive closed-form asymptotic results for the impact of
coding on the communication cost and maximum load of cache networks. Furthermore, we investigate
our findings in finite size networks by extensive simulations.
The rest of the paper is organized as follows. Our system model and performance metrics are introduced
in Section II. Section III presents our asymptotic analysis of the uncoded load balancing scenario. Then,
our proposed coded scheme is presented in Section IV and its maximum load and communication cost
are asymptotically analyzed. Next, we discuss practical aspects of our proposal in Section V. Then, in
Section VI numerical results for medium-sized networks are presented. Finally, the paper is concluded in
Section VII.
II. S YSTEM M ODEL
A. Notation
Throughout the paper, with high probability (w.h.p.) refers to an event that happens with probability
1 − 1/nc , as n → ∞, for some constant c > 0. Let G = (V, E) be a graph with vertex set V and edge set
E. For u ∈ V let d(u) denote the degree of u in G. For every pair of nodes u, v ∈ V, dG (u, v) denotes the
length of a shortest path from u to v in G. The neighborhood of u at distance r is defined as
Br (u) , {v : dG (u, v) ≤ r and v ∈ V(G)} .
1 Luby

Transform.

3

For a set A we use Ā to denote its complement. To show the complement of an event E we use ¬E. We
use Po(λ) to denote the Poisson distribution with parameter λ, and H(X) denotes the entropy of random
variable X.
For asymptotic notation, we use g(n) = O( f (n)) if there exist c and n0 such that for n > n0 we
have g(n) < c f (n). In this case we also write f (n) = Ω(g(n)). Moreover, we write g(n) = o( f (n)) if
limn→∞ g(n)/ f (n) = 0. In this case one can also write f (n) = ω(g(n)).
B. Problem Setting
We consider a cache network consisting of n caching
√ servers (also called cache-enabled nodes) and
√
edges connecting neighboring servers forming a n × n grid. Thus, direct communication is possible
only between adjacent nodes, and other communications should be carried out in a multi-hop fashion.
Remark 1. Throughout the paper, for the sake of presentation clarity, we may consider a torus with n
nodes. This helps to avoid boundary effects of the grid and all the asymptotic results hold for the grid as
well.
Suppose that the cache network is responsible for handling a library of K files W = {W1, . . . , WK },
each of size F bits, whereas the popularity profile follows a known distribution P = {p1, . . . , pK }.
The network operates in two phases, namely, cache content placement and content delivery. In the
cache content placement phase, each node i caches Zi , Ψi (W1, . . . , WK ) such that H(Zi ) ≤ M F where
M is the cache size of each node.
Consider a time block during which n files are requested from the servers sequentially. The server of
each request is chosen uniformly at random from all n servers. Let Di denote the number of requests
(demands) arrived at server i. Then for large n we have Di ∼ Po(1) for all 1 ≤ i ≤ n.
For the library popularity profile P, we consider Zipf distribution with parameter γ ≥ 0, where the
request probability of the i-th popular file is inversely proportional to its rank as follows
1/i γ
, i = 1, . . . , K,
pi =
K
Í
γ
1/ j
j=1

which has been confirmed to be the case in many practical applications [23], [24].
In the content delivery phase, suppose Server i has requested a set of files Wi , {Wdi,1, . . . , Wdi,Di }
where di, j is the file index of jth request of Server i. In order to satisfy demand Wdi, j , a set of messages
( j)
( j)
Ml→i for l ∈ {1, . . . , n} can be sent from other servers to Server i where Ml→i , which is a function
of Zl , is the message sent from Server l to Server i to satisfy jth request of Server i. Then we say
that
decode the request Wdi, j if there exists a decoding function Φ(·) such that
 Server i can successfully

( j)

( j)

Φ M1→i, . . . , Mn→i, Zi = Wdi, j .
For a given cache content placement, a delivery strategy is defined as follows.

Definition 1 (Delivery Strategy). By assuming full knowledge of cache contents of all then servers,
o n and
(
j)
n , the Delivery Strategy determines the message sets M
for a given set of file requests {Wi }i=1
for
l→i l=1
all j ∈ [1 : Di ] and i ∈ [1 : n].
Now, for each strategy2 , we define the following metrics.
Definition 2 (Communication Cost and Maximum Load).
• The communication cost (per request) of a strategy is defined as follows


1 Õ Õ Õ
( j)
C,
dG (l, i)H Ml→i .
nF
l∈[1:n] i∈[1:n] j∈[1:Di ]

2 From

here on, we use the terms “strategy” and “delivery strategy” alternatively.

4

•

The maximum load of a strategy is also defined as follows


Õ Õ
1
( j)
L,
max
H Ml→i .
F l∈[1:n]
i∈[1:n] j∈[1:Di ]

It should be noted that since file requests are random, C and L are random variables in the above
definitions.
III. U NCODED L OAD BALANCING
In this section, we assume that no coding is used in the cache content placement and delivery phases. In
the cache content placement, each user saves M files from the library randomly with the same distribution
as the library popularity profile P. In other words, for the content of user i cache we have

Zi = Ψi (W1, . . . , WK ) = Wci,1, . . . , Wci, M ,
where Wci, j is the j-th file cached at user i in the placement phase and ci, j ∈ {1, . . . , K } are sampled from
the distribution P.
In the second phase, upon each request arrival, we should assign a node to serve that request. The
simplest scheme, formally defined as follows, is to assign the nearest node, which has cached the
corresponding file.
Definition 3 (Nearest Replica Strategy). In this strategy each request is assigned to the nearest node –in
the sense of the graph shortest path distance– which has cached the requested file. If there are multiple
choices ties are broken randomly.
The Nearest Replica strategy results in the minimum communication cost, without trying to balance-out
servers’ loads. As shown in [14], the communication cost of this strategy is given in Theorem 1.
√
√
Theorem 1 (Uncoded Communication Cost [14]). For a grid network of n × n, under Zipf popularity
distribution with parameter γ, if the cache size is M = Θ(1) and number of files is K, we have

p


:
0 ≤ γ < 1,
Θ K/M




 p


Θ K/M log K :
γ = 1,




 

√
E [C] = Θ K 1−γ/2 / M
:
1 < γ < 2,
(1)



√ 


:
γ = 2,
Θ log K/ M



 √ 



:
γ > 2.
 Θ 1/ M

The main point of Theorem 1 is the effect of Zipf parameter γ on the communication cost. For example
for small values of gamma, i.e., 0 ≤ γ < 1, we have the largest communication cost the same as the
uniform popularity distribution captured by γ = 0. By enlarging γ we have more skew in file request
popularity, which will in turn reduce communication cost. That is a consequence of the cache placement
strategy, i.e., cache more popular files with higher probability.
Furthermore, the maximum load of this strategy is stated in the following theorem.
√
√
Theorem 2 (Uncoded Maximum Load [14]). For a grid network n × n, under the uniform popularity
distribution, the maximum load of the network is as follows.
(a) If number of files K = n1− (for some constant 0 <  < 1), and size of caches M = Θ(1), then the
maximum load L is Θ(log n) w.h.p.
(b) If number of files K = n and size of caches M = nα (for some 0 < α < 1/2), then the maximum load
L is in the interval [Ω(log n/log log n), O(log n)] w.h.p.

5

Simply put, Theorem 2 says that the Nearest Replica strategy will result in a load imbalance of order
log n. The intuition behind this result is based on the classical balls and bins problem as follows. If you
have n bins and put n balls uniformly at random into these bins, the most loaded bin has almost Θ(log n)
balls [25]. Also as stated in [14], Theorem 2 can be extended to Zipf distribution, as we cache files at
the placement phase with the same distribution P of file request popularity at the delivery phase. This
will make the load imbalance inside the network insensitive to the choice of P.
IV. C ODED L OAD BALANCING
In this section, we consider a coded cache placement using random linear coding, e.g., Fountain-like
codes [26]–[28]. Let us first take each file W k of F bits, partition it into ` equal-sized chunks, i.e., W k(r)
where r ∈ [1 : `], each of F/` bits. Then, we define a random linear operator L as
L(W k ) ,

Õ̀

αr W k(r),

(2)

r=1

where αr ’s are chosen uniformly at random over a finite field Fq , with q = Θ(F/`), and the summation
is in Fq . Moreover, we assume that each use of the operator L is independent of other instances.
In the cache content placement phase, each node stores `M coded chunks of the files according to the
popularity distribution P as explained in Algorithm 1.
Algorithm 1 Coded Cache Content Placement for Server i
Require: `, M, P, and W
1: repeat
2:
Sample k according to P
3:
Append L(W k ) to cache Zi
4: until Server i’s cache is full
In the content delivery phase, we assume n requests arrive uniformly at random at network nodes. Let
us consider Node i which has Po(1) requests, i.e., Di ∼ Po(1). For satisfying each request, ` nearest coded
chucks of that request should be routed to this user according to Algorithm 2.
Algorithm 2 Coded Delivery Phase for Server k
k
Require: {dk, j } D
j=1 , `
1: for j = 1 : D k do
2:
I = indices of the nodes caching ` nearest coded chunks corresponding to Wdk, j
3:
for l ∈ I do
( j)
4:
Ml→k = coded chuck of file Wdk, j at node l
( j)
5:
Forward Ml→k from node l to node k via the shortest path
6:
end for
7: end for

It is clear that if the field size q is large enough, then Algorithm 2 will successfully satisfy all requests
of Server k w.h.p., i.e., probability of order O( q1 ).
Next, we analyze the communication cost and maximum load of coded cache content placement and
delivery of Algorithms 1 and 2.
√ √
Theorem 3 (Coded Communication Cost). For a grid network of n× n, suppose that P = {p1, p2, . . . , pK }
be the file popularity distribution, where number of files K = O(n), and let number of file chunks

6

p
√
` = Ω(log n). Define p̃ j , 1 − (1 − p j ) M·` where we assume `/ p̃j = o( n) for every j. Then, w.h.p., the
p
communication cost for every requested file W j , 1 ≤ j ≤ K, is Θ `/ p̃ j . Moreover, we have
E [C] =

K
Õ

q

Θ `/ p̃ j p j .

(3)

j=1

Proof. Upper Bound: Suppose that u ∈ G be an arbitrary node that requests for some file W j . For every
v ∈ G, let Xv, j denote the indicator random variable taking 1 Í
if v has cached a coded chunk of W j , and
zero otherwise. Then, for every positive number r, Yu ( j, r) = v∈Br (u) Xv, j denotes the number of servers
that have cached a coded chunk of W j in Br (u). Notice that


 M·`
p̃ j = Pr Xv, j = 1 = 1 − 1 − p j
.
Thus,

E [Yu ( j, r)] = |Br (u)| · p̃ j .

We know that, for a grid, |Br (u)| = 2r(r + 1) + 1 = 2r 2 (1 + o(1)). Hence by choosing r j =
z = max[6 log n, 5`], we get


E Yu ( j, r j ) = 2z(1 + o(1)) ≥ 12 log n(1 + o(1)).

q

z
p̃ j ,

where

Since Xv, j ’s are independent and identical indicator random variables, applying a Chernoff bound (e.g.,
see Lemma 1 in Appendix) for Yu ( j, r j ) yields that



Pr Yu ( j, r j ) ≤ 0.1 E Yu ( j, r j ) = o(1/n3 ).
Thus, with probability 1 − o(1/n3 )


Yu ( j, r j ) ≥ 0.1 E Yu ( j, r j ) = 0.2z(1 + o(1)) ≥ `,
which means Br (u) contains at least ` nodes that have cached a coded chunk of W j .
Let Eu, j denote the event that u requests for file W j and Yu ( j, r j ) < `. Now by the union bound over
all n nodes and K = O(n) requests we have,

 Õ 
 Õ
Pr ∪u, j Eu, j ≤
Pr Eu, j =
o(1/n3 ) = o(1/n).
u, j

u, j

Since the entropy of each coded chunk is F/` and with probability 1 − o(1/n) q
we can
 find all the required
`
coded chunks in Br (u), the communication cost defined in Definition 2 is O
p̃ j , as z = O(`).
q 


z
Lower Bound: If we set r j = o
p̃ j , then E Y ( j, r j ) = o(z) = o(`). Thus, by Markov inequality for
any constant α > 0




Pr Yu ( j, r j ) > α E Yu ( j, r j ) ≤ 1/α.

So for every u, with probability at least 1 − 1/α,


Yu ( j, r j ) < α E Yu ( j, r j ) < `.
Let Tu,i denote the indicator random variable taking one if the ith
` coded
 request, born at u, fails toÍfind
n Í Du
chunks of the requested file in Br (u). Thus, we have Pr Tu,i = 1 > 1 − 1/α. Also let S = u=1 i=1 Tu,i
denote the total number of failures. Then,


E [S] = n · Pr Tu,i = 1 > (1 − 1/α)n.

7

Since the requests are independent, another application of the Chernoff bound for random variable S
results that
Pr [S < E [S] /2] < exp(−Ω(n)).
Hence, w.h.p. at least (1 − 1/α)n/2 requests cannot
p be responded in the r-neighborhood of the requesting
node, and the communication cost for W j is Ω( `/ p̃ j ).
p
Since the upper and lower bounds meet, the communication cost of requesting file W j is Θ( `/ p̃ j ).
Consequently, by averaging over the library with probability distribution P, the average communication
cost is
q

K
Õ
E [C] =
Θ `/ p̃ j p j .
j=1

√



√

Corollary 1. For a grid network of n × n, suppose that the cache size M is constant, number of
files K = nδ , for any δ ∈ (0, 1], and number of file chunks ` = Θ(log n). Then For Zipf distribution with
parameter γ, the average communication cost is
p



Θ
K/M
:
0 ≤ γ < 1,




p



γ = 1,
Θ K/M log K :


 


√
E [C] = Θ K 1−γ/2 / M
:
1 < γ < 2,




√


 Θ log K/ M
:
γ = 2,



√

 Θ( `)
:
γ > 2,

w.h.p.
Proof. To show this, for some small constant  > 0 let us define two sets, say A , { j : 1 ≤ j ≤
K, p j M` >  } and its complement Ā. So for every j ∈ A, we have p̃ j = Θ(1) and for every j ∈ Ā,
p̃ j = 1 − (1 − p j ) M` ≈ p j M`.
Thus, the average communication cost reduces to the following summation

Õ √ 
Õ q
E [C] =
Θ ` pj +
Θ
p j /M .
j∈A

j∈ Ā

For Zipf distribution, p j ’s are decreasing in j so let us define j ∗ = max A if A is not empty and j ∗ = 0,
otherwise. Also let p0 = 0. Then,
q

j∗
K
Õ
√ Õ
pj +
Θ
p j /M .
(4)
E [C] = Θ( `)
j=0

|

{z

j= j ∗ +1

} |

S1 (γ)

{z

}

S2 (γ)
j∗

Í
Now let us estimate S1 (γ) in (4). It is clear that 0 ≤ j=0 p j < 1, thus
(
√
O( `) :
0 ≤ γ ≤ 1,
√
S1 (γ) =
Θ ` :
γ > 1,

(5)

8

√
`) as p1 = Θ(1) when γ Í> 1. In what follows we provide an estimation for S2 (γ) =
where
S
(γ)
=
Θ(
1
p
ÍK
Θ(
p
/M).
Let us define Λ(γ, s) , Kj=s+1 j −γ . So
j
j= j ∗ +1
!
!
K
Õ
Λ(γ/2, j ∗ )
j −γ/2
=Θ p
.
S2 (γ) =
Θ p
MΛ(γ,
0)
MΛ(γ,
0)
j= j∗+1
Also we know that (see Lemma 2 in Appendix)



Θ K 1−γ − Θ( j ∗ 1−γ ) :


Λ(γ, j ∗ ) = Θ (log K) − log j ∗
:

 O (1)
:


0 ≤ γ < 1,
γ = 1,
γ > 1.

Note that by the definition of j ∗ , we have


≤ p j ∗ < j ∗ −γ,
M`
and hence j ∗ ≤



M`


 1/γ

= O((log n)1/γ ). This implies that we can ignore terms j ∗ 1−γ and log j ∗ in

comparison with Θ(K 1−γ ) and Θ(log K), respectively, as K = nδ , for some constant δ ∈ (0, 1]. In other
words
!
Λ(γ/2, 0)
S2 (γ) = Θ p
.
MΛ(γ, 0)
Then, we will have


p


K/M
:
Θ






p



Θ K/M log K :

 

√ 
S2 (γ) = Θ K 1−γ/2 / M
:





√



Θ log K/ M
:



 O(1)
:

Now, considering equalities (5) and (6) completes the proof.

0 ≤ γ < 1,
γ = 1,
1 < γ < 2,

(6)

γ = 2,
γ > 2.


In the next Theorem we characterize the load balancing performance of the proposed scheme.
√
√
Theorem 4 (Coded Maximum Load). For a grid network of n × n, suppose that P = {p1, p2, . . . , pK }
be the file popularity distribution and let the number of file chunks be ` = Ω(log n). Then, the maximum
load is Θ(1) w.h.p.
Proof. By assumption, each server has at most M` distinct coded chunks. For every fixed node u ∈ V(G),
let us define the indicator random variable Yu,i , taking one if the i-th request has asked a coded chunk
from u and zero otherwise.
p
Let E denote the event that ` coded chunks of an arbitrary file W j is found in Br j (u) where r j = α`/ p̃ j
for some positive constant α (remember that p̃ j = 1 − (1 − p j ) M` is the probability that an arbitrary node
has cached a coded chunk of W j ).
Also note that a server might be asked to respond a request if
(1) the request is born at a neighborhood of radius r j and,
(2) a coded chunk of the requested file is cached in the server.

9

Then we can write


Pr Yu,i = 1


= Pr Yu,i = 1|E Pr [E]


+ Pr Yu,i = 1|¬E Pr [¬E]


(a)
≤ Pr Yu,i = 1|E + o(1/n)
K
Õ


=
Pr Yu,i = 1|E, W j requested p j + o(1/n)
j=1

≤

K
Õ
|Br j (u)|
j=1

n

p̃ j · p j + o(1/n)

2α`(1 + o(1))
+ o(1/n)
n
2α`(1 + o(1))
,
=
n
(b)

≤

where (a) follows from Theorem 1 and (b) follows from Br j (u) = 2r j2 (1 + o(1)).
Ín
Now let Su = i=1
Yu,i count the number of requests that are responded by u, during allocating n
requests. Hence, we have
n
Õ
 
E [Su ] =
E Yu,i ≤ 2α`(1 + o(1)).
i=1

Applying a Chernoff bound for Su implies that
Pr [Su ≥ (1 + δ)2α`] ≤ exp(−δ2 α`) = o(1/n2 ),
for appropriate choices of constants δ and α, and since ` = Ω (log n). Taking union bound over all servers
shows that each server is requested at most O ` (1 + o(1)) times during the allocation process. However,
each server is responsible for a coded chunk of entropy F/` bits, and hence it has to handle at most O(1)
bits. This concludes the proof.

V. D ISCUSSIONS AND R EMARKS
Theorems 1 and 2 characterize the communication cost and load balancing performance of the uncoded
Nearest Replica strategy, while Theorems 3 and 4 characterize the same metrics for the proposed Coded
Load Balancing scheme. Comparing the results shows a surprising finding. By introducing coding into
the cache content placement and delivery phases, one can achieve an almost perfectly balanced network
without sacrificing communication cost (in the scaling sense). However, this achievement is at the expense
of increasing the encoding/decoding complexity in the network. In what follows, we discuss this issue
and other practical considerations regarding our proposed scheme.
A. Reducing the Decoding Complexity
In the proposed coded caching scheme, at the end of the content delivery phase, each server has received
` coded chunks for each of its requests. Then, in order to recover the requested file, it has to calculate
the inverse of an ` × ` = log n × log n matrix over a finite field Fq . Basically, this introduces a complexity
of order O(` 2.37 ) finite field operations [29]. This may not be computationally feasible in certain practical
scenarios. Thus, one may ask what are other approaches which achieve the same performance with less
computational complexity.

10

An alternative approach to reduce decoding complexity is to cache uncoded file chunks at the servers.
In other words after dividing each file into ` chunks, the servers cache uncoded chunks of the library
based on the distribution P. This removes the need to invert the aforementioned matrix. However, as we
will discuss next, this modification will result in unsatisfactory performance.
In contrast to the coded scheme, here each server needs to collect ` disticnt chunks of its request. Thus,
the average distance of its search area will be increased due to the Coupon Collector Problem Effect. In
other words, here we should find approximately ` log ` chunkspin which ` of them are distinct. This will
increase the communication cost by a multiplicative factor of log `.
Another alternative approach is to use Fountain-like codes, originally proposed for packet erasure
channels [27]. This coding technique benefits from a non-uniform coding operator (similar to (2) but
with non-uniform distribution over the coefficients αr ). The main idea behind these codes is that by
optimizing over the coding coefficients distribution, one can design the parity check matrix of these codes
such that the complexity of the encoding and decoding algorithms will be significantly reduced.
More specifically, in the cache content placement phase in Algorithm 1, one can use the encoder of
a Raptor code [28], instead of a uniform operator L, defined in (2). It is shown that the Raptor codes
have linear encoding and decoding complexity in the codewords length [28]. Translating to our problem
setting, this leads to the encoding and decoding complexity of order ` = log(n) finite field operations,
compared to the aforementioned matrix inversion.
B. Other Practical Considerations
The main reason why we have investigated a 2D-Grid is for ease of presentation. However, it should be
noticed that our approach can be extended to a much more general graph model class in a straightforward
manner. The main feature of the 2D-Grid which affects our results is that |Br (u)| = Θ(r 2 ) for all u. Now
suppose, instead of assuming a 2D-Grid, we consider a graph in which |Br (u)| = Θ(r dim ), w.h.p. for all
u. Then the parameter dim will appear in our results instead of dim = 2 in the special case of 2D-Grid.
More generally, even for |Br (u)| = Θ( f (r)), our technicalities can be extended too. This generalization
will cover a wider class of graph models which are more similar to real-world CDN network topologies.
Another important issue is that in above results we have assumed the total number of requests and
nodes to be equal to n. If we denote the number of requests by another parameter m, one can generally
consider three cases of n  m, n  m and n = Θ(m), where our results apply to the last one. Intuitively,
in the first case since we have much less requests than servers, no server will become overloaded. In the
second case, the average load of each server will be of order m/n, and the deviation of the maximum
load from the average load is negligible compared to the average load. Thus, in the first two regimes, the
issue of load balancing is automatically resolved (see e.g., [30]). That is why we have focused on the
case where we have equal number of requests and servers.
C. Coded Load Balancing vs. Power of Two Choices
An alternative approach to balance out loads in our problem setup is benefiting from the power of
two choices as proposed in [14]. Simply put, the cache content placement of this scheme is the same
as the uncoded scheme of Section III. However, upon each request arrival in the content delivery phase,
instead of assigning the request to the nearest replica, first the current load of two randomly selected
nodes which have cached the request in the vicinity of the request origin is queried. Then the request is
assigned to the least loaded server. The result in [14] suggests that in certain regimes of parameters this
randomized scheme will decreases the maximum load from the Θ(log n) in the Nearest Replica strategy
to Θ(log log n), which is an exponential improvement.
The Coded Load Balancing scheme has two advantages compared to the scheme proposed in [14].
First, its load balancing performance is better, i.e., Θ(1) versus Θ(log log n). Second, in the Coded Load
Balancing scheme we do not need to query the current load of other servers, which incurs an extra
overhead. The only drawback of the coded scheme is its encoding/decoding complexity which can be
alleviated by the techniques described above.

11

9

Nearest Replica
8

7

max load

6
cache size = 1
cache size = 2
cache size = 10

5

Coded # chunks = 4

Coded # chunks = 10

4

3

2

1

0

500

1000

1500

2000

2500

3000

3500

number of servers

Fig. 1: Comparing maximum load L of the Nearest Replica and Coded Load Balancing strategies versus
the number of servers n. The library size is K = 100, and each data point is averaged over 5000 simulation
runs.

VI. N UMERICAL A NALYSIS
In this section, we use Monte Carlo simulations to estimate the communication cost and maximum load
performance
of a content delivery network, under the model described in Section II. In this section, our
uesday, Farvardin
24, 17
main goal is twofold. First, we verify our key understandings from asymptotic theoretical results about the
benefit of coding. Second, we investigate other effects not revealed in asymptotic analyses. As described
in Section II, the content delivery network considered is a square grid with n servers which respond to
n requests. The files are requested uniformly at random from the servers following a Zipf popularity
distribution with parameter γ.
In order to clarify the effect of different parameters of the network on the performance, we start
numerical analysis with a uniform popularity distribution, i.e., γ = 0, and then investigate the effect of
varying γ on the results. In Fig. 1 the maximum load L is plotted versus the network size n for the
Nearest Replica and Coded Load Balancing strategies, introduced in Sections III and IV respectively. The
library size is K = 100, and each data point is averaged over 5000 simulation runs. As shown in Fig. 1,
the maximum load L is a decreasing function of the cache size M of each server. Also Fig. 1 shows
using our coded scheme reduces the maximum load of the network significantly, verifying the results of
Theorems 2 and 4. Moreover, in the coded scheme, when the number of file chunks ` is increased we
will have better load balancing performance.
In Fig. 2 the communication cost C of the Nearest Replica and Coded Load Balancing strategies is
plotted versus the server cache size M for a square grid of size n = 2025, where γ = 0. The cache size
varies in the range M ∈ {1, . . . , 100}. First we notice that in all curves the communication cost reduces
as the cache size increases. This is consistent with the results of Theorems 1 and 3. Second, Fig. 2 shows
that the communication cost of the Coded Load Balancing scheme is slightly less than the Nearest Replica
strategy in finite size networks, not revealed by the asymptotic analysis. This surprising finding confirms
the superiority of our proposed coded scheme in terms of the both network performance metrics, i.e., L
and C.

12

30
Nearest Replica library size 100
Nearest Replica library size 1000
Nearest Replica library size 2000
Coded #chunks 4, library size 100
Coded #chunks 4, library size 1000
Coded #chunks 4, library size 2000
Coded #chunks 10, library size 100
Coded #chunks 10, library size 1000
Coded #chunks 10, library size 2000

communication cost

25

20

15

10

5

0

0

10

20

30

40

50

60

70

80

90

100

cache size

Fig. 2: Comparing communication cost C of the Nearest Replica and Coded Load Balancing strategies
versus the cache size M for a square gird network with 2025 servers. Each data point is averaged over
5000 simulation runs.
In order to understand the effect of the number of chunks ` on the load balancing performance of our
proposed scheme, we have run a simulation for a square grid with n = 2025 servers, a library size of
K = 100 files, and γ = 0. Fig. 3 shows the maximum load of such scenario versus the number of chunks
` ∈ {1, . . . , 10}, averaged over 2000 simulation runs. From Fig. 3 we see that for small values of ` the
effect of increasing ` on decreasing the maximum load L is considerable. However, we observe this effect
to be diminishing by increasing `. This is consistent with the result of Theorem 4 which states that by
having ` ∼ log n we will have an almost perfect load balancing performance, and there is no benefit in
further increasing `.
Thus far, for the purpose of clarity, we have investigated different aspects of the proposed coded strategy
in the case of γ = 0. Here we move forward to investigate the role of Zipf parameter γ on the network
performance as presented in Fig. 4. We consider a square grid of n = 2025 servers each with a cache of
size M = 10 files. Also we assume the number of file chunks to be ` = 10. In the cache content placement
phase, according to the Algorithm 1, the chunks are cached proportional to the popularity distribution3 .
Fig. 4-(a) shows the maximum load L of the Coded Load Balancing scheme versus the Zipf parameter
γ, while Fig. 4-(b) shows the communication cost versus γ. Each data point is the result of averaging
over 4000 simulation runs. In Fig. 4-(a) we observe that the maximum load decreases moderately as
γ increases, while the communication cost decreases considerably. This figure shows that our proposed
scheme benefits from the skewness in the file popularity to arrive at a better network performance.
VII. C ONCLUSIONS
In this work, considering content delivery networks, we have proposed and investigated a coded cache
content placement and content delivery scheme, called the Coded Load Balancing strategy. We have
considered the conventional Nearest Replica strategy as our baseline scheme, and compared the load
balancing performance and the communication cost of these two schemes, asymptotically. By deriving
3 Also

we ensure that all the library is cached somewhere inside the network.

13

8
cache size 1
cache size 2
cache size 10
cache size 100

7

6

max load

5

4

3

2

1

0

1

2

3

4

5

6

7

8

9

10

number of file chunks

Fig. 3: The maximum load versus the number of file chunks in the Coded Load Balancing strategy. Here
we have a square grid with n = 2025 servers and a library size of K = 100 files. Each data point is
averaged over 2000 simulation runs.

8

2.6
library size 100
library size 1000
library size 2000

2.4

library size 100
library size 1000
library size 2000

7

communication cost

2.2

max load

2

1.8

1.6

1.4

1.2

6

5

4

3

2

1

1

0.8

0

0.5

1

γ

1.5

(a) Maximum load vs. γ.

2

2.5

0

0

0.5

1

γ

1.5

2

2.5

(b) Communication cost vs. γ.

Fig. 4: Maximum Load (a), Communication Cost (b) of the Coded Load Balancing scheme versus the
Zipf parameter γ. Here we have a square grid network with n = 2025, M = 10, and ` = 10. Each data
point is the result of averaging over 4000 simulation runs.

14

closed-form expressions, we have shown that the proposed scheme will result in an almost perfect
load balancing performance without sacrificing communication cost, in large networks. Moreover, our
simulation results suggest the same finding in practical regimes as well.
R EFERENCES
[1] S. Manfredi, F. Oliviero, and S. P. Romano, “A distributed control law for load balancing in content delivery networks,” IEEE/ACM
Trans. Netw., vol. 21, no. 1, pp. 55–68, 2013.
[2] V. Cardellini, E. Casalicchio, M. Colajanni, and P. S. Yu, “The state of the art in locally distributed web-server systems,” ACM Comput.
Surv., vol. 34, no. 2, pp. 263–311, Jun. 2002.
[3] Z. Zeng and B. Veeravalli, “Design and performance evaluation of queue-and-rate-adjustment dynamic load balancing policies for
distributed networks,” IEEE Transactions on Computers, vol. 55, no. 11, pp. 1410–1422, Nov 2006.
[4] G. Pallis and A. Vakali, “Insight and perspectives for content delivery networks,” Commun. ACM, vol. 49, no. 1, Jan. 2006.
[5] A.-M. K. Pathan and R. Buyya, “A taxonomy and survey of content delivery networks,” Grid Computing and Distributed Systems
Laboratory, University of Melbourne, Technical Report, 2007.
[6] V. Mathew, R. K. Sitaraman, and P. J. Shenoy, “Energy-aware load balancing in content delivery networks,” in Proceedings of the
IEEE INFOCOM, 2012, pp. 954–962.
[7] V. Cardellini, M. Colajanni, and P. S. Yu, “Request redirection algorithms for distributed web systems,” IEEE Trans. Parallel Distrib.
Syst., vol. 14, no. 4, pp. 355–368, Apr. 2003.
[8] J. Dilley, B. Maggs, J. Parikh, H. Prokop, R. Sitaraman, and B. Weihl, “Globally distributed content delivery,” IEEE Internet Computing,
vol. 6, no. 5, pp. 50–58, 2002.
[9] E. Nygren, R. K. Sitaraman, and J. Sun, “The akamai network: A platform for high-performance internet applications,” SIGOPS Oper.
Syst. Rev., vol. 44, no. 3, pp. 2–19, Aug. 2010.
[10] Z. Zhang and W. Fan, “Web server load balancing: A queueing analysis,” European Journal of Operational Research, vol. 186, no. 2,
pp. 681 – 693, 2008.
[11] A.-M. K. Pathan, C. Vecchiola, and R. Buyya, “Load and proximity aware request-redirection for dynamic load distribution in peering
cdns,” in OTM 2008 Confederated International Conferences,, 2008, pp. 62–81.
[12] J. Tang, W.-P. Tay, and Y. Wen, “Dynamic request redirection and elastic service scaling in cloud-centric media networks,” IEEE Trans.
Multimedia, vol. 16, no. 5, pp. 1434–1445, 2014.
[13] R. Stanojevic and R. Shorten, “Load balancing vs. distributed rate limiting: An unifying framework for cloud control,” in Proceedings
of IEEE International Conference on Communications, ICC 2009, Dresden, Germany, 14-18 June 2009, 2009, pp. 1–6.
[14] A. Pourmiri, M. Jafari Siavoshani, and S. P. Shariatpanahi, “Proximity-aware balanced allocations in cache networks,” to appear at
IEEE IPDPS 2017. [Online]. Available: http://arxiv.org/abs/1610.05961
[15] M. J. Siavoshani, S. P. Shariatpanahi, H. Ghasemi, and A. Pourmiri, “On communication cost vs. load balancing in content delivery
networks,” CoRR, vol. abs/1610.04513, 2016. [Online]. Available: http://arxiv.org/abs/1610.04513
[16] C. Gkantsidis and P. R. Rodriguez, “Network coding for large scale content distribution,” in Proceedings IEEE 24th Annual Joint
Conference of the IEEE Computer and Communications Societies ( INFOCOM 2005)., vol. 4, Mar 2005, pp. 2235–2245.
[17] U. Lee, J.-S. Park, J. Yeh, G. Pau, and M. Gerla, “Code torrent: Content distribution using network coding in VANET,” in Proceedings
of the 1st International Workshop on Decentralized Resource Sharing in Mobile Computing and Networking, ser. MobiShare ’06, 2006,
pp. 1–5.
[18] G. Zhang, H. Li, T. Zhang, D. Li, and L. Xu, “A multi-path forwarding strategy for content-centric networking,” in 2015 IEEE/CIC
International Conference on Communications in China (ICCC), 2015, pp. 1–6.
[19] T. Guven, R. J. La, M. A. Shayman, and B. Bhattacharjee, “A unified framework for multipath routing for unicast and multicast traffic,”
IEEE/ACM Transactions on Networking, vol. 16, no. 5, pp. 1038–1051, 2008.
[20] E. Magli, M. Wang, P. Frossard, and A. Markopoulou, “Network coding meets multimedia: A review,” IEEE Transactions on Multimedia,
vol. 15, no. 5, pp. 1195–1212, Aug 2013.
[21] K. Shanmugam, N. Golrezaei, A. G. Dimakis, A. F. Molisch, and G. Caire, “Femtocaching: Wireless content delivery through distributed
caching helpers,” IEEE Transactions on Information Theory, vol. 59, no. 12, pp. 8402–8413, Dec 2013.
[22] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” IEEE Trans. Information Theory, vol. 60, no. 5, pp. 2856–2867,
2014.
[23] L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker, “Web caching and Zipf-like distributions: evidence and implications,” in
INFOCOM ’99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, vol. 1,
Mar 1999, pp. 126–134 vol.1.
[24] M. Cha, H. Kwak, P. Rodriguez, Y.-Y. Ahn, and S. Moon, “I tube, you tube, everybody tubes: Analyzing the world’s largest user
generated content video system,” in Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement, ser. IMC ’07. New
York, NY, USA: ACM, 2007, pp. 1–14.
[25] Y. Azar, A. Z. Broder, A. R. Karlin, and E. Upfal, “Balanced allocations,” SIAM J. Comput., vol. 29, no. 1, pp. 180–200, 1999.
[26] M. Luby, “LT codes,” in Proceedings of the 43rd Symposium on Foundations of Computer Science, ser. FOCS ’02, 2002.
[27] J. W. Byers, M. Luby, M. Mitzenmacher, and A. Rege, “A digital fountain approach to reliable distribution of bulk data,” SIGCOMM
Comput. Commun. Rev., vol. 28, no. 4, pp. 56–67, Oct. 1998.
[28] A. Shokrollahi, “Raptor codes,” IEEE Trans. Information Theory, vol. 52, no. 6, pp. 2551–2567, 2006.
[29] D. Coppersmith and S. Winograd, “Matrix multiplication via arithmetic progressions,” J. Symb. Comput., vol. 9, no. 3, pp. 251–280,
Mar. 1990.
[30] P. Berenbrink, A. Czumaj, A. Steger, and B. Vöcking, “Balanced allocations: The heavily loaded case,” SIAM J. Comput., vol. 35,
no. 6, pp. 1350–1385, 2006.

15

[31] D. P. Dubhashi and A. Panconesi, Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press,
2009.

A PPENDIX
Lemma 1 (Chernoff
Bounds). Suppose that X1, X2, . . . , Xn ∈ {0, 1} are independent random variables
Ín
and let X = i=1 Xi . Then for every δ ∈ (0, 1) the following inequalities hold
Pr [X ≥ (1 + δ) E [X]] ≤ exp(−δ2 E [X] /2),
Pr [X ≤ (1 − δ) E [X]] ≤ exp(−δ2 E [X] /3).
In particular,
Pr [|X − E [X] | ≥ δ E [X]] ≤ 2 exp(−δ2 E [X] /3).
For a proof see [31].
Lemma 2. For Λ(γ, j) =

i −γ , where γ ≥ 0, we have

1−γ − Θ( j 1−γ ) :


 Θ K

:
Λ(γ, j) = Θ (log K) − log j

 O (1)
:


ÍK

i= j

0 ≤ γ < 1,
γ = 1,
γ > 1.

Proof. First notice that by the definition of Riemann integration, we can upper and lower bound Λ(γ, j)
as follows
∫ K+1
∫ K
K
Õ
−γ
−γ
−γ
t dt ≤
i ≤ j +
t −γ dt.
j

i= j

j

This can be simplified to

1 
(K + 1)1−γ − j 1−γ ≤ Λ(γ, j)
1−γ
and
Λ(γ, j) ≤ j −γ +


1  1−γ
K
− j 1−γ .
1−γ

Now, considering the following three cases 0 ≤ γ < 1, γ = 1, and γ > 1 will conclude the proof.



