# DeePref: Deep Reinforcement Learning For Video Prefetching In Content
Delivery Networks

Nawras Alkassab
University of South Carolina  Chin-Tser Huang
University of South Carolina  Tania Lorido Botran
Roblox

###### Abstract

Content Delivery Networks carry the majority of Internet traffic, and the
increasing demand for video content as a major IP traffic across the Internet
highlights the importance of caching and prefetching optimization algorithms.
Prefetching aims to make data available in the cache before the requester
places its request to reduce access time and improve the Quality of Experience
on the user side. Prefetching is well investigated in operating systems,
compiler instructions, in-memory cache, local storage systems, high-speed
networks, and cloud systems. Traditional prefetching techniques are well
adapted to a particular access pattern, but fail to adapt to sudden variations
or randomization in workloads. This paper explores the use of reinforcement
learning to tackle the changes in user access patterns and automatically adapt
over time. To this end, we propose, DeePref, a Deep Reinforcement Learning
agent for online video content prefetching in Content Delivery Networks.
DeePref is a prefetcher implemented on edge networks and is agnostic to
hardware design, operating systems, and applications. Our results show that
DeePref DRQN, using a real-world dataset, achieves a 17% increase in
prefetching accuracy and a 28% increase in prefetching coverage on average
compared to baseline approaches that use video content popularity as a
building block to statically or dynamically make prefetching decisions. We
also study the possibility of transfer learning of statistical models from one
edge network into another, where unseen user requests from unknown
distribution are observed. In terms of transfer learning, the increase in
prefetching accuracy and prefetching coverage are [$30\%$, $10\%$],
respectively. Our source code will be available on Github
111https://www.github.com.

##  1 Introduction and Related Work

Prefetching is a well-studied speculation technique that aims to make data
available in the cache before the requester places their request. A prefetcher
masks/reduces I/O latency between the data provider and consumer by predicting
future demands based on historical access patterns. Prefetching differs from
caching [57, 46, 49, 54] in the sense that data needs to be available in the
cache before the initial request by predicting future accesses and fetching
them into memory with the hope that they will be requested in the near future.
In caching, the item needs to be requested at least once in order for it to be
cached. Substantial work has been done studying the interaction between
prefetching and caching [11, 50, 33]. For example, Kimbrel and Karlin [33] had
made the first attempt towards understanding prefetching and caching pages
from parallel disks. The authors provided an offline theoretical model that
captures the characteristics of the system for prefetching with multiple disks
with a limited look-ahead into the request stream. Such an oracle is often not
provided, but it is helpful for setting up a baseline and understanding the
integration between caching and prefetching.

Figure 1: Content Delivery Networks Architecture with possible prefetching
implemented in different nodes across different layers.

Many prefetching techniques have been proposed over the last two decades to
exploit hardware design/features [74, 24, 85, 73, 44, 9], compiler-injected
instructions [13, 38, 53, 51, 35, 19], or memory access patterns in operating
systems [76, 3]. They are often limited to specific hardware design, access
pattern, or application-specific features/hints, and they exploit the design
of a lower level memory stack. For example, LEAP [3] is a kernel prefetcher
designed specifically for applications using remote memory. Such design of
prefetching algorithms limits its applications to various workloads which
exhibit a mixture of both sequential and random streams. In this work, we
present a prefetching algorithm that is agnostic to the hardware design,
operating system, and applications/workloads. Our approach takes only the
request ID to decide when and what to prefetch.

Furthermore, prefetching applications have become a prevalent feature in
numerous applications, such as local memory management, wherein the item is
prefetched from a Hard Disk Drive (HDD) or Solid State Drive (SSD) to the
local cache. SARC [22], for example, is a prefetching algorithm that
dynamically partitions the cache space into sequential blocks representing the
prefetched items and random blocks representing the on-demand pages. The SARC
algorithm considers the cache pollution by equalizing the marginal utility of
both prefetched data and demand-paged data. This equalization of cache misses
between random blocks and sequential blocks is not quite fair, since
sequential blocks require less time to fetch compared to random blocks due to
their spatial locality exposed in HDDs and SSDs. Therefore, a more weight
should be given to penalizing fetching random blocks. DULO [29] had addressed
this problem by giving random blocks more weight for being kept in cache to
compensate for their prefetching cost. In DULO, the characteristics of the
hard disk are exploited so that sequential access is more efficient than
random access. Further, AMP [21] reduces cache pollution by determining the
prefetching trigger point (i.e., when to prefetch) and the prefetching degree
(i.e., amount of data to prefetch). QuickMine [61] is a context-aware online
prefetching technique that relies on hints from applications to discover block
correlations in storage systems. QuickMine is a history-based prefetching
technique which is typically expensive compared to sequential prefetching
algorithms. To overcome that, QuickMine tags each application I/O block
request with a context identifier corresponding to a higher level application
context (e.g., a web interaction, database transaction). The tag enables the
request sequence to be split before mining, thus masking computation overhead
is manageable. The key novelty of QuickMine lies in detecting and leveraging
block correlations within application contexts. However, QuickMine leverages
the application contexts to make prefetching predictions. Thus, QuickMine
requires insights/hints from applications which may not be available or
feasible to the prefetching head in some environment. Rendering QuickMine
unavailable for legacy systems and makes it hard to deploy. VanDeBogart et al.
[72] proposed, libprefetch, an application-directed prefetching scheme that
aims at minimizing the I/O fetch time of non-sequential single-disk reads by
speculating the access patterns deduced from the application source code
itself. Chang et al. [12] focused on parallel disk I/O systems by providing
more I/O bandwidth. For SSD prefetching, the authors of FAST [31] proposed a
prefetching scheme on SSD drives to accelerate the application launch time.
Their approach is inherited from the fact that the I/O request sequence does
change over repeated start-up of the application during cold start, by
overlapping the SSD access (I/O) time with the computational (CPU) time by
running the application prefetcher concurrently with the application itself.

Figure 2: An illustrative flow chart of the communication between access
network, edge network, and cloud network upon a cache miss in CDNs. Note:  RTT
between edge and cloud networks is much larger than RTT between access and
edge networks.

Furthermore, hardware data prefetching is a well-known technique for hiding
and tolerating off-chip memory latency for single core and multicore systems
[4, 48, 47, 66, 9, 83]. Recently, Bera el al. [9] proposed a hardware
prefetching technique, Pythia, which learns to prefetch using multiple
different types of program context and system-level feedback information
inherent to its design by formulating the problem as Markov Decision Process
(MDP) and treating the prefetcher as a reinforcement learning agent. We take a
similar approach in this work by formulating the prefetching problem in CDNs
as a reinforcement learning problem, which we will discuss in Sec.3. For a
recent survey of hardware prefetching, please visit this paper [44]. For web
applications and cloud tenants prefetching, block storage systems such as
cloud tenants are disk-bound where the bottleneck is accessing blocks from the
disk itself (i.e., HDD, SSD), recent caching and prefetching techniques for
cloud applications have been proposed [77, 81, 30, 82, 14] to mitigate access
latency. For example, MITHRIL tracks temporal associations between blocks
whose access patterns are moderately frequent, leaving the more frequent
requests to be handled by the underlying caching mechanism. Unlike MITHRIL,
our approach does not rely on the underlying caching system by eliminating the
caching head and leaving the prefetching head to accomplish prefetching tasks
only.

For web security, a full TLS handshake between HTTPS client and web server is
considered a bottleneck, since the client needs to fetch and validate the
server’s certificate before a secure connection between client and server is
established. A typical TLS handshake consists of two round trips to complete.
Caching the server’s certificate on the web browser reduces the handshake to
one round trip [56, 37] or even to zero round trips [36], however, the TLS
certificate’s validation status may not be cached, and the latency imposed by
the validation process will still impact the QoE on the client side.
Therefore, Stark et al. [62] proposed a prefetching and pre-validating scheme
for TLS server certificate into the client’s web browser, allowing the client
to perform the TLS handshake and validate the server’s certificate with zero
round trips. Further, one of the methods proposed to perform certificate
prefetching is to prefetch the server certificate from CDNs to avoid any
overload on the server side [62].

