Towards Practical File Packetizations in
Wireless Device-to-Device Caching Networks
Nicholas Woolsey, Student Member, IEEE, Rong-Rong Chen, Member, IEEE,

arXiv:1712.07221v1 [cs.IT] 19 Dec 2017

and Mingyue Ji, Member, IEEE
Abstract
We consider wireless device-to-device (D2D) caching networks with single-hop transmissions. Previous work has demonstrated that caching and coded multicasting can significantly increase per user
throughput. However, the state-of-the-art coded caching schemes for D2D networks are generally impractical because content files are partitioned into an exponential number of packets with respect to the number
of users if both library and memory sizes are fixed. In this paper, we present two novel combinatorial
approaches to coded caching design in D2D networks with the goal of reducing the required packetization
while keeping the desired throughput gain compared to the conventional uncoded unicasting. The first
proposed approach is based on a novel “hypercube” design, where each user caches a “hyperplane” in
this hypercube and the intersections of “hyperplanes” lead to coded multicasting codewords. In addition,
we also extend this centralized scheme to a decentralized design. The second approach uses the RuzsaSzeméredi graph to define the cache placement and disjoint matchings on this graph represent coded
multicasting opportunities. Both approaches yield an exponential reduction of packetizations with respect
to the number of users while providing a per-user throughput that is comparable to the state-of-the-art
designs in the literature. Furthermore, by using the spatial reuse in D2D networks, besides further reducing
the required packetizations, we demonstrate that the per user throughput can be improved significantly
for some parameter regimes.
Index Terms
Coded Caching, Device-to-Device Communication, Packetization, Spatial Reuse

I. I NTRODUCTION
Wireless caching is a promising approach to significantly improve the user throughput and simultaneously accommodate a large number of user demands in future generations of wireless networks [1]–[13]. In
The authors are with the Department of Electrical Engineering, University of Utah, Salt Lake City, UT 84112, USA. (e-mail:
nicholas.woolsey@utah.edu, rchen@ece.utah.edu and mingyue.ji@utah.edu)

2

this paper, we investigate achievable coded caching schemes in device-to-device (D2D) caching networks,
where users strategically cache packets of content files to enable coded multicasting opportunities which
serve distinct content to multiple users simultaneously. Different from the seminal shared link caching
networks [1], where one source node (base station) with access to the entire library serves all the users
over a multicast channel, in D2D networks, users receive requested packets from other users. For such a
network consisting of n users, each caching an equivalent M files out of a library of m files, previous
work demonstrates that when spatial reuse is not allowed, and when M n ≥ m and m ≥ n, meaning
that any transmission can be successfully received by any users in the network, the transmission rate

m
(i.e., normalized traffic load) is Θ M
, which is not a function of n. Hence, the aggregate throughput of
the network is scalable [14].1 This surprising result shows that the transmission rate of the shared link
caching scheme in [1] and D2D caching scheme in [14] are identical for a large number of users.2
D2D caching networks have the potential to provide some unique advantages. For example, D2D
caching networks have a greater flexibility to implement spatial reuse in comparison to shared link
caching networks. The authors in [14] demonstrate that users in a D2D network can be grouped into
clusters based on proximity. These clusters can perform the coded multicasting delivery simultaneously
and surprisingly, the order-optimal traffic load in each cluster is identical to the traffic load when no
clustering is enabled (e.g., consider the entire network as a single cluster). Nevertheless, clustering may
improve per user throughput since the link rate (bits/second/Hz) in each cluster may increase as the size
of each cluster decreases.
The promised gain in per user throughput of the state-of-the-art coded D2D caching schemes relies on
a large amount of file packetization which makes the networks impractical to implement. In particular, if

n
+
no spatial reuse is considered, let t = nM
m ∈ Z , the required number of packets per file, K = t t , which
grows exponentially as the number of users, n, increases. Moreover, a recent study which implements a
shared link caching network with hardware demonstrates that a header packet, labeling the content of the
multicast, must be included with every transmission under some scenarios [15]. The size of this header
will become large as the number of packets per file increases. Spatial reuse in D2D caching networks
partially solves this issue by forming many small user clusters where the number of file partitions decreases
1

Note that when no spatial reuse is allowed, the per user throughput is inversely proportional to the traffic load in the network.

2

We will use the following standard “order” notation: given two functions f and g, we say that: 1) f (n) = O (g(n)) if

there exists a constant c and integer N such that f (n) ≤ cg(n) for n > N . 2) f (n) = o (g(n)) if limn→∞

f (n)
g(n)

= 0. 3)

f (n) = Ω (g(n)) if g(n) = O (f (n)). 4) f (n) = ω (g(n)) if g(n) = o (f (n)). 5) f (n) = Θ (g(n)) if f (n) = O (g(n))
and g(n) = O (f (n)).

3

as the number of clusters increases [14]. However, spatial reuse alone may not be able to reduce the
packetization sufficiently since the number of clusters in the network can be limited.
In this paper, we aim to propose achievable coded caching schemes in D2D networks such that the
packetization of each file is significantly reduced without sacrificing much throughput of the currently
proposed D2D caching schemes. In particular, we propose two combinatorial approaches to design
centralized D2D caching networks. The first approach uses a hypercube to define the cache placement
and we demonstrate how the geometry of this hypercube relates to coded multicasting opportunities for
delivery. The hypercube approach is optimized specifically for D2D caching networks as opposed to
adapting an already studied shared link scheme. In addition, by adopting the idea recently proposed in
[16], we extend this approach to a decentralized coded D2D caching scheme, which allows a much more
flexible design for given network parameters. Meanwhile, the advantage of the reduced packetization of
the hypercube approach still remains in the decentralized D2D caching networks. The second approach
is based on an application of the Ruzsa-Szeméredi graph [17], [18], which is first used for shared link
caching in [19]. In this paper, we extend the use of Ruzsa-Szeméredi graph to D2D caching networks.
For both approaches, while sustaining the significant throughput gain compared to conventional uncoded
unicast [20], the required packetizations are reduced exponentially with respect to the number of users
n while keeping the library size m and memory size M fixed. Finally, we study the impact of enabling

spatial reuse in these caching networks. Besides further reducing the required packetizations, we also
demonstrate that spatial reuse can improve the per user throughput significantly for some parameter
regimes.
The outline of this paper is as follows. In section II, we introduce the D2D network model and problem
formulation. In Section III, we present the hypercube based coded caching approach and analyze its
performance. We also show that this centralized scheme can be used to design a decentralized D2D
caching network. Section IV introduces the Ruzsa-Szeméredi graph based coded caching approach and
analyzes its performance. In Section V, we show how the proposed schemes can take advantage of spatial
reuse. Finally, we conclude the paper in Section VI.
II. N ETWORK M ODEL AND P ROBLEM F ORMULATION
We consider a wireless D2D network with single-hop transmissions formed by the set of users U =
√
{0, . . . , n − 1}. The users are uniformly distributed on a unit grid with a minimum distance of 1/ n
as shown in Fig. 1(a). Each user u ∈ U makes a request fu ∈ F , where F = {1, · · · , m} is a file
library of m independently generated messages {W0 , ..., Wm−1 } with entropy F bits each. We denote

4

the demand vector as f = (f0 , · · · , fn−1 ). The file library, F , is generated once and kept unchanged
during subsequent network operations. In addition, we assume m ≥ n and users request distinct files.
∆

Each user locally caches the equivalent of M files, or M F bits. Furthermore, define t = nM/m ≥ 1, as
the number of times the library is cached collectively among the users.
Users have active links between one another based on the protocol model [21] described as follows.
A communication link, consisting of user u transmitting to user v , will be successful if and only if the
distance between user u and v is less than or equal to r and user v is at least a distance of (1 + ∆)r
from all transmitting users other than user u. The parameters r, ∆ > 0 are given by the protocol model.
We assume that any r > 0 is possible and r dictates a constant data rate, Cr , in the unit of bits/s/Hz.3
The protocol model allows for spatial reuse as shown in Fig. 1(a). Four users, one in each green cluster,
are transmitting to four other local users who are at most a distance of r away. The users receiving the
transmission are at least a distance of (1 + ∆)r from the other three transmitting users. The users of
Fig. 1(a) may be part of a larger network of users as shown in Fig. 1(b) which depicts active clusters
(involved in a successful communication link) in green and non-active clusters (neither receiving or
transmitting) in red. The set of active clusters highlighted in green is one of K sets. K is defined as the
reuse factor or the number of cluster sets such that, for any given set, each cluster of that set can be
active without interference and the K cluster sets collectively include all clusters.
A D2D caching scheme consists of three phases: the cache placement phase, the coded delivery phase,
and the transmission phase. These are defined as follows.
Definition 1: (Cache Placement Phase) The cache placement phase maps the file library F onto the
caches of all users u ∈ U . Every file in F is split into K equally sized packets and each user caches M K

F
packets or equivalently M F bits. For u ∈ U , the function φu : FmF
→ FM
generates cache content
2
2

Zu , φu (Wf : f ∈ F), which are stored in user caches at the beginning, and kept fixed throughout

♦

subsequent operations.

Definition 2: (Coded Delivery Phase) The coded delivery phase is defined by two sets of functions:
the node encoding functions, denoted by {ψu : u ∈ U}, and the node decoding functions, denoted by
{λu : u ∈ U}. Let RuT denote the number of coded bits transmitted by node u to satisfy the demand

vector f . The transmission rate of node u is defined by Ru =

T
Ru
F .

F
The function ψu : FM
× F n → FF2 Ru
2

