1

Joint Pushing and Caching for Bandwidth
Utilization Maximization in Wireless Networks
Yaping Sun, Ying Cui, and Hui Liu

arXiv:1702.01840v2 [] 29 Jun 2017

Shanghai Jiao Tong University, China

Abstract
Joint pushing and caching is recognized as an efficient remedy to the problem of spectrum scarcity
incurred by tremendous mobile data traffic. In this paper, by exploiting storage resources at end users
and predictability of user demand processes, we design the optimal joint pushing and caching policy
to maximize bandwidth utilization, which is of fundamental importance to mobile telecom carriers.
In particular, we formulate the stochastic optimization problem as an infinite horizon average cost
Markov Decision Process (MDP), for which there generally exist only numerical solutions without
many insights. By structural analysis, we show how the optimal policy achieves a balance between
the current transmission cost and the future average transmission cost. In addition, we show that the
optimal average transmission cost decreases with the cache size, revealing a tradeoff between the cache
size and the bandwidth utilization. Then, due to the fact that obtaining a numerical optimal solution
suffers the curse of dimensionality and implementing it requires a centralized controller and global
system information, we develop a decentralized policy with polynomial complexity w.r.t. the numbers
of users and files as well as cache size, by a linear approximation of the value function and optimization
relaxation techniques. Next, we propose an online decentralized algorithm to implement the proposed
low-complexity decentralized policy using the technique of Q-learning, when priori knowledge of user
demand processes is not available. Finally, using numerical results, we demonstrate the advantage of
the proposed solutions over some existing designs. The results in this paper offer useful guidelines for
designing practical cache-enabled content-centric wireless networks.

Index Terms
Pushing, caching, Markov Decision Process, Q-learning, bandwidth utilization.
The paper was submitted in part to IEEE GLOBECOM 2017.

June 30, 2017

DRAFT

2

I. I NTRODUCTION
The rapid proliferation of smart mobile devices has triggered an unprecedented growth of
global mobile data traffic [1], resulting in the spectrum crunch problem in wireless systems. In
order to improve the bandwidth utilization and support the sustainability of wireless systems,
researchers have primarily focused on increasing the access rate of wireless systems and the
density of network infrastructures, e.g., base stations (BSs). However, the expansive growth
of both the access rate and the density of network infrastructures entails prohibitive network
costs. On the other hand, modern data traffic exhibits a high degree of asynchronous content
reuse [2]. Thus, caching is gradually recognized as a promising approach to further improve the
bandwidth utilization by placing contents closer to users, e.g., at BSs or even at end users, for
future requests. Recent investigations show that caching can effectively reduce the traffic load
of wireless and backhaul links as well as user-perceived latency [3]–[8].
Based on whether content placement is updated, caching policies can be divided into two
categories, i.e., static caching policies and dynamic caching policies. Static caching policies
refer to the caching policies under which content placement remains unchanged over a relatively
long time. For example, [3]–[5] consider static caching policies at BSs to reduce the traffic
load of backhaul links. In addition, in [6], [7], static caching policies at end users are proposed
to not only alleviate the backhaul burden but also reduce the traffic load of wireless links.
However, all the static caching policies in [3]–[7] are designed based on content popularity,
e.g., the probability of each file being requested, which is assumed to be known in advance,
and cannot exploit temporal correlation of a demand process to further improve performance of
cache-assisted systems. Dynamic caching policies refer to the caching policies where content
placement may update from time to time by making use of instantaneous user request information.
In this way, dynamic caching policies can not only operate without priori knowledge of content
popularity but also capture the temporal correlation of a demand process. The least recently
used (LRU) policy and the least frequently used (LFU) policy [8] are two of the commonly
adopted dynamic caching policies, primarily due to ease of implementation. However, they are
both heuristic designs and may not guarantee promising performance in general.
Pure dynamic caching policies only focus on caching contents which have been requested and
delivered to the local cache, and hence have limitations in smoothing traffic load fluctuations
and enhancing bandwidth utilization. To address these limitations, joint pushing (i.e., proac-

June 30, 2017

DRAFT

3

tively transmitting) and caching has been receiving more and more attention, as it can further
improve bandwidth utilization. Specifically, the underutilized bandwidth at low traffic time can
be exploited to proactively transmit contents for satisfying future user demands. Therefore, it is
essential to design intelligent joint pushing and caching policy based on the knowledge of user
demand processes.
For instance, [9] considers joint pushing and caching to minimize the energy consumption,
assuming complete knowledge of future content requests. In most cases, the assumption cannot be
satisfied, and hence the proposed joint design has limited applications. To address this problem,
[10]–[15] consider joint pushing and caching based on statistical information of content requests
(e.g., content popularity), while [16] considers online learning-aided joint design adaptive to
instantaneous content requests and without priori knowledge of statistical information of content
requests. Specifically, [10] optimizes joint pushing and caching to maximize the network capacity
in a push-based converged network with limited user storage. In [11], the authors maximize the
number of user requests served by small BSs (SBSs) via optimizing the pushing policy using
Markov decision process (MDP). Note that in [11], the cache size at each user is assumed to be
unlimited, and thus caching design is not considered. In [12] and [13], the optimal joint pushing
and caching policies are proposed to maximize the number of user requests served by the local
caches in the scenarios of a single user and multiple users, respectively. [14] studies the optimal
joint pushing and caching policy to minimize the transmission cost. However, the joint designs
in [12]–[14] do not take into account future reuse of requested files, and thus cannot be applied
to certain applications which involve reusable contents, such as music and video streaming.
Moreover, in [10]–[14], temporal correlation of a demand process is not captured, and hence the
potential of joint pushing and caching cannot be fully unleashed. In contrast, [15] and [16] exploit
temporal correlation in the joint designs. In particular, [15] investigates efficient transmission
power control and caching to minimize both the access delay and the transmission cost using
MDP. In [16], the authors maximize the average reward obtained by proactively serving user
demands and propose an online learning-aided control algorithm. However, in [15] and [16],
only a single user setup is considered without reflecting asynchronous demands for common
contents from multiple users, and hence the proposed joint designs may not be directly applied
to practical networks with multiple users. Moreover, the pushing policy in [16] can predownload
contents only one time slot ahead.
To further exploit the promises of joint pushing and caching in bandwidth utilization, in this

June 30, 2017

DRAFT

4

paper, we investigate the optimal joint pushing and caching policy and reveal the fundamental
impact of storage resource on bandwidth utilization. Specifically, we consider a cache-enabled
content-centric wireless network consisting of a single server connected to multiple users via
a shared and errorless link. Each user is equipped with a cache of limited size and generates
inelastic file requests. We model the demand process of each user as a Markov chain, which captures both the asynchronous feature and temporal correlation of file requests. By the majorization
theory [18], we choose a nondecreasing and strictly convex function of the traffic load as the
per-stage cost and consider the time averaged transmission cost minimization. In particular, we
formulate the joint pushing and caching optimization problem as an infinite horizon average cost
MDP. Note that there generally exist only numerical solutions for MDPs, which suffer from the
curse of dimensionality and cannot offer many design insights. Hence, it is a great challenge
to design an efficient joint pushing and caching policy with acceptable complexity and offering
design insights. In this paper, our main contributions are summarized as below.
•

First, we analyze structural properties of the optimal joint pushing and caching policy. In
particular, by deriving an equivalent Bellman equation, we show that the optimal pushing
policy balances the current transmission cost with the future average transmission cost,
while the optimal caching policy achieves the lowest future average transmission cost given
the optimal pushing policy. In addition, based on coupling and interchange arguments, we
prove that the optimal average transmission cost decreases with the cache size, revealing
the tradeoff between the cache size and the bandwidth utilization. Moreover, via relative
value iteration, we analyze the partial monotonicity of the value function, based on which
the sizes of both the state space and the caching action space are reduced, and thereby the
complexity of computing the optimal joint design is reduced.

•

Then, considering that obtaining the optimal policy requires computational complexity
exponential with the number of users K and combinatorial with the number of files F
as well as the cache size C, and implementing it requires a centralized controller and
global system information, we develop a low-complexity (polynomial with K, F and C)
decentralized joint pushing and caching policy by using a linear approximation of the value
function [19], [20] and optimization relaxation techniques.

•

Next, noting that our proposed low-complexity decentralized policy requires statistic information of user demand processes, we propose an online decentralized algorithm (ODA) to

June 30, 2017

DRAFT

5

Table I: Key Notations
Notation

Meaning

F, K, k, f

set of all files, set of all users, user index, file index

F , K, C

file number, user number, cache size

A = (Ak )k∈K , S = (Sk,f )k∈K,f ∈F

system demand process, system cache state

Xk = (Ak , Sk ), X = (A, S)
(k) 
Qk = qi,j i∈F̄ ,j∈F̄

state of user k, system state
transition matrix of demand process of user k

R = (Rf )f ∈F , P = (Pf )f ∈F , ∆S = (∆Sk )k∈K
U(X), µ = (µP , µ∆S )
θ, V (X)

reactive transmission action, pushing action, caching action
system action space under X, joint pushing and caching policy
optimal average cost, value function of system state X

implement the low-complexity decentralized policy using the technique of Q-learning [21],
when priori knowledge of user demand processes is not available.
•

Finally, by numerical results, we compare the performance of our proposed solutions with
some existing designs at different system parameters, including the user number, file number,
cache size and some key factors of user demand processes.

The key notations used in this paper are listed in Table I.
II. S YSTEM M ODEL
A. Network Architecture
As in [22], we consider a cache-enabled content-centric wireless network with a single server
connected through a shared error-free link to K users,1 denoted as K , {1, 2, · · · , K}, as shown
in Fig. 1. The server is accessible to a database of F files, denoted as F , {1, 2, · · · , F }. All
the files are of the same size. Each user is equipped with a cache of size C (in files). The
system operates over an infinite time horizon and time is slotted, indexed by t = 0, 1, 2, · · · . At
the beginning of each time slot, each user submits at most one file request, which is assumed
to be delay intolerant and must be served before the end of the slot, either by its own cache
if the requested file has been stored locally, or by the server via the shared link. At each slot,
the server can not only reactively transmit a file requested by some users at the slot but also
push (i.e., proactively transmit) a file which has not been requested by any user at the slot. Each
1