Another interesting line of prefetching is web content prefetching [64].
Summers et al. [64] proposed an adaptive prefetching scheme for HTTP streaming
video servers that automatically adjusts prefetch size to gain higher disk
throughput on the server side. To do so, their algorithm uses system
measurements such as available memory, disk usage, and video bit rate from the
operating system to inform the application to periodically adjust the prefetch
size. The authors treat the entire operating system as a gray box and provide
application-level prefetching implementation without modifying the kernel.
Further, extensive experimentation on HTTP Streaming video workloads had been
conducted previously [63, 65] to better design flexible prefetching algorithms
(i.e., aggressive vs. non-aggressive). Measurement studies [10, 23] show that
video content has a long tail popularity distribution similar to Zipf
distribution. Meaning that only few of the hottest video files will benefit
from in-memory caching. However, studies show that 70-80% of videos are
watched only once [23, 84]. Therefore, we exclude, in this work, caching from
the memory management system on edge devices to allow the edge node to
accomplish prefetching tasks only as discussed in Sec.3. Moreover, assuming
that the workload follows Zipf-like distribution throughout the entire
experiment may be invalid, since the popularity distribution of video content
may change very rapidly in CDNs. Thus, we only provide visibility on the
popularity distribution to our prefetching agent as part of its initial state.

For high-speed networks with low latency, Voelker et al. [76, 6] introduced a
prefetching and caching algorithm that utilizes the free memory in idle
workstations in Local Area Networks (LAN) environments whereas the cost of
prefetching over a high-speed network is less than the cost of prefetching
locally on the hard-disk. This assumption is invalid considering CDNs because
the propagation delay is considerably large compared to LAN environments.
Another strong assumption the authors had made is that their central algorithm
assumes a complete prior knowledge of the reference streams of the
applications running on all participating nodes, including the pages to be
referenced, the relative order in which they are referenced, and the inter-
reference times. These assumptions cannot hold true considering nowadays
applications and workloads that express more stochasticity than sequentiality
such as cloud-based applications and video streaming applications in CDNs.

Recently, Multi-access Edge Computing (MEC) enabled caching and prefetching
techniques to be implemented at edge networks, enhancing QoE at the user-side
while benefiting cloud server at the core layer in CDNs. Video streaming
applications can utilize MEC environments to prefetch video segments to end
users at edge networks, allowing multi-users that are, possibly, close
geographically to benefit from the prefetched segments. SPACE [2] is a
prefetching and caching framework that utilizes MEC to prefetch video segments
to edge networks in cellular networks (i.e., 5G). SPACE models video segment
prefetching as a Markov finite state machine which can be updated online and
it uses the buffer size, link bit rate, previous QoE, previous link bit rate.
The authors of SPACE also proposed a cache eviction algorithm to evict the
prefetched segments, named Least Popular Used (LPU). Behravesh et al. [7]
proposed a segment prefetching algorithm based on bit rate prediction of
client segment requests using a near-optimal machine learning approach. COOPEC
is a video segment prefetcher that utilizes client requests and past viewing
history to minimize the bit rate oscillations caused by the web browser when
cache hits are inconsistent. MVP [20] is a video segment prefetching technique
implemented at edge networks for 4K Videos On Demand (VoD) applications. MVP
achieves seamless playback in realistic LTE-A network infrastructure.

To this end, we hypothesize that prefetching an entire video content with high
quality has its advantages over segment prefetching in CDNs where the
bottleneck is the upstream network between edge networks and cloud networks.
To name a few, 1) Prefetching video content as a bulk saves resources in the
upstream network, however, segment prefetching is still subject to
fluctuations in the upstream network since a continuous Transmission Control
Protocol (TCP) session needs to be maintained throughout watching the video
content. 2) Round Trip Time (RTT) of edge-cloud network is much larger than
access-edge network due to the propagation delay, therefore, prefetching an
entire video content eliminates any propagation delay of future requests. 3)
QoE is guaranteed in bulk prefetching, and it is only subject to Adaptive Bit
Rate Algorithms (ABR) of the end user network (i.e., access networks). To
illustrate, Fig.2 shows a flow chart of user requests generated in access
networks and forwarded to edge networks. Upon a cache miss, the request will
be forwarded to the cloud network in CDNs. We design a prefetcher that resides
at edge networks and makes prefetching decisions synchronous to user requests
online. The aim is to prefetch an entire video content with high quality, with
the hope that future requests from the same or different user will occur soon.
Our approach is minimally invasive and is agnostic to hardware design,
operating system, and application.

In this work, we utilize both DQN and DRQN designs as building blocks to
tackle the prefetching problem. We propose a prefetcher which is implemented
at edge networks where possible transfer learning can occur between edge
networks, as shown in Fig,4. We discuss the results for transfer learning in
Sec.5.2, but first we express the need to use Deep Reinforcement Learning
(DRL) due to the large state and action spaces exposed in video content
prefetching in CDNs.

Our results show that DeePref DRQN, using a real-world dataset, achieves 17%
increase in prefetching accuracy and 28% increase in prefetching coverage on
average compared to baseline approaches that use video content popularity as a
building block to statically or dynamically make prefetching decisions. In
terms of transfer learning, the increase of prefetching accuracy and
prefetching coverage are [$30\%$, $10\%$], respectively. We discuss the
experimental design and results in Sec. 5. We show that DeePref DRQN
outperforms baseline approaches with an increase of at least [$17\%$, $28\%$]
in terms of prefetching accuracy and coverage, respectively.

##  2 Motivation And Contribution

In recent years, we have witnessed an exponential growth in Internet traffic.
Mainly, this is due to the explosion of Big Data [42], the increased usage of
social media [32], the emergence of cloud computing [43] and edge computing
[59]. This rapid growth has accelerated the implementation and design of CDNs.
Cisco [16] had predicted that around 64% of the entire Internet traffic will
cross CDNs in 2020, up from 45% in 2015. Video streaming service providers
such as Netflix 222https://www.netflix.com and Hulu 333https://www.hulu.com
rely heavily on CDNs to distribute their video content to end users [1]. For
example, Akamai Technologies 444https://www.akamai.com is the market leader
(80% of the overall CDN market) in providing content delivery services where
it owns more than 12,000 servers over 1,000 networks in 62 countries [46].
Furthermore, There exists an increased trend in the popularity of video
content as a major internet traffic. According to Cisco [16], global Internet
video traffic (business and consumer, combined) will grow 4-fold from 2015 to
2020, a compound annual growth rate of 31%. Internet video traffic will be 79%
of all Internet traffic in 2020, up from 63% in 2015. In addition, Internet
video traffic will reach 127.8 Exabytes per month in 2020, up from 33.7
Exabytes per month in 2015, and Ultra HD and HD video content will be 15.7% of
Internet video traffic in 2020, up from 2.3% in 2015. This recent trend of
video popularity highlights the importance of video content prefetching from
cloud networks to fog networks in CDNs. Further, prefetching can be
implemented in various nodes from end users to cloud servers in CDNs, as
illustrated in Fig.1. Recently, Hu et al. [27] proposed a Reinforcement
Learning (RL) approach to prefetch successive episodes of video series to
access points that are shipped with large storage capacity and close to end
users, the assumption is that the end user is more likely to watch more than
one episode without skipping. IPAC [41] integrates prefetching with caching to
allow the video player at the end user side to generate prefetch requests for
successive video segments with the same bit-rates as the current request. IPAC
requires a modification of the underlying cache eviction algorithm, and it
does not consider multi-user prefetching (inter-correlation among user
requests). Further, Alkassab et al. [5] addressed the advantages and the
disadvantages of video content prefetching across different layers (core,
distribution, and access) in CDNs and discussed the utilization of out-of-band
bandwidth for prefetching in fog networks. Wu et al. [80] proposed a
prefetching scheme based on Bayesian Networks and Markov chains to prefetch
video files and designed a cache eviction algorithm which utilizes the content
heat and re-access probability such that the cached content with the least re-
access weight is evicted. On the other hand, Sham et al. [58] proposed an
admission control system to place prefetching requests based on CPU, memory
and other resource parameters in hybrid edge-cloud networks. Such design of
prefetching algorithms require system-level and application-level information
that may not be available at the prefetcher side, limiting the
applicability/implementation of such algorithms.