generates the transmitted message Xu,f , ψu (Zu , f) of node u as a function of its cache content Zu and
3

Note that in practice, Cr can be a function of the transmission range r. However, the protocol model does not capture this

relationship.

5

Fig. 1.

a) Representation of 81 users on a square grid. Users are divided into 9 equally sized clusters of 9 users

based on user proximity. The clusters highlighted in green represent clusters which can be simultaneously active
assuming that cluster highlighted in red are not active. b) A larger network which includes the 81 users of Fig. 1(a)
where the clusters highlighted in green can be simultaneously active. The reuse factor is K = 4.

the demand vector f .4
Let Du denote the set of users whose transmit messages are received by user u (according to some
F

transmission policy in Definition 3). The function λu : F2

P

v∈Du

Rv

F
× FM
× F n → FF2 decodes the
2

request of user u from the received messages and its own cache, i.e., we have
Ŵu,f , λu ({Xv,f : v ∈ Du }, Zu , f).

♦
Since users make arbitrary requests, similar to [1], [14], we focus on the worst-case error probability
defined as


Pe = maxn max P Ŵu,f 6= Wfu .
f∈F

u∈U

For a given number of users n and library size m, letting the transmission rate R =

P

u∈U

Ru , we say

that the cache-rate pair (M, R) is achievable if ∀ ε > 0 there exists a sequence indexed by the file size
F → ∞ of cache encoding functions {φu }, delivery functions {ψu } and decoding functions {λu }, with
(F )

rate R(F ) and probability of error Pe

(F )

such that lim supF →∞ R(F ) ≤ R and lim supF →∞ Pe

≤ ε.

Note that RF gives the achievable total traffic load transmitted in the whole network.
Definition 3: (Transmission Phase) The transmission policy Π is a rule to activate D2D links in the
network. Let L denote the set of all directed links. Let A ⊆ 2L denote the set of all possible feasible
4

We also refer the transmission rate to traffic load in this paper.

6

subsets of links (this is a subset of the power set of L, formed by all sets of links forming independent
sets in the network interference graph induced by the protocol model). Let At ⊂ A denote a feasible
set of simultaneously active links at time t. A feasible transmission policy Π consists of a sequence of
activation sets, i.e., sets of active transmission links, {At : t = 1, 2, 3, . . .}, such that at each time t the
♦

active links in At do not violate the protocol model.

Different from the shared link network model [1], the performance of D2D caching networks cannot
be completely characterized by the transmission rate, R, because of spatial reuse under protocol model.
Hence, we define the per user throughput as follows,
∆

T =

F
,
D

(1)

where D is the number of channel uses required to satisfy all user requests. We say that the pair (M, T )
is achievable if RF is achievable and there exists a transmission policy Π such that the RF encoded bits
can be delivered to their destinations in D ≤ F/T channel uses. Then, the optimal achievable throughput
is defined as
T ∗ (M ) , sup{T : (M, T ) is achievable}.

Remark 1: Note that, when considering clustering and assuming that the transmission rate of each
cluster is exactly Rc , we can obtain D =

Rc F K
Cr .

Therefore, the per user throughput for a clustering

scheme is
Tc =

Cr
.
Rc K

(2)

In the following, we will compare the per user throughput of clustering and non-clustering schemes.
III. H YPERCUBE C ODED C ACHING A PPROACH
√
In this section, we consider the case when the transmission range r ≥ 2. In other words, a transmission
from any node can be received by the rest of the nodes in the network and there is no user clustering.
We first introduce two motivating examples of the proposed hypercube coded caching approach and then
present the general achievable scheme and transmission rate.

A. 2-Dimension Example
In this example, we propose a cache placement and a delivery scheme based on a d = 2 dimensional
hypercube (a plane) lattice. We consider a D2D network with n = 4 users,

m
M

= 2, and t =

nM
m

= 2.

Assume that each user requests a distinct file, i.e., user i requests file fi . The 2-dimensional lattice is

7

constructed where the size of each dimension is

m
M

= 2. Each lattice point represents a set of m packets,

each from a different file in F . For instance, in Fig. 2(a), each lattice point represents {Wi,(j,k) , i ∈ F}
where Wi,(j,k) is a packet from file i ∈ F and the subscript (j, k) represents the corresponding position
on the lattice. Hence, the total number of lattice points equals the number of packets per file. Since in
m t
m d
this case we have t = d = 2, there are K = ( M
) = (M
) = 22 = 4 points in this 2-dimensional lattice,

corresponding to 4 partitions of each file. The number of users equals t times the number of lattice points
on each dimension, i.e., n =

m
Mt

=

m
Md

= 2 · 2 = 4.

For the cache placement, each user caches a line on the lattice as shown in Fig. 2(a). For instance,
user 0 caches Wi,(0,0) and Wi,(0,1) for all i ∈ F . The intersection of two lines represents a set of packets
cached by two users. Each user requests two packets (from its demanded file) each of which is in the
cache of two other users. In the delivery phase, each user unicasts two requested packets to the appropriate
users. In this example, the number of user groups is equivalent to the number of packets per file and
m t
) = 22 = 4 user groups, each with a size of t = 2, i.e., we pick one user from each
there are K = ( M

dimension. User 0 is involved in two user groups, {0, 2} and {0, 3}. Hence, user 0 will send Wf2 ,(0,1) to
user 2 and send Wf3 ,(0,0) to user 3. Therefore, R = 2 since the rate simply equals the number of packets
that the users are missing normalized by the file size. Note that, in this simple example there is a coded
multicasting opportunity. Each user can include their transmitted packets into a single coded multicast.
For instance, user 0 can transmit Wf3 ,(0,0) ⊕ Wf2 ,(0,1) to users 2 and 3, who can decode Wf2 ,(0,1) and
Wf3 ,(0,0) successfully. However, as we will see later, this pattern will not hold for larger values of n and
t. The multicasting opportunities which scale with n and t consist of users transmitting requested packets

to a set of t − 1 users whose cache “planes” are aligned along different dimensions. This will be shown
in the following example.
B. 3-Dimension Example
Mn
m

= 3 and each

m t
= 3 lattice points. Hence, the number of packets per file is K = M
= 27.

We consider a 3-dimensional hypercube (cube in this case), where d = t =

m
dimension consists of M

m
m 2
Let n = M
t= M
= 9 and user i request file i. Similar to the 2-dimensional lattice, each lattice point

on the cube represents a set of m packets, each from a different Wi , i ∈ F (see Fig. 2(b)). For the cache
placement, each user caches all packet sets represented by a plane of lattice points of the cube.
In Fig. 2(b), we show the cache of 3 users, u0 , u1 and u2 , depicted by the red, green and blue planes
which are orthogonal (let users u0 = 2, u1 = 4 and u2 = 8). Given this 3-tuple of orthogonal planes, first
consider the packet set {Wi,(2,1,2) , ∀i ∈ F} which lies on the intersection of all three planes and therefore

8

(a)

(b)

Fig. 2. a) An example of the proposed scheme in a D2D network with n = 4, M/m = 1/2 and K = 4. Each point

on the lattice represents a set of packets. Each user’s cache is represented by a line, where the user caches the points
on the lattice which intersect that line. b) Each point on the 3D-lattice represents a set of packets. Each user’s cache
is represented by a plane of lattice points. The right figure represents a multicasting group, or a collection of 3
planes, where any two are orthogonal. The points on the intersection of two or more of these planes are highlighted.
Every two users in this group share two packets that are requested by the third user.

cached by all 3 users. Any packet from this set does not need to be transmitted among these 3 users. Next,
consider packets which are cached by exactly 2 of the 3 users. This is analogous to the points which lie
on the intersection of exactly 2 out of the 3 planes. The intersection of the red and green planes yields
the points representing the packets Wi,(2,1,0) and Wi,(2,1,1) for all i ∈ F . These packets are cached at
both users u0 and u1 , but not user u2 . It can be seen that Wf8 ,(2,1,0) and Wf8 ,(2,1,1) are requested by user
u2 = 8, and are available at user u0 and u1 . In general, each user among this 3-tuple requests two packets

which are cached at the other two users. Equivalently, this shows a coding opportunity for multicasting
from one user to the other two users within this 3-tuple, which will be shown in the following.
In this delivery phase, each user will multicast the coded packets based on the observations discussed
above. In particular, every 3-tuple of orthogonal planes on the cube (representing the cache content of 3
users) represents a coded multicasting group, where each user multicasts one codeword to the other two
users. For example, in Fig. 2(b), for the depicted 3-tuple of planes (red, blue, green), user u0 transmits
Wf4 ,(2,2,2) ⊕ Wf8 ,(2,1,1) to u1 and u2 ; user u1 transmits Wf2 ,(1,1,2) ⊕ Wf8 ,(2,1,0) to u0 and u2 ; user u2

transmits Wf2 ,(0,1,2) ⊕Wf4 ,(2,0,2) to u0 and u1 . By using the cached packets, each user within this multicast
group can decode the requested packets. In this case, 3 coded multicasting packets are transmitted and
will result in a traffic load of

3
27

= 19 . In general, each user needs packets which are associated with all

lines orthogonal to the plane representing that user’s cache. These lines are formed by the intersections of

9

all planes which are orthogonal to each other and orthogonal to the plane representing the user’s cache.
In other words, each user will receive all requested packets by forming multicasting groups with all pairs
of users for which all three users cache a plane orthogonal to each other. The total number of 3-tuples,
or multicasting groups, is equivalent to the number of lattice points, K . The transmission rate is equal

m t
to the product of the number of multicasting groups, K = M
= 27, the number of transmissions per