Note that the server can be a BS and each user can be a mobile device or a SBS.

June 30, 2017

DRAFT

6

F Files

Server

Multicast

Size C

K Users

Figure 1: System model.

transmitted file can be received by all the users concurrently before the end of the time slot.2
After being received, a file can be stored into some user caches.
B. System State
1) Demand State: At the beginning of time slot t, each user k generates at most one file
request. Let Ak (t) ∈ F̄ , F ∪ {0} denote the demand state of user k at the beginning of time
slot t, where Ak (t) = 0 indicates that user k requests nothing, and Ak (t) = f ∈ F indicates
that user k requests file f . Here, F̄ denotes the demand state space of each user which is of
cardinality F + 1. Let A(t) , (Ak (t))k∈K ∈ F̄ K denote the system demand state (of the K
users), where F̄ K represents the system demand state space. Note that the cardinality of F̄ K is
(F + 1)K , which increases exponentially with K.
For user k, we assume that Ak (t) evolves according to a first-order (F +1)-state Markov chain,
denoted as {Ak (t) : t = 0, 1, 2, · · · }, which captures temporal correlation of order one of user
k’s demand process and is a widely adopted traffic model [16]. Let Pr[Ak (t + 1) = j|Ak (t) = i]
denote the transition probability of going to state j ∈ F̄ at time slot t + 1 given that the
demand state at time slot t is i ∈ F̄ for user k’s demand process. Assume that {Ak (t)} is
(k)

time-homogeneous and denote qi,j , Pr[Ak (t + 1) = j|Ak (t) = i]. Furthermore, we restrict
(k) 
our attention to an irreducible Markov chain. Denote with Qk , qi,j i∈F̄ ,j∈F̄ the transition
probability matrix of {Ak (t)}. We assume that the K time-homogeneous Markov chains, i.e.,
2

We assume that the duration of each time slot is long enough to average the small-scale channel fading process, and hence

the ergodic capacity can be achieved using channel coding.

June 30, 2017

DRAFT

7

{Ak (t)}, k ∈ K, are independent of each other. Thus, we have Pr[A(t + 1) = j|A(t) = i] =
QK (k)
K
and j , (jk )k∈K ∈ F̄ K .
k=1 qik ,jk , where i , (ik )k∈K ∈ F̄
2) Cache State: Let Sk,f (t) ∈ {0, 1} denote the cache state of file f in the storage of user k

at time slot t, where Sk,f (t) = 1 means that file f is cached in user k’s storage and Sk,f (t) = 0
otherwise. Under the cache size constraint, we have
X
Sk,f (t) ≤ C, k ∈ K.

(1)

f ∈F

Let Sk (t) , (Sk,f (t))f ∈F ∈ S denote the cache state of user k at time slot t, where S ,
P
{(Sf )f ∈F ∈ {0, 1}F :
f ∈F Sf ≤ C} represents the cache state space of each user. Here,

the user index is suppressed considering that the cache state space is the same across all the
users. Let S(t) , (Sk,f (t))k∈K,f ∈F ∈ S K denote the system cache state at time slot t, where S K
P
K
C
F
represents the system cache state space. The cardinality of S K is
, which increases
i=0 i
with the number of users K exponentially.

3) System State: At time slot t, denote with Xk (t) , (Ak (t), Sk (t)) ∈ F̄ × S the state of user
k, where F̄ × S represents the state space of user k. The system state consists of the system
demand state and the system cache state, denoted as X(t) , (A(t), S(t)) ∈ F̄ K × S K , where
F̄ K × S K represents the system state space. Note that X(t) = (Xk (t))k∈K .
C. System Action
1) Pushing Action: A file transmission can be reactive or proactive at each time slot. Denote
with Rf (t) ∈ {0, 1} the reactive transmission action for file f at time slot t, where Rf (t) = 1
when there exists at least one user who requests file f but cannot find it in its local cache and
Rf (t) = 0 otherwise. Thus, we have
Rf (t) =

max

k∈K:Ak (t)=f


1 − Sk,f (t) , f ∈ F ,

(2)

which is determined directly by X(t).3 Denote with R(t) , (Rf (t))f ∈F the system reactive
transmission action at time slot t. Also, denote with Pf (t) ∈ {0, 1} the pushing action for file f
at time slot t, where Pf (t) = 1 denotes that file f is pushed (i.e., transmitted proactively) and
Pf (t) = 0 otherwise. Considering that file f is transmitted at most once at time slot t, we have
Pf (t) + Rf (t) ≤ 1, f ∈ F ,
3

(3)

Note that we do not need to design the reactive transmission action.

June 30, 2017

DRAFT

3

3

2

2

y(t)

x(t)

8

1
0

1

2

3

t

(a) Sequence {x(t)}.

and

1
5

P5

t=1

4

2

1
5

P5

t=1

1
0

5

1

2

3

(b) Sequence {y(t)}.

x(t) = 1,

x (t) = 2.2.

and

1
5

P5

t=1

4

t

2

1
5

y (t) = 1.

P5

t=1

5

y(t) = 1,

Figure 2: An illustration of the relationship between the average cost and bandwidth utilization. Note that
P5
P5
P5
P5
1
1
1
1
2
2
t=1 x(t) = 5
t=1 y(t), while 5
t=1 x (t) > 5
t=1 y (t).
5

where Rf (t) is given by (2). Furthermore, if file f has already been cached in each user’s storage,
there is no need to push it. Hence, we have
Pf (t) ≤ 1 − min Sk,f (t), f ∈ F .

(4)

k∈K

Denote with P(t) , (Pf (t))f ∈F ∈ UP (X(t)) the system pushing action at time slot t, where
UP (X) , {(Pf )f ∈F ∈ {0, 1}F : (3), (4)} represents the system pushing action space under X.
System pushing action P together with reactive transmission action R incurs a certain transmission cost. We assume that the transmission cost is an increasing and continuously convex

P
function of the corresponding traffic load, i.e., f ∈F Rf + Pf , denoted by φ(·). In accordance
with practice, we further assume that φ(0) = 0. For example, we can choose φ(x) = ax − 1

with a > 1 or φ(x) = xd with d ≥ 2.4 Here, we note that the per-stage transmission cost
is bounded within set {0, φ(1), · · · , φ(min{F, KC})}. By the technique of majorization [18], a
small time-averaged transmission cost with such a per-stage cost function corresponds to a small
peak-to-average ratio of the bandwidth requirement, i.e., a high bandwidth utilization, which is
of fundamental importance to a mobile telecom carrier, as illustrated in Fig. 2.
2) Caching Action: After the transmitted files being received by all the users, the system
cache state can be updated. Let ∆Sk,f (t) ∈ {−1, 0, 1} denote the caching action for file f at
user k at the end of time slot t, where ∆Sk,f (t) = 1 means that file f is stored into the cache
of user k, ∆Sk,f (t) = 0 implies that the cache state of file f at user k does not change, and
4

Note that by choosing φ(x) = 2x − 1, φ(

June 30, 2017

P

f ∈F

Rf (t) + Pf (t)) can represent the energy consumption at time slot t.

DRAFT

9

∆Sk,f (t) = −1 indicates that file f is removed from the cache of user k. Accordingly, the
caching action satisfies the following cache update constraint:
− Sk,f (t) ≤ ∆Sk,f (t) ≤ Rf (t) + Pf (t), f ∈ F , k ∈ K,

(5)

where Rf (t) is given by (2). In (5), the first inequality is to guarantee that file f can be removed
from the cache of user k only when it has been stored at user k, and the second inequality is to
guarantee that file f can be stored into the cache of user k only when it has been transmitted
from the server. The cache state evolves according to:
Sk,f (t + 1) = Sk,f (t) + ∆Sk,f (t),

f ∈ F , k ∈ K.

(6)

Since Sk,f (t+ 1) belongs to {0, 1} and also satisfies (1), we have the following two cache update
constraints:
Sk,f (t) + ∆Sk,f (t) ∈ {0, 1},
X

Sk,f (t) + ∆Sk,f (t) ≤ C,

f ∈ F , k ∈ K,

(7)

f ∈ F , k ∈ K.

(8)

f ∈F

From (5), (7) and (8), we denote with ∆Sk (t) , (∆Sk,f (t))f ∈F ∈ U∆S,k (Xk (t), R(t) + P(t)) the
caching action of user k at the end of time slot t, where U∆S,k (Xk ,R + P) , {(∆Sk,f )f ∈F ∈
{−1, 0, 1}F : (5), (7), (8)} represents the caching action space of user k under its state Xk ,
system reactive transmission action R and pushing action P. Let ∆S(t) , (∆Sk,f (t))k∈K,f ∈F ∈
U∆S (X(t), P(t)) denote the system caching action at the end of time slot t, where U∆S (X, P) ,
Q
k∈K U∆S,k (Xk , R + P) represents the system caching action space under system state X and

pushing action P.

3) System Action: At time slot t, the system action consists of both the pushing action
and caching action, denoted as (P(t), ∆S(t)) ∈ U(X(t)), where U(X) , {(P, ∆S) : ∆S ∈
U∆S (X, P), P ∈ UP (X)} represents the system action space under system state X.
III. P ROBLEM F ORMULATION
Given an observed system state X, the joint pushing and caching action, denoted as (P, ∆S),
is determined according to a policy defined as below.
Definition 1 (Stationary Joint Pushing and Caching Policy). A stationary joint pushing and
caching policy µ , (µP , µ∆S ) is a mapping from system state X to system action (P, ∆S), i.e.,

June 30, 2017

DRAFT

10

(P, ∆S) = µ(X) ∈ U(X). Specifically, we have P = µP (X) ∈ UP (X) and ∆S = µ∆S (X, P) ∈
U∆S (X, P).
From the properties of {A(t)} and {S(t)}, we see that the induced system state process {X(t)}
under policy µ is a controlled Markov chain. The time averaged transmission cost under policy
µ is given by

T −1   X

1X
E φ
Rf (t) + Pf (t)
,
φ̄(µ) , lim sup
T →∞ T
t=0

(9)

f ∈F