As discussed previously, prefetching in CDNs has many advantages such as
preventing bandwidth under-utilization, optimize server load, and reducing
access latency. Consequently, improving the overall system response time and
the Quality of Service (QoS) experienced by end users. On the other hand,
prefetching increases system resource demands in order to improve response
time which increases the incurred bandwidth consumption and storage resources
[75]. Thus, prefetching in CDNs exposes two difficult challenges that can be
addressed by the following questions:

  * •

What items should be prefetched, considering the large volume of video content
residing on video streaming platforms (e.g., Netflix) and millions of end
users connected to thousands of edge devices?; a question that is similar to
what items to suggest to end users by recommendation systems.

  * •

And, when a prefetching action should occur?; prefetching items very
frequently indicates more eviction actions to be taken by the edge network
which increases cache pollution, network traffic, and server load at the cloud
network, hence, reducing the overall system performance. On the other hand,
prefetching items on rare occasions reduces the prefetching coverage and
accuracy, since content prefetching is a time-sensitive subject.

We propose, DeePref, a deep reinforcement learning agent for prefetching video
content from cloud networks to edge networks in CDNs. DeePref is agnostic to
hardware design, operating system, and application where it takes only the
request ID of the user request as input to make future prefetching decisions
online.

In a separate line of research, Reinforcement Learning (RL) [67] has recently
witnessed a tremendous success in games [60, 70] as well as in robotics [34,
40]. RL focuses on building agents that interact with an environment to
maximize a cumulative future reward or a long-term reward. The environment or
the problem whom the agent is trying to solve needs to constitute the
Markovian property in order to be modeled as a Markov Decision Process (MDP)
[52], as in Def. (2.1). Unfortunately, many real-world problems do not
directly exhibit the Markovian property and/or the agent can only partially
observe the underlying states of the environment, prohibiting it from
discovering the true states of the environment. Thus, a generalization of MDPs
is called Partially Observable Markov Decision Processes (POMDPs) allow us to
learn decision policies if it’s assumed that the underlying environment is
Markovian (e.g., MDP). In this direction, we frame the prefetching problem as
an MDP, as in Def. (2.1) and investigate different design and implementation
approaches to learn prefetching policies in CDNs where possible transfer
learning can occur from one edge network into another.

######  Definition 2.1.

Markov Decision Process or MDP is defined as a tuple
$M:=(S,A,P,R,\rho_{0},\gamma$). Where $S$ is the state space, $A$ is the
action space, and $P$ is the transition function from state $s$ to state
$s^{{}^{\prime}}$ after taking an action $a$, that is
($s\xrightarrow[]{a}s^{{}^{\prime}}$). The reward function $R:S\times A\times
S\rightarrow\mathcal{R}$ is a random variable representing the reward after
transitioning from one state to another and observing a reward
$R_{t}=R(S_{t},A_{t},S_{t+1})$, $\rho_{0}$ is the initial state distribution,
and $\gamma\in[0,1]$ is the discount factor that trades off the instantaneous
and future rewards.

##  3 System Architecture

Figure 3: DeePref System Architecture.

We design, DeePref, such that a prefetching decision is made at edge networks
every time a user request is received from access networks. Consequently, the
prefetching requests are synchronous to user requests as shown in DeePref
architecture, see Fig.3. We also eliminate the cache manager from the cache
management system and allow the prefetch manager to accomplish prefetching
tasks only, unlike other approaches such as IPAC [41]. We use LRU for cache
eviction when comparing DeePref to baselines approaches unless otherwise
mentioned.

Further, the set of video content residing at content servers in cloud
networks can be thought of as a set of actions the prefetcher can take at edge
networks. Therefore, we add a new action which is the "do-not-prefetch” action
in order to tolerate the aggressiveness of our approach. In fact, our results
show that DeePref is more moderate compared to baselines, as discussed in
Sec.5.2. Moreover, we assume that the cloud network periodically updates the
edge network with newly added video content to accommodate for prefetching
new/unseen items. We also assume that the connection between the cloud network
and edge network is the bottleneck considering the limited bandwidth in the
upstream network. In other words, we assume that the Round Trip Time (RTT) of
edge-cloud network is much larger than RTT of access-edge network.

DeePref prefetches video content at the same bit-rate since there is high
probability (> 0.83) that a video player residing at the end user side will
send the next request with the same bit-rate as the current request [41]
because the video play avoids frequent bit-rate changes which degrades the QoE
at the end user side [18, 28].

##  4 Learning Prefetching Policies On Edge

In its most abstract setting, RL aims to find an optimal policy for an agent
sequentially interacting with an environment over a sequence of time-steps,
$\mathit{t=1,2,3,...,}$. The agent executes actions and receives observations
and rewards, and the aim is to maximize the future cumulative reward [55].
Value-based approaches such as Q-learning [78] and policy-based ones (policy-
gradient) such as REINFORCE [79] constitute classification approaches to solve
RL problems [67]. Value-based approaches present many advantages such as
seamless off-policy learning and better sampling efficiency compared to
policy-gradient methods, however, they are prone to learning instability when
mixed with function approximation [69]. Although policy convergence in value-
based methods is not well-studied, the emergence of deep learning [39] has
empowered the recent success of many value-based methods such as Deep
Q-networks (DQN) [45] and DRQN [45].

In this work, we follow the norm of decoupling the functionality of the
underlying cache management system from the prefetching head, and we eliminate
the cache management system which allows only the prefetching head to make
prefetching decisions, as shown in Fig.3. Further, we use Least Recently Used
(LRU) as a unified eviction algorithm when comparing prefetching policies,
unless otherwise mentioned. We also assume no partial prefetching when making
prefetching decisions since prefetching successive video content by means of
partial prefetching may leave many prefetched blocks inaccessible, which
increases the prefetching pollution. Our work considers prefetching one video
content as a whole and the aim is to maximize both prefetching accuracy and
prefetching coverage at the edge node by prefetching video content that have
the highest likelihood to be accessed by end users since each video content
may be accessed at least once [23, 84].

Figure 4: Learning Local prefetching policies on edge networks.

###  4.1 Large State And Action Space

If we decide to prefetch one video content naively from the cloud network to
an edge network, the problem of prefetching can be thought of as selecting one
of the available video content among all content residing on the cloud
network. Thus, we can model the prefetching problem as a Markov Decision
Process (MDP) [52] as in Definition, 2.1, which is a tuple $(S,A,P,R,\gamma)$.
Where $S$ is the state space, $A$ is the action space, $P$ is the transition
function, $R$ is the reward function, and $\gamma$ is the discount factor
$\gamma\in[0,1]$. Consequently, we can construct the underlying MDP as
follows.

  * •

_State Space:_ Let $S=\\{s_{1},s_{2},...,s_{t},...,s_{T}\\}$ denote the state
space. Such that the current state at time step $t$ can be represented as:
$s_{t}=\\{m_{1},m_{2},\dots,m_{i},m_{M}\\}\in\mathbb{R}^{C_{e}}$ where
$m_{i}\in M$, $M$ is the total number of video content residing at the cloud
network, and $C_{e}$ is the storage capacity at the edge node $e$.