t
m
1
group, t = 3, and the size of each transmission, 1/ M
= 27
. Therefore, R = 3.
m 2
C. General Achievable Scheme for n = ( M
)

We build a hypercube lattice with t dimensions and each dimension has

m
M

lattice points in length.

Each lattice point represents a set of m packets, each from a different i ∈ F . Each user caches packets
represented by the lattice points of a distinct (t − 1)-dimensional hyperplane of the hypercube by holding
one dimension constant and allowing other dimensions to vary. In the delivery phase, each multicast group
comprises of users, each of which caches a hyperplane that is “orthogonal” to the cached hyperplanes
of every other user in the group. Within these groups, users multicast a set of coded packets requested
by other users in the group. Formally, the cache placement and delivery phase are as follows:

m t
• Cache Placement Phase: For all Wi ∈ F , partition file Wi into M
packets of equal size labeled

m
as Wi,(`0 ,...,`t−1 ) where `j ∈ {0, . . . , M
− 1} for all j ∈ {0, . . . , t − 1}. Let user u ∈ U cache a

set of packets {Wi,(`0 ,...,`t−1 ) , i = 1, · · · , m} such that `j = (u mod

m
M ),

m
where j = bu/ M
c, and

m
m t−1
`i ∈ {0, . . . , M
− 1} for any i 6= j . Hence, each user caches ( M
)
packets from each file i ∈ F .5
•

Delivery Phase: Consider all sets of users S = {u0 , . . . , ut−1 } ⊂ {0, . . . , n − 1} such that

m
buj / M
c = j for all j ∈ {0, . . . , t − 1} and |S| = t. Each user ui ∈ S transmits
⊕s∈{0,...,t−1}\i Wfus ,(a0 ,...,at−1 )

(3)

where
aq =




(us + s − i) mod


uq mod

m
M,

m
M,

if q = s
(4)
if q 6= s

The correctness of the proposed scheme is shown in Appendix A. To illustrate the notations of the
general scheme, we re-state the 3-dimensional example discussed in Section III-B as follows.
5

Throughout this paper, we use the following definition for the modulo operation: a mod b = a − ba/bc. It follows that if

a ∈ Z and b ∈ Z+ , then a mod b is a non-negative integer in the range of [0, b − 1].

10
m 2
1) An Example Using General Scheme for n = ( M
) : In Fig. 2(b), the selected multicast group

is a set of three users: S = {2, 4, 8}. We relabel these users so that u0 = 2, u1 = 4 and u2 = 8.

m
This satisfies the condition that j = buj / M
c for j ∈ {0, . . . , t − 1}, which ensures that these 3
users cache planes orthogonal to each other. Moreover, S ⊂ {0, . . . , n − 1} and |S| = t. Using (3)
and (4), user u0 (user 2) includes a packet in a multicast for all s ∈ {0, 1, 2} \ 0. Those packets
are Wfu1 ,(u0 mod

m
M

,(u1 +1) mod

values of u0 , u1 , u2 and

m
M

m
M

,u2 mod

m
M

)

and Wfu2 ,(u0 mod

m
M

,u1 mod

m
M

,(u2 +2) mod

m
M

).

Substituting the

yields packets Wf4 ,(2,2,2) and Wf8 ,(2,1,1) which match the packets u0 transmits

in Fig. 2(b).
In the cache placement phase, user 2 caches all packets Wi,(2,`1 ,`2 ) for i ∈ {0, ..., m − 1} and `1 , `2 ∈
{0, 1, 2}. Both packets transmitted by user 2 satisfy these conditions. Furthermore, user 4 only caches

packets {Wi,(`0 ,1,`2 ) }, and user 8 only caches packets {Wi,(`0 ,`1 ,2) }. Hence, we recognize that Wf4 ,(2,2,2)
is in user 8’s cache, but not in user 4’s cache and the opposite is true for Wf8 ,(2,1,1) . Therefore, both user
4 and 8 can decode the requested packet as they have the other packet of the coded multicast cached. A
similar argument will show the coded multicasts from users 4 and 8 follow (3) and (4) can effectively
deliver the requested packets to users {2, 8} and {2, 4}, respectively.
D. Achievable Rate and Packetization
The achievable rate using the proposed hypercube based approach is given by the following theorem.
Theorem 1: Let m, n, M be the library size, number of users and the cache size per user, respectively.
√

m 2 m
, M ∈ Z+ and t ≥ 2, the following rate is achievable:
For r ≥ 2, n = M
Rhc (M ) =

with the requirement of K = K hc =

√

√

n

n

m
M

(5)

.

Proof: The number of packets per file is equal to
 m t  m nM/m √ √
n
K hc =
=
= n ,
M
M
m
M,

or the number of lattice points of each dimension,

(6)

raised to the power equal to the number of

dimensions, t.
The multicast groups consist of all possible user sets such that one user is selected from t (number

m t
m
of dimensions) sets of M
(number of lattice points per dimension) users. Therefore, there are M

m t
multicast groups for which each of t users transmits a codeword with a length of 1/ M
F . The rate
is then
hc

R (M ) =


m t
M

·t·
F

1
t

m
(M
)

F
=t=

nM
m
=
m
M

(7)

11

where n =


m 2
M .

The throughput achieved by the proposed achievable scheme is given as follows.

m
M

Corollary 1: Let Cr be the constant link rate under the protocol model. For r ≥

√
2, n =


m 2
M ,

∈ Z+ and t ≥ 2, the throughput achieved by the proposed scheme is:
T hc (M ) =

Cr
hc
R (M )

=

M
Cr
m

(8)

Proof: Following (1), in order to deliver F Rhc (M ) coded bits without spatial reuse (at most one
active link transmitting at any time), we need D = F Rhc (M )/Cr channel uses. Therefore, we obtain
(8).
E. Extension of the achievability to n ≤


m 2
M

From the construction of the hypercube scheme, we see that within each multicasting group, each user

m
m 2
m
us ∈ S needs to receive M
− 1 packets from t − 1 users. When n = M
− 1,
, we have t − 1 = M
meaning that each of the t − 1 users in S \ us sends c = 1 packet to user us . This guarantees a symmetric
multicasting group, where every user transmits the same number of coded packets. The work of [14]
demonstrated that a caching scheme with symmetric multicasting groups generally results in an overall
smaller transmission rate than that of a caching network with asymmetric multicasting groups.
A more general condition that makes the multicasting groups symmetric is
c(t − 1) =

m
− 1,
M

(9)

where c ∈ Z+ . In this case, for a multicasting group, each user requests c(t − 1) packets that the rest of
the t − 1 users have cached. Each user transmits c packets that a user requests. Note that these c packets
cannot be included in a single coded multicast because the receiving user cannot decode more than one
unknown packet and therefore cannot recover the requested packets. Hence, for each multicasting group,
each user will transmit c coded multicast messages. In this case, the required number of packets per file

m t
m
K = Kghc = M
is identical to K hc . By substituting c = ( M
− 1)/(t − 1), the transmission rate is
given by

M
.
(10)
M
M
m

m 2
We note that an exact description of the extension to the case of n ≤ M
requires a modification of

2
m
the delivery phase shown in Section III-C for n = M
and its correctness follows from a modified
Rghc (M ) =

 m t  m −t

ct =

t m
t−1M



1−

version of the proof in Appendix A. These are omitted due to space limitation.

12

F. Comparison to State-of-the-Art D2D Caching Networks
As was proposed in [14], the achievable rate and packetization pair is
 
   
 
m
n
m
n
M
0
0
(R , K ) =
1−
,t
=
− 1, t
.
M
m
t
M
t
Implementing Stirling’s formula demonstrates that
  s
m
M
m
M
n
M
K0 = t
∼
eln n+n( m ln M +(1− m ) ln m−M ) ,
t
2π(m − M )

(11)

(12)

as n → ∞. We are interested by what factor the hypercube approach has reduced the necessary
packetizations in comparison to the scheme in [14]:
s
M
m
K0
M
∼
eln n+n(1− m ) ln m−M ,
hc
2π(m − M )
Kg

(13)

which grows exponentially as n → ∞. Furthermore, we are interested in comparing R0 and R achieved
by the scheme in [14] and the proposed hypercube based approach. Hence, we obtain
R0 (M )
t−1
m
=
=1−
,
t
nM
Rghc (M )

(14)

It is clear that, given a constant m and M ,
K0
= ∞,
n→∞ Kghc

(15)

R0 (M )
= 1.
hc (M )
n→∞ Rg

(16)

lim

and
lim

The hypercube approach demonstrates a significant decrease in the number of packetizations, especially
as the number of users becomes large. Furthermore, the rate only increases slightly, and for a large
number of users the rate of the two schemes are essentially equivalent.

G. Decentralized Coded Caching using Proposed Schemes
Using the idea of [16], we will now explore the use of centralized D2D caching schemes to design
decentralized coded D2D caching networks. A decentralized network consists of n users, randomly caches
√
2. A centralized cache
a M
m fraction of content files. In the following, we focus on the case that r ≥
placement phase defines sets of packets from which users randomly cache one of these sets independently
of other users’ cache. Then, a modified delivery phase is used to serve the user requests.
More specifically, we consider the file partition and cache placement of the proposed D2D caching
scheme designed for n0 (dummy) users such that each of them caches a

M
m

fraction of the content files,

13

where n0  n.6 This means that we partition each file into K 0 =

cache placement proposed in Section III-C and III-E, where t0 =

0
m t
M
n0 M
m .

packets defined by the centralized
Then, we have n0 sets of packets

and each of which is designed to be cached by one of the n0 dummy users. Each of the n users in the
decentralized network randomly caches one of the n0 packet sets defined by the centralized scheme. The
probability of caching any packet set is

1
n0 .

The coded multicasting opportunities become clear as we

consider subsets of users in the network who have collectively cached all of the n0 packet sets exactly
once. In this case, these users can have their requests satisfied by performing the corresponding delivery
phase defined by the centralized scheme. This process is repeated until the remaining unsatisfied users do
not collectively cache all packet sets. These remaining users are served with a slightly modified delivery
phase. The following example demonstrates this process for the hypercube approach.
1) An Example: In this example, a decentralized network of n = 32 users and each user caches
of the library. Let n0 = 6 and t0 =

n0 M
m

M
m

=

1
3

= 2. There are 6 packet sets defined by a 2-dimensional hypercube

described in Section III-E. As shown in Fig. 3, there are

m
M

= 3 lattice points on each dimension of the
0

m t
) = 9.
hypercube. The number of packets per file for this decentralized network is K 0 = Kghc = ( M

The packet sets, corresponding to each row or column of the hypercube, are labeled as Zi,j where
m
i ∈ {0, . . . , t0 − 1} and j ∈ {0, . . . , M
− 1}. Each of the 32 users caches one of these sets at random

using a uniform distribution, independently of other users, such that each set has an equal probability of
being cached at any given user. A possible outcome of the random caching is shown in Fig. 3. Let the
random variable Xi,j be the number of users that cache Zi,j and xi.j be the realization of Xi,j . In this
case, we have x0,0 = 6, x0,1 = 3, x0,2 = 6, x1,0 = 7, x1,1 = 6 and x1,2 = 4. For instance, 6 users cache
the 0-th row of packets, Z0,0 , and 4 users cache the 2nd column of packets, Z1,2 .
To satisfy the 32 distinct user requests, there are multiple delivery phases. First, observe that we can
choose min{x0,0 , x0,1 , x0,2 , x1,0 , x1,1 , x1,2 } = 3 non-overlapping user sets each consisting of 6 users who
collectively cache the 6 packet sets (see Fig. 3(a)). These 3 user sets can perform the delivery phases as
if they were centralized networks. After this, there are 32 − 3 · 6 = 14 remaining users with unsatisfied
requests as shown in Fig. 3(b). Of these remaining users, we consider a set of 5 users who collectively
cache every packet set except Z0,1 . These 5 users can perform a centralized delivery scheme by including
one previously satisfied user who caches Z0,1 .7 In the third phase, as shown in Fig. 3(c), of the remaining
14 − 1 · 5 = 9 unsatisfied users, we consider 2 sets of 4 users who collectively cache the packet sets Z0,0 ,
6

Note that n0 is only a dummy variable to define the packet sets for the n users in the decentralized network to cache.

7

We can simply let a satisfied user request empty packets.

14

user group not
considered

6

3

2

--

3

--

--

--

6

3

2

--

# of 7
6
users
3 delivery phases

(a)

4

4

3

1

1 delivery phase

(b)

3

2

--

2 delivery phases
(8 of 9 user groups)

(c)

1

--

--

1 delivery phase
(3 of 9 user groups)

(d)

Fig. 3. A depiction of the caching and delivery phases using the hypercube approach to design decentralized D2D

caching networks. The lattice structure represents the file packetization and the numbers to the left and bottom of
the lattice are the number of remaining unsatisfied users who cache the rows and columns respectively. The red
“X”s represent pairs of users that are not considered in the delivery phase.

Z0,2 , Z1,0 and Z1,1 . These user sets can perform the delivery phases by including previously satisfied

users that cache Z0,1 and Z1,2 . Note that the points of the 3 by 3 lattice not only represent a packet for
every file in the library, but also represent all multicasting groups in the delivery phase. In this particular
example, there is one multicasting group marked by the red “X” in Fig. 3(c) that does not need to be
considered since both users in this multicasting group are satisfied. Similarly, after the delivery shown in
Fig. 3(c), we are left with a single user (but forming 3 multicast groups) who can obtain the requested
packets from the 3 users caching these packets. The transmission rate of this example is given by


1
220
8
0
Rghc =
.
(17)
R = 3+1+2· +3·
9
9
9
This decentralized scheme does not require any additional packetization. Interestingly, note that the

transmission rate of this scheme is even larger than that of conventional unicasting with Ru = n 1 − M
m =
64
3 .

This occurs because there is only unicasting for the 2-dimensional hypercube approach and we

assume every user transmits in every applicable user pair (multicasting group), which allows unnecessary
transmissions as users would be transmitting to users with previously satisfied requests (e.g., in Fig. 3(b),
we assume users still serve users caching the packet sets of the middle row). We want to emphasize
that this example is just for the purpose of illustration and this effect on the overestimation of the rate
diminishes for a larger values n and t0 (see Fig. 4).
2) General Decentralized Algorithm: In this subsection, we describe a general algorithm for using the
hypercube scheme for the design of decentralized coded D2D caching networks. The cache placement

15

and delivery phases are defined as follows:
0

•

Cache Placement Phase: Define n0  n such that t0 = nmM ∈ Z+ . For all k ∈ F , split file
0
m t
m
k into M
packets of equal size labeled as Wk,(`0 ,...,`t0 −1 ) where `q ∈ {0, . . . , M
− 1} for all