where Rf (t) is given by (2) and the expectation is taken w.r.t. the measure induced by the K
Markov chains. Note that φ̄(µ) can reflect the bandwidth utilization, as illustrated in Fig. 2.
In this paper, we aim to obtain an optimal joint pushing and caching policy µ to minimize the
time averaged transmission cost φ̄(µ) defined in (9), i.e., maximizing the bandwidth utilization.
Before formally introducing the problem, we first illustrate a simple example that highlights how
the joint pushing and caching policy affects the average cost, i.e., bandwidth utilization.
Motivating Example. Consider a scenario with K = 4, F = 4, C = 1 and φ(x) = x2 . The
user demand model is illustrated in Fig. 3 (a). A sample path of the user demand processes is
shown in Fig. 3 (b). Note that at time slot 2, there is no file request, while at time slot 3, the
number of file requests achieves the maximum value, i.e., 4. Fig. 3 (c)-(h) illustrate the system
cache states and the multicast transmission actions over three time slots under the following
three policies: the most popular (MP) caching policy in which the C most popular files (i.e.,
the first C files with the maximum limiting probabilities) are cached at each user [4], the LRU
caching policy and a joint pushing and caching (JPC) policy. We can calculate the average cost
over the three time slots under the aforementioned three policies, i.e., φ̄1 ,
φ̄2 ,

12 +02 +42
3

=

17
3

and φ̄3 ,

12 +12 +12
3

12 +02 +32
3

=

10
,
3

= 1. Note that φ̄3 < φ̄1 < φ̄2 . From Fig. 3 (h), we learn

that under the joint pushing and caching policy, the bandwidth at low traffic time (e.g., time slot
2) can be exploited to proactively transmit contents for satisfying future user demands (e.g., at
time slot 3), thereby improving the bandwidth utilization.
Problem 1 (Joint Pushing and Caching Optimization).
φ̄∗ , min φ̄(µ)
µ

s.t.

June 30, 2017

(2), (3), (4), (5), (7), (8),

DRAFT

11

where φ̄∗ denotes the minimum time averaged transmission cost under the optimal policy µ∗ ,
(µ∗P , µ∗∆S ), i.e., φ̄∗ = φ̄(µ∗ ).

A 4 (t)
0.35
0.32
File Set
0.75

0.75
0.25

A 2 (t)

0.75

0.25

A 3 (t)

0.2

0.08

0.75

0.25
0.25

0.05

A1 (t)

0.25
0.25

0.25

0.25

No Request

Transition Graph

1

Stationary Distribution

(a) Demand model for each user. Qk , k ∈ K

2

3

t

(b) A sample path of {A(t)}.

are the same.
S4 (t)
S3 (t)
R(t)

S2 (t)
S1 (t)

1

2

3

t

(c) Cache state under MP.

1

2

3

t

(d) Reactive transmission under MP. Average
cost φ̄1 ,

12 +02 +32
3

=

10
.
3

S4 (t)
S3 (t)

R(t)

S2 (t)
S1 (t)

1

2

3

1

t

(e) Cache state under LRU.

2

3

t

(f) Reactive transmission under LRU. Average
cost φ̄2 ,

12 +02 +42
3

=

17
.
3

R(t)

S4 (t)
S3 (t)

1

2

3

t

1

2

3

t

S2 (t)
P(t)

S1 (t)

1

2

(g) Cache state under JPC.

3

t

(h) Reactive transmission and pushing under
JPC. Average cost φ̄3 ,

12 +12 +12
3

= 1.

Figure 3: Motivating Example. We consider K = 4, F = 4, C = 1 and φ(x) = x2 . Note that the blank square
indicates that there is no file request.

June 30, 2017

DRAFT

12

Problem 1 is an infinite horizon average cost MDP. According to Definition 4.2.2 and Proposition 4.2.6 in [21], we know that there exists an optimal policy that is unichain. Hence, in this
paper, we restrict our attention to stationary unichain policies. Moreover, the MDP has finite state
and action spaces as well as a bounded per-stage cost. Thus, there always exists a deterministic
stationary unichain policy that is optimal and it is sufficient to focus on the deterministic
stationary unichain policy space. In the following, we use µ to refer to a deterministic stationary
unichain policy.
IV. O PTIMAL P OLICY
A. Optimality Equation
We can obtain the optimal joint pushing and caching policy µ∗ through solving the following
Bellman equation.
Lemma 1 (Bellman equation). There exist a scalar θ and a value function V (·) satisfying
n X
o
X Y (k)

′
θ+ V (X) =
min
φ
(Rf + Pf ) +
qAk ,A′ V (A , S+ ∆S) ,
(P,∆S)∈U(X)

k

f ∈F

A′ ∈F̄ K k∈K

X ∈ F̄ K × S K ,

(10)

where Rf is given by (2) and A′ , (A′k )k∈K . θ = φ̄∗ is the optimal value of Problem 1 for all
initial system states X(0) ∈ F̄ K ×S K , and the optimal policy µ∗ can be obtained from
n X
o
X Y (k)

µ∗ (X) = arg
min
φ
(Rf + Pf ) +
qAk ,A′ V (A′ , S + ∆S) ,
(P,∆S)∈U(X)

k

f ∈F

A′ ∈F̄ K k∈K

X ∈ F̄ K × S K .

(11)

Proof. Please see Appendix A.
From (11), we see that the optimal policy µ∗ achieves a balance between the current transmission cost (i.e., the first term in the objective function of (11)) and the future average transmission
cost (i.e., the second term in the objective function of (11)). Moreover, how µ∗ = (µ∗P , µ∗∆S )
achieves the balance is illustrated in the following corollary.
Corollary 1. The optimal pushing policy µ∗P is given by
n X
o

∗
µP (X) = arg min
φ
(Rf + Pf ) + W (X, P) ,
P∈Up (X)

June 30, 2017

X ∈ F̄ K × S K ,

(12)

f ∈F

DRAFT

13

where W (X, P) ,

min

P

∆S∈U∆S (X,P)

A′ ∈F̄ K

(k)
k∈K qAk ,A′kV

Q

(A′ , S + ∆S) is a nonincreasing function of

P. Furthermore, the optimal caching policy µ∗∆S is given by
X Y (k)
µ∗∆S (X, µ∗P (X)) = arg
min ∗
qAk ,A′ V (A′ , S + ∆S), X ∈ F̄ K × S K ,
∆S∈U∆S (X,µP (X))

(13)

k

A′ ∈F̄ K

k∈K

where µ∗P is obtained from (12).

Proof. (12) and (13) follow directly from (11). In addition, if P1  P2 ,5 U∆S (X, P1 ) ⊆
U∆S (X, P2 ), implying that W (X, P1 ) ≥ W (X, P2 ). The proof ends.
Remark 1 (Balance between Current Transmission Cost and Future Average Transmission Cost).

P
Note that the current transmission cost φ
f ∈F (Rf + Pf ) increases with P and the future

average transmission cost W (X, P) decreases with P. Thus, the optimal pushing policy µ∗P in

(12) achieves the perfect balance between the current transmission cost and the future average
transmission cost for all X. In addition, from (13), we learn that the optimal caching policy µ∗∆S
achieves the lowest future average transmission cost under the optimal pushing policy µ∗P .
From Lemma 1 and Corollary 1, we note that µ∗ depends on system state X via the value
function V (·). Obtaining V (·) involves solving the equivalent Bellman equation in (10) for all X,
and there generally exist only numerical results which cannot offer many design insights [21].
In addition, obtaining numerical solutions using value iteration or policy iteration is usually
infeasible for practical implementation, due to the curse of dimensionality [21]. Therefore, it
is desirable to study optimality properties of µ∗ and exploit these properties to design lowcomplexity policies with promising performance.
B. Optimality Properties
First, we analyze the impact of cache size C on the optimal average transmission cost θ.
For ease of exposition, we rewrite θ as a function of cache size C, i.e., θ(C), and obtain the
following lemma based on coupling and interchange arguments [15].
Lemma 2 (Impact of Cache Size). θ(C) decreases with C when C < F and θ(C) = 0 when
C ≥F .
Proof. Please see Appendix B.
5

The notion  indicates the component-wise ≤.

June 30, 2017

DRAFT

14

Remark 2 (Tradeoff between Cache Size and Bandwidth Utilization). As illustrated in Fig. 2, a
lower average transmission cost always corresponds to a higher bandwidth utilization. Hence,
Lemma 2 reveals the tradeoff between the cache size and the bandwidth utilization.
In the following, we focus on the case of C < F . By analyzing the partial monotonicity of
value function V (·), we obtain the next lemma.
Lemma 3 (Transient System States). Any X = (A, S) with S ∈
/ Š K is transient under µ∗ , where

P
Š , (Sf )f ∈F : Ff=1 Sf = C .

Proof. Please see Appendix C.

Remark 3 (Reduction of System State Space and Caching Action Space). Lemma 3 reveals that
the optimal policy µ∗ makes full use of available storage resources. Also, considering the expected
sum cost over the infinite horizon incurred by a transient state is finite and negligible in terms of
average cost, we restrict our attention to the reduced system state space F̄ K × SˇK without loss
P
of optimality. Also, the cache update constraint in (7) is replaced with f ∈F Sk,f + ∆Sk,f = C,
and thus the caching action space can be further reduced.

Remark 4 (Computational Complexity and Implementation Requirement). To obtain the optimal
policy µ∗ from (11) under the reduced system state space given in Lemma 3, we need to compute
K
V (X), X ∈ F̄ K × SˇK , by solving a system of (F + 1) F
equations in (10), the number of
C

which increases exponentially with the number of users K and combinatorially with the number

of files F as well as the cache size C. Moreover, given V (·), computing µ∗ (X) for all X involves

brute-force search over the action space U(X), which requires complexity of O K2F CF . In
practice, K, F and C are relatively large, and hence the complexity of computing µ∗ is not

acceptable. Besides, the implementation of µ∗ requires a centralized controller and system state
information, resulting in large signaling overhead.
V. L OW-C OMPLEXITY D ECENTRALIZED P OLICY
To reduce the computational complexity and achieve decentralized implementation without
much signaling overhead, we first approximate the value function V (·) in (10) by the sum of
per-user per-file value functions. Based on the approximate value function, we obtain a lowcomplexity decentralized policy for practical implementation.

