# Scheduling Inference Workloads on Distributed Edge Clusters with
Reinforcement Learning

Gabriele Castellano, Flavio Esposito and Fulvio Risso G. Castellano and F.
Risso are with the Department of Control and Computer Engineering, Politecnico
di Torino, Italy<EMAIL_ADDRESS><EMAIL_ADDRESS>Esposito is with the Computer Science Department at Saint Louis University,
USA<EMAIL_ADDRESS>Gabriele Castellano21, Juan-José Nieto 34, Jordi
Luque 3, Ferrán Diego 3, Carlos Segura 3
Diego Perino 3, Flavio Esposito2, Fulvio Risso1, Aravindh Raman 3
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>2Computer Science, Saint Louis University, USA  1Computer and Control
Engineering, Politecnico di Torino, Italy  4Universitat Politècnica de
Catalunya, Spain  3Telefónica Research, Spain

###### Abstract

Many real-time applications (e.g., Augmented/Virtual Reality, cognitive
assistance) rely on Deep Neural Networks (DNNs) to process inference tasks.
Edge computing is considered a key infrastructure to deploy such applications,
as moving computation close to the data sources enables us to meet stringent
latency and throughput requirements. However, the constrained nature of edge
networks poses several additional challenges to the management of inference
workloads: edge clusters can not provide unlimited processing power to DNN
models, and often a trade-off between network and processing time should be
considered when it comes to end-to-end delay requirements. In this paper, we
focus on the problem of scheduling inference queries on DNN models in edge
networks at short timescales (i.e., few milliseconds). By means of
simulations, we analyze several policies in the realistic network settings and
workloads of a large ISP, highlighting the need for a dynamic scheduling
policy that can adapt to network conditions and workloads. We therefore design
ASET, a Reinforcement Learning based scheduling algorithm able to adapt its
decisions according to the system conditions. Our results show that ASET
effectively provides the best performance compared to static policies when
scheduling over a distributed pool of edge resources.

##  I Introduction

In the last years, we have witnessed the growing popularity of applications
leveraging Deep Neural Networks (DNNs), from Augmented/Virtual Reality (AR/VR)
to cognitive assistance or video surveillance. The DNN model training process
typically does not have strict latency constraints and it is performed
_offline_ in well-provisioned centralized data-centers or in a distributed
fashion via, e.g., federated learning [1]. Differently, the DNN inference task
is usually performed _online_ with constraints in terms of accuracy,
throughput, and latency, which may significantly differ across applications.
For instance, services like cognitive assistance require high accuracy but may
tolerate few hundreds of milliseconds latency, while others, like self-driving
cars, have more stringent latency needs (i.e., tens of milliseconds).

††* Gabriele Castellano and Juan-José Nieto contributed equally to this work
during his internship at the Telefónica Research team, in Spring 2020.

Providing an inference service requires to address several challenges to meet
this diverse set of application constraints, e.g., the selection of the
appropriate variant of the model to be used (programming framework, compiler
optimization, batching size, etc.), the processing unit to leverage for the
inference (e.g., GPU, CPU, TPU), and the nodes and resources (e.g., memory,
computing) to be allocated to every application. This requires management at
different timescale. On a short timescale (i.e, milliseconds), a _scheduler_
is in charge of selecting the appropriate computing instance for every new
incoming request to meet its application requirements. This includes not only
the selection of the computation node but also the appropriate model variant
and computation technology. On a longer timescale (i.e., seconds, minutes), an
_orchestrator_ selects the proper model variants to deploy, optimizes their
placement across the nodes, and allocates the appropriate resources to them.
Recent work [2, 3, 4, 5] focused on data centers and proposed DNN inference
workload management for such environments. Further, commercial solutions have
been deployed in recent years [6, 7, 8] by major cloud providers.

Edge computing is considered a key enabler to deploy DNN-based applications
with stringent delay or bandwidth requirements, as it moves computation
capabilities closer to end-users with respect to centralized cloud platforms.
This is especially the case for users connected via mobile access (e.g. 5G).
However, realizing DNN inference at the edge poses several additional
challenges. Edge infrastructures are indeed complex networks composed of
several layers with heterogeneous limited resources and different latencies to
end users [9]. Due to the less availability of resources at edge, multiple
inference models of different capacities should be considered, and end-to-end
delay requirements may lead to considering a trade-off between network delay
and processing time. This differs from centralized cloud platforms, which
usually feature large pools of uniform hardware available in a single location
where DNN models can be scaled up almost indefinitely. For these reasons, the
optimal selection of inference models while scheduling real-time requests at
Edge is still a challenging task. Recent work combined edge computing and deep
learning [10], with a focus on scheduling requests to minimize end-to-end
delay [11] or maximize accuracy [12]. However, none of the existing work
analyzes inference workload optimization taking into account different
application constraints in realistic edge network settings.

In this paper, we focus on the problem of _scheduling_ DNN inference requests
taking into account not only accuracy (i.e., model selection) but also
throughput and latency constraints under realistic edge deployment settings.
First, we model our distributed edge inference system and provide a definition
of the scheduling problem (Section III), also proposing several baseline
static scheduling policies both original and from literature. From evaluating
static policies on a realistic network topology, we observe that a policy that
always performs better does not exist, as different applications may benefit
differently from each scheduling strategy. Based on the insights derived by
this analysis we propose ASET111 In ancient Egyptian mythology, Aset was a
major goddess said to have power over fate itself.  (Adaptive Scheduling of
Edge Tasks), an adaptive scheduling algorithm based on Reinforcement Learning
(Section IV), which dynamically follows system conditions and apps
requirements optimizing its decisions accordingly. We evaluate ASET simulating
three topologies based on the realistic network of a large ISP and using a
pool of reference edge applications (Section V). Our findings show that, while
some static policies are well suited to optimize workloads on cloud-based
topologies, ASET improves performance over any static policy when resources
are distributed across the edge network, effectively increasing the percentage
of successfully handled queries.

##  II Related Work

The provisioning of on-demand inference services has been investigated in
several recent works.

Inference scheduling in data centers. Most of the existing solutions address
the common scenario where inference queries have to be scheduled over the
resources of a Data Center. Some of the main production systems are Tensorflow
Serving [6], Azure ML [7], and Cloud ML [8]. Most scientific works focused on
proposing algorithms and strategies to improve the performance and ease of use
of such cloud inference systems. [2] and [3] address the problem of scheduling
Directed Acyclic Graph (DAGs) tasks with the objective of improving the
throughput; GrandSLAm [2] relies on a prediction model that estimates job
duration, while [3] proposes an efficient RL approach to select the number of
servers to allocate for a given job. Being oriented to a Cloud infrastructure,
none of them takes into account network latency between the servers and their
heterogeneity. In [13] a Model Master manages the dynamic allocation of DNN
models across the servers of a heterogeneous data center based on Azure ML,
and proposes a protocol among servers to forward queries to the correct
destination. Clipper [4] provides a generalization of TensorFlow Serving [6]
to enable the usage of different frameworks. One of the most complete
solutions is provided by INFaaS [5], which focuses on ease of use, providing
transparent scheduling of incoming queries over available model variants, and
autoscaling of deployed models based on load thresholds. However, all the
previous works address the scheduling problem only from the boundaries of a
data center, considering neither (i) network latency, thus becoming no
suitable in scenarios with real-time constraints, nor (ii) resource
constrained clusters, thus failing to address situations where workers cannot
be indefinitely scaled up/out.