Intuitively, the state dimensions/space can be expressed through the following
equation:

$\mid S\mid=\binom{M}{C_{e}},$ (1)

  * •

_Action Space:_ Let $A=\\{a_{1},a_{2},...,a_{t},...,a_{T}\\}$ denote the
action space. Where $a_{t}$ is the prefetching action to be taken by the cloud
device at time step $t$. The cloud device can make the following possible
prefetching decisions:

    1. 1.

_Prefetch one video content:_ The edge node will choose to prefetch one video
content among the available $M$ video content located at the cloud.

    2. 2.

_No prefetching action required:_ The edge node $E$ can decide not to prefetch
at all. Consequently, there will be no eviction of items taken at the edge
node $E$.

Consequently, the action space can be expressed as follows.

$\mid A\mid=\binom{M}{1}+1,$ (2)

  * •

_Transition Function:_ At time step $t+1$, the system state transitions to
another state after taking an action where the transition probability can be
given by the following equation:

$P(s_{t+1}\mid s_{t},a_{t})=P(m\textsuperscript{e}_{t+1}\mid
m_{t}\textsuperscript{e},a_{t}),$ (3)

Thus, the system’s state/action space can be expressed as follows:

$\mid S\mid\cdot\mid A\mid=(\binom{M}{1}+1)\cdot\binom{M}{C_{e}},$ (4)