June 30, 2017

DRAFT

15

A. Value Approximation
To alleviate the curse of dimensionality in computing V (·), for all X ∈ F̄ K × SˇK , motivated
by [19], [20], we approximate V (X) in (10) as follows:
X
X
V (X) ≈ V̌ (X) =

V̌k1 (Xk1 ),

(14)

k∈K fk ∈F :Sk,fk =1

where Xk1 , (Ak , fk ) ∈ F̄ × F and for all k ∈ K, V̌k1 (Xk1 ), Xk1 ∈ F̄ × F satisfy:
X (k)
θk1 + V̌k1 (Xk1 ) = φ′ (Xk1 ) + 1min
qAk ,A′ V̌k1 (A′k , fk′ ), Xk1 ∈ F̄ × F .
1
1
∆Sk ∈Uk (Xk )

Here, φ′ (Xk1 ) ,

1
K



φ(1)
−φ
C

1(Ak = fk )



k

(15)

A′k ∈F̄

1(Ak 6= 0),6 Uk1 (Xk1 ) , {0, −1(Ak ∈
/ {0, fk })} and

fk′ , (1 + ∆Sk1 )fk − ∆Sk1 Ak . The equation in (15) corresponds to the Bellman equation of a
per-user per-file MDP for user k with unit cache size. θk1 and V̌k1 (·) denote the average cost and
value function of the per-user per-file MDP for user k, respectively. Specifically, at time slot t,
Xk1 (t) = (Ak (t), fk (t)) denotes the system state, where Ak (t) ∈ F̄ denotes the demand state and
fk (t) ∈ F denotes the cached file; ∆Sk1 (t) ∈ Uk1 (Xk1 ) denotes the caching action; the demand
state Ak (t) evolves according to the Markov chain {Ak (t)} and the cache state fk (t) evolves
according to fk (t + 1) = (1 + ∆Sk1 (t))fk (t) − ∆Sk1 (t)Ak (t); φ′ (Xk1 (t)) denotes the per-stage
cost. The K per-user per-file MDPs are obtained from the original MDP by eliminating the
couplings among the K users and the C cache units of each user, which are due to the multicast
transmission and the cache size constraint, respectively.
In the following, we characterize the performance of the value approximation in (14) from the
perspectives of the average transmission cost and the complexity reduction, respectively. First,
by analyzing the relaxation from the original MDP to the K per-user per-file MDPs, we have
the following relationship between the average cost of the original MDP and the sum of the
average costs of the K per-user per-file MDPs.
Lemma 4. θ(C) and θk1 , k ∈ K satisfy that θ(C) ≥ C
Proof. Please see Appendix D.

1
k∈K θk .

P

In addition, note that obtaining V (X), X ∈ F̄ K × Š K requires to solve a system of (F +
K
1) CF
equations given in (10), while obtaining V̌k1 (Xk1 ), Xk1 ∈ F̄ × F , k ∈ K only requires
6

1(·) represents the indicator function throughout this paper.

June 30, 2017

DRAFT

16

to solve a system of KF (F + 1) equations given in (15). Therefore, under the value function
approximation in (14), the non-polynomial computational complexity is eliminated.
Remark 5. The linear value function approximation adopted in (14) differs from most existing
approximation methods. Firstly, different from the traditional linear approximation in [23], our
approach is not based on specific basis functions. Secondly, compared with the randomized
approach proposed in [19], [20], our approach leads to a lower bound of the optimal average
cost as illustrated in Lemma 4.
B. Low-complexity Decentralized Policy
By replacing V (X) in (10) with V̌ (X) in (14), the minimization problem in (11) which
determines the optimal policy µ∗ is approximated by:
Problem 2 (Approximate Joint Pushing and Caching Optimization). For all X ∈ F̄ K × SˇK ,
min

(P,∆S)

s.t.

ϕ(P, ∆S)
(2), (3), (4), (5), (7), (8),

 P P
P
′
where ϕ(P, ∆S) , φ
f ∈F (Rf +Pf ) + k∈K
f ∈Sk′ gk (Ak , f ), Sk , {f ∈ F : Sk,f+∆Sk,f = 1}
P
(k)
and gk (Ak , f ) , A′ ∈F̄ qAk ,A′ V̌k1 (A′k , f ). Let µ̌∗ (X) denote the corresponding optimal solution.
k

k

Note that due to the coupling among K users incurred by the multicast transmission, solving

Problem 2 still calls for complexity of O K2F CF and centralized implementation with system

state information, which motivates us to develop a low-complexity decentralized policy. Specif-

ically, given system state X, first ignore the multicast opportunities in pushing and separately
optimize the per-user pushing action of each user k under given state Xk and reactive transmission
R. Then, the server gathers the information of the per-user pushing actions of all the users and
multicasts the corresponding files. Next, each user optimizes its caching action given the files
obtained from the multicast transmissions. The details are mathematically illustrated as follows.
First, for all k ∈ K, replace Pf with Pk,f and by adding constraints Pf = Pk,f , we obtain an
equivalent problem of Problem 2. The constraint in (3) is rewritten as
Pk,f (t) ≤ 1 − Rf (t),

June 30, 2017

f ∈ F , k ∈ K,

(16)

DRAFT

17

which is to guarantee that each file f ∈ F is transmitted at most once to user k at each time
slot t. The constraints in (4) and (5) can be replaced by
Pk,f (t) ≤ 1 − Sk,f (t),

f ∈ F , k ∈ K,

− Sk,f (t) ≤ ∆Sk,f (t) ≤ Rf (t) + Pk,f (t), f ∈ F , k ∈ K.

(17)
(18)

Via omitting the constraints Pf = Pk,f , k ∈ K, we attain a relaxed optimization problem of
Problem 2. Given R, by (16) (17) and (18), the relaxed problem can be decomposed into K
separate subproblems, one for each user, as shown in Problem 3.
Problem 3 (Pushing Optimization for User k). For all state Xk and R,

o
n φ P (Rf +Pk,f )
f ∈F
∗
+Wk (Xk , R + Pk )
ϕk , min
Pk
K
s.t.

(2), (7), (8), (16), (17), (18),
P
∗
where Wk (Xk , R + Pk ) , min∆Sk ∈U∆S,k (Xk ,R+Pk )
f ∈S ′ gk (Ak , f ). Let Pk denote the optimal
k

solution.

Then, we obtain P∗k as follows. Denote with yk (pk ) , (yk,f (pk ))f ∈F the optimal pushing
action for user k when the number of pushed files for user k is pk . From the definition of
Wk (Xk , R+Pk ), we learn that user k always pushes the first pk files with the minimum values
of gk (Ak , f ), f ∈ {f ∈ F : Sk,f +Rf = 0}. Hence, we obtain yk (pk ) as follows. Given Xk and R
in (2), sort the elements in Gk (Xk , R) , {gk (Ak , f ) : Sk,f + Rf = 0, f ∈ F } in ascending order,
let fk,i denote the index of the file with the i-th minimum in Gk (Xk , R), and we have

 1, f = f , i ≤ p ,
k,i
k
yk,f (pk ) =
f ∈ F , pk ∈ {0, 1, · · · , |Gk (Xk , R)|}.
 0, otherwise,

(19)

is given by (19) and p∗k is given by
 X

Rf + pk + Wk (Xk , R+yk (pk )) .
p∗k , arg min φ

(20)

Based on (19), we can easily obtain P∗k , as summarized below.

Optimal Solution to Problem 3: For all state Xk and R, P∗k = (yk,f (p∗k ))f ∈F , where yk,f (p∗k )

pk

f ∈F

Next, based on P∗k , k ∈ K, we propose a low-complexity decentralized policy, denoted as

µ̌ , (µ̌P , µ̌∆S ), which reconsiders the multicast opportunities in pushing. Specifically, for all
X ∈ F̄ K × Š K , we have µ̌P (X) , (P̌f )f ∈F and µ̌∆S (X) , (∆Šk )k∈K , where
∗
P̌f , max Pk,f
, f ∈ F,
k∈K

June 30, 2017

(21)

DRAFT

18

∆Šk , arg

min
∆Sk ∈Ǔ∆S (Xk ,R+µ̌P (X))

X

gk (Ak , f ), k ∈ K.

(22)

f ∈Sk′

Finally, we characterize the performance of µ̌. Lemma 5 illustrates the relationship among the
optimal values of Problem 2 and Problem 3 as well as the objective value of Problem 2 at µ̌.
Lemma 5. For all X ∈ F̄ K × Š K ,

P

k∈K

ϕ∗k ≤ ϕ(µ̌∗ (X)) ≤ ϕ(µ̌(X)), where the equality holds if

and only if Xk1 = Xk2 and Qk1 = Qk2 for all k1 ∈ K and k2 ∈ K.
Proof. Due to the relaxation from Problem 2 to Problem 3, the action space becomes larger
and thus we can show the first inequality directly. Due to the suboptimality of µ̌, the second
inequality holds. Furthermore, when Xk1 = Xk2 and Qk1 = Qk2 for all k1 ∈ K and k2 ∈ K,
P∗k1 = P∗k2 = µ̌P (X) and thus the equality holds. We complete the proof.
Remark 6 (Computational Complexity and Implementation Requirement). Given V̌k1 (·), for all

X ∈ F̄ K × SˇK , the complexity of computing µ̌(X) is O KF log(F ) much lower than that

of computing µ∗ (X), i.e., O K2F FC . Furthermore, we note that µ̌ can be implemented in a
decentralized manner. Specifically, first, each user submits its request Ak if Ak ∈ {f ∈ F : Sk,f =

0}. Then the server broadcasts the corresponding file indexes {f ∈ F : maxk∈K:Ak =f (1−Sk,f ) =
1}, which implies R. Next, based on Xk and R, user k computes P∗k and reports it to the server.
Finally, the server obtains µ̌(X) and transmits the files in {f ∈ F : Rf + P̌f ≥ 1}, based on
which user k obtains ∆Šk .
VI. O NLINE D ECENTRALIZED A LGORITHM
To implement the low-complexity decentralized policy µ̌ proposed in Section V, we need
P
(k)
1
′
to compute gk (Xk1 ) =
A′ ∈F̄ qAk ,A′ V̌k (Ak , fk ), requiring priori knowledge of the transition
k