Inference offloading. Another related set of works concerns offloading, with a
focus on the end-devices. While offloading has been widely studied in the
literature [14, 15], the specific use case of DNN workload introduces
additional degrees of freedom (e.g., model variant selection and
configuration) that can be exploited for improving optimization over the mere
selection of the task placement. Some recent works [16, 17, 18] provides
intelligent offloading techniques for DNN tasks. DeepDecision [17] addresses
the problem in the particular case of a single device running a single
application; queries are scheduled among a series of local small models
providing different performance/requirements trade-off, and one remote model,
which provides the best performance. On the other hand, LinkShare [18] focuses
on the orthogonal problem of ordering the offloaded requests from multiple
apps on the same device, with the main constraint of network bandwidth. MCDNN
[16] proposes a scheduler to handle queries from multiple applications on the
same device, deciding (i) the model variant to be used and (ii) whether to
offload the inference task or not, seeking average accuracy maximization. Such
decisions are taken considering constraints such as latency requirements,
device energy, cloud monetary budget.

Inference and edge computing. Fewer and more recent are the trends that
combine DNN with edge computing [10], with the aim of overcoming scalability
and latency limitations of cloud computing. The use of edge computing brings
additional challenges deriving from the high resource requirements of DNN
based tasks on less powerful edge compute resources. Despite some issues have
been addressed in recent works [19, 20, 12, 11], edge-oriented solutions for
inference systems are still largely embryonic compared to data center
solutions, with many open challenges. CloudPath [19] focuses on the problem of
data distribution on a hierarchical continuum of computing resources between
edge and cloud. In [20], authors propose an approach to schedule DAGs across
multiple edge servers, seeking minimization of end-to-end latency. However,
the proposed algorithm assumes the possibility to indefinitely allocate new
edge servers when needed, with no geographical restrictions, thus not
addressing the problem of constrained resources at the edge. Other works [12,
11] study the problem of processing data streams from scattered devices,
exploiting the geographically distributed edge/cloud clusters. In particular,
VideoEdge [12] assumes a deployment of cameras generating a known set of video
streams, on which various DNN tasks should be performed. The proposed approach
decides globally the cluster where each stream should be processed, as well as
the model variant to employ and its configuration, considering computation and
network bandwidth as constraints and seeking accuracy maximization. However,
neither processing nor network latencies are taken as constraints, thus making
this approach not suitable for interactive or critical scenarios (e.g.,
virtual reality, autonomous driving, and more). A similar use case is analyzed
in [11], which focuses on minimizing the end-to-end latency processing data
flowing from the edge to the cloud. However, it only considers the problem of
task allocation, missing the possibility to optimize properly selecting model
variants and their configurations.

To the best of our knowledge, none of the existing works on inference serving
systems addresses the problem simultaneously considering (i) end-to-end
latency, accuracy, and throughput constraints, (ii) edge-cloud computing and
multi-cluster deployment, (iii) real-time job dispatching, (iv) optimization
on model variant selection.

##  III Scheduling in edge-cloud infrastructure

In this section, we formally define the problem of scheduling inference tasks
on a distributed edge-cloud infrastructure. Additionally, we describe a set of
static scheduling policies (both original and from literature), that we then
use in Section IV as a baseline for our dynamic scheduling approach.

###  III-A System modeling

Applications and data-streaming sources. We consider a set of sources (e.g.,
end users, IoT devices, vehicles) running a variety of applications (e.g.,
virtual reality, autonomous driving) each relying on one or more DNN inference
tasks. Every application generates queries to be processed, i.e., each query
represents the request to perform a specific inference task $j\in J$ (e.g.,
object detection, speech recognition) on a given input (e.g., a video frame),
where $J$ is the set of inference tasks supported by the system. Since
applications often require more than one query to be processed, we treat
sequential queries as streams (e.g., all the frames captured by an AR
headset). Therefore, each query $q$ belongs to a stream $i\in I$, being $I$
the entire set of streams currently served by the system. Every query of a
stream has a set of requirements such as a maximum end-to-end delay $D^{i}$,
and a minimum required accuracy $A^{i}$. Additionally, every stream $i$ has a
data rate $\rho_{i}$, that is the number of queries submitted each second
(e.g., frame rate), and every query of stream $i$ has an input of size
$\zeta_{i}$ (e.g., frame size). Note that all queries of a stream are for the
same task $j\in J$ with the same requirements.

DNN Models and Variants. Every inference task $j$ can be served using a _Deep
Neural Network model_ $m$ among the set of $M^{j}$ models that are trained for
task $j$. Therefore, the system provides a total of $N_{m}=\sum_{j\in
J}|M^{j}|$ DNN models. Take object detection as an example application. A
model $m$ represents a particular Neural Network architecture with pre-trained
weights (e.g., yolo-v3, ssd-mobilenet-v1), and features a given accuracy
$A_{m}$ (mean average precision - mAP). A model $m$ can be deployed and run
through different setups and underlying hardware (e.g., SSD Mobilenet v1 on
(i) Tensorflow-GPU with batch size 8, or on (ii) Opencv-CPU batch size 1 and 2
replicas, and more), thus obtaining a set $V^{m}$ of different model variants.
A model variant $v$ features a given processing delay $D_{v}$, throughput
capacity $C_{v}$ (i.e., the maximum number of queries it can process per
second), and resource usage $\boldsymbol{r}_{v}\in\mathbb{R}_{+}^{k}$ (e.g.,
in terms of CPU, system memory and GPU memory). Note that the processing delay
may vary based on the size $\zeta_{i}\in\mathbb{R}_{+}$ of the input data,
thus it is a function $D_{v}\colon\mathbb{R}_{+}\to\mathbb{R}_{+}$; with
$D_{v}$ we refer to the time needed to process the maximum input size
supported by the model (analogous considerations hold for the capacity
$C_{v}$).

Network topology and computing clusters. We consider a geographically
distributed cloud-edge infrastructure composed by $N_{\nu}$ computing clusters
(e.g., a centralized data center, a telco regional cloud, an eNodeB) typically
organized in a hierarchical topology. Each cluster potentially provides
different resources. We denote $\boldsymbol{c}_{n}\in\mathbb{R}_{+}^{k}$ the
overall capacity of cluster $n$, with $c_{nk}$ representing the amount of
resource $k\in\mathbb{N}$ available on cluster $n$. Examples of resources
include CPU, system memory and GPU memory.

Model variants are deployed at different computing clusters consuming a
different amount of resources. On a long timescale (i.e., seconds, minutes),
an _orchestrator_ selects the appropriate set of model variants to deploy,
optimizes their placement across the clusters, and allocates the appropriate
resources. Finally, stream sources are connected to a small cluster at the
lower layer of the hierarchy. This can be either the antenna/eNodeB in case of
cellular communication or the home gateway in the fixed access case. Queries
need to be _scheduled_ for processing across model variants available at
different computing clusters to meet application requirements on a short
timescale (i.e., tens of milliseconds). In the following, we provide a
definition of the scheduling problem we tackle in this paper.

Figure 1: The scheduler dispatches streams of queries on available model
variants based on their constraints and geographical position of clusters.

###  III-B Scheduling problem definition

We assume a scheduler is located at the nearest compute cluster available to
existing stream sources, i.e., antenna/eNodeB or the home gateway/central
office in the fixed access case. It follows every stream source is served by a
scheduler $s$ among $N_{s}$ different ones (one per each lower layer cluster).
Each scheduler $s$ has a given average network delay $d_{n}^{s}$ towards each
cluster $n$; we also model the associated delay deviation as
${\sigma}_{n}^{s}$. Note that an additional access delay from the stream
source to the scheduler has to be taken into account (e.g, the radio latency
between a device and the nearest 5G antenna). We denote $\delta_{i}$ the
additional access delay that affects stream $i$. Every scheduler is aware of
each model variant $v$ currently available on each cluster $n$, each with its
current load $L_{vn}(t)$ (measured in terms of incoming queries per
second222Each stream $i$ contributes to the total load as a fraction
$\eta_{v}^{i}$ of its data rate $\rho_{i}$ (named fractional load), based on
the stream data size $\zeta_{i}$.). Based on the current conditions of the
available model variants, for every stream $i$ it serves, a scheduler $s$
decides which model variant $v$ on which cluster $n$ should be used to process
stream $i$.