m
q ∈ {0, . . . , t0 − 1}. For all i ∈ {0, . . . , t0 − 1} and j ∈ {0, . . . , M
− 1}, define packet set Zi,j to

include all packets Wk,(`0 ,...,`t0 −1 ) such that `i = j . Let every user u ∈ {0, . . . , n − 1} uniformly
caches one of the n0 packets sets at random with probability
•

Delivery Phase: Define X as a t0 ×

m
M

1
n0 .

matrix where element xi,j equals the number of users who

cache the packet set Zi,j . While X has non-zero elements, we do the following. 1) let Xi∗ be the
P 0 −1 ∗
number of zero elements in the i-th row of X ; let X̂ ∗ = ti=0
Xi . 2) let x be the minimum non-zero
element of X . 3) let user sets {S1 , . . . , Sx } be disjoint sets each of which contains n0 −X̂ ∗ unsatisfied
users. Each of this user set collectively caches every packet set Zi,j that satisfies xi,j 6= 0; 4) define

user sets {S10 , . . . , Sx0 } such that each user set has size X̂ ∗ and collectively caches every packet set
Zi,j that satisfies xi,j = 0. Note that Sk ∩ Sk0 = ∅. 5) for each k ∈ {1, . . . , x}, let users in Sk ∪ Sk0
Q 0 −1 ∗
perform a centralized hypercube D2D delivery phase while ignoring the ti=1
Xi multicasting

groups which contain only previously satisfied users; 6) update xi,j as xi,j = max(0, xi,j − x). 7)
go back to step 1) until all elements in X are zero.
3) Performance: Performance of the decentralized design is given in the following theorem.
Theorem 2: Let m, n, M be the library size, number of users and the cache size per user, respectively.
√
0
m
m
− 1, where ( M
, c) ∈ Z+ , t0 = nmM ≥ 2, and the required number
Assume that r ≥ 2, c(t0 − 1) = M
0
m t
of packets per file K 0 = M
. Furthermore, if n ≥ βn0 log n0 for some β > 1, then all the packet sets

can be cached in the network with probability 1 − n0 1−β , and the following transmission rate is achieved
with probability 1 − o(1) as n, n0 → ∞,

Rdhc (M )

t0 m
≤ kα 0
t −1M



M
1−
m


,

(18)

where

kα =














 n

n0


0
m
(dβ − 1 + α) log n0 t0t−1 M
1− M
m ,
q

 0

n
2n
t m
M
0
+
α
log
n
n0
n0
t0 −1 M 1 − m ,
q

 0
2n log n0
t m
1 log log n0
+
1 − α 2 log n0
n0
t0 −1 M 1 −

if n = βn0 log n0 ,
if ω (n0 log n0 ) = n ≤ n · polylog(n),



3
M
,
if
n
=
ω
n
(log
n)
.
m

(19)
Here, α > 1, dβ is a number depending only on β and polylog(n) denotes the class of functions

S
k
k≥1 O (log n) .

16

Proof: First, we show that with probability 1 − n0 1−β , all the packet sets can be cached in the D2D
network. Since each packet set is uniformly selected by each user at random, it can be observed that it
is a famous “bin-ball” problem, where the packet sets are the n0 bins and users are the n balls. Hence,
we need to characterize the probability that no bin is empty. Let Yk demote the event that the k bin is
empty, then we can compute

P (Yk ) =

1
1− 0
n

n

0

≤ e−n/n .

(20)

Hence
P ∩k Yk



X

0
= P ∪k Yk = 1 − P (∪k Yk ) ≥ 1 −
P (Yk ) ≥ 1 − n0 e−n/n
k

0 −βn0 log n0 /n0

≥ 1−ne

=1−n

0 1−β

.

(21)

Second, we will show (18) holds with probability 1 − o(1). Let L denote the maximum number of users
that cache the same packet sets, or equivalently, the maximum number of balls in each bin. This problem


is to find kα such that the tail estimate P {L ≥ kα } ∩ ∩k Yk = 1 − o(1). Hence, by using (10), we


0
m
t0 m
M
can obtain Rdhc (M ) ≤ L t0t−1 M
1− M
m ≤ kα t0 −1 M 1 − m with probability 1 − o(1). From Theorem
1 in [22], we can show that if kα , α > 1 satisfies (19), then we must have P ({L ≥ kα }) = 1 − o(1).
Furthermore, since


P ({L ≥ kα }) = P {L ≥ kα } ∩ ∩k Yk + P ({L ≥ kα } ∩ {∪k Yk })


= P {L ≥ kα } ∩ ∩k Yk + P ({∪k Yk }) P ({L ≥ kα } | {∪k Yk })


1−β
,
≤ P {L ≥ kα } ∩ ∩k Yk + n0

(22)



we obtain P {L ≥ kα } ∩ ∩k Yk ≥ P ({L ≥ kα }) − n0 1−β = 1 − o(1). This completes the proof.
4) Simulation Methods and Results: Decentralized networks are simulated with the number of users,
n, equals to 1000 and 10000 users, respectively. For these networks we simulate a decentralized cache

scheme for all parameter pairs, n0 , t0 ∈ Z+ , such that t0 ≥ 3, n0 ≤ 64 for the network of 1000 users and

n0 ≤ 500 for the network of 10000 users, and c (t0 − 1) =

m
M

− 1 holds, where c ∈ Z+ and t0 =

n0 M
m .

For each parameter pair, 104 decentralized cache placement and delivery phases are simulated. Given
that n0  n in all cases, there were no instances of a simulated decentralized network where a packet
set was not cached at least once. The mean and standard deviation of the rate, µR and σ , respectively,
are depicted in Fig. 4.
From these results, we can see that the decentralized hypercube scheme outperforms the uncoded
scheme. On both plots, the set of points with a fixed t0 is highlighted. As t0 increases, the rate comes

17

1

0.8

0.6

0.4

0.2

0
0

0.2

0.4

0.6

0.8

1

0

0.2

0.4

0.6

0.8

1

Results of the hypercube approach decentralized D2D caching network simulations for n = 1000 users


(left plot) and n = 10000 users (right plot). The mean rate µR = E Rdhc (M ) plus or minus 3 times the standard

Fig. 4.

deviation, µR ± 3σ, for a variety of hypercube constructions are compared to the uncoded rate and centralized rate.

closer to the centralized coded rate. However, the number of packets per file, K 0 , increases exponentially.
This exciting result demonstrates that there is a trade-off in designing decentralized D2D caching networks
using the hypercube approach. Specifically, we can increase the number of packets to reduce the rate
and vice versa. This may provide the flexibility to yield a practical amount of packetization while having
limited impact on the transmission rate. Furthermore, we can see that the decentralized approach yields
more realizable constructions of the hypercube. In fact, as shown in Fig. 4, the number of realizable
hypercube schemes for 1000 and 10000 users are 2 and 3 respectively (t = 4, 10 for n = 1000 and
t = 4, 10, 100 for n = 10000). In comparison, the decentralized network design provides many more

possibilities.
IV. RUZSA -S ZEM ÉREDI GRAPH C ODED C ACHING A PPROACH
While the hypercube approach requires significantly (in fact, exponentially) less number of packets per
file compared to [14], the hypercube approach still yields an exponential number of packets relative to
n if m and M are fixed. While the hypercube approach certainly increases the domain for which a D2D

caching network is implementable, it is still an open question as to whether there exists a coded D2D
√
caching network scheme without spatial reuse (r > 2) with a sub-exponential number of packets per file.
Motivated by [19], in this section we propose a coded D2D caching scheme based on Ruzsa-Szeméredi
graphs which requires only a sub-quadratic packetization.

18

A. Ruzsa-Szeméredi Graphs
In this section, we focus on a specific Ruzsa-Szeméredi graph design, which was first introduced in
[17] and used in a novel manner in [19] to construct a cache placement and coded multicasting scheme
for a shared link caching network. Let G(V, E) be an undirected graph, where V is the vertex set and E
is the edge set. We introduce the following definitions [18], [19].
Definition 4: Given a graph G(V, E), a matching M in G is a set of pairwise non-adjacent edges; that
is, no two edges share a common vertex.

♦

Definition 5: The set of edges M ∈ E is an induced matching if for the set S of all the vertices incident
on the edges in M, the induced graph GS contains no other edges apart from those in the matching M.
♦
Definition 6: A disjoint matching M is a matching such that any pair of the edges in M are not
adjacent to any third edge in E .

♦

Definition 7: A graph G(V, E) is called an (γ, τ )−Ruzsa-Szeméredi (RS) Graph if its set of edges
consists of τ pairwise disjoint induced matching, each of size γ .

♦

An example of RS graph is shown in Fig. 5(a), which is also used in [19]. We will apply RuzsaSzeméredi graph to construct a cache placement and a coded multicasting scheme in wireless D2D
caching networks. In this section, we will focus on the case that a transmission from any node can be
√
received and successfully decoded by all nodes in the network (e.g., r ≥ 2). In the remainder of this
section, we will first introduce a motivating example and then present the general achievable scheme.
B. An Example
Similar to [19], our proposed scheme is based on RS Graphs. In this example, let m = n = 6 and
M = 4. Each file is partitioned into 4K packets with F/K bits each. Without loss of generality, we

let user u request file u. To find the cache placement and the coded multicasting scheme, we build a
(2, 3)-Ruzsa-Szeméredi graph G with 6 vertices as shown in Fig. 5(a) where each vertex is represented

by 3 packets. In our proposed achievable scheme, we partition each file into n(2γ − 1) = 18 packets
and denote the j th packet from file i by Wi,j , i ∈ {1, · · · 6}, j ∈ {1, · · · , 18}. The cache placement and
coded multicasting scheme are shown in Fig. 5(b), where each vertex represents a user and his cached
packets are shown inside each vertex. For instance, the most left vertex, vertex 1, represents user 1 and
his cached packets, which are Wi,j , where i ∈ {1, · · · , 6} and j ∈ {1, 2, 3, 7, 8, 9, 10, 11, 12, 13, 14, 15}.
Note that these exclude the packets represented by its neighboring vertices, vertex 2 and vertex 6, which
are shown in Fig. 5(b).

19

Vertex 2

Vertex 3

User 2

Wi,4 , Wi,5 , Wi,6

Wi,7 , Wi,8 , Wi,9

Wi,j
j 2 {4, 5, 6, 10, 11, 12
13, 14, 15, 16, 17, 18}

Vertex 1

Vertex 4
Wi,10 , Wi,11 , Wi,12

Wi,1 , Wi,2 , Wi,3

Wi,13 , Wi,14 , Wi,15

Vertex 6

Vertex 5

W1,4
W3,4

W4,14
W5,16

W5,11 W2,7 W5,17
W6,13 W1,16 W4,8

W2,1

W4,13

W5,10 W1,17

W6,14
W6,2

User 1

User 4

Wi,j
j 2 {1, 2, 3, 7, 8, 9

10, 11, 12, 13, 14, 15}

Wi,16 , Wi,17 , Wi,18

User 3
Wi,j
j 2 {1, 2, 3, 7, 8, 9
13, 14, 15, 16, 17, 18}

W3,10

W4,7

W6,1

W2,9
W1,18

W3,6 W5,18 W1,6
W3,12 W4,9 W2,8

Wi,j

W1,5

W3,11 W6,3
W2,2 W5,12

W2,3
W3,5

W4,15
W6,15

j 2 {4, 5, 6, 7, 8, 9
10, 11, 12, 16, 17, 18}

Wi,j
j 2 {1, 2, 3, 4, 5, 6
7, 8, 9, 13, 14, 15}

User 6

User 5

(a)

Wi,j
j 2 {1, 2, 3, 4, 5, 6
10, 11, 12, 16, 17, 18}

(b)

Fig. 5. a) A (2, 3)-Ruzsa-Sezmeredi graph with 6 vertices which represents a coded caching scheme where n = 6,

M/m = 2/3, and K = n(2γ − 1) = 3n = 18. The graph can be split into τ = 3 induced pairwise disjoint
matchings denoted by different colors in the graph, which cover all edges of the original graph. b) An example of
the proposed scheme in a D2D network with n = m = 6, K = 18 and M = 4. Each vertex represents a user. The
content of each rectangle represents cached packets. The coded multicast packets are shown in the center of the
figure.

The coded multicasting scheme is shown in the center of Fig. 5(b). For example, user 1 transmits
W2,1 ⊕ W4,13 ⊕ W5,10 , which are used by users 2, 4, 5 to decode packets W2,1 , W4,13 , W5,10 , respectively.

In particular, it can be seen that user 2 has W4,13 and W5,10 such that he can decode W2,1 . Similarly,
user 4 and 5 can also decode the corresponding packet in a similar manner. In this example, if we use the


achievable scheme proposed in [14], each file is split into t nt = 4 64 = 60 packets and the transmission
rate is given by

m
M

−1 =

6
4

− 1 = 12 . While using the proposed scheme, the transmission rate is

12
18

= 23 .

Therefore, the proposed scheme requires K = 18 instead of K = 60 as the scheme in [14], and the
achievable transmission rate of the proposed scheme is

2
3

instead of

1
2

achived by the scheme in [14].

Hence, we observe that while sacrificing the transmission rate by ( 23 − 21 )/ 12 =
scheme reduces the number of packets needed per file by

60−18
60

=

7
10

1
3

= 33%, the proposed

= 70%.

C. General Achievable Scheme
In this section, we generalize the deterministic caching and coded delivery scheme illustrated in Section
IV-B to the general case of m, n and M .

20

•

Building the Ruzsa-Szeméredi graph: We build a Ruzsa-Szeméredi graph with n vertices, each
with a degree of n − t. This graph consists of τ pairwise disjoint induced matchings and each has
γ edges.

•

Cache Placement Phase: The cache placement scheme is closely related to the scheme in [19]
and is designed according to the Ruzsa-Szeméredi graph. Each file is divided into K = n(2γ − 1)
packets, labeled by {Wi,j , i = 1, · · · , m, j = 1, · · · , K}. Each vertex in the RS graph represents
2γ − 1 distinct packets. Node u caches packets corresponding to those vertices that are not adjacent

to itself and packets corresponding to the vertex itself.
•

Delivery Phase: As a consequence of the caching scheme described above, any subset of 2γ − 1
nodes belonging to a disjoint matching of size γ in U = {1, . . . , n} has the property that they share
2γ − 1 packets from each file. Consider one such subset. For any file requested by the remaining
(2γ)-th node, by construction, there are 2γ − 1 packets shared by the other 2γ − 1 nodes and needed

by the (2γ)-th node. Therefore, each node in every disjoint matching has 2γ − 1 packets that are
useful for the remaining 2γ −1 nodes. Furthermore, such sets of packets are disjoint (empty pairwise
intersections). For delivery, in each disjoint matching, each node computes the XOR of its 2γ − 1
useful packets and multicasts it to all other nodes in this disjoint matching. In this way, for every
multicast transmission exactly 2γ −1 nodes will be able to decode a useful packet using “interference
cancellation” based on their cached content.
The achievable rate is given in the following.
Theorem 3: Let m, n, M be the library size, number of users and the cache size per user, respectively.
√
For r ≥ 2, n = Λz , where Λ is any positive integer such that z ≥ 2Λ, and
1

M = 2mn− 2Λ4 ln Λ ,

and let t =

nM
m

(23)

∈ Z+ , the following rate is achievable:
RRS (M ) =

with the requirement that K = K RS = (2γ − 1)n.

τ 2γ
n 2γ − 1

(24)


Proof: Theorem 1 is proved in Appendix B.
When we consider the asymptotic regime as n becomes large, we obtain the following corollary.
√

Corollary 2: For r ≥ 2, when n → ∞, K = O n2−δ and M = 2mn−c1 δ exp(−c2 /8) , where c1 , c2
are some positive constants, let t =

nM
m

∈ Z+ , the following rate is achievable:
RRS (M ) ≤ nδ + o(nδ ),

(25)

21

where δ =

2 ln 10.5
ln Λ .



Corollary 2 can be proved using the value of τ given in Appendix B and the relation γ = O (n/τ ).
From Corollary 2, we can see that when Λ is large enough, or equivalently, n is large enough, δ can
be arbitrarily small. In other words, it can be computed from (25) that RRS (M ) = (10.5)2 logΛ n . The
throughput achieved by the proposed achievable scheme is given as follows.
Corollary 3: Let Cr be the constant link rate under the protocol model. For r ≥

√

2, the per user

throughput is given by
T RS (M ) =

Cr
RRS (M )



= C√2 · n−δ + o n−δ ,

n→∞

where RRS (M ) and δ are given by (24) or (25), is achievable.

(26)


Proof: This corollary can be proved by using the same procedure as the proof of Corollary 1.
D. Comparison to Other Schemes
Due to the sub-quadratic packetization with the number of users n, which is significantly lower than
that of the hypercube based approach proposed in Section III, the achievable rate of the RS graph based
√
design given by (5) and (25) for r ≥ 2 is obviously worse than the achievable rate of the hypercube
based design given in (10) and the original design [14], when n increases and m and M are fixed.
However, there is still a significant gain in terms of transmission rate compared to the conventional
uncoded unicasting scheme in some parameter regimes. In the following, we compare the transmission
rates of the uncoded scheme, Ru , and the RS Graph scheme, RRS where m, M and n are the same for
both schemes. By solving (23) for n we obtain
 m 2Λ4 ln Λ
n= 2
M

(27)

which better defines the constraint relating n to M/m for the this scheme based on the proposed RS
graph design. For the purposes of comparison, (27) holds for both the uncoded and RS schemes. The
transmission rate for the uncoded scheme is

 


M
m 2Λ4 ln Λ
M
u
R =n 1−
= 2
1−
.
m
M
m
Furthermore, the transmission rate of the RS scheme given by (5) is
2γ
2γ  m 4Λ4 ln 10.5
RRS =
nδ =
2
2γ − 1
2γ − 1 M

(28)

(29)

Then we obtain


M
Ru
2γ − 1  m 2Λ4 (ln Λ−2 ln 10.5)
=
2
1−
.
RRS
2γ
M
m

(30)

22

Notice that, (30) is only dependent on M , m and Λ and not dependent on z . This occurs because z is a

m
function of M , m and Λ and for these derivations z is essentially substituted with z = 2Λ4 ln 2 M
/ ln Λ.
2Λ4 ln(2 m )
2 ln 10.5
M
This result demonstrates that for a fixed m/M and Λ > 10.52 , by using τ = Λ ln Λ (1+ ln Λ +o(1))
(see Appendix B), we have8
Ru
Ru
=
lim
= ∞,
n→∞ RRS
Λ→∞ RRS
lim

(31)

which shows a significant gain in terms of transmission rate of the RS graph approach compared to
uncoded unicasting scheme.
Remark 2: It can be seen that the idea of designing the decentralized coded caching approach discussed
in Section III-G can also be extended to the RS graph coded caching methods. The major difference
is that the packet sets, each of which will be randomly and uniformly cached by users, are constructed
based on the RS graph. The delivery procedure is similar to that in Section III-G.
V. ACHIEVABILITY WITH S PATIAL R EUSE
In this section, we choose (e.g., reduce) the transmission range r in order to have localized D2D
√
communication such that some spatial reuse is allowed. In contrast to the regime where r ≥ 2, in
this case, we also need to design a non-trivial transmission policy to schedule concurrent active D2D
transmissions. Similar to the scheduling schemes in [14], the proposed policy is based on clustering: the
network is divided into clusters of equal size gc users. Users are allowed to receive messages only from
nodes in the same cluster.9 Therefore, each cluster is treated as a smaller network compared to the entire
network. Assuming that gc M ≥ m,10 the total cache size of each cluster is sufficient to store the entire
file library. Under this assumption, the cache placement and delivery schemes introduced in Sections
III-C and IV-C can be applied to each cluster. Hence, it can been seen that the transmission rate in each
cluster is given by either

Rchc (M )

8

tc m
=
tc − 1 M



M
1−
m


,

(32)

Note that the RS graph based approach cannot perform worse than the uncoded unicasting by the construction. The reason

we need the condition that Λ > 10.54 is due to the fact that the τ obtained from [18], [19] and used in (5) is a sufficient
condition and may not be necessary.
9

Note that this condition can be relaxed by using the similar communication scheme base on ITLinQ [23].

10

If the condition gc M ≥ m is not satisfied, we can choose a larger transmission range such that this condition is feasible.

23
∆

where we define tc = gc M/m, or
RcRS (M ) =

τ 2γ
gc 2γ − 1

gc →∞

=

gcδ + o(gcδ ),

(33)

where tc = gc M/m, gc = Λz and τ , γ and δ are given in Theorem 3. As mentioned in Remark 1, a
straightforward achievable transmission policy consists of grouping the set of clusters into K spatial reuse
sets such that the clusters of the same reuse set do not interfere and can be activated simultaneously.11
In each active cluster, a single transmitter is active per time-slot and it is received by all nodes in
the cluster, as in classical time-frequency reuse schemes with reuse factor K that are currently used in
cellular networks [24, Ch. 17]. An example of a reuse set is shown in Fig. 1. In particular, we can pick
√

2
K=
2(1 + ∆) + 1 [21].
In [14], we observe that there is potentially no order gains as n → ∞ by using spatial reuse. The
benefit of spatial reuse is completely determined by the value of link rate Cr and reuse factor K. In
the newly proposed schemes, since the transmission rate in each cluster is a function of the number of
users, spatial reuse may achieve a higher gain in terms of throughput. Note that from the achievability
point of view, reducing the transmission range r is equivalent to reducing gc . We consider the use of the
hypercube and RS graph approaches separately as we investigate clustering in D2D caching networks.

A. Clustering with the Hypercube Caching Approach
The multiplicative gap between the transmission rate of Rchc and Rghc is given by
Ghc
R =

Rchc
gc t − 1
=
.
hc
n tc − 1
Rg

(34)

From (34), we can see that the transmission rate of each cluster decreases as gc decreases. Furthermore,
the achievable throughput of the hypercube approach with clustering is given by the following theorem.
Theorem 4: Let m, n, M be the library size, number of users and the cache size per user, respectively.
√
m
m
− 1 and M
, tc , c ∈ Z+ , the following per user throughput
For r ≤ 2, tc = gcmM ≥ 2, c(tc − 1) = M
Tchc (M ) is achievable:
Tchc (M ) =

with the requirement of K = Kchc =
11


m tc
.
M

Cr M t c − 1
K m − M tc

(35)

Note that the interference management in this paper is based on protocol model. However, similar scheme can be designed

for AWGN or fading channel model based on the condition that treating interference as noise is optimal (ITLinQ [23]).

24

Proof: By using (2), we can obtain
Tchc (M ) =

where Rchc (M ) is given by (32).

1
Cr M t c − 1
Cr
=
,
hc
K Rc (M )
K m − M tc

(36)

Using (6) and replacing t by tc , we get
Kchc =

 m tc
M

(37)

The multiplicative gap of Tghc and Tchc throughput is given by
Ghc
T =

Cr
1
Cr n t c − 1
Tchc
= √
= √
C 2 K Ghc
C
Tghc
2 K gc t − 1
R

(38)

Remark 3: Note that the throughput has increased by using the clustering scheme compared to the
√
scheme for r ≥ 2 if Ghc
T > 1 or in other words
Cr
C√

2

K

>

gc t − 1
.
n tc − 1

(39)

This relationship can be further simplified if gc M  m and clustering will improve the throughput if
Cr /K > C√2 . This provides a similar result to that was shown in [14]. The exact relationship between

link rate, Cr , and transmission range, r, depends on the physical channel model and wireless network
design. However, Cr may not decrease as r decreases. Hence, clustering has the potential to increase
throughput. In addition, from (37), clustering can also be used for the purpose of reducing the number
of file partitions as also shown in [14]. For a cluster with gc users, the number of file partitions is
 m tc  m gc M/m
=
,
(40)
Kchc =
M
M
and the ratio of the number of file partitions with and without clustering is
(n−gc )
Kghc  m  M
m
,
(41)
=
M
Kchc
√
where Kghc given in (6) is the number of file partitions when r ≥ 2 such that no clustering is used. As
the cluster size gc becomes smaller, an exponential decrease in the number of file partitions is observed.

25

B. Clustering with the RS Graph Caching Approach
In this section we first discuss the throughput of the RS graph coded caching approach with clustering.
We then consider two ways of reducing gc based on the construction in [18], [19] and study their impact
on throughput and cache size requirement. The RS graph scheme achieves the following throughput:
Theorem 5: Let m, n, M be the library size, number of users and the cache size per user, respectively.
√
For r < 2, K = (2γ − 1)gc , gc = Λz , where Λ is any positive integer such that z ≥ 2Λ, and
− 2Λ41ln Λ

M = 2mgc

, let tc =

gc M
m

∈ Z+ , the per user throughput is given by:
TcRS (M ) =

Cr gc 2γ − 1
.
K τ 2γ

(42)


We have the following corollary for the asymptotic regime.
√

−c δ exp(−c2 /8)
, where
Corollary 4: For r < 2, when gc → ∞, K = O gc2−δ , tc ≥ 2, and M = 2mgc 1

where δ =

gc M
m

∈ Z+ , the throughput is given by:


Cr −δ
Cr −δ
RS
Tc (M ) =
g +o
g
,
K c
K c

c1 , c2 are some positive constants, let tc =

2 ln 10.5
ln Λ .

(43)


Since the proofs of Theorem 5 and Corollary 4 are similar to that of Theorem 4 by using Theorem 1
and Corollary 2, the proofs are omitted due to space limitation.
0

1) Decreasing gc by reducing z 0 while keeping Λ the same: Let n = Λz and gc = Λz , where z 0 < z .
From (25) and (33), the multiplicative gap between the transmission rate of RcRS (M ) and RRS (M ) is
given by
GRS
=
R





RcRS (M )
gcδ + o(gcδ )
2(z 0 −z)
2(z 0 −z)
δ(z 0 −z)
δ(z 0 −z)
. (44)
=
=
10.5
+
o
10.5
=
Λ
+
o
Λ
RRS (M )
nδ + o(nδ )

From (44), we can observe that by clustering the D2D network, the transmission rate (traffic load) can
be reduced significantly. For example, if z − z 0 = 2, e.g., the network is partitioned into Λ2 clusters,

−4 < 10−4 . Nevertheless, due to the spatial reuse gain, by using Corollary 1 and 4, the
GRS
R = 10.5

multiplicative gap between TcRS (M ) and T RS (M ) is given by
GRS
T

=
(a)

=


Cr −δ
Cr −δ
TcRS (M )
K gc + o K gc

= √ −δ
T RS (M )
C 2 n + o C√2 n−δ


Cr 1
2(z−z 0 )
2(z−z 0 )
10.5
,
10.5
+
o
C√2 K

where (a) is obtained by repeating the same procedure as (44). From (45), we can see that if

(45)
Cr 1
C√2 K

and Λ

are positive constants, then by increasing z − z 0 , e.g., increasing the number of clusters, the multiplicative

26

RS
RS (M ) can grow to infinity, which means that the gain by using the
gap GRS
T between Tc (M ) and T

spatial reuse in D2D network can be infinite. In practice, even for finite z − z 0 , it is possible to achieve
gains by using spatial reuse. For example, if z − z 0 = 2, then from (45), we can see that
GRS
T =

Cr 1
10.54 ,
C√2 K

(46)

which can be much larger than 1. This surprising result demonstrates that spatial reuse provides significant
gain in throughput even when the reuse factor K is relatively large and there is little increase in the link
capacity from decreasing the transmission range.
As clustering is performed, the required cache capacity M increases. For this specific clustering scheme,
from Theorem 1 and Theorem 5, the following condition for cache capacity M (gc ) must hold
M (gc ) =

− 1
2mgc 2Λ4 ln Λ

− 2Λ41ln Λ

= 2mn


z − z0
= M (n) exp
.
2Λ4

− 2Λ41ln Λ

gc

1

n− 2Λ4 ln Λ

(47)

Note that by using (47), to achieve the promised throughput, it needs M (gc ) ≥ M (n) exp
example, if z − z 0 = 2, it requires M (n/Λ2 ) = M (n)e

1
Λ4

z−z 0
2Λ4



. For

. This demonstrates that if the network is
1

divided into Λ2 clusters, the lower bound of M increases by a factor of e Λ4 , which is insignificant for
reasonablely large values of Λ.
2) Decrease gc by reducing Λ while keeping z unchanged: Let n = Λz and gc = (Λ0 )z , where Λ0 < Λ.
From Corollary 2 and (32), the multiplicative gap between the transmission rate of RcRS (M ) and RRS (M )
is given by
0

GRS
R

0

2 ln 10.5

RRS (M )
g δ + o(gcδ )
(Λ0 ) ln Λ0 z
= cRS
= cδ
=
+o
2 ln 10.5
R (M )
n + o(nδ )
Λ ln Λ z

(Λ0 )
Λ

2 ln 10.5
ln Λ0

2 ln 10.5
ln Λ

z

!

z

= 1 + o (1) .

(48)

From (48), interestingly, we can see that in this case by clustering the D2D network, the transmission
rate is almost unchanged. It follows from Corollary 1 and 4 that the multiplicative gap between TcRS (M )
and T RS (M ) is given by
GRS
T

=
=

0
Cr −δ 0
+ o CKr gc−δ
TcRS (M )
K gc

= √ −δ
T RS (M )
C 2 n + o C√2 n−δ
!
Cr 1
Cr 1
+o
.
C√2 K
C√2 K

(49)

From (49), we can see that similar to [14], there is no fundamental cumulative gain by using both spatial
reuse and coded multicasting. Under our assumptions, spatial reuse may or may not be advantageous,
depending on whether

Cr
K

is larger or smaller than C√2 . In addition, this also depends on how the link

27

rate varies as a function of communication range. This aspect is not captured by the protocol model,
and the answer may depend on the operating frequency and appropriate channel model of the underlying
wireless network physical layer [20].
VI. C ONCLUSION
This work aims to find D2D coded caching network designs which require a more practical amount of
packetization as compared to the state-of-the-art coded D2D caching schemes in [14]. We propose two
new network design approaches, which are hypercube approach and Ruzsa-Szeméredi graph approach. In
particular, the hypercube approach has been designed specifically for D2D and not based off a shared link
scheme as that in [14]. The hypercube approach requires exponentially less packetization as compared
to coded caching scheme in [14] and yields nearly the same per user throughput for a large number of
users. The RS Graph approach was expanded from a previously studied shared link network design [19]
and modified for the design of D2D networks. It requires only subquadratic packetization in terms of the
number of users and achieves a near constant per user throughput. The dramatic decrease in packetization
resulted from the RS Graph approach comes at the cost of a significant increase in throughtput compared
to [14]. In addition, we demonstrate how the hypercube scheme can be expanded to design decentralized
networks and discovered a clear trade-off between transmission rate and packetization. Furthermore, we
explore how breaking up larger networks into smaller networks can utilize spatial reuse and increase
per user throughput. This work represents a major step forward towards practical file packetization in
D2D coded caching networks. Future work may yield other RS graph constructions with more general
packetization requirements and a trade-off between packetization and transmission rate.
A PPENDIX A
P ROOF OF THE C ORRECTNESS OF THE G ENERAL H YPERCUBE S CHEME
In this section, we demonstrate the correctness of the proposed scheme by verifying that all users:
1) locally cache at most M F bits; 2) only transmit content that is locally cached; 3) decode requested
packets from received coded multicasts; and 4) recover the entire requested file.
m t−1
For 1), each user caches a set of ( M
)
packets of size

F
(m/M )t

total number of bits cached locally at each user is
 m t−1
F
·
t · m = M F
m
M
M

which satisfies the local memory constraint for each user.

bits for all m files in the library. The

(50)

28

For 2), for each packet, Wfus ,(a0 ,...,at−1 ) , included in a multicast from user ui , notice that ai = ui mod
m
M,

m
which follows from (3) and (4), and bui / M
c = i as defined for a user in a set S in the delivery

phase. This precisely matches the definition for a packet that user ui cached during the placement phase,
and therefore each user ui ∈ S is guaranteed to have the packets cached that it is about to transmit.
For 3), first notice that, for any user set, S , as defined in the delivery phase, a user uj ∈ S will receive
a requested packet from all users in S \ uj . To prove this consider any user ui ∈ S \ uj . Notice that
(j − i) mod

m
M

m
6= 0 because i 6= j and i, j ∈ {0, . . . , M
− 1}. Furthermore, by (3) and (4), the multicast

from user ui will include a packet Wfuj ,(a0 ,...,at−1 ) such that
aj = (uj + j − i) mod

m
m
6= uj mod
.
M
M

(51)

This precisely defines a packet which is part of user uj ’s request and is not included in user uj ’s cache.
Next, consider every other packet, Wfuk ,(a0 ,...,at−1 ) , included in a multicast from the user ui and notice
that aj = uj mod

m
M

which follows from (3) and (4) where k 6= i, j . This means user uj has these

packets cached and is able to decode the uncached, requested packet from the received multicast from
user ui .
For 4), first consider the following useful property
{(a + b) mod c : b ∈ {−x, . . . , c − 1 − x} \ 0} = {0, . . . , c − 1} \ a mod c

(52)

where x ∈ Z and 0 ≤ x ≤ c − 1. This property holds because {b mod c} = {1, . . . , c − 1}. Now consider
a user group, S , as defined by the delivery phase. By (3) and (4), user uj ∈ S will receive every packet,
Wfuj ,(a0 ,...,at−1 ) , such that aq equals some constant if q 6= j and
aj ∈ {(uj + j − i) mod

m
: i ∈ {0, ..., t − 1} \ j}.
M

(53)

Furthermore, recognizing that i − j ∈ {−j, ..., t − 1 − j} \ 0 and t = m/M demonstrates that
aj ∈ {0, . . . ,

m
m
− 1} \ aj mod
.
M
M

(54)

In other words, user uj collectively receives a “line” of packets from users S \ uj for which t − 1
dimensions of the “hypercube” are held constant and one dimension varies the length of the “hypercube”. The only exception is the packet which user uj already has cached. Moreover, the constants,
{a0 , . . . , at−1 } \ aj , are defined as aq = uq mod

m
M.

Therefore, for user uj to receive any packet,

Wfuj ,(a0 ,...,at−1 ) , not already cached, user uj can form a multicast group with the set of users
S 0 = {aq + q(

m
) : q ∈ {0, . . . , t − 1} \ j}
M

(55)

29
m
Given that, aq ∈ {0, . . . , M
− 1} for all q ∈ {0, ..., t − 1}, recognize that S 0 ∪ uj ⊂ U . Also, |S 0 ∪ uj | = t

m
m
c = k for all k ∈ {0, . . . , M
− 1}. Therefore, S 0 ∪ uj
and there exists a user uk ∈ S 0 ∪ uj such that buk / M

meets the requirements for a group, S , as defined by the delivery phase. This proves that by forming
all user sets as defined in the delivery phase, all users will recover all packets of the requested file that
were not already cached.
A PPENDIX B
P ROOF OF T HEOREM 1
To prove Theorem 1, we first introduce the following construction of RS Graph from [18], [19].
Definition 8: (Graph Construction) A graph, G(V, E), is defined such that V = [Λ]z where Λ ∈ Z+ ,
z is even, and z ≥ 2Λ. Let µ = Ex,y [||x − y||22 ], where x and y are sampled uniformly from V . For a

pair of vertices, u, v ∈ V , (u, v) ∈ V if and only if | ||u − v||22 − µ| ≤ z .

♦

Given this construction, the graph consists of τ = nf edge disjoint induced matchings and misses at
most nk edges such that f = 1 + 2 lnln10.5
Λ + o(1), and k = 2 −

1
2Λ4 ln Λ

+ o(1).

Furthermore, given a vertex, x ∈ V , the degree of x, defined as d, is bounded by [19]


1
d = |y ∈ V : (x, y) ∈ E| ≥ n 1 − 2n− 2Λ4 ln Λ .

(56)

The degree of any vertex defines the number of packets that a user does not cache. Therefore, if the
following holds,
1
dlb
M
≥1−
= 2n− 2Λ4 ln Λ ,
m
n

where dlb is the lower bound of d, then the graph construction can be used as a cache placement scheme.

1
+
Hence, we can pick M = 2mn− 2Λ4 ln Λ . Since d ≥ dlb = n 1 − M
m = n − t, we have t ∈ Z .
By the construction of the proposed scheme described in Section IV-C, each file is partitioned into
n(2γ − 1) packets, and each contains F/K bits. Moreover, for each disjoint matching in the constructed

RS graph, there are 2γ transmissions, and each has size

F
n(2γ−1)

bits. Since the number of disjoint

matching is τ , there are 2γ · τ transmissions.
R(M ) = 2γ · τ ·

Hence, we finish the proof.

F
1
τ 2γ
·
=
.
n(2γ − 1) F
n 2γ − 1

(57)

30

R EFERENCES
[1] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” Information Theory, IEEE Transactions on, vol. 60,
no. 5, pp. 2856–2867, 2014.
[2] E. Bastug, M. Bennis, and M. Debbah, “Living on the edge: The role of proactive caching in 5g wireless networks,”
Communications Magazine, IEEE, vol. 52, no. 8, pp. 82–89, 2014.
[3] 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.
[4] D. Liu, B. Chen, C. Yang, and A. F. Molisch, “Caching at the wireless edge: design aspects, challenges, and future
directions,” IEEE Communications Magazine, vol. 54, no. 9, pp. 22–28, September 2016.
[5] K. Shanmugam, M. Ji, A. M. Tulino, J. Llorca, and A. G. Dimakis, “Finite length analysis of caching-aided coded
multicasting,” in Communication, Control, and Computing (Allerton), 2014 52nd Annual Allerton Conference on. IEEE,
2014, pp. 914–920.
[6] K. Wan, D. Tuninetti, and P. Piantanida, “On caching with more users than files,” in 2016 IEEE International Symposium
on Information Theory (ISIT), July 2016, pp. 135–139.
[7] K. Wan, D. Tuninetti, and P. Piantanida, “On the optimality of uncoded cache placement,” in 2016 IEEE Information
Theory Workshop (ITW), Sept 2016, pp. 161–165.
[8] Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “Characterizing the rate-memory tradeoff in cache networks within a
factor of 2,” arXiv preprint arXiv:1702.04563, 2017.
[9] N. Karamchandani, U. Niesen, M. A. Maddah-Ali, and S. Diggavi, “Hierarchical coded caching,” IEEE Transactions on
Information Theory, vol. PP, no. 99, pp. 1–1, 2016.
[10] A. Sengupta and R. Tandon, “Improved approximation of storage-rate tradeoff for caching with multiple demands,” IEEE
Transactions on Communications, vol. 65, no. 5, pp. 1940–1955, May 2017.
[11] S. W. Jeon, S. N. Hong, M. Ji, G. Caire, and A. F. Molisch, “Wireless multihop device-to-device caching networks,” IEEE
Transactions on Information Theory, vol. 63, no. 3, pp. 1662–1676, March 2017.
[12] A. Liu, V. Lau, and G. Caire, “Cache-induced hierarchical cooperation in wireless device-to-device caching networks,”
arXiv preprint arXiv:1612.07417, 2016.
[13] S. P. Shariatpanahi, G. Caire, and B. H. Khalaj, “Physical-layer schemes for wireless coded caching,” arXiv preprint
arXiv:1711.05969, 2017.
[14] M. Ji, G. Caire, and A. F. Molisch, “Fundamental limits of caching in wireless d2d networks,” IEEE Transactions on
Information Theory, vol. 62, no. 2, pp. 849–869, Feb 2016.
[15] Y. Fadlallah, A. M. Tulino, D. Barone, G. Vettigli, J. Llorca, and J.-M. Gorce, “Coding for caching in 5g networks,” IEEE
Communications Magazine, vol. 55, no. 2, pp. 106–113, 2017.
[16] S. Jin, Y. Cui, H. Liu, and G. Caire, “New order-optimal decentralized coded caching schemes with good performance in
the finite file size regime,” arXiv preprint arXiv:1604.07648, 2016.
[17] I. Ruzsa and E. Szemerédi, “Triple systems with no six points carrying three triangles,” Combinatorics (Keszthely, 1976),
Coll. Math. Soc. J. Bolyai, vol. 18, pp. 939–945, 1978.
[18] N. Alon, A. Moitra, and B. Sudakov, “Nearly complete graphs decomposable into large induced matchings and their
applications,” in Proceedings of the 44th annual ACM symposium on Theory of computing. ACM, 2012, pp. 1079–1090.
[19] K. Shanmugam, A. M. Tulino, and A. G. Dimakis, “Coded caching with linear subpacketization is possible using ruzsaszeméredi graphs,” arXiv preprint arXiv:1701.07115, 2017.

31

[20] M. Ji, G. Caire, and A. F. Molisch, “Wireless device-to-device caching networks: Basic principles and system performance,”
IEEE Journal on Selected Areas in Communications, vol. 34, no. 1, pp. 176–189, Jan 2016.
[21] F. Xue and PR Kumar, Scaling laws for ad hoc wireless networks: an information theoretic approach, Now Pub, 2006.
[22] M. Raab and A. Steger, “‘balls into bin’–a simple and tight analysis,” Randomization and Approximation Techniques in
Computer Science, pp. 159–170, 1998.
[23] N. Naderializadeh, D. T. H. Kao, and A. S. Avestimehr, “How to utilize caching to improve spectral efficiency in deviceto-device wireless networks,” in 2014 52nd Annual Allerton Conference on Communication, Control, and Computing
(Allerton), Sept 2014, pp. 415–422.
[24] A.F. Molisch, Wireless communications, 2nd edition, IEEE Press - Wiley, 2011.