k

matrices of the K user demand processes, i.e., Qk , k ∈ K. In this section, we propose an online

decentralized algorithm (ODA) to implement µ̌ via Q-learning [21], when Qk is unknown.
First, introduce the Q-factor Qk (Xk1 ,∆Sk1 ) of the per-user per-file state-action pair (Xk1 ,∆Sk1 ) as
X (k)
qAk ,A′ Vk1 (A′k , fk′ ), Xk1 ∈ F̄ ×F , ∆Sk1 ∈ Uk1 (Xk1 ). (25)
θk1 + Qk (Xk1 , ∆Sk1 ) , φ′ (Xk1 )+
k

A′k ∈F̄

By (15) and (25), we have
V̌k1 (Xk1 ) =

June 30, 2017

min

∆Sk1 ∈Uk1 (Xk1 )

Qk (Xk1 , ∆Sk1 ), Xk1 ∈ F̄ × F ,

(26)

DRAFT

19

Algorithm 1 Online Decentralized Algorithm (ODA)
1: Initialization. Set t = 0. Each user k initializes Qk,t (·).
2: Per-User Per-File Q-factor Update. At the beginning of the tth slot, t ≥ 1, each user k updates Qk (·)

according to
Qk,t (Xk1 , ∆Sk1 ) = Qk,t−1 (Xk1 , ∆Sk1 )+γ(vk,t−1 (Ak ))1(Ak (t−1) = Ak ) φ′ (Xk1 )+
min

′

′
′
∆Sk1 ∈Uk1 (Xk1 )

′

Qk,t−1 Xk1 , ∆Sk1 ) −Qk,t−1 (Xk1 , ∆Sk1 )−

min

1 ∈U 1 (X 1 )
∆Sk,0
k
k,0


1
1
Qk,t−1 (Xk,0
, ∆Sk,0
) ,

Xk1 ∈ F̄ × F , ∆Sk1 ∈ Uk1 (Xk1 ),

(23)

′

where Xk1 , (Ak , fk ), Xk1 , (Ak (t), fk′ ) and vk,t (Ak ) denotes the number of times that Ak ∈ F̄ has been
requested by user k up to t, and then updates gk,t (Xk1 ), Xk1 ∈ F̄ × F according to
gk,t (Xk1 ) =

min

1 ∈U 1 (X 1 )
∆Sk,0
k
k,0

1
1
Qk,t (Xk,0
, ∆Sk,0
) + Qk,t (Xk1 , 0) − φ′ (Xk1 ), Xk1 ∈ F̄ × F .

(24)

3: Reactive Transmission Message. Each user k submits Ak (t) if Ak (t) ∈ {f ∈ F : Sk,f (t) = 0}. Then the server

broadcasts the file indexes {f ∈ F : maxk∈K:Ak (t)=f (1 − Sk,f (t)) = 1}.
4: Per-User Pushing Computation. Each user k constructs R(t). Given Xk (t), R(t) and gk,t (Ak (t), fk ), fk ∈ F ,

user k computes P∗k (t) and then reports it to the server.
5: Multicast Transmission at Server. The server obtains P̌f (t) in (21) and multicasts the files in {f ∈ F :

Rf (t) + P̌f (t) = 1}.
6: Per-User Caching. Each user k updates its own cache state Sk (t) according to ∆Šk (t) in (22).
7: Set t ← t + 1 and go back to Step 2.

θk1 + Qk (Xk1 , ∆Sk1 ) = φ′ (Xk1 ) +

X

A′k ∈F̄

(k)

qAk ,A′

k

min
′

′

′

∆Sk1 ∈Uk1 (Xk1 )

Qk ((A′k , fk′ ), ∆Sk1 ),
Xk1 ∈ F̄ × F , ∆Sk1 ∈ Uk1 (Xk1 ).

(27)

Then, by (25) and (27), we can express gk (Xk1 ) as a function of the Q-factor Qk (·), k ∈ K, i.e.,
gk (Xk1 ) = θk1 + Qk (Xk1 , 0) − φ′ (Xk1 ),

Xk1 ∈ F̄ × F .

(28)

Recall that µ̌ given in (21) and (22) is expressed in terms of gk (Xk1 ), k ∈ K. From (28), we learn
that µ̌ can be determined by the Q-factor Qk (·), k ∈ K. Considering that µ̌ cannot be obtained
directly via minimizing the corresponding Q-factor, the standard Q-learning algorithm cannot be
used to implement µ̌ online. Next, we propose the ODA, as shown in Algorithm 1, to learn Qk (·)
and implement µ̌ online when Qk , k ∈ K are unknown. In particular, the stepsize γ(·) in the ODA
P∞ 2
P
satisfies that 0 < γ(n) < ∞, ∞
n=1 γ (n) < ∞. Based on the convergence
n=1 γ(n) = ∞ and
June 30, 2017

DRAFT

20

results of Q-learning in [21], we can easily show that limn→∞ Qk,n (Xk1 , ∆Sk1 ) = Qk (Xk1 , ∆Sk1 )
almost surely.
Remark 7 (Illustration of the ODA). The proposed ODA differs from the standard Q-learning
algorithm in the following two facets. Firstly, for each per-user per-file MDP, at each time
slot, instead of updating the Q-factor at the currently sampled state-action pair, it updates
the Q-factors at a set of state-action pairs with the current demand state, thereby speeding
up the convergence. Secondly, when learning the Q-factors of the K per-user per-file MDPs,
it implements a policy which cannot be directly obtained from the optimal policies of the K
per-user per-file MDPs.
VII. N UMERICAL R ESULTS
In this section, we first evaluate the convergence of our proposed ODA and then compare
it with five baselines. Specifically, we consider three baselines which operate based on priori
knowledge of Qk , k ∈ K: the aforementioned MP caching policy in Section III, local most
popular (LMP) caching policy in which at each time slot t, each user k stores the C files in {f ∈
F : Rf (t)+Sk,f (t) = 1} with the largest transition probabilities given current demand state Ak (t)
[24], as well as joint threshold-based pushing [25] and local most popular caching policy (TLMP)
P
(k)
where at each time slot t, the server pushes the file f ∗ (t) , arg maxf ∈F k∈K:Sk,f (t)=0 qAk (t),f
P
if and only if f ∈F Rf (t) is below a threshold T , and each user implements the LMP caching

policy. Note that MP and LMP are of the same complexity order, i.e., O KF log(F ) , while

the complexity order of TLMP is O KF 2 log(F ) . In addition, we consider two other baselines
which operate without priori knowledge of Qk , k ∈ K, and make caching decisions based on

instantaneous user demand information, i.e., LRU and LFU. They are of the same complexity

order, i.e., O KF . In the simulation, we consider Qk = Q for all k ∈ K and adopt Q ,
(qi,j )i∈F̄ ,j∈F̄ similar to the demand model in [24], where qi,j is given by


Q0 , i ∈ F̄ , j = 0,



1


 (1 − Q0 ) PF jγ 1 , i = 0, j ∈ F ,
j ′ =1 j ′γ
qi,j ,

1

(1 − Q0 ) N , i ∈ F , j = (i + q) mod (F + 1), q ∈ {1, 2, · · · , N},




 0, otherwise.

(29)

Note that Q is parameterized by {Q0 , γ, N}. Specifically, Q0 denotes the transition probability

of requesting nothing given any current file request. The transition probability of requesting

June 30, 2017

DRAFT

21

any file f ∈ F given no current file request, i.e., i = 0, is modeled by a Zipf distribution
parameterized by γ. For any i ∈ F , we assign a set of neighboring files, i.e., Ni , {f ∈ F :
f = (i + q) mod (F + 1), q = 1, 2, · · · , N}, where N represents the number of neighbors.
Then, the transition probability of requesting any file f ∈ Ni given the current file request i ∈ F
is modeled by the uniform distribution. The transition probability of requesting any file f ∈
/ Ni
given current file request i ∈ F is zero. In the simulation, we set F = 100, T = 1, N = 2,
Q0 = 0.2 and γ = 0.5 unless otherwise stated.
Fig. 4 (a) shows that the proposed ODA converges quite fast. Fig. 4 (b)-(f) illustrate the average
cost versus several system parameters. We observe that LMP behaves better than MP, LRU and
LFU, mainly due to the fact that LMP considers the temporal correlation of each user demand
process. The performance of TLMP is almost the same as that of LMP as its pushing and caching
policies are not intelligently designed. The last not the least, our proposed ODA significantly
outperforms the five baselines, primarily due to the fact that ODA takes into account both the
asynchronous feature and temporal correlation of file requests and jointly designs both pushing
and caching. Additionally, ODA achieves a good balance between the current transmission cost
and the future average transmission cost.
Specifically, Fig. 4 (b) illustrates the average cost versus the cache size. Intuitively, the
average cost monotonically decreases with the cache size. We can also see that our proposed
ODA achieves good performance gains over the five baselines even at a small cache size.
Fig. 4 (c) illustrates the average cost versus the number of users K. As expected, the average
cost monotonically increases with the number of users, since the traffic load increases with the
number of users. Furthermore, we can see that the performance gains of our proposed ODA over
the five baselines increase with the number of users. Therefore, ODA behaves much robuster
against the change of the number of users than the five baselines. Fig. 4 (d)-(g) illustrate the
average cost versus the parameters of the transition matrix of the user demand process, i.e., N,
γ and Q0 . Specifically, Fig. 4 (d) illustrates the average cost versus the number of neighbors N.
We can see that the average cost monotonically increases with the number of neighbors. This
is because the user demand processes become less predictable as N becomes larger. Fig. 4 (e)
illustrates the average cost versus the Zipf exponent γ. We see that the average cost monotonically
decreases with γ. This is because as γ grows, the probability that a requested file is popular
and is cached becomes larger. Fig. 4 (f) illustrates the average cost versus Q0 . The average cost
decreases with Q0 , mainly due to the fact that the traffic load becomes lighter. As Q0 decreases,
June 30, 2017

DRAFT

22

4000

3500

LRU
LFU
MP
LMP
TLMP
ODA

3000

3500

2500

3000

Average Cost