When scheduling a stream $i$ to the proper model variant/cluster, the
scheduler takes into account application requirements. Specifically, it
considers the stream data size $\zeta_{i}$, its data rate $\rho_{i}$, its bit
rate $b_{i}$, the maximum tolerated end-to-end delay $D^{i}$ and the minimum
required accuracy $A^{i}$, satisfying the following constraints:

(i) the selected model variant $v$ is a valid implementation of task $j$
required by $i$,

$v\in V^{m}\land m\in M^{j};$ (1)

(ii) the load capacity of the chosen model variant is not exceeded,

$L_{vn}(t)+\eta_{v}^{i}\rho_{i}\leq C_{v},$ (2)

being $\eta_{v}^{i}$ the fractional load of stream $i$ for model variant $v$;

(iii) the sum of expected network delay and processing time does not exceed
the maximum tolerated delay,

$2(\delta_{i}+d_{n}^{s}+2{\sigma}_{n}^{s})+b_{i}\zeta_{i}+D_{v}(\zeta_{i})\leq
D^{i},$ (3)

where the first addendum is the round-trip propagation time, the second is the
transmission delay for one query and the third is the time needed to process
the query;

(iv) the selected model provides an adequate accuracy

$A_{m}\geq A^{i}.$ (4)

A graphical representation of the scheduling problem is depicted in Figure 1,
while a scheduling policy can be formally defined as follows.

######  Definition 1.

(scheduling policy). Let us consider a stream $i$ to be processed through a
task $j$ on an edge-cloud infrastructure that features a set of $V^{m}$
compatible model variants over $N_{\nu}$ clusters ($|N|=N_{\nu}$). A
scheduling policy is any function

$\begin{gathered}\mathcal{\beta}\colon I\to V^{m},N\end{gathered}$ (5)

that binds stream $i$ to a feasible model variant $v\in V^{m}$ deployed on
cluster $n\in N$, so that constraints at Equations (1), (2), (3), and (4) are
satisfied.

Note that, as requests are handled in real-time, scheduler decisions should be
taken in an amount of time that is negligible compared to the stream latency
requirements.

Scheduling performance metrics and objectives. Based on the scheduling
decisions, in a given time instant $t$ the stream $i$ will feature a reject
ratio $q_{i}^{R}(t)\in[0,1]$, i.e., the fraction of queries from stream $i$
that have not been processed by the system because of resource unavailability,
and a failure ratio $q_{i}^{F}(t)\in[0,1]$, i.e. the fraction of queries that
have been served violating one or more application requirements (i.e.,
delivered out of maximum tolerated delay).

The goal of the scheduler is typically to maximize, over time, the fraction of
queries that are served successfully, i.e., to minimize the sum of reject
ratio and failure ratio.

###  III-C Static scheduling policies

Several policies have been proposed for static scheduling of inference tasks
on edge clusters [21, 9]. In this work we consider the following ones (both
original and from literature):

1) closest: bind stream $i$ to any feasible model variant $v^{*}$ located on
the cluster $n^{*}$ that features the lower network latency to serving
scheduler $s$, i.e., $n^{*}=\operatorname*{\arg\min}_{n\in
N}{(d_{n}^{s}+2{\sigma}_{n}^{s})}$. This policy may lead to the early
saturation of smaller clusters at the very edge, as they are always preferred
[22].

2) load balancing: bind the input stream to model variant $v^{*}$ on cluster
$n^{*}$ such that $(v^{*},n^{*})=\operatorname*{\arg\min}_{v,n\in V^{m}\times
N}{L_{vn}(t)}$. This policy can bring huge performance gains compared to
closest [22]; however, it may lead to unfair allocation when latency-sensitive
applications are in the minority.

3) farthest: bind stream $i$ to any feasible model variant $v^{*}$ located on
the cluster $n^{*}$ with the highest (still feasible) network latency, i.e.
$n^{*}=\arg\max_{v\in N}{(d_{n}^{s}+2{\sigma}_{n}^{s})}$. As opposed to
closest, this policy preserves smaller clusters at the very edge for those
apps that really need them [23]; however, it is highly affected by the
unreliability of network delay for long distance communications.

4) cheaper: bind stream $i$ to model variant $v^{*}$ on cluster $n^{*}$ such
that the expected end-to-end delay (round-trip and processing time) is
maximized, i.e., $(v^{*},n^{*})=\operatorname*{\arg\min}_{v,n\in V^{m}\times
N}{(2(d_{n}^{s}+2{\sigma}_{n}^{s})+D_{v}(\zeta_{i}))}$. We designed this
policy as an improvement over farthest, as it additionally tries to preserve
the most performing model variants.

5) random-proportional latency: bind stream $i$ to model variant $v$ on
cluster $n$ with probability
$1/(2(d_{n}^{s}+2{\sigma}_{n}^{s})+D_{v}(\zeta_{i}))$. This guarantees that,
on a large enough number of streams, bindings are proportionate to end-to-end
delays [21].

6) random-proportional load: bind stream $i$ to model variant $v$ on cluster
$n$ with probability $C_{v}/L_{vn}(t)$. This guarantees that, on a large
enough number of streams, bindings are proportional to the capacity of each
model variant.

7) least impedance: bind stream $i$ to model variant $v^{*}$ on cluster
$n^{*}$ such that end-to-end latency to $s$ is minimized, i.e.,
$(v^{*},n^{*})=\operatorname*{\arg\min}_{v,n\in V^{m}\times
N}{(2(d_{n}^{s}+2{\sigma}_{n}^{s})+D_{v}(\zeta_{i}))}$ [21]. This greedy
policy leads to the best performance when the overall load is low, but may
suffer from a high rejection rate once the closest and fastest model variants
are saturated.

Our experiments (Section V) show that, for a heterogeneous pool of
applications, a policy that always performs better than the others does not
exists: different applications may benefit differently from each scheduling
strategy, and also the physical topology and the particular streams arrivals
can be determinant. Based on these findings, in the next section we propose
ASET, an algorithm for Adaptive Scheduling of Edge Tasks that leverages
Reinforcement Learning to optimize its decisions dynamically based on the
current system conditions.

##  IV ASET Scheduling Algorithm

Our adaptive scheduling approach aims to learn the optimal policy depending on
current system conditions, e.g, current applications, network topology, and
stream arrivals that vary over time. Due to the lack of labeled data, the
optimal policy learning is formulated as a Reinforcement Learning (RL)
problem; hence, an intelligent agent tries to learn the optimal policy
selection strategy according to the observed state of the environment. This is
accomplished by an RL policy that estimates a probability distribution of each
possible action (policy selection) that cumulatively maximizes a reward
(typically maximizing the fraction of queries that are served successfully),
as shown in Figure 2.

Let us consider a learner and decision-maker called the agent, and an
environment that is the external world that the agent interacts with at
discrete time steps $t$. Given $S_{t}\in S$, where $S$ is the set of possible
states of the environment, the agent can select an action $A_{t}\in A(S_{t})$,
standing for the set of available actions in state $S_{t}$. The agent receives
an observation of the environment $S_{t}$ at time $t$ and, one step later, a
numerical reward, $r_{t+1}\in R\subset\mathbb{R}$, and it jointly determines
the action $A_{t}$ to perform, which, in part, yields to next state $S_{t+1}$.