Where $M$ is the total number of video content residing at the cloud network,
and $C_{e}$ is the storage capacity at edge network, such that $M\gg C_{e}$.
The state space (e.g., how many possible combinations of item that can reside
at edge network is given by $\mid S\mid=\binom{M}{C_{e}}$, and the action
space is $\mid A\mid=\binom{M}{1}+1$ (e.g., selecting one video content to
prefetch or decide not to prefetch at all).

Naturally, the prefetching problem suffers from large state space and action
space and deriving an optimal prefetching policy is tricky since the action
space is non-stationary and items are continuously added to the cloud network
(e.g., continuous action space). Moreover, an optimal prefetching policy
differs from an optimal caching policy such that in prefetching the item
selection is not constrained to the set of items that had been previously seen
(e.g., cached) by edge networks, rather, an optimal prefetching policy needs
to consider/predict any item to be requested despite how many times it had
been requested before. Unlike caching, where an optimal policy can be derived
by selecting one of the items that had been previously cached before, which
reduces the action space and problem dimensionality.

###  4.2 Reward Design

As mentioned previously, the heart of reinforcement learning is to learn a
reward function to maximize the agent’s future cumulative reward. This
learning mechanism depends heavily on the reward design. In DeePref, we
simplify the reward design as much as possible to entail all aspects of
prefetching in numerical values ranging between $[-2,2]$ based on normalized
latency, $[0,1]$ as described below:

  * •

The agent receives a reward of $2$ if there is a cache hit and the agent
decided not to prefetch. This indicates that the item already resides at edge
and had been prefetched before.

  * •

The agent receives a reward of $2-l_{i}$ if there is a cache hit and the agent
decided to prefetch an item $i$ with latency $l_{i}$.

  * •

The agent receives a reward of $-1$ if there is a cache miss and the agent
decided not to prefetch.

  * •

The agent receives a reward of $-1-l_{i}$ if there is a cache miss and the
agent decided to prefetch an item $i$ with latency $l_{i}$.

The goal of a single agent Reinforcement Learning (RL) is to solve the
underlying MDP by finding a policy $\pi:S\rightarrow\Delta(A)$, a mapping from
the state space $S$ to a distribution over the action space $A$, so that
$a_{t}\sim\pi(\cdot|s_{t})$ and maximizing the return $G$. The return is the
discounted accumulated reward, that is,
$G_{t}=\sum_{t=0}^{\infty}\gamma^{t}R(s_{t},a_{t},s_{t+1})$. We can define a
value function $V(s)$ Eq. (5) or action-value function $Q(s,a)$ Eq. (6) under
policy $\pi$ as follows:

$V(s):=E[G_{t}\mid S_{t}=s],$ (5) $Q(s,a):=E[G_{t}\mid S_{t}=s,A_{t}=a],$ (6)

In Reinforcement Learning (RL), we usually use methods of Dynamic Programming
(DP) [52], to maximize the return $G_{t}$ by calculating a value function
$V(s)$ or the action-value function $Q(s,a)$ when using policy $\pi$. The
computations carried in this procedure to approximate an optimal policy
$\pi^{*}$ is called policy improvement and policy evaluation [68] where we
typically use value-based methods or policy-based methods such as Temporal
Difference (TD) learning algorithms [70, 71, 68] which have convergence
guarantees under some conditions. For example, Q-learning [78] is an off-
policy TD learning algorithm that may converge to an optimal policy $\pi^{*}$
by performing the following update rule

$Q_{t+1}(s,a)\leftarrow(1-\alpha)Q_{t}(s,a)+\alpha[r+\gamma\max_{a^{{}^{\prime}}}Q(s^{{}^{\prime}},a^{{}^{\prime}})],$
(7)

where $\alpha$ is the learning rate and $r$ is the reward received upon taking
action $a$ from state $s$. We usually derive a new policy $\pi^{{}^{\prime}}$
which is greedy with respect to $Q^{\pi}(s,a)$, that is, ${\pi^{{}^{\prime}}}$
$\in$ $argmax_{a}Q^{\pi}(s,a)$. The new policy $pi^{{}^{\prime}}$ is
guaranteed to be at least as good as policy $\pi$. Q-learning convergence and
performance guarantees leading to an optimal policy $\pi^{*}$ is studied in
[78, 67].

Using DQN, we use a history of one-hot encoded user requests concatenated with
a binary indicator vector representing edge items as input for DQN. Fig. 5
shows DeePref DQN architecture which consists of an input layer that outputs
512 neurons fully connected to an intermediate layer which outputs 512 neurons
to the output layer which outputs the $Q(s,a)$ for each possible action $a$
being in state $s$.

Figure 5: DeePref DQN Architecture

DQN architecture does not capture the inter-sample dependencies across user
requests since the input of DQN is a concatenation of user requests mimicking
request history, which only captures spatial dependencies across samples.
Therefore, we utilize Deep Recurrent Q-Network (DRQN) which uses Recurrent
Neural Networks (RNNs) such as Long Short-Term Memory (LSTM) [26] and Gated
Recurrent Unit (GRU) [15] to counter the partial observability of the received
user requests and to account for inter-sample dependencies across user
requests which capture short-long term (temporal) dependencies of the
previously seen samples (i.e., user requests). Thus, there is no need to
encode user requests history as one-hot encoded as in the case of DQN.
Instead, It suffices to only encode the currently requested content as one-hot
encoded, since DRQN will be able to handle the inter-sample dependencies
across user requests. Further, we append to the one hot encoded user request a
binary indicator vector representing items at edge network. Afterward, the
input is fed to a linear body as an input layer of size 512 followed by LSTM
acting as RNN which is connected to an output layer where each neuron on the
output layer represents the $Q(s,a)$ of each possible action $a$ being in
state $s$. DeePref DRQN architecture is shown in Fig. 6.

Figure 6: DeePref DRQN Architecture

Moreover, DRQNs suffer from slowness during training when dealing with large
sequences (i.e., large time-steps); therefore, we used Truncated Back
Propagation Through Time (TBPTT) with $k_{1}=k_{2}=300$ where $k_{1}$ is the
number of forward-pass time-steps between LSTM updates, and $k_{2}$ is the
number of time-steps to which we apply Back Propagation Through Time (BPTT).

##  5 Experiment Design

Figure 7: Average episodic reward during training phase

Edge Capacity | EC = 10 |  |  |  | EC = 50 |  |  |  | EC = 100 |  |  |
---|---|---|---|---|---|---|---|---|---|---|---|---
Metric | Acc. | Cov. | Timeliness | Aggr. | Acc. | Cov. | Timeliness | Aggr. | Acc. | Cov. | Timeliness | Aggr.
Belady-Prefetch | 0.99 | 0.99 | $0.03\pm{0.19}$ | 0.99 | 0.99 | 0.99 | $20.39\pm{39.54}$ | 0.99 | 0.99 | 0.99 | $44.21\pm{60.79}$ | 0.99
Top-k Popularity | 0.3 | 0.085 | $127.1\pm{61.74}$ | 0.05 | 0.5 | 0.27 | $108.64\pm{47.24}$ | 0.25 | 0.72 | 0.46 | $83.83\pm{24.97}$ | 0.5
Top-k Size | 0.2 | 0.01 | $183.25\pm{35.55}$ | 0.05 | 0.22 | 0.05 | $175.35\pm{38.98}$ | 0.25 | 0.27 | 0.13 | $155.43\pm{43.07}$ | 0.5
Popularity Recent | 0.1 | 0.1 | $8.28\pm{3.25}$ | 1.0 | 0.26 | 0.26 | $28.18\pm{19.3}$ | 0.99 | 0.52 | 0.5 | $33.16\pm{23.77}$ | 0.97
Popularity All | 0.1 | 0.1 | $8.08\pm{3.39}$ | 0.97 | 0.23 | 0.23 | $31.59\pm{18.95}$ | 0.99 | 0.48 | 0.46 | $35.86\pm{27.48}$ | 0.96
DeePref DQN | 0.42 | 0.15 | $98.0\pm{56.21}$ | 0.71 | 0.56 | 0.27 | $80.11\pm{47.37}$ | 0.73 | 0.76 | 0.56 | $66.81\pm{38.88}$ | 0.76
DeePref DRQN | 0.67 | 0.37 | $69\pm{54.56}$ | 0.5 | 0.76 | 0.58 | $83.3\pm{50.9}$ | 0.67 | 0.89 | 0.74 | $70.64\pm{38.37}$ | 0.82

Table 1: Testing Results on Edge ID = 1

###  5.1 Dataset

Figure 8: Silhouette Analysis to determine the number of k (edge nodes) in
k-means clustering

We used the benchmark dataset MovieLens-100K (ml-100k) [25] which is widely
used in the research community to improve recommendation systems.
MovieLens-100k (ml-100k) contains $100,000$ ratings from $943$ users on $1682$
movies. The data were collected over a period of seven months from September
19th, 1997 through April 22nd, 1998. ml-100k contains users’ information such
as age, gender, occupation, and zip code. We extract the longitude and
latitude of each zip code from the US Census dataset and used k-means
clustering to categorize user requests geographically into clusters, where
each cluster represents an edge network. We used the elbow method with
silhouette analysis to determine the number of clusters, as shown in Fig. 8.
We chose $k=3$ as it has one of the lowest silhouette scores, as shown in Fig.
8. In other words, we select the number of agents to be 3 where we train two
agents $(ID=0,ID=1)$ and we leave the third agent ($ID=2$) for transfer
learning.

We calculate the latency of each content to be prefetched from the cloud
network based on the content size. We assign content size randomly and to
calculate the throughput $throughput=\frac{8\times CWND}{RTT}$ (RFC 6349
[17]). We assume Round Trip Time (RTT) to be $100$ ms and the receiver TCP
window size (CWND) of $65536$ B.

Figure 9: Test Results for Edge ID = 1

Edge Capacity | EC = 10 |  |  |  | EC = 50 |  |  |  | EC = 100 |  |  |
---|---|---|---|---|---|---|---|---|---|---|---|---
Metric | Acc. | Cov. | Timeliness | Aggr. | Acc. | Cov. | Timeliness | Aggr. | Acc. | Cov. | Timeliness | Aggr.
Belady-Prefetch | 0.99 | 0.99 | $0.04\pm{0.21}$ | 0.99 | 0.99 | 0.99 | $0.17\pm{0.37}$ | 0.89 | 0.99 | 0.99 | $0.27\pm{0.44}$ | 0.99
Top-k Popularity | 0.23 | 0.05 | $150.2\pm{50.95}$ | 0.05 | 0.36 | 0.2 | $131.76\pm{41.67}$ | 0.25 | 0.42 | 0.34 | $108.99\pm{32.86}$ | 0.5
Top-k Size | 0.0 | 0.0 | $200\pm{0.0}$ | 0.05 | 0.28 | 0.07 | $160.53\pm{53.99}$ | 0.25 | 0.29 | 0.15 | $150.19\pm{43.96}$ | 0.5
Popularity Recent | 0.12 | 0.12 | $7.48\pm{3.39}$ | 0.95 | 0.23 | 0.25 | $29.52\pm{19.53}$ | 0.99 | 0.43 | 0.51 | $34.55\pm{27.46}$ | 0.93
Popularity All | 0.08 | 0.07 | $8.67\pm{3.92}$ | 0.85 | 0.21 | 0.22 | $31.41\pm{19.0}$ | 0.99 | 0.41 | 0.48 | $36.31\pm{28.87}$ | 0.93
DeePref DQN | 0.32 | 0.2 | $102.92\pm{66.88}$ | 0.23 | 0.42 | 0.37 | $84.54\pm{50.04}$ | 0.44 | 0.65 | 0.46 | $70.27\pm{40.36}$ | 0.32
DeePref DRQN | 0.56 | 0.34 | $85.32\pm{49.59}$ | 0.25 | 0.66 | 0.48 | $74.55\pm{47.15}$ | 0.42 | 0.72 | 0.58 | $72\pm{50.36}$ | 0.23

Table 2: Transfer Results of Edge ID = 1 to Edge ID = 2

###  5.2 Results

We trained two agents $(ID=0,ID=1)$ using DeePref DQN and DeePRef DRQN
architectures and compared our testing and transferring results to the
following baseline prefetching algorithms:

  * •

_Belady-Prefetch_ : The edge network will prefetch (fetch) the item that is
currently being requested in case of a cache miss. Once the item is received
from the cloud network, Belady eviction algorithm [8] will be used to evict
the item in which its occurrence happens the furthest. This approach will
serve as an oracle in our experiments.

  * •

_Top-k Popularity_ : The edge network will prefetch Top-k popular video
content that is known to the cloud network. The cloud network periodically
provides a list of top-k popular video content to edge networks based on their
geographical location [5].

  * •

_Top-k Size_ : The edge network will prefetch Top-k largest video content that
is known to the cloud network. The cloud network periodically provides a list
of top-k largest video content to edge networks based on their geographical
location [5].

  * •

_Popularity Recent_ : Using on-edge prefetching, the agent (i.e., edge
network) will prefetch the most popular content using a sliding time window of
24 hours. If the most popular item seen in the past 24 hours already exists at
the edge’s storage, then no item will be prefetched.

  * •

_Popularity All_ : Using on-edge prefetching, the agent (i.e., edge network)
will prefetch the most popular item that has been seen so far since the
beginning of the experiment.

We use the following evaluation metrics to compare DeePref DQN and DRQN
architectures with baselines:

  * •

_Prefetching Accuracy (Precision Ratio)_ : Prefetching Accuracy describes how
precise the prefetching decisions are in terms of sent prefetches. Prefetching
accuracy is also referred to as the precision ratio of prefetching, which is
defined below:

$Accuracy\>(Precision)=\frac{\\#hits}{\\#hits+\\#misses}=\frac{\\#hits}{\\#user\>requests}$
(8)

  * •

_Prefetching Coverage (Recall Ratio)_ : Prefetching Coverage describes the
usefulness of sent prefetches. Prefetching coverage is also referred to as
recall ratio, which is defined in the following equation:

$Coverage\>(Recall)=\frac{\\#used\>prefetches}{\\#sent\>prefetches}$ (9)

  * •

_Prefetching Aggressiveness_ : Prefetching Aggressiveness describes how many
prefetches had been sent throughout the entire experiment. This metric is used
to compare prefetching algorithms when they are achieving similar prefetching
accuracy and coverage and is defined below:

$Aggressiveness=\frac{\\#sent\>prefetches}{\\#hits+\\#misses}=\frac{\\#sent\>prefetches}{\\#user\>requests}$
(10)

  * •

_Prefetching Timeliness_ : Timeliness measures how long the item had been
residing at edge storage before it got evicted. If the item received a cache
hit, its timeliness timer is refreshed. This metric in correlation with
prefetching aggressiveness is important since we are decoupling prefetching
algorithms from eviction algorithms, as stated previously.

We trained two edge networks using DeePref DQN and DeePref DRQN models. Both
trained edge networks, namely: $EdgeID=0$ and $EdgeID=1$ show similar results.
We highlight the results of only $EdgeID=1$ for brevity. As shown in Fig. 7,
DeePref DRQN model clearly outperforms DeePref DQN model during the training
phase in terms of average episodic reward. This can be explained due the fact
that the DRQN agent is equipped with a replay memory in the form of Recurrent
Neural Networks (RNNs) such as LSTMs and GRUs which capture the spatio-
temporal dependencies across input samples (i.e., user requests). We design
the replay memory of DeePref DRQN using both LSTMs and GRUs where both show
comparative results. Moreover, the replay memory is random instead of
sequential since user requests are coming from heterogeneous networks that are
in nature represent a non i.i.d distribution.

More importantly, we address and discuss how well DeePref DQN and DeePref DRQN
models perform on unseen scenarios, namely: 1) testing dataset which consists
of unseen user requests drawn from the same distribution of user requests that
the edge network serves, and 2) transfer dataset which consists of unseen user
requests obtained from a different edge network cluster, that is $EdgeID=2$
since possible transfer learning of statistical model such as DeePref DQN and
DeePref DRQN can occur across edge networks.

As shown in Table 1 and depicted in Fig. 9, the testing results show that both
DeePref DQN and DeePref DRQN architectures outperform traditional prefetching
schemes such as Top-k Popularity and Popularity Recent in terms of prefetching
accuracy and prefetching coverage. DeePref DRQN outperforms baseline
approaches with an increase of at least [$17\%$, $28\%$] in terms of
prefetching accuracy and coverage, respectively. As presented in Table 1, our
results show that more aggressive algorithms tend to have better prefetching
accuracy and coverage since some prefetching algorithms such as Top-k Size may
decide not to prefetch at all, missing $100\%$ of the chances of observing a
prefetch hit. Furthermore, Fig.9 shows that the increase in the Edge Capacity
(EC) increases both prefetching accuracy and coverage.

Furthermore, when transferring DeePref DRQN model from the trained edge (e.g.,
$EdgeID=1$) to an entirely new edge network (e.g., $EdgeID=2$) which
represents a different statistical distribution, our results show similar
improvements compared to baseline approaches. As shown in Table 2, DeePref
DRQN improves both prefetching accuracy and prefetching coverage compared to
baseline approaches with an increase of [$30\%$,$10\%$], respectively.

##  6 Concluding Remarks

We proposed DeePref DRQN, a prefetcher for video prefetching in CDNs. DeePref
is a Deep Reinforcement Learning agent that utilizes the network latency in
terms of punishments and rewards to make prefetching decisions online. DeePref
is a prefetcher that is implemented at edge networks and is agnostic to
hardware design, operating system, and application. Our results show that
DeePref DRQN outperforms baseline approaches in terms of prefetching accuracy
and prefetching coverage. Our results also show that aggressive approaches
tend to have better prefetching accuracy and coverage. DeePref is an auto-
aggressive prefetcher in the sense that it adapts to user requests online
without any changes in the model architecture.

## Acknowledgement

We thank the Research Computing team at the University of South Carolina for
their efforts in making High-Performance Computing (HPC) clusters available
for us to run our experiments.

## References

  * [1] Vijay K Adhikari, Yang Guo, Fang Hao, Volker Hilt, Zhi-Li Zhang, Matteo Varvello, and Moritz Steiner.  Measurement study of netflix, hulu, and a tale of three cdns.  IEEE/ACM Transactions on Networking, 23(6):1984–1997, 2014.
  * [2] Jesús Aguilar-Armijo, Christian Timmerer, and Hermann Hellwagner.  Space: Segment prefetching and caching at the edge for adaptive video streaming.  IEEE Access, 11:21783–21798, 2023.
  * [3] Hasan Al Maruf and Mosharaf Chowdhury.  Effectively prefetching remote memory with leap.  In 2020 USENIX Annual Technical Conference (USENIX ATC 20), pages 843–857, 2020.
  * [4] Jorge Albericio, Rubén Gran, Pablo Ibánez, Víctor Viñals, and Jose María Llabería.  Abs: A low-cost adaptive controller for prefetching in a banked shared last-level cache.  ACM Transactions on Architecture and Code Optimization (TACO), 8(4):1–20, 2012.
  * [5] Nawras Alkassab, Chin-Tser Huang, Yu Chen, Baek-Young Choi, and Sejun Song.  Benefits and schemes of prefetching from cloud to fog networks.  In 2017 IEEE 6th International Conference on Cloud Networking (CloudNet), pages 1–5. IEEE, 2017.
  * [6] Gretta Bartels, Anna Karlin, Darrell Anderson, Jeffrey Chase, Henry Levy, and Geoffrey Voelker.  Potentials and limitations of fault-based markov prefetching for virtual memory pages.  ACM SIGMETRICS Performance Evaluation Review, 27(1):206–207, 1999\.
  * [7] Rasoul Behravesh, Akhila Rao, Daniel F Perez-Ramirez, Davit Harutyunyan, Roberto Riggio, and Magnus Boman.  Machine learning at the mobile edge: The case of dynamic adaptive streaming over http (dash).  IEEE Transactions on Network and Service Management, 19(4):4779–4793, 2022.
  * [8] Laszlo A. Belady.  A study of replacement algorithms for a virtual-storage computer.  IBM Systems journal, 5(2):78–101, 1966.
  * [9] Rahul Bera, Konstantinos Kanellopoulos, Anant Nori, Taha Shahroodi, Sreenivas Subramoney, and Onur Mutlu.  Pythia: A customizable hardware prefetching framework using online reinforcement learning.  In MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture, pages 1121–1137, 2021.
  * [10] Lee Breslau, Pei Cao, Li Fan, Graham Phillips, and Scott Shenker.  Web caching and zipf-like distributions: Evidence and implications.  In IEEE INFOCOM’99. Conference on Computer Communications. Proceedings. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. The Future is Now (Cat. No. 99CH36320), volume 1, pages 126–134. IEEE, 1999.
  * [11] Pei Cao, Edward W Felten, Anna R Karlin, and Kai Li.  A study of integrated prefetching and caching strategies.  ACM SIGMETRICS Performance Evaluation Review, 23(1):188–197, 1995\.
  * [12] Fay Chang and Garth Gibson.  Automatic i/o hint generation through speculative execution.  USENIX, 1999.
  * [13] Tien-Fu Chen and Jean-Loup Baer.  Effective hardware-based data prefetching for high-performance processors.  IEEE transactions on computers, 44(5):609–623, 1995.
  * [14] Ron C Chiang, Ahsen J Uppal, and H Howie Huang.  An adaptive io prefetching approach for virtualized data centers.  IEEE Transactions on Services Computing, 10(3):328–340, 2015.
  * [15] Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio.  Learning phrase representations using rnn encoder-decoder for statistical machine translation.  arXiv preprint arXiv:1406.1078, 2014.
  * [16] VNI Cisco.  Cisco visual networking index: Forecast and trends, 2017–2022.  White Paper, 2018.
  * [17] Barry Constantine, Gilles Forget, Ruediger Geib, and Reinhard Schrage.  Framework for tcp throughput testing.  Technical report, 2011.
  * [18] Nicola Cranley, Philip Perry, and Liam Murphy.  User perception of adapting video quality.  International Journal of Human-Computer Studies, 64(8):637–647, 2006.
  * [19] Michael Ferdman, Cansu Kaynak, and Babak Falsafi.  Proactive instruction fetch.  In Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture, pages 152–162, 2011.
  * [20] Chang Ge, Ning Wang, Gerry Foster, and Mick Wilson.  Toward qoe-assured 4k video-on-demand delivery through mobile edge virtualization with adaptive prefetching.  IEEE Transactions on Multimedia, 19(10):2222–2237, 2017.
  * [21] Binny S Gill and Luis Angel D Bathen.  Amp: Adaptive multi-stream prefetching in a shared cache.  In FAST, volume 7, pages 185–198, 2007.
  * [22] Binny S Gill and Dharmendra S Modha.  Sarc: Sequential prefetching in adaptive replacement cache.  In USENIX Annual Technical Conference, General Track, pages 293–308, 2005.
  * [23] Phillipa Gill, Martin Arlitt, Zongpeng Li, and Anirban Mahanti.  Youtube traffic characterization: a view from the edge.  In Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, pages 15–28, 2007.
  * [24] Yao Guo.  Compiler-assisted hardware-based data prefetching for next generation processors.  University of Massachusetts Amherst, 2007.
  * [25] F Maxwell Harper and Joseph A Konstan.  The movielens datasets: History and context.  Acm transactions on interactive intelligent systems (tiis), 5(4):19, 2016.
  * [26] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  Neural computation, 9(8):1735–1780, 1997.
  * [27] Wen Hu, Jiahui Huang, Zhi Wang, Peng Wang, Kun Yi, Yonggang Wen, Kaiyan Chu, and Lifeng Sun.  Musa: Wi-fi ap-assisted video prefetching via tensor learning.  In 2017 IEEE/ACM 25th International Symposium on Quality of Service (IWQoS), pages 1–6. IEEE, 2017.
  * [28] Junchen Jiang, Vyas Sekar, and Hui Zhang.  Improving fairness, efficiency, and stability in http-based adaptive video streaming with festive.  In Proceedings of the 8th international conference on Emerging networking experiments and technologies, pages 97–108, 2012.
  * [29] Song Jiang, Xiaoning Ding, Feng Chen, Enhua Tan, and Xiaodong Zhang.  Dulo: an effective buffer cache management scheme to exploit both temporal and spatial locality.  In Proceedings of the 4th conference on USENIX Conference on File and Storage Technologies, volume 4, pages 8–8, 2005.
  * [30] Song Jiang, Xiaoning Ding, Yuehai Xu, and Kei Davis.  A prefetching scheme exploiting both data layout and access history on disk.  ACM Transactions on Storage (TOS), 9(3):1–23, 2013.
  * [31] Yongsoo Joo, Junhee Ryu, Sangsoo Park, and Kang G Shin.  $\\{$FAST$\\}$: Quick application launch on $\\{$Solid-State$\\}$ drives.  In 9th USENIX Conference on File and Storage Technologies (FAST 11), 2011.
  * [32] Andreas M Kaplan and Michael Haenlein.  Users of the world, unite! the challenges and opportunities of social media.  Business horizons, 53(1):59–68, 2010.
  * [33] Tracy Kimbrel and Anna R Karlin.  Near-optimal parallel prefetching and caching.  SIAM Journal on computing, 29(4):1051–1082, 2000.
  * [34] Jens Kober, J Andrew Bagnell, and Jan Peters.  Reinforcement learning in robotics: A survey.  The International Journal of Robotics Research, 32(11):1238–1274, 2013.
  * [35] Aasheesh Kolli, Ali Saidi, and Thomas F Wenisch.  Rdip: Return-address-stack directed instruction prefetching.  In 2013 46th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 260–271. IEEE, 2013.
  * [36] Adam Langley et al.  Transport layer security (tls) snap start.  Working Draft, 2010.
  * [37] Adam Langley, Nagendra Modadugu, and Bodo Moeller.  Transport layer security (tls) false start.  Technical report, 2016.
  * [38] Chris Lattner and Vikram Adve.  Automatic pool allocation: improving performance by controlling data structure layout in the heap.  ACM Sigplan Notices, 40(6):129–142, 2005.
  * [39] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  nature, 521(7553):436–444, 2015.
  * [40] Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel.  End-to-end training of deep visuomotor policies.  The Journal of Machine Learning Research, 17(1):1334–1373, 2016\.
  * [41] Ke Liang, Jia Hao, Roger Zimmermann, and David KY Yau.  Integrated prefetching and caching for adaptive video streaming over http: an online approach.  In Proceedings of the 6th ACM Multimedia Systems Conference, pages 142–152. ACM, 2015.
  * [42] Andrew McAfee, Erik Brynjolfsson, Thomas H Davenport, DJ Patil, and Dominic Barton.  Big data: the management revolution.  Harvard business review, 90(10):60–68, 2012.
  * [43] Peter Mell, Tim Grance, et al.  The nist definition of cloud computing.  2011\.
  * [44] Sparsh Mittal.  A survey of recent prefetching techniques for processor caches.  ACM Computing Surveys (CSUR), 49(2):1–35, 2016.
  * [45] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller.  Playing atari with deep reinforcement learning.  arXiv preprint arXiv:1312.5602, 2013.
  * [46] George Pallis and Athena Vakali.  Insight and perspectives for content delivery networks.  Communications of the ACM, 49(1):101–106, 2006.
  * [47] Biswabandan Panda.  Spac: A synergistic prefetcher aggressiveness controller for multi-core systems.  IEEE Transactions on Computers, 65(12):3740–3753, 2016.
  * [48] Biswabandan Panda and Shankar Balachandran.  Caffeine: A utility-driven prefetcher aggressiveness engine for multicores.  ACM Transactions on Architecture and Code Optimization (TACO), 12(3):1–25, 2015.
  * [49] Al-Mukaddim Khan Pathan and Rajkumar Buyya.  A taxonomy and survey of content delivery networks.  Grid Computing and Distributed Systems Laboratory, University of Melbourne, Technical Report, 4:70, 2007.
  * [50] R Hugo Patterson, Garth A Gibson, Eka Ginting, Daniel Stodolsky, and Jim Zelenka.  Informed prefetching and caching.  In Proceedings of the fifteenth ACM symposium on Operating systems principles, pages 79–95, 1995.
  * [51] Leeor Peled, Shie Mannor, Uri Weiser, and Yoav Etsion.  Semantic locality and context-based prefetching using reinforcement learning.  In 2015 ACM/IEEE 42nd Annual International Symposium on Computer Architecture (ISCA), pages 285–297. IEEE, 2015.
  * [52] Martin L Puterman.  Markov decision processes: discrete stochastic dynamic programming.  John Wiley & Sons, 2014.
  * [53] Rodric M Rabbah, Hariharan Sandanagobalane, Mongkol Ekpanyapong, and Weng-Fai Wong.  Compiler orchestrated prefetching via speculation and predication.  ACM SIGARCH Computer Architecture News, 32(5):189–198, 2004.
  * [54] Bhaskar Prasad Rimal, Eunmi Choi, and Ian Lumb.  A taxonomy and survey of cloud computing systems.  In 2009 Fifth International Joint Conference on INC, IMS and IDC, pages 44–51. Ieee, 2009.
  * [55] Stuart Russel, Peter Norvig, et al.  Artificial intelligence: a modern approach.  Pearson Education Limited, 2013.
  * [56] Hovav Shacham, Dan Boneh, et al.  Fast-track session establishment for tls.  In NDSS. Citeseer, 2002.
  * [57] Muhammad Zubair Shafiq, Alex X Liu, and Amir R Khakpour.  Revisiting caching in content delivery networks.  In The 2014 ACM international conference on Measurement and modeling of computer systems, pages 567–568, 2014.
  * [58] Eht E Sham and Deo Prakash Vidyarthi.  Intelligent admission control manager for fog-integrated cloud: A hybrid machine learning approach.  Concurrency and Computation: Practice and Experience, page e6687, 2021.
  * [59] Weisong Shi, Jie Cao, Quan Zhang, Youhuizi Li, and Lanyu Xu.  Edge computing: Vision and challenges.  IEEE Internet of Things Journal, 3(5):637–646, 2016.
  * [60] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al.  Mastering the game of go with deep neural networks and tree search.  nature, 529(7587):484–489, 2016.
  * [61] Gokul Soundararajan, Madalin Mihailescu, and Cristiana Amza.  $\\{$Context-Aware$\\}$ prefetching at the storage server.  In 2008 USENIX Annual Technical Conference (USENIX ATC 08), 2008\.
  * [62] Emily Stark, Lin-Shung Huang, Dinesh Israni, Collin Jackson, and Dan Boneh.  The case for prefetching and prevalidating tls server certificates.  In NDSS, volume 12, 2012.
  * [63] Jim Summers, Tim Brecht, Derek Eager, and Alex Gutarin.  Characterizing the workload of a netflix streaming video server.  In 2016 IEEE International Symposium on Workload Characterization (IISWC), pages 1–12. IEEE, 2016.
  * [64] Jim Summers, Tim Brecht, Derek Eager, Tyler Szepesi, Ben Cassell, and Bernard Wong.  Automated control of aggressive prefetching for http streaming video servers.  In Proceedings of International Conference on Systems and Storage, pages 1–11, 2014.
  * [65] Jim Summers, Tim Brecht, Derek Eager, and Bernard Wong.  Methodologies for generating http streaming video workloads to evaluate web server performance.  In Proceedings of the 5th Annual International Systems and Storage Conference, pages 1–12, 2012.
  * [66] Gongjin Sun, Junjie Shen, and Alexander V Veidenbaum.  Combining prefetch control and cache partitioning to improve multicore performance.  In 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 953–962. IEEE, 2019.
  * [67] Richard S Sutton and Andrew G Barto.  Reinforcement learning: An introduction.  MIT press, 2018.
  * [68] Richard S Sutton, Andrew G Barto, et al.  Introduction to reinforcement learning, volume 2.  MIT press Cambridge, 1998.
  * [69] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour.  Policy gradient methods for reinforcement learning with function approximation.  Advances in neural information processing systems, 12:1057–1063, 1999.
  * [70] Gerald Tesauro.  Temporal difference learning and td-gammon.  Communications of the ACM, 38(3):58–68, 1995.
  * [71] John N Tsitsiklis and Benjamin Van Roy.  Analysis of temporal-diffference learning with function approximation.  In Advances in neural information processing systems, pages 1075–1081, 1997.
  * [72] Steve VanDeBogart, Christopher Frost, and Eddie Kohler.  Reducing seek overhead with application-directed prefetching.  In USENIX Annual Technical Conference, 2009.
  * [73] Steven P Vander Wiel and David J Lilja.  When caches aren’t enough: Data prefetching techniques.  Computer, 30(7):23–30, 1997.
  * [74] Steven P Vander Wiel and David J Lilja.  A compiler-assisted data prefetch controller.  In Proceedings 1999 IEEE International Conference on Computer Design: VLSI in Computers and Processors (Cat. No. 99CB37040), pages 372–377. IEEE, 1999.
  * [75] Arun Venkataramani, Praveen Yalagandula, Ravindranath Kokku, Sadia Sharif, and Mike Dahlin.  The potential costs and benefits of long-term prefetching for content distribution.  Computer Communications, 25(4):367–375, 2002.
  * [76] Geoffrey M Voelker, Eric J Anderson, Tracy Kimbrel, Michael J Feeley, Jeffrey S Chase, Anna R Karlin, and Henry M Levy.  Implementing cooperative prefetching and caching in a globally-managed memory system.  In Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, pages 33–43, 1998\.
  * [77] Carl A Waldspurger, Nohhyun Park, Alexander Garthwaite, and Irfan Ahmad.  Efficient $\\{$MRC$\\}$ construction with $\\{$SHARDS$\\}$.  In 13th USENIX Conference on File and Storage Technologies (FAST 15), pages 95–110, 2015.
  * [78] Christopher JCH Watkins and Peter Dayan.  Q-learning.  Machine learning, 8(3-4):279–292, 1992.
  * [79] Ronald J Williams.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  Machine learning, 8(3-4):229–256, 1992.
  * [80] Hao Wu, Youlong Luo, and Chunlin Li.  Optimization of heat-based cache replacement in edge computing system.  The Journal of Supercomputing, 77:2268–2301, 2021.
  * [81] Juncheng Yang, Reza Karimi, Trausti Sæmundsson, Avani Wildani, and Ymir Vigfusson.  Mithril: mining sporadic associations for cache prefetching.  In Proceedings of the 2017 Symposium on Cloud Computing, pages 66–79, 2017.
  * [82] Suli Yang, Kiran Srinivasan, Kishore Udayashankar, Swetha Krishnan, Jingxin Feng, Yupu Zhang, Andrea C Arpaci-Dusseau, and Remzi H Arpaci-Dusseau.  Tombolo: Performance enhancements for cloud storage gateways.  In 2016 32nd Symposium on Mass Storage Systems and Technologies (MSST), pages 1–14. IEEE, 2016.
  * [83] Dongjie Zhu, Haiwen Du, Yundong Sun, and Zhaoshuo Tian.  Ctdgm: A data grouping model based on cache transaction for unstructured data storage systems.  arXiv preprint arXiv:2009.14414, 2020.
  * [84] Michael Zink, Kyoungwon Suh, Yu Gu, and Jim Kurose.  Characteristics of youtube network traffic at a campus network–measurements, models, and implications.  Computer networks, 53(4):501–514, 2009.
  * [85] Daniel F Zucker, Ruby B Lee, and Michael J Flynn.  Hardware and software cache prefetching techniques for mpeg benchmarks.  IEEE Transactions on Circuits and Systems for Video Technology, 10(5):782–796, 2000.

##  Appendix A Appendix

###  A.1 LSTM Equations

We list LSTM equations below for completeness:

$i_{t}=\sigma(w_{i}[h_{t-1},x_{t}]+b_{i}),$ (11)
$f_{t}=\sigma(w_{f}[h_{t-1},x_{t}]+b_{f}),$ (12)
$o_{t}=\sigma(w_{o}[h_{t-1},x_{t}]+b_{o}),$ (13)

$\hat{c}_{t}=tanh(w_{c}[h_{t-1},x_{t}]+b_{c}),$ (14)
$c_{t}=f_{t}*c_{t-1}+i_{t}*\hat{c}_{t},$ (15) $h_{t}=o_{t}*tanh(c_{t}),$ (16)

Where $x_{t}$ is the input, $h_{t-1}$ is the hidden state at time-step $t-1$,
$i_{t}$ is the input gate, $f_{t}$ is the forget gate, and $o_{t}$ is the
output gate. The weights for the input gate $i_{t}$, forget gate $f_{t}$, and
the output gate $o_{t}$ are noted as $w_{i},w_{f},w_{o}$, respectively.
Similarly, the biases for these gates are noted as $b_{i},b_{f},b_{o}$,
respectively. Where $c_{t}$ is the cell state at time-step $t$, $\hat{c}_{t}$
is the candidate cell state at time-step $t$, and $\sigma$ is the sigmoid
activation function.