Average Cost

LDP
ODA

2000

1500

2000

1500

1000

1000

500

0

2500

0

500

1000

1500

2000

2500

3000

3500

4000

4500

500
2

5000

4

6

8

10

(a) Convergence at K = 10, C = 5.

5

LRU
LFU
MP
LMP
TLMP
ODA

1600
1400

4
3

1000
800
600

1

400

10

15

20

25

30

35

40

45

50

200
1

2

3

4

5

(c) Number of users at C = 10.

7

8

9

10

(d) N at C = 10, K = 10, γ = 1.
6000

240
LRU
LFU
MP
LMP
TLMP
ODA

220

LRU
LFU
MP
LMP
TLMP
ODA

5000

200

4000

Average Cost

Average Cost

6

N

K

180

3000

160

2000

140

1000

120
0.05

20

1200

2

0
5

18

LRU
LFU
MP
LMP
TLMP
ODA

1800

Average Cost

Average Cost

6

16

(b) Cache size at K = 10.

x 10

7

14

2000

5

8

12

C

Time Slots

0.1

0.15

0.2

0.25

0.3

0.35

γ

(e) γ at C = 10, K = 10.

0.4

0.45

0.5

0
0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5

Q0

(f) Q0 at C = 10, K = 10, N = 15.

Figure 4: Convergence and average cost versus cache size C and number of users K.
June 30, 2017

DRAFT

23

the performance gains of ODA over the five baselines become larger, which again indicates that
ODA is much robuster against the change of the traffic load than the five baselines.
VIII. C ONCLUSIONS
In this paper, we formulate the bandwidth utilization maximization problem via joint pushing
and caching as an infinite horizon average cost MDP. By structural analysis, we show how the
optimal policy balances the current transmission cost with the future average transmission cost.
In addition, we show that the optimal policy achieves a tradeoff between the cache size and the
bandwidth utilization. By a linear approximation of the value function and relaxation techniques,
we develop a decentralized policy with polynomial complexity. Moreover, we propose an online
decentralized algorithm to implement the proposed low-complexity decentralized policy when
priori knowledge of user demand processes is unknown. Finally, using numerical results, we
demonstrate the advantage of the proposed solutions over some existing designs.
A PPENDIX A: P ROOF

OF

L EMMA 1

First, we show that the Weak Accessibility (WA) condition holds for our system. Consider
any two system states X1 , (A1 , S1 ) ∈ F̄ K × S K and X2 , (A2 , S2 ) ∈ F̄ K × S K . Recall that
for any k ∈ K, {Ak (t)} is an irreducible Markov chain. Thus, there exists an integer t′ ≥ 1
such that Pr[Ak (t′ ) = A2k |Ak (0) = A1k ] ≥ 0. In addition, there exists a policy µ̄ , (µ̄P , µ̄∆S )
such that µ̄∆S (A, S1 ) = S2 and µ̄∆S (A, S2 ) = S2 for all A ∈ F̄ . Hence, Pr[X(t′ ) = X2 |X(0) =
X1 , µ̄] = Pr[A(t′ ) = A2 |A(0) = A1 ] ≥ 0, i.e., X2 is accessible from X1 under policy µ̄. By
Definition 4.2.2 in [21], we conclude that WA holds for the MDP. Thus, by Proposition 4.2.3
and Proposition 4.2.1 in [21], the optimal average costs of the MDP in Problem 1 for all initial
system states are the same and the solution (θ, V (·)) to the following Bellman equation exists:
o
n X
X
Pr[X′ |X, (P, ∆S)]V (X′ ) , ∀ X, (30)
θ + V (X) =
min
φ( (Rf + Pf )) +
(P,∆S)∈U(X)

f ∈F

X′ ∈F̄ K ×S K

where X′ , (A′ , S′ ) and Rf is given by (2). Furthermore, the optimal policy µ∗ is given by
n X
o
X

µ∗ (X) = arg
min
φ
(Rf + Pf ) +
Pr[X′ |X, (P, ∆S)]V (X′ ) , ∀ X. (31)
(P,∆S)∈U(X)

f ∈F

X′ ∈F̄ K ×S K

Note that the transition probability of the system state is given by:

Pr[X′ |X, (P, ∆S)] = Pr[(A′ , S′ )|(A, S), (P, ∆S)] = Pr[A′ |A] Pr[S′ |S, ∆S]

June 30, 2017

DRAFT

24

=



Q

(k)
k∈K qAk ,A′k ,


0,

S′ = S + ∆S,

(32)

′

S 6= S + ∆S.

By substituting (32) into (30) and (31), we obtain the Bellman equation in (10) and the optimal
policy in (11), respectively. Therefore, we complete the proof.
A PPENDIX B: P ROOF

OF

L EMMA 2

First, for any C1 and C2 such that C1 < C2 < F , we show θ(C1 ) > θ(C2 ) based on the
coupling and interchange arguments [15]. Consider two independent MDP systems, i.e., System 1
and System 2, which have the same transition matrix of user demand processes, i.e., (Qk )k∈K ,
and numbers of files and users, i.e., F and K, but have different cache sizes, denoted as C1 and
C2 , where C1 < C2 < F . Suppose A1 (t) = A2 (t) for all time slot t. That is, the two systems are
under the same sample paths of the user demand processes. In addition, both systems adopt the
same pushing action at each time slot t, denoted as P1∗ (t), which is the optimal pushing action
for System 1 and a feasible pushing action for System 2 (due to C1 < C2 ). On the other hand, the
two systems may have different caching actions at each time slot t. Consider any S1 (0) ∈ S1 ,
P
P
{(Sk,f )k∈K,f ∈F : f ∈F Sk,f = C1 } and S2 (0) ∈ S2 , {(Sk,f )k∈K,f ∈F : f ∈F Sk,f = C2 } such

that S1 (0)  S2 (0). The cache state of System 1 evolves according to S1 (t+1) = S1 (t)+∆S1∗ (t),
where ∆S1∗ (t) denotes the optimal caching action for System 1 at each time slot t. System 2
implements a caching policy such that at each time slot t, S2 (t) ∈ S2 and S1 (t)  S2 (t).

This holds because that C1 < C2 , S1 (0)  S2 (0) and P2 (t) = P1∗ (t). Based on the facts that
A1 (t) = A2 (t) and S1 (t)  S2 (t), by (2) we have R2 (t)  R1 (t), i.e., Rf2 ≤ Rf1 , f ∈ F ,
P

P

implying φ f ∈F Rf2 (t)+Pf1∗(t) ≤ φ f ∈F Rf1 (t)+Pf1∗(t) at each time slot t. Considering

that C1 < C2 < F and S1 (t)  S2 (t), for each user k, there exists at least a file fk ∈ F such

1
2
that Sk,f
(t) = 0 < Sk,f
(t) = 1. For each k ∈ K, since {Ak } is irreducible, fk can be requested
k
k

by user k within a finite average number of transitions. Therefore, there exists at least a time
slot t such that Ak (t) = fk for all k ∈ K. By (2), Rf1k (t) > Rf2k (t) holds for all k ∈ K and
P

P

thus φ f ∈F Rf2 (t)+Pf1∗(t) < φ f ∈F Rf1 (t)+Pf1∗(t) . Thus, θ(C1 ) > θ′ (C2 ), where θ′ (C2 )

denotes the average cost for System 2 under the aforementioned policy for System 2. Hence,
P
θ(C1 ) > θ(C2 ). Secondly, when C ≥ F , intuitively, at each time slot, f ∈F Rf = 0 can be

satisfied. Hence, θ(C) = 0. The proof ends.

June 30, 2017

DRAFT

25

A PPENDIX C: P ROOF

OF

L EMMA 3

We prove Lemma 3 based on the partial monotonicity of value function V (·) w.r.t. the system
cache state S shown using relative value iteration algorithm (RVIA) and mathematical induction.
First, we introduce RVIA [21]. For all X ∈ F̄ K × S K , let Vn (X) denote the value function
in the nth iteration, where n = 0, 1, · · · . Define
!
F
X
X Y (k)
Jn+1 (X, un ) , φ
Rn,f + Pn,f +
qAk ,A′ Vn (A′ , S + ∆Sn ),
k

(33)

A′ ∈F̄ K k∈K

f =1

where un , (Pn , ∆Sn ) denotes the system action under state X in the nth iteration. Note that
Jn+1 (X, un ) corresponds to the R.H.S of the Bellman equation in (10). We refer to Jn+1 (X, un )
as the state-action cost function in the nth iteration. Under RVIA, Vn (X) evolves according to
Vn+1 (X) = min Jn+1 (X, un ) − min Jn+1 (X§ , un )
un

un

= Jn+1 (X, µ∗n (X)) − Jn+1 (X§ , µ∗n (X§ )), X ∈ F̄ K × S K

(34)

where Jn+1 (X, un) is given by (33), µ∗n denotes the optimal policy that attains the minimum of
the first term in (34) in the nth iteration and X§ ∈ F̄ K × S K is some fixed state. By Proposition
4.3.2 in [21], for all X ∈ F̄ K × S K , the generated sequence {Vn (X)} converges to V (X) given
in the Bellman equation in (10) under any initialization of V0 (X), i.e.,
lim Vn (X) = V (X), X ∈ F̄ K × S K ,

n→∞

(35)

where V (X) satisfies the Bellman equation in (10).
Next, we prove the partial nonincreasing monotonicity of V (·) w.r.t. the system cache state
S, i.e., for all S1 , S2 ∈ S K such that S1  S2 , V (A, S1 ) ≥ V (A, S2 ) for all A ∈ F̄ K . Based on
RVIA, it is equivalent to show that for all S1 , S2 ∈ S K such that S1  S2 ,
Vn (A, S1 ) ≥ Vn (A, S2 ),

(36)