######  Definition 2.

(stochastic reinforcement learning policy). An RL policy $\pi_{\phi}$, where
$\phi\in\mathbb{R}^{d}$ denotes policy parameters, is any function or
algorithm that determines and maps the next action to take by an agent. A
stochastic RL policy, additionally, estimates a probability distribution over
actions that an agent can take at a given state:

$\displaystyle\pi_{\phi}\colon\>A\,\text{x}\,S\to[0,1],$ (6)
$\displaystyle\pi_{\phi}(a|s)\overset{\mathrm{def}}{=\joinrel=}\mathbb{P}(\text{take
action }a|\text{given state }s).$

Figure 2: Algorithm overview. State $S_{t}$, sampled from the environment, is
forwarded through the agent DNN, which outputs action $A_{t}$; performing
$A_{t}$ on the environment contributes to reward $r_{t+1}$ obtained at the
next step.

Overall, the goal of the proposed adaptive scheduling is to learn an optimal
sequence of static network scheduling policies that maximizes the percentage
of successfully dispatched streams. At a $T$ seconds rate, the RL-based
scheduler samples the environment by collecting a variety of observations from
the edge-cloud infrastructure, e.g., responses and loads, building up the
current state $\mathit{S_{t}}$ of the environment. Then, the agent evaluates a
discrete set $A$ of actions and chooses an action $A_{t}\in A$, where $A$
stands in this work for the set of available network scheduling policies
$\mathcal{\beta}$. Note that the set of actions does not depend on the state
itself, thus the sets $A(S_{t})=A$ are the same (Section III-C). Therefore,
every time that the agent takes an action $\mathit{A_{t}}$, the state of the
environment $\mathit{S_{t}}$ is observed and a reward score $\mathit{r_{t+1}}$
is used as feedback information to improve the policy selection, see Figure 2.
In this work, these rewards are defined as a linear combination of the ratio
of “failed” queries and the ratio of queries that have been “rejected” for
lack of available resources (Section IV-C).

The particular policy $\mathcal{\beta}_{t}$, selected by the agent at time
$t$, is used to dispatch all incoming streams during the subsequent time
window $[t,t+T]$. Therefore, given the corresponding states sequence
$\mathbf{S}=[{S}_{0},{S}_{T},{S}_{2T},...,{S}_{kT}]$ with $k\in\mathbb{N}$,
the resulting overall scheduling policy
$\mathcal{\beta}(\mathbf{S})=[\mathcal{\beta}_{0},\mathcal{\beta}_{T},\mathcal{\beta}_{2T},...,\mathcal{\beta}_{kT}]$
dynamically maps, with the corresponding baseline policies
$\mathcal{\beta}_{t}$, a stream $i$ to a model variant $v$ and its deployment
on cluster $n$. From now, and for the sake of simplicity, we will refer as
$\pi$ to the policy learned by the ASET agent (Definition 2), which leads to a
particular static policy sequence $\mathcal{\beta}(\mathbf{S})$. It
corresponds to any function employed to estimate the optimal sequence of
actions that the agent should perform at each time window $[t,t+T]$ and given
a state $S_{t}$,
$\mathcal{\beta}(\mathbf{S})=[\mathit{A}_{0},\mathit{A}_{T},\mathit{A}_{2T},...,\mathit{A}_{kT}]$.
The intuition of this behavior is provided in Figure 3. Note that each of the
static scheduling policies from Section III-C corresponds to a deterministic
agent that always returns the same action $\mathit{A_{t}}$ independently of
the system state; whereas the policy $\pi$ learned by the ASET agent can be
seen as a meta-policy (or as a policy of baseline scheduling strategies) that
also satisfies the constraints from Equations (1), (2), (3), and (4).

(a) Cloud-based topology.

(b) Edge-based topology.

Figure 3:  The ASET RL agent infers the optimal policy sequence based on the
system conditions, seeking an optimal binding between workloads and model
variants that maximizes the percentage of success queries. Plots show two runs
on a cloud-based topology and on an edge-based one (see Section V).

###  IV-A Deep Q-Learning policy optimization

Our RL agent has to cope with a discrete set of actions, with
$A\subset\mathbb{N}$. This is often modeled in literature as a stochastic
process with no memory, which is a Markov Decision Process [24] (MDP). In this
work, our MDP defined by tuples $(S,A,\mathcal{T},\mathcal{R},\gamma$)
represents states comprised of partial observations from the system.
Nonetheless, the model parameters of such MDP are unknown, i.e., the
transition probabilities ${\mathcal{T}(s^{\prime}|a,s)}$ and the rewards
${\mathcal{R}(s^{\prime}|a,s)}$ of taking the action $A_{t}=a$ and moving from
state ${S_{t}}=s$ to state ${S_{t+1}}=s^{\prime}$. Note that the ASET agent
should experience each transition among states at least once, or even multiple
times to get a reliable estimation of both transition and cumulative rewards.

At each step $t=kT$, with $k\in\mathbb{N}$, the RL agent can choose one of
several possible scheduling policy-actions,
$\mathcal{\beta}_{t}\equiv\mathit{A_{t}}$. The transition probability
$\mathit{\mathcal{T}(s^{\prime}|a,s)}$ depends in part on the chosen action,
and, additionally, from some positive or negative reward that may be returned
by every state transition, named return of actions. Overall, our objective is
to find a strategy, i.e., a policy $\mathcal{\pi}$ mapping to a sequence
$\mathcal{\beta}(\mathbf{S})$, that maximizes the expected return $G(t)$ of
rewards over time. Thus, $G(t)$ is defined in terms of the cumulative weighted
rewards along with states and given the corresponding optimal sequence of
actions to take in the future:

$G(t)=\sum_{\tau=0}^{H}\gamma^{\tau}r_{\tau}\qquad\gamma\in[0,1],$ (7)

where $r_{\tau}={\mathcal{R}(s^{\prime}|a,s)}$ is the reward at time step
$\tau$ due to corresponding state transition $(s,s^{\prime})$, $\gamma$ is a
weighting factor that reduces the contribution of long-term rewards, usually
known as the discount factor, and time $H$ is the last time step within a
training episode (see Section IV-C for further details). Therefore, the RL
agent’s target policy is

$\pi^{*}(a|s)=\operatorname*{\arg\max}_{\pi_{\phi}}\mathbb{E}_{t^{*}\sim\pi_{\phi}}\left\\{G(t)\right\\},$
(8)

which translates the scheduler state into a distribution over actions, see
Definition 2. Note that the expectation is computed over the distribution of
trajectories $t^{*}=(s_{0},a_{0},s_{1},...)$.

In Q-Learning, the optimal pair values $(s,a)$, i.e., those yielding to the
sequence of optimal actions, are generally called Quality-Values (Q-Values)
and noted as $Q^{*}(s,a)$ [25]. They correspond to the sum of weighted rewards
that the RL agent can expect on average after performing action $a$ on state
$s$. It is also known as the expected return of actions,

$Q(s,a)=\mathbb{{E}}_{t^{*}\sim\pi_{\phi}}\left\\{G_{t}|S_{t}=s,A_{t}=a\right\\}.$
(9)

Bellman [24] showed that if an agent’s trajectory follows the highest
Q-Values, then its policy is optimal and leads to the highest $G(t)$ as well.
Bellman also reported that an accurate estimate of Q-Values can be found
recursively by using the Bellman Optimality Equation, also known as the Value
Iteration algorithm. In fact, Q-Learning is an adaptation of Bellman’s value
iteration algorithm, where a policy is implicitly, or off-line, learned by
following trajectories yielding to the highest Q-Values [25]. It is usually
computed by dynamic programming and assumes that the optimal value of state
$S_{t}=s$ is equal to the reward it will get on average, after taking one
optimal action $a$ and adding the expected optimal value of all possible next
states along the future path of decisions, that is
$Q(s,a)=\mathbb{E_{\pi}}\left\\{r+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime})|s,a\right\\}$.
Equation (9) turns out into the following iteration algorithm, which converges
to the optimal $Q^{*}(s,a)$,

$Q_{k+1}(s,a)\leftarrow\sum_{s^{\prime}}\mathcal{T}(s,a,s^{\prime})\big{[}r+\gamma\max_{a^{\prime}}Q_{k}(s^{\prime},a^{\prime})\big{]},$
(10)

for all $s^{\prime}\in S$, $a^{\prime}\in A$ and $k\in\mathbb{N}$ as iteration
step. For simplicity, we set the transition probability matrix $\mathcal{T}$
to all elements equal to $\mathit{1}$, allowing initial transitions among all
seen states. Once Q-Values are estimated, the optimal policy $\pi^{*}$ for the
RL agent corresponds to chose the action that has the highest Q-Values:
$\pi^{*}(a|s)=\operatorname*{\arg\max}_{\pi}Q_{\pi}(s,a)$, for all $s\in S$
and $a\in A\equiv\beta$ static policies in Section III-C.

However, previous algorithm does not scale for large MDPs with a large number
of states. A solution is to approximate the optimal $Q^{*}(s,a)$ using a Deep
Neural Network, named Deep Q-Network (DQN) [26], to get an estimate
$Q(s,a;\phi)\approx Q^{*}(s,a)$, where $\phi$ stands for the parameters of the
DQN model, see line 16 in Algorithm 1. The using of a DQN for approximate
Q-Learning is known as Deep Q-Learning.

###  IV-B State Encoding