holds for all n = 0, 1, · · · . We now prove (36) based on mathematical induction. First, we
initialize V0 (X) = 0 for all X ∈ F̄ K × S K . Thus, we have V0 (A, S1 ) ≥ V0 (A, S2 ), meaning (36)
holds for n = 0. Then, assume (36) holds for some n ≥ 0. Denote with (P1n , ∆S1n ) the optimal
action under (A, S1 ), i.e., µ∗n (A, S1 ) = (P1n , ∆S1n ), and denote with (P2n , ∆S2n ) the optimal action
′
)k∈K,f ∈F where
under (A, S2 ), i.e., µ∗n (A, S2 ) = (P2n , ∆S2n ). Define ∆S′n , (∆Sn,k,f


∆S 1 , S 2 + ∆S 1
n,k,f
k,f
n,k,f ≤ 1,
′
∆Sn,k,f ,
k ∈ K, f ∈ F .

2
1
0,
Sk,f + ∆Sn,k,f > 1,
June 30, 2017

(37)

DRAFT

26

From (37), (P1n , ∆S′n ) is a feasible action under (A, S2 ). From (34), we have
Vn+1 (A, S2 ) = Jn+1 ((A, S2 ), µ∗n (A, S2 )) − min Jn+1 (X§ , un )
un

(a)

≤ Jn+1 ((A, S2 ), (P1n , ∆S′n )) − min Jn+1 (X§ , un )
un
X
X Y (k)
2
1
= φ(
Rn,f
+ Pn,f
)+
qAk ,A′ Vn (A′ , S2 + ∆S′n ) − min Jn+1 (X§ , un )

(b)

≤ φ(

X

1
1
Rn,f
+ Pn,f
)+

≤ φ(

X

1
1
Rn,f
+ Pn,f
)+

f ∈F
(d)

un

(k)

X Y

qAk ,A′ Vn (A′ , S2 + ∆S′n ) − min Jn+1 (X§ , un )

X Y

qAk ,A′ Vn (A′ , S1 + ∆S1n ) − min Jn+1 (X§ , un )

k

A′ ∈F̄ K k∈K

f ∈F
(c)

k

A′ ∈F̄ K k∈K

f ∈F

A′ ∈F̄ K k∈K

un

(k)

k

un

= Vn+1 (A, S1 ),

(38)

where (a) follows from the optimality of µ∗n (A, S2 ) under (A, S2 ) and the feasibility of (P1n , ∆S′n )
under (A, S2 ) in the nth iteration. (b) follows from the fact that R 2  R 1 according to (2) since
S1  S2 . (c) follows from S1 + ∆S1n  S2 + ∆S′n (due to S1  S2 and (37)) and (36). (d)
follows from (33) and (34). Hence, (36) holds in the (n + 1)th iteration. By induction, we
show that Vn (A, S1 ) ≥ Vn (A, S2 ) holds for all n = 0, 1, · · · . Thus, by RVIA, we conclude that
V (A, S1 ) ≥ V (A, S2 ). Similarly, we can show that for all S1 , S2 ∈ S K such that S1  S2 , if there
1
2
exists at least a pair of k and f satisfying that Sk,f
< Sk,f
, V (A, S1 ) > V (A, S2 ) for all A ∈ F̄ K .

Finally, based on the partial nonincreasing monotonicity of the value function, we prove
P
Q
(k)
Lemma 3. For all state (A, S) ∈ F̄ K × SˇK , denote with G(A, S + ∆S) ,
q
′
′
K
A ∈F̄

k∈K Ak ,Ak

V (A′, S+∆S) the objective function in (13) for all ∆S ∈ U∆S (X, µ∗P (X)) and ∆S∗ = µ∗∆S (A, S)

the optimal caching action given in (13). Since for all S1 , S2 ∈ S K such that S1  S2 , V (A, S1 ) ≥
V (A, S2 ) for all A ∈ F̄ K , we have G(A, S + ∆S1 ) ≥ G(A, S + ∆S2 ) for all ∆S1 , ∆S2 such that
1
2
∆S1  ∆S2 . Furthermore, if there exists at least a pair of k and f satisfying that Sk,f
< Sk,f
,

G(A, S + ∆S1 ) > G(A, S + ∆S2 ). In the sequel, we consider two cases:
•

Case i: S ∈
/ SˇK . First, we show that ∆S∗  0 by contradiction. Suppose that there exist k ′
and f ′ such that ∆Sk∗′ ,f ′ < 0. Denote ∆S , (∆Sk,f )k∈K,f ∈F where


0,
k = k′, f = f ′,
∆Sk,f ,

∆S ∗ , otherwise.
k,f

(39)

Then, ∆S  ∆S∗ with ∆Sk′ ,f ′ > ∆Sk∗′ ,f ′ . Hence, G(A, S + ∆S) < G(A, S + ∆S∗ )

which contradicts the optimality of ∆S∗ . Thus, we have ∆S∗  0. Furthermore, since

June 30, 2017

DRAFT

27

P
S ∈
/ Š K and C < F , there always exists a demand state A such that
f ∈F Rf =

P
1 − Sk,f > 0. By contradiction, we can show that for a state (A, S)
f ∈F maxk∈K:Ak =f
P
such that S ∈
/ Š K and f ∈F Rf > 0, there exists at least a pair of k ∈ K and f ∈ F

∗
such that Sk,f = 0 and ∆Sk,f
= 1. Recall that for all k ∈ K, {Ak } is irreducible, i.e., any

demand state Ak ∈ F̄ can be visited within a finite average number of transitions. Thus,
under the optimal policy µ∗ , if the system state starts from any state (A, S) where S ∈
/ Š K ,
the cache state S will transit into the set SˇK and never move back.
•

Case ii: S ∈ SˇK . First, we show that S + ∆S∗ ∈ Š K by contradiction. Suppose that
S + ∆S∗ ∈
/ Š K , then there exists ∆S such that S + ∆S∗  S + ∆S ∈ Š K , implying
1
2
that there exists at least a pair of k and f satisfying Sk,f
= 0 and Sk,f
= 1. Hence,

G(A, S + ∆S∗ ) < G(A, S + ∆S) which contradicts the optimality of ∆S∗ . Thus, under the
optimal policy µ∗ , if started at all state (A, S) where S ∈ Š K , the system state shall never
come to a state (A, S) where S ∈
/ SˇK .
The proof ends.
A PPENDIX D: P ROOF

OF

L EMMA 4

We prove Lemma 4 by illustrating the relationship between the K per-user per-file MDPs and
the original MDP. First, we relax the action space U(X) via ignoring the multicast opportunities
(i.e., considering unicast transmissions) in both reactive transmission and pushing. Specifically,
let Rk , (Rk,f )f ∈F ∈ {0, 1}F denote the reactive transmission action of user k, where
Rk,f , 1{Ak = f }(1 − Sk,f ), f ∈ F , k ∈ K.

(40)

Denote with Pk , (Pk,f )f ∈F ∈ {0, 1}F the pushing action of user k. The per-user pushing action
constraints are as follows:
Pk,f (t) ≤ 1 − Rk,f (t),

f ∈ F , k ∈ K,

(41)

Pk,f (t) ≤ 1 − Sk,f (t),

f ∈ F , k ∈ K,

(42)

where (41) is to guarantee that each file f ∈ F is not transmitted more than once to user k
at each time slot t and (42) is to guarantee that a file f which has already been cached in
the storage of user k is not pushed again at each time slot t. By omitting the coupling among

June 30, 2017

DRAFT

28

users incurred by the multicast transmission, i.e., Rf = maxk∈K Rk,f and Pf = maxk∈K Pk,f , we
rewrite the cache update constraint in (5) as:
− Sk,f (t) ≤ ∆Sk,f (t) ≤ Rk,f (t) + Pk,f (t), f ∈ F , k ∈ K.

(43)

In this way, we construct action space Ǔ(X) , {(P, ∆S) : ∆S ∈ Ǔ∆S (X, P), P ∈ ǓP (X)}.
Q
Specifically, Ǔ∆S (X, P) , k∈K Ǔ∆S,k (Xk , Rk +Pk ) where Ǔ∆S,k (Xk , Rk +Pk ) , {(∆Sk,f )f ∈F :
Q
(7)(8)(43)} denotes the caching action space of user k and ǓP (X) , k∈K ǓP (Xk ) where

ǓP (Xk ) , {(Pk,f )f ∈F : (41)(42)} denotes the pushing action space of user k. Thus, Ǔ(X) =
Q
k∈K Ǔk (Xk ), where Ǔk (Xk ) , {(Pk , ∆Sk ) : ∆Sk ∈ Ǔ∆S,k (Xk , Rk + Pk ), Pk ∈ ǓP,k (Xk )}.

Then, we establish an MDP under the unicast transmission, named as unicast MDP. For the

P
P
unicast MDP, the per-stage cost is K1 k∈K φ
f ∈F (Rk,f +Pk,f ) and the action space is Ǔ(X).
By Proposition 4.2.2 in [21] and the proof of Lemma 1, for the unicast MDP, we learn that there

exist (θ̌, V̌ (·)) satisfying:
o
n1 X X
 X Y (k)
φ
(Rk,f + Pk,f ) +
qAk ,A′ V̌ (A′ , S+∆S) , ∀X, (44)
θ̌+ V̌ (X) = min
k
(P,∆S)∈Ǔ(X) K
′
Kk∈K
k∈K
f ∈F
A ∈F̄

where θ̌ and V̌ (·) represent the average cost and value function of the unicast MDP, respectively.
Considering that the optimal policy µ∗ in (11) is a feasible policy for the unicast MDP and


P
P
P
1
φ
k∈K φ
f ∈F (Rk,f + Pk,f ) when Rk,f = Rf and Pk,f = Pf , we
f ∈F (Rf + Pf ) = K

have θ ≥ θ̌. Note that the per-stage cost of the unicast MDP is additively separable and the action
Q
space Ǔ(X) can be decoupled into K local action spaces, i.e., Ǔ(X) = k∈K Ǔk (Xk ). Hence,
P
P
(θ̌, V̌ (X)) of the unicast MDP can be expressed as V̌ (X) = k∈K V̌k (Xk ) and θ̌ = k∈K θ̌k ,
respectively, where (θ̌k , V̌k (Xk )) satisfy:
n1 X
o
 X (k)
θ̌k + V̌k (Xk ) =
min
qAk ,A′ V̌k (A′k , Sk+∆Sk ) , ∀Xk . (45)
φ
(Rk,f +Pk,f ) +
k
(Pk ,∆Sk )∈Ǔk (Xk ) K
′
f ∈F
Ak ∈F̄

The Bellman equation in (45) corresponds to a per-user MDP for user k. θ̌k and V̌k (Xk )
denote the per-user average cost and value function for user k, respectively. Specifically, for
the per-user MDP of user k, at each time slot t, Xk (t) = (Ak (t), Sk (t)) denotes the system
state; Rk (t) and Pk (t) denote the reactive transmission action and pushing action, respectively;
∆Sk (t) ∈ U∆S,k (Xk (t), Rk (t) + Pk (t)) denotes the caching action; the demand state Ak (t)
evolves according to the Markov chain {Ak (t)} and the cache state Sk (t) evolves according to

P
Sk (t + 1) = Sk (t) + ∆Sk (t); K1 φ
f ∈F (Rk,f (t) + Pk,f (t)) denotes its per-stage cost.
June 30, 2017

DRAFT

29

Next, we establish K per-user per-file MDPs via omitting the coupling among the cache units
for each user of the K per-user MDPs. Specifically, for each per-user MDP, considering that at
each time slot, the transmission cost is either φ(1) or 0, there is no need to push and hence each
user only has to decide whether to cache the received (i.e., requested) file and evict the cached
file in its storage or not. Given user state Xk = (Ak , Sk ), we have ∆Sk,f ∈ {0, −1(Ak ∈
/ {0, f })}
for all f ∈ {f ∈ F : Sk,f = 1} and ∆Sk,f = 0 for all f ∈ {f ∈ F : Sk,f = 0}. By omitting
P
the constraint f ∈F Sk,f + ∆Sk,f = 0 and treating each cache unit independently, we relax
Q
′
U∆S,k (Xk , R+P) into U∆S,k
(Xk , R+P) , fk ∈F :Sk,f =1 Uk1 (Xk1 ), where Xk1 , (Ak , fk ) denotes
k

the per-user per-file state and Uk1 (Xk1 ) , {0, −1(Ak ∈
/ {0, fk })}. Similarly, by Proposition 4.2.2

in [21] and the proof of Lemma 1, there exist (θ̌k′ , V̌k′ (·)) satisfying:
X (k)
X

1
qAk ,A′ V̌k′ (A′k , Sk + ∆Sk ), ∀Xk ,
Rk,f +
min
θ̌k′ + V̌k′ (Ak , Sk ) = φ
′
k
K f ∈F
∆Sk ∈Ǔ∆S,k (Xk ) ′

(46)

Ak ∈F̄

′
where Rk,f is given by (40). For any Xk ∈ F̄ × Š, based on the fact that Ǔ∆S,k (Xk ) ⊆ Ǔ∆S,k
(Xk ),

the optimal policy for the original per-user MDP, denoted as µ̌∗k , is feasible to the relaxed per-user
MDP. Denote with θ̌k′ (µ) the average cost of the relaxed per-user MDP under policy µ and then

P
we have θ̌k′ ≤ θ̌k′ (µ̌∗k ) = θ̌k . Note that for per-user state (Ak , Sk ), K1 φ
R
= K1 φ 1 −
k,f
f ∈F


P
−φ
1(A
=
f
)
1(Ak 6= 0),
Sk,Ak 1(Ak 6= 0) = fk ∈F :Sk,f =1 φ′ (Xk1 ), where φ′ (Xk1 ) , K1 φ(1)
k
k
C
k
Q
and Ǔ′∆S,k (Xk ) = fk ∈F :Sk,f =1 Uk1 (Xk1 ). Thus, we have that V̌k′ (Ak , Sk ) and θ̌k′ in (46) can
k
P
1
′
1
be expressed as V̌k′ (Ak , Sk ) =
f ∈F :Sk,f =1 V̌k (Ak , f ) and θ̌k = Cθk , respectively, where for
all k ∈ K, Xk1 ∈ F̄ × F , (θk1 , V̌k1 (Xk1 )) satisfy (15). Here, (15) corresponds to the Bellman
equation of the aforementioned per-user per-file MDP for user k with unit cache size and θk1
and V̌k1 (Xk1 )) represent the per-user per-file average cost and value function, respectively. Since
P
P
P
P
C k∈K θk1 = k∈K θ̌k′ ≤ k∈K θ̌k ≤ θ(C), we have θ(C) ≥ C k∈K θk1 . The proof ends.
R EFERENCES
[1] Cisco, “Cisco visual networking index: Global mobile data traffic forecast update 2016–2021” White Paper, 2017. [Online].
Available: http://goo.gl/tZ6QMk
[2] G. Paschos, E. Bastug, I. Land, G. Caire, and M. Debbah, “Wireless caching: technical misconceptions and business barriers,”
IEEE Commun. Mag., vol. 54, no. 8, pp. 16–22, Aug. 2016.
[3] K. Poularakis, G. Iosifidis, V. Sourlas and L. Tassiulas, “Multicast-aware caching for small cell networks,” 2014 IEEE
Wireless Commun. and Networking Conference (WCNC), Istanbul, 2014, pp. 2300-2305.
[4] E. Bastug, M. Bennis and M. Debbah, “Cache-enabled small cell networks: Modeling and tradeoffs,” 2014 11th International
Symposium on Wireless Commun. Systems (ISWCS), Barcelona, 2014, pp. 649-653.