We model the state in a continuous fashion, representing the environment in a
given time $t$ as a set of some particular features sampled from the system
and averaged along a time window of size $T$. Features are evaluated
separately for each available worker $w\in W$,333A worker is a model variant
instance $v$ running on a particular cluster $n$, therefore we can assume
index $w=n\cdot v+v$. and are as follows: (i) the number $|I_{w}|$ of streams
currently served by worker $w$, being $I_{w}=\\{i\in I|~{}\beta(i)=(v,n)\\}$;
(ii) the current throughput $R_{w}(t)$ of worker $w$, in terms of responses
delivered at the time instant $t$; (iii) the current load $L_{w}(t)$, measured
in terms queries per second normalized on input size (as defined in Section
III-B); (iv) number of incoming instant queries grouped by stream
characteristics, e.g., queries of all streams that require end-to-end delay
within a given range $[\delta^{1},\delta^{2}[$ and features a data rate in the
interval $[\rho^{4},+\infty[$, i.e., $\sum_{i\in I_{1,4}}\rho_{i}$, where
$I_{1,4}=\\{i\in
I|~{}D^{i}\in[\delta^{1},\delta^{2}[\land\rho_{i}\in[\rho^{4},+\infty[\\}$. In
particular, we consider a partition
$0=\delta^{0}<\delta^{1}<\delta^{2}<...<\delta^{N_{\delta}-1}$ of
$\mathbb{R}_{+}$ with $N_{\delta}$ delay intervals, and a second partition
$0=\rho^{0}<\rho^{1}<\rho^{2}<...<\rho^{N_{\rho}-1}$ of $\mathbb{R}_{+}$ with
$N_{\rho}$ input-rate intervals, evaluating $N_{\delta}\cdot N_{\rho}$
different sum of instant queries, that is one feature for each combination of
the two partitioning sets. The features defined so far constitute a vector as,

$\begin{gathered}\boldsymbol{S}_{w,t}=\Bigg{[}|I_{w}|,R_{w}(t),L_{w}(t),\sum_{i\in
I_{0,0}}\rho_{i},\dots,\smashoperator[l]{\sum_{i\in
I_{N_{\delta}-1,N_{\rho}-1}}^{}}\rho_{i}\Bigg{]}\end{gathered}$ (11)

where $\boldsymbol{S}_{w,t}\in\mathbb{R}_{+}^{3+N_{\delta}\cdot N_{\rho}}$.
Therefore, the complete state $\boldsymbol{S}$ is modeled as a three-
dimensional vector in $\mathbb{R}_{+}^{(3+N_{\delta}\cdot
N_{\rho})\times|W|\times T}$, that is, each feature in (11) is first evaluated
for each available worker (each model variant on each node), and then for each
time instant within the considered time window. For instance, vector
$\boldsymbol{S}_{w}$ stores, for worker $w$, every features in (11) evaluated
at every time instant $t-T+1$, $t-T+2$, …, $t$ within time window $[t-T+1,t]$.
From now, we refer to the state vector encoding as simply $s$ or $s_{t}$ for a
generally speaking state or a state referred to a time window, respectively.

###  IV-C Training

The proposed RL scheduling agent is trained over a series of episodes that
resemble various scenarios. Each episode corresponds to a different workload
execution with given parameters, e.g. requirements from tasks, number of
clients per minute ($\lambda$) or the seed value ($\zeta$) for random number
generation (RNG), and is concluded when the percentage of success queries,
$q^{S}_{t}$, falls below a given threshold $\theta$ or when a timeout $H$ is
reached. This allows us to speed up the training by terminating unsuccessful
or steady episodes quickly. At every time step $t$, a reward $r_{t}$ scores
the rate of successful queries, see Algorithm 1 at lines 9-10, where
$q^{F}_{t}$ is the ratio of “failed” queries, i.e., those delivered violating
one or more constraints (e.g., out of tolerated delay), and $q^{R}_{t}$ is the
ratio of queries “rejected” by the system for lack of resources, normalized by
corresponding time window. $\psi$ is a penalty inverse proportional to the
episode active time. It ensures that both short and bad action trajectories do
not reach higher returns than optimal ones.

Algorithm 1 ASET training procedure

1:initialize replay buffer $D=\emptyset$ ring of size $N_{r}$ and $\phi_{0}$
DQN parameters

2:initialize training RNG seeds $\zeta\in[0,...,P-1]$

3:for episode k $\in[0,...,M]$ do

4: sample random seed $\zeta\sim\mathcal{U}(P)$

5: initialize
$\pi_{k}(a|s)=\epsilon\;\mathcal{U}(\beta)+(1-\epsilon)\delta(a=\operatorname*{\arg\max}_{a}Q(s,a;\phi_{k}))$

6: for step t $\in[0,...,H]$ do

7: sample $a_{t}\sim\pi_{k}(a|s)$

8: sample $s_{t+1}$ state from edge-network and reward $r_{t}$

9: if $\varphi>1-(q^{F}_{t}+q^{R}_{t})$ then $r_{t}=-(q^{F}_{t}+q^{R}_{t})$

10: else $r_{t}=\psi$

11: $D\leftarrow D\cup\\{(s_{t},a_{t},s_{t+1},r_{t})\\}$ with circular
replacement

12: if $q^{S}_{t}\leq\theta$ then $t\leftarrow H$, ends this episode

13: $\phi_{k,0}\leftarrow\phi_{k}$

14: for gradient descend step g $\in[0,...,G-1]$ do

15: sample batch $B\subset D$ with $idx\sim\mathcal{U}(N_{r})$

16: compute $C_{t}\leftarrow
r_{t}+\gamma\operatorname*{\arg\max}_{a_{t+1}}Q(s_{t+1},a(s_{t+1});\phi_{k})$

17: compute loss $L=\sum_{i}(C_{i}-Q(s_{i},a_{i};\phi_{k}))^{2}$

18: update replay network
$\phi_{k,g+1}\leftarrow\phi_{k,g}-\alpha\nabla_{\phi_{k,g}}L$

19: update DQN parameters $\phi_{k+1}\leftarrow\phi_{k,G}$

Note that DQN network is used to minimize the target loss L, see lines 14-18,
by Adam optimizer and $\alpha$ learning rate. It takes gradient steps on the
Bellman error objective L, see factor $C$ at line 16 and Eq. (10),
concurrently with data collection from the replay buffer [27] for an efficient
off-line learning. This is a common hybrid approach to implement Q-Learning
[28, 29, 25]. Additionally, we employ an $\epsilon$-greedy exploration policy,
see line 5, with parameter $\epsilon$ dynamically updated. The architecture of
our DQN consists of a stacking of convolutional layers that extracts temporal
correlations from the state tensor $\mathbf{S}$. Such feature extraction part
is composed of three convolutional layers with 4x4 kernels along the time and
feature dimensions, followed by Re-Lu activation and max-pooling. Finally, two
linear layers squeeze the dimension from 256 to as many outputs as different
static policies $\beta$.

##  V Performance evaluation

We evaluate ASET using a prototype implementation of an edge inference system
that will be released upon acceptance of the paper. We first use our prototype
to run small scale experiments with the aim of profiling some representative
models and their variants (results not shown). Then we use such profiling data
to run large scale experiments on a simulated setup, comparing the performance
of ASET to those of static scheduling policies.

###  V-A Evaluation settings

System Prototype. Our prototype implements the edge inference system
functionalities described in Section III. On each cluster, a Master deploys
workers and routes streams between them and remote clients; each Worker runs
in a Docker container and implements a pipeline that processes queries in FIFO
order from different streams, based on the model variant batch size; a
Monitoring agent on each cluster collects stats from model variants usage and
their performance, used (i) to build a catalog of model variants and (ii) to
provide each Scheduler with aggregated observations on the system state. We
use such a prototype to profile variants of pre-trained inference models with
respect to their resource usage and performance (see below).

Simulation Setup. To evaluate our approach on a large scale, we set up a
simulated environment where each worker simulates the inference task based on
the profiling information available for its model variant. Therefore, empty
responses are generated for each batch of queries after simulating a
processing delay (based on a normal distribution). Additionally, we simulate
network delay between stream sources and destination clusters (see below for
considerations on the network topologies), as well as the transmission delay.
Apart from simulated workers, other system components are deployed using their
prototype implementation. Therefore, the system operates on a realistic
timescale.

Network topology. We leverage the network topology of a large ISP to assess
scheduling performance under realistic settings. Specifically, our simulated
environment is a cloud-to-edge topology with clusters of different sizes
deployed hierarchically. To preserve ISP confidentiality, we only report a
high-level summary of topology, latency, and hardware distribution
characteristics. Similarly to the tiered topologies from [30, 31], our
topology can provide clusters with computation capabilities at different
layers: network access (e.g., antennas, home gateway), central offices
(multiple payers), operator data center, and remote cloud (third parties).
Specifically, we focus on three scenarios: (i) _dc-cloud_ , where resources
are deployed at ISP data center and remote cloud only; (ii) _co-dc-cloud_ ,
where resources are deployed at central offices, operator data center and
remote cloud; (iii) _full-edge_ topology, where clusters are deployed at all
layers previously mentioned. Note that we limit the simulations to the
topology serving 1,000 antennas from the full ISP topology, and appropriately
scale resources (see below). For the evaluation, we assume a 5G radio access
technology with antennas deployed similarly to LTE. Network/transmission
delays range from few milliseconds, to reach the eNodeBs behind the antennas,
to the order of ten milliseconds for central offices and ISP data centers, and
few tens of milliseconds for the remote cloud.

TABLE I: Characteristics of reference applications [32, 33].

Edge app |  Tolerated |  |  |
---|---|---|---|---
|  Frame |  |  |
|  Streams |  |  |
|  Required |  |  |
| accuracy |  |  |
Pool | 95 ms | 5 FPS | 5-10 s | 10 mAP
Workout Assistant | 300 ms | 2 FPS | 90 s | 10 mAP
Ping-pong | 150 ms | 15-20 FPS | 20-40 s | 15 mAP
Face Assistant | 370 ms | 5 FPS | 1-5 s | 30 mAP
Lego/Draw/Sandwich | 600 ms | 10-15 FPS | 60 s | 25 mAP
Gaming | 20-30 ms | 25 FPS | 10-30 m | 35 mAP
Connected Cars | 150 ms | 10-15 FPS | 15-30 m | 40 mAP
Tele-Robots | 25-35 ms | 10 FPS | 5 m | 40 mAP
Remote-driving | 20-30 ms | 20 FPS | 15-30 m | 50 mAP
Interactive AR/VR | 30-50 ms | 25 FPS | 30-60 s | 35 mAP

Requests workload. Requests are generated following a Poisson distribution.
Each generator runs on average $\lambda$ clients per minute querying the
scheduler of a given geographical area (antenna). Once spawned, each client
requests for processing a stream featuring randomized characteristics in terms
of frame rate, required end-to-end latency, required model accuracy, frame
sizes, stream duration. To capture realistic queries characteristics, we
modeled metrics of generated streams according to the reference edge
applications in Table V-A. In our settings, a generator with $\lambda$ = 60
brings a load of almost 1000 queries per second on the serving antenna.

Computing clusters and model variant. We assume a given reference hardware
distribution across clusters, with computing capabilities increasing from the
access network to the cloud. Specifically, the access network can be equipped
with an 8-16 cores machine, 16 GB of memory and a small TPU, central offices
can host in the order of tens of servers (32-64 CPUs, 128-256 GB, and few
GPUs), ISP data centers can host hundreds of servers, while for the
centralized cloud we assume unlimited resources. In our evaluation, we focus
on DNN models for the object detection task, as it is one of the most
challenging and computation-intensive inference service [34, 35]. Using our
prototype we profile MobileNet-SSD, Yolo-v3, and Tinyyolo-v2 models [36, 37],
with CPU and GPU variants on different batch sizes, scaling on allocated
resources and number of replicas. Such a set of results is not shown for lack
of space. We use profiled information to run our simulations on top of the
three topologies described above. On each cluster, workers have been scaled on
the number of replicas up to resource saturation.

(d) Average values for episodes with dynamic clients rates.

Figure 4: Success percentage for different apps on the full-edge topology.

###  V-B Experimental Results

We compare the performance of the baseline policies described in Section III-C
distinguishing results for different applications from Table V-A. As a
performance metric we consider the percentage of queries that are successfully
processed by the system satisfying the application QoS requirements. Figure
LABEL:subfig:apps-policies-60 shows results of multiple runs with $\lambda$ =
60. Results suggest that there is no one-size-fits-all policy, as various
applications may benefit differently from each policy. Varying the rate of
stream requests on the antenna (Figure 3(d)) may further increase the
uncertainty of relying on a single policy. In the following, we compare the
performance of the ASET RL scheduling approach with the performance of static
policies, evaluating the benefits it can introduce in the various scenarios.
We trained three different versions of ASET (one for each topology). In
particular, we sample the state using a time window $T$ = 25 seconds, and we
experimentally chose an episode timeout of 8 minutes to avoid steady states in
the network. Despite we evaluate on multiple clients rate, our agent has been
trained only on episodes with $\lambda$ = 60.

(a) Time avg on dc-cloud for $\lambda$ = 60. (c) Time avg on co-dc-cloud for
$\lambda$ = 60. (d) Different clients rate on co-dc-cloud.

Figure 5: Performance of ASET compared with static policies for (ab) the dc-
cloud topology and (cd) the co-dc-cloud topology.

Cloud deployment. When all the available resources are located in a few
centralized clusters, the various static policies have small differences in
performance and a dynamic approach has little room for improvement. Results
for the dc-cloud topology are shown in Figures V-Aab. In particular, Figure
4(a) plots, for every moment of the simulation (time axis), the percentage of
queries that are handled successfully, averaging multiple runs with different
workloads. The graph shows that, for this topology, ASET does not improve over
static policies, and it even performs worse for higher lambdas (Figure
LABEL:subfig:cloud-lambdas). Figures V-Acd shows that moving some resources to
Central Offices (co-dc-cloud topology) makes a huge difference: in general,
all the policies achieve a higher success ratio on this configuration (Figure
4(c)), as they can exploit the additional lower latency spots, and the higher
level of distribution gives to ASET a certain margin of improvement. Figure
4(d) shows that ASET introduces some improvement over all the baselines for
every lambda, despite being trained only for $\lambda$ = 60.

(a) Queries handled successfully.

(c) Queries delivered with QoS violations.

(d) Queries rejected for lack of resources.

Figure 6: Performance of ASET compared with static policies for the full-edge
topology. (a) (c) and (d) show averages of multiple runs with $\lambda$ = 60.

Edge deployment. The results so far suggest that a good distribution of
computing resources is a key factor to improve against static scheduling
policies. As shown in Figure V-A, the benefits of using a dynamic scheduling
approach become more concrete in a full-edge topology, where resources are
better distributed on multiple smaller clusters in different locations. In
fact, Figure 5(a) shows that the dynamic approach of ASET is able to achieve a
constant improvement over any static policy, with a higher success ratio over
time. In particular, Figures V-Acd show that, while maintaining the same
rejection rate as the best static-policy, ASET effectively reduces the number
of queries that are handled violating one or more QoS requirements. Moreover,
Figure LABEL:subfig:edge-lambdas shows that an ASET agent trained only for
$\lambda$ = 60 can also generalize on different requests rate, even supporting
a load of more than 1600 queries per second ($\lambda$ = 100) on a single
antenna.

Dynamic input rate. We have performed some additional experiments to evaluate
how the system behaves in dynamic situations where the requests rate varies
over time. For this purpose, we have set up some dynamic runs where the lambda
value changes every 150 seconds: a first pattern simulates a particularly fast
variation with values of 20, 60, and 100 clients per minute (Figure 6(a)); a
different pattern simulates a more steady scenario where the requests rate
first moves from 60 to 40 clients per minute, then drops to 20, and finally
slowly goes back to 60 (Figure 6(b)). Similar to previous plots, the outcomes
for this set of experiments are shown averaging values over time for multiple
runs (Figure 7). Results in both figures show that having a dynamic requests
arrival even introduces a bigger margin for improvement that ASET effectively
exploits reaching the highest percentage of queries handled successfully. This
appears particularly evident in the case where the variation between client
arrivals is faster and bigger (Figure 6(a)). This result suggests that, while
some of the static policies may achieve decent performance when the system
load is stable, they struggle on more dynamic scenarios. In such situations,
an adaptive algorithm such as ASET is more suitable as it can learn how to
best optimize the system under different conditions. Moreover, results suggest
that ASET training generalizes enough as the algorithm performs well under
previously unseen dynamic conditions.

(a) Burst variation of $\lambda$ from 20 to 100.

(b) Steady variation of $\lambda$ between 60 and 20.

Figure 7: Performance of ASET varying the requests rate over time with two
different load variation patterns (full-edge topology).

Training and applicability. Figure 7(a) shows the cumulative distribution of
the time needed by ASET to infer a switching decision from the current policy
to the one that is best suitable for the current system conditions (non-dashed
line). The switching delay is compared with distributions of the intervals
between subsequent requests for different lambdas. As shown, even for very
large client loads (100 clients connected to the antenna), the time interval
between two stream arrivals is typically in the scale of seconds or hundreds
of milliseconds, while the delay for switching between policies is one order
of magnitude smaller. Finally, Figure 7(b) shows the learning curve of ASET
for different topologies on continuous stream request arrivals. The figure
shows that ASET quickly reaches a certain level of performance in the first
training iterations (before 100 episodes) independently from the topology
complexity, leaving room for extra improvements to the subsequent episodes
based on the margin left by the topology itself.

(a) Cumulative distribution of delay.

(b) Learning curve.

Figure 8: (a) Delay for switching policy compared with requests arrival
intervals. (b) Learning curve while training ASET on different topologies.

##  VI Conclusions

This paper proposes ASET, an adaptive algorithm based on Reinforcement
Learning for scheduling inference workloads at the network edge. ASET solves
the problem of exploiting scattered clusters of resources to serve inference
queries from multiple edge applications (e.g., AR/VR, cognitive assistance).
We model an edge inference system where queries from different access networks
are processed across a multitude of distributed processing locations. The
constrained nature of the edge network introduces a trade-off between network
delay and processing time based on the various available DNN models. In such a
scenario, ASET optimizes the binding between inference stream requests and
available DL models across the network, maximizing the throughput and ensuring
that any requirement in terms of inference accuracy and end-to-end delay is
satisfied. We evaluated our approach over the realistic network topology of a
large ISP and considering a heterogeneous pool of edge applications. Our
findings show that ASET effectively improves the performance compared to
static policies when resources are deployed across the whole edge-cloud
infrastructure.

## References

  * [1] J. Konecny, H. B. McMahan, F. Yu, P. Richtarik, A. Theertha Suresh, and D. Bacon, “Federated learning: Strategies for improving communication efficiency,” in _29th Conference on Neural Information Processing Systems(NIPS)_ , 2016.
  * [2] R. S. Kannan, L. Subramanian, A. Raju, J. Ahn, J. Mars, and L. Tang, “Grandslam: Guaranteeing slas for jobs in microservices execution frameworks,” in _Proceedings of the Fourteenth EuroSys Conference 2019_. ACM, 2019, p. 34.
  * [3] H. Mao, M. Schwarzkopf, S. B. Venkatakrishnan, Z. Meng, and M. Alizadeh, “Learning scheduling algorithms for data processing clusters,” in _Proceedings of the ACM Special Interest Group on Data Communication_ , 2019, pp. 270–288.
  * [4] D. Crankshaw, X. Wang, G. Zhou, M. J. Franklin, J. E. Gonzalez, and I. Stoica, “Clipper: A low-latency online prediction serving system,” in _14th $\\{$USENIX$\\}$ Symposium on Networked Systems Design and Implementation ($\\{$NSDI$\\}$ 17)_, 2017, pp. 613–627.
  * [5] F. Romero, Q. Li, N. J. Yadwadkar, and C. Kozyrakis, “Infaas: Managed & model-less inference serving,” _arXiv preprint arXiv:1905.13348_ , 2019.
  * [6] C. Olston, N. Fiedel, K. Gorovoy, J. Harmsen, L. Lao, F. Li, V. Rajashekhar, S. Ramesh, and J. Soyke, “Tensorflow-serving: Flexible, high-performance ml serving,” _arXiv preprint arXiv:1712.06139_ , 2017.
  * [7] D. Chappell, “Introducing azure machine learning,” _A guide for technical professionals, sponsored by microsoft corporation_ , 2015.
  * [8] “Ai platform of google cloud,” https://cloud.google.com/ai-platform.
  * [9] P. Mach and Z. Becvar, “Mobile edge computing: A survey on architecture and computation offloading,” _IEEE Communications Surveys & Tutorials_, vol. 19, no. 3, pp. 1628–1656, 2017.
  * [10] J. Chen and X. Ran, “Deep learning with edge computing: A review,” _Proceedings of the IEEE_ , vol. 107, no. 8, pp. 1655–1674, 2019.
  * [11] R. Ghosh and Y. Simmhan, “Distributed scheduling of event analytics across edge and cloud,” _ACM Transactions on Cyber-Physical Systems_ , vol. 2, no. 4, p. 24, 2018.
  * [12] C.-C. Hung, G. Ananthanarayanan, P. Bodik, L. Golubchik, M. Yu, P. Bahl, and M. Philipose, “Videoedge: Processing camera streams using hierarchical clusters,” in _2018 IEEE/ACM Symposium on Edge Computing (SEC)_. IEEE, 2018, pp. 115–131.
  * [13] J. Soifer, J. Li, M. Li, J. Zhu, Y. Li, Y. He, E. Zheng, A. Oltean, M. Mosyak, C. Barnes _et al._ , “Deep learning inference service at microsoft,” in _2019 $\\{$USENIX$\\}$ Conference on Operational Machine Learning (OpML 19)_, 2019, pp. 15–17.
  * [14] E. Cuervo, A. Balasubramanian, D.-k. Cho, A. Wolman, S. Saroiu, R. Chandra, and P. Bahl, “Maui: making smartphones last longer with code offload,” in _Proceedings of the 8th international conference on Mobile systems, applications, and services_. ACM, 2010, pp. 49–62.
  * [15] M.-R. Ra, A. Sheth, L. Mummert, P. Pillai, D. Wetherall, and R. Govindan, “Odessa: enabling interactive perception applications on mobile devices,” in _Proceedings of the 9th international conference on Mobile systems, applications, and services_. ACM, 2011, pp. 43–56.
  * [16] S. Han, H. Shen, M. Philipose, S. Agarwal, A. Wolman, and A. Krishnamurthy, “Mcdnn: An approximation-based execution framework for deep stream processing under resource constraints,” in _Proceedings of the 14th Annual International Conference on Mobile Systems, Applications, and Services_. ACM, 2016, pp. 123–136.
  * [17] X. Ran, H. Chen, X. Zhu, Z. Liu, and J. Chen, “Deepdecision: A mobile deep learning framework for edge video analytics,” in _IEEE INFOCOM 2018-IEEE Conference on Computer Communications_. IEEE, 2018, pp. 1421–1429.
  * [18] B. Hu and W. Hu, “Linkshare: device-centric control for concurrent and continuous mobile-cloud interactions,” in _Proceedings of the 4th ACM/IEEE Symposium on Edge Computing_ , 2019, pp. 15–29.
  * [19] S. H. Mortazavi, M. Salehe, C. S. Gomes, C. Phillips, and E. de Lara, “Cloudpath: a multi-tier cloud computing framework,” in _Proceedings of the Second ACM/IEEE Symposium on Edge Computing_. ACM, 2017, p. 20.
  * [20] S. Khare, H. Sun, J. Gascon-Samson, K. Zhang, A. Gokhale, Y. Barve, A. Bhattacharjee, and X. Koutsoukos, “Linearize, predict and place: minimizing the makespan for edge-based stream processing of directed acyclic graphs,” in _Proceedings of the 4th ACM/IEEE Symposium on Edge Computing_ , 2019, pp. 1–14.
  * [21] C. Cicconetti, M. Conti, and A. Passarella, “An architectural framework for serverless edge computing: design and emulation tools,” in _2018 IEEE International Conference on Cloud Computing Technology and Science (CloudCom)_. IEEE, 2018, pp. 48–55.
  * [22] M. Jia, J. Cao, and W. Liang, “Optimal cloudlet placement and user to cloudlet allocation in wireless metropolitan area networks,” _IEEE Transactions on Cloud Computing_ , vol. 5, no. 4, pp. 725–737, 2015.
  * [23] J. Long, M. Dong, K. Ota, and A. Liu, “A green tdma scheduling algorithm for prolonging lifetime in wireless sensor networks,” _IEEE Systems Journal_ , vol. 11, no. 2, pp. 868–877, 2015.
  * [24] R. Bellman, “A markovian decision process,” _Journal of mathematics and mechanics_ , pp. 679–684, 1957.
  * [25] S. Levine, A. Kumar, G. Tucker, and J. Fu, “Offline reinforcement learning: Tutorial, review, and perspectives on open problems,” _arXiv preprint arXiv:2005.01643_ , 2020.
  * [26] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. A. Riedmiller, “Playing atari with deep reinforcement learning,” _CoRR_ , vol. abs/1312.5602, 2013. [Online]. Available: http://arxiv.org/abs/1312.5602
  * [27] L. ji Lin, “Self-improving reactive agents based on reinforcement learning, planning and teaching,” in _Machine Learning_ , 1992, pp. 293–321.
  * [28] C. J. C. H. Watkins and P. Dayan, “Q-learning,” _Machine Learning_ , vol. 8, no. 3, pp. 279–292, 1992. [Online]. Available: https://doi.org/10.1007/BF00992698
  * [29] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski _et al._ , “Human-level control through deep reinforcement learning,” _nature_ , vol. 518, no. 7540, pp. 529–533, 2015.
  * [30] L. Tong, Y. Li, and W. Gao, “A hierarchical edge cloud architecture for mobile computing,” in _IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications_. IEEE, 2016, pp. 1–9.
  * [31] A. Ceselli, M. Premoli, and S. Secci, “Mobile edge cloud network design optimization,” _IEEE/ACM Transactions on Networking_ , vol. 25, no. 3, pp. 1818–1831, 2017.
  * [32] Z. Chen, W. Hu, J. Wang, S. Zhao, B. Amos, G. Wu, K. Ha, K. Elgazzar, P. Pillai, R. Klatzky _et al._ , “An empirical study of latency in an emerging class of edge computing applications for wearable cognitive assistance,” in _Proceedings of the Second ACM/IEEE Symposium on Edge Computing_ , 2017, pp. 1–14.
  * [33] A. Cartas, M. Kocour, A. Raman, I. Leontiadis, J. Luque, N. Sastry, J. Nuñez-Martinez, D. Perino, and C. Segura, “A reality check on inference at mobile networks edge,” in _Proceedings of the 2nd International Workshop on Edge Systems, Analytics and Networking_ , 2019, pp. 54–59.
  * [34] L. Jiao, F. Zhang, F. Liu, S. Yang, L. Li, Z. Feng, and R. Qu, “A survey of deep learning-based object detection,” _IEEE Access_ , vol. 7, pp. 128 837–128 868, 2019.
  * [35] A. Srivastava, D. Nguyen, S. Aggarwal, A. Luckow, E. Duffy, K. Kennedy, M. Ziolkowski, and A. Apon, “Performance and memory trade-offs of deep learning object detection in fast streaming high-definition images,” in _2018 IEEE International Conference on Big Data (Big Data)_. IEEE, 2018, pp. 3915–3924.
  * [36] W. Liu, D. Anguelov, D. Erhan, C. Szegedy, S. Reed, C.-Y. Fu, and A. C. Berg, “Ssd: Single shot multibox detector,” in _European conference on computer vision_. Springer, 2016, pp. 21–37.
  * [37] J. Redmon, S. Divvala, R. Girshick, and A. Farhadi, “You only look once: Unified, real-time object detection,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 779–788.