June 30, 2017

DRAFT

30

[5] Y. Cui and D. Jiang, “Analysis and Optimization of Caching and Multicasting in Large-Scale Cache-Enabled Heterogeneous
Wireless Networks,” IEEE Trans. Wireless Commun., vol. 16, no. 1, pp. 250-264, Jan. 2017.
[6] N. Golrezaei, P. Mansourifard, A. F. Molisch and A. G. Dimakis, “Base-Station Assisted Device-to-Device Communications
for High-Throughput Wireless Video Networks,” IEEE Trans. Wireless Commun., vol. 13, no. 7, pp. 3665-3676, July 2014.
[7] N. Golrezaei, A. G. Dimakis and A. F. Molisch, “Scaling Behavior for Device-to-Device Communications With Distributed
Caching,” IEEE Trans. Inf. Theory, vol. 60, no. 7, pp. 4286-4298, July 2014.
[8] J. Wang, “A Survey of Web Caching Schemes for the Internet”, SIGCOMM Comput. Commun. Rev., vol. 29, no. 5, pp.
36–46, Oct. 1999.
[9] M. Gregori, J. Gmez-Vilardeb, J. Matamoros, and D. Gndz, “Wireless content caching for small cell and d2d networks,”
IEEE J. Select. Areas Commun., vol. 34, no. 5, pp. 1222–1234, May 2016.
[10] H. Feng, Z. Chen and H. Liu, “Performance Analysis of Push-Based Converged Networks With Limited Storage,” IEEE
Trans. Wireless Commun., vol. 15, no. 12, pp. 8154-8168, Dec. 2016.
[11] J. Gong, S. Zhou, Z. Zhou and Z. Niu, ”Policy Optimization for Content Push via Energy Harvesting Small Cells in
Heterogeneous Networks,” IEEE Trans. Wireless Commun., vol. 16, no. 2, pp. 717-729, Feb. 2017.
[12] W. Chen and H. V. Poor, “Content pushing with request delay information,” IEEE Trans. Wireless Commun., vol. PP,
no. 99, pp. 1–1, 2017.
[13] Y. Lu, W. Chen, and H. Poor,“Content pushing based on physical layer multicasting and request delay information,” Proc.
IEEE GLOBECOM, Dec. 2016.
[14] J. Tadrous and A. Eryilmaz, “On Optimal Proactive Caching for Mobile Networks With Demand Uncertainties,” IEEE
Trans. Networking., vol. 24, no. 5, pp. 2715-2727, 2016.
[15] S. Gitzenis and N. Bambos, “Joint transmitter power control and mobile cache management in wireless computing,” IEEE
Trans. Mobile Computing, vol. 7, no. 4, pp. 498–512, April 2008.
[16] L. Huang, “System intelligence: Model, bounds and algorithms,” in Proc. 17th ACM MobiHoc, New York, NY, USA, pp.
171–180, 2016.
[17] B. Zhou, Y. Cui and M. Tao, “Stochastic Content-Centric Multicast Scheduling for Cache-Enabled Heterogeneous Cellular
Networks,” IEEE Trans. Wireless Commun., vol. 15, no. 9, pp. 6284-6297, Sept. 2016.
[18] J. D. Salehi, Zhi-Li Zhang, J. Kurose and D. Towsley, “Supporting stored video: reducing rate variability and end-to-end
resource requirements through optimal smoothing,” IEEE/ACM Trans. Networking., vol. 6, no. 4, pp. 397-410, Aug. 1998.
[19] Y. Cui, V. Lau, and Y. Wu, “Delay-aware BS discontinuous transmission control and user scheduling for energy harvesting
downlink coordinated MIMO systems,” IEEE Trans. Signal Process., vol. 60, no. 7, pp. 3786C3795, July 2012.
[20] Y. Cui, V. K. N. Lau, R. Wang, H. Huang and S. Zhang, “A Survey on Delay-Aware Resource Control for Wireless
SystemsłLarge Deviation Theory, Stochastic Lyapunov Drift, and Distributed Stochastic Learning,” IEEE Trans. Inf. Theory.,
vol. 58, no. 3, pp. 1677-1701, March 2012.
[21] D. P. Bertsekas, “Dynamic programming and optimal control 3rd edition, volume II,” Belmont, MA: Athena Scientific.,
2011.
[22] M. A. Maddah-Ali and U. Niesen, “Fundamental Limits of Caching,” IEEE Trans. Inf. Theory, vol. 60, no. 5, pp. 2856–
2867, May 2014.
[23] C. Guestrin, D. Koller, R. Parr, and S. Venkataraman, “Efficient solution algorithms for factored mdps,” Journal of Artificial
Intelligence Research, pp. 399C468, 2003.
[24] K. Psounis, et al. “Modeling Correlations in Web Traces and Implications for Designing Replacement Policies,” Comput.
Netw., vol. 45, no. 4, pp. 379–398, Jul. 2004.
[25] Y. Jiang, M. Wu and S. Wei, “Web prefetching: Costs, benefits and performance,” Proc. 7th WCW, 2002.

June 30, 2017

DRAFT

