tt MSReferences

# COSCO: Container Orchestration using Co-Simulation and Gradient Based
Optimization for Fog Computing Environments

Shreshth Tuli, Shivananda Poojara, Satish N. Srirama, Giuliano Casale and
Nicholas R. Jennings  S. Tuli, G. Casale and N. R. Jennings are with the
Department of Computing, Imperial College London, United Kingdom. E-mails:
{s.tuli20, g.casale<EMAIL_ADDRESS>Poojara is with the
Institute of Computer Science, University of Tartu, Estonia. E-mail:
<EMAIL_ADDRESS>N. Srirama is with the School of Computer and Information
Sciences, University of Hyderabad, India. E-mail<EMAIL_ADDRESS>
###### Abstract

Intelligent task placement and management of tasks in large-scale fog
platforms is challenging due to the highly volatile nature of modern workload
applications and sensitive user requirements of low energy consumption and
response time. Container orchestration platforms have emerged to alleviate
this problem with prior art either using heuristics to quickly reach
scheduling decisions or AI driven methods like reinforcement learning and
evolutionary approaches to adapt to dynamic scenarios. The former often fail
to quickly adapt in highly dynamic environments, whereas the latter have run-
times that are slow enough to negatively impact response time. Therefore,
there is a need for scheduling policies that are both reactive to work
efficiently in volatile environments and have low scheduling overheads. To
achieve this, we propose a Gradient Based Optimization Strategy using Back-
propagation of gradients with respect to Input (GOBI). Further, we leverage
the accuracy of predictive digital-twin models and simulation capabilities by
developing a Coupled Simulation and Container Orchestration Framework (COSCO).
Using this, we create a hybrid simulation driven decision approach, GOBI*, to
optimize Quality of Service (QoS) parameters. Co-simulation and the back-
propagation approaches allow these methods to adapt quickly in volatile
environments. Experiments conducted using real-world data on fog applications
using the GOBI and GOBI* methods, show a significant improvement in terms of
energy consumption, response time, Service Level Objective and scheduling time
by up to 15, 40, 4, and 82 percent respectively when compared to the state-of-
the-art algorithms.

###### Index Terms:

Fog Computing, Coupled Simulation, Container Orchestration, Back-propagation
to input, QoS Optimization.

##  1 Introduction

Fog computing is an emerging paradigm in distributed systems, which
encompasses all intermediate devices between the Internet of Things (IoT)
layer (geo-distributed sensors and actuators) and the cloud layer (remote
cloud platforms). It can reduce latency of compute, network and storage
services by placing them closer to end users leading to a multitude of
benefits. However, fog environments pose several challenges when integrating
with real-world applications. For instance, many applications, especially in
healthcare, robotics and smart-cities demand ultra low response times
specifically for applications sensitive to Service Level Objectives (SLO) [1].
Other applications involving energy scavenging edge devices and renewable
resources need supreme energy efficiency in task execution [2]. The challenge
of reaching low response times and energy consumption is further complicated
by modern-day application workloads being highly dynamic [3] and host machines
having non-stationary resource capabilities [4].

To provide quick and energy efficient solutions, many prior works focus on
developing intelligent policies to schedule compute tasks on fog hosts [5, 6,
7]. These methods have been dominated by heuristic techniques [8, 9, 7, 10].
Such approaches have low scheduling times and work well for general cases, but
due to steady-state or stationarity assumptions, they provide poor performance
in non-stationary heterogeneous environments with dynamic workloads [9]. To
address this, some prior approaches use more intelligent and adaptive schemes
based on evolutionary methods and reinforcement learning. These methods adapt
to changing scenarios and offer promising avenues for dynamic optimization
[11]. However, they too are unable to efficiently manage volatile fog
environments because of their poor modelling accuracies and low scalability
[5, 3]. For accurate and scalable modelling of the fog environment, there have
been many works that use deep learning based local search or learning models
with neural networks which approximate an objective function such as energy
consumption or response time [3, 12, 5]. As these neural networks approximate
objective functions of optimization problem, they are often referred to as
“neural approximators” [13, 14]. Specifically, many recent state-of-the-art
techniques primarily use optimization methods like genetic algorithms (GA)
[12] and policy-gradient learning [3] to optimize QoS parameters, thanks to
their generality. However, gradient-free methods like GA are slow to converge
to optima due to undirected search schemes [15]. Further, policy-gradient
learning takes time to adapt to sudden changes in the environment and shares
the same problem of high scheduling overheads. Such high scheduling times
limit the extent of the possible improvement of latency and subsequently SLO
violations. This is not suitable for highly volatile environments where host
and workload characteristics may suddenly and erratically change. Thus, there
is a need for an approach which not only can adapt quickly in volatile
environments but also have low scheduling overheads to efficiently handle
modern workload demands.

To solve this problem, a natural choice is to use directed schemes like A*
search or gradient-based optimization strategies. Even though such strategies
have been shown to converge much faster than gradient-free approaches, prior
work does not use them due to the highly non-linear search spaces in real-
world problems which can cause such methods to get stuck in local optima [16].
Moreover, prior works fail to leverage recent advances like root-mean-square
propagation, and momentum and annealed gradient descent with restarts that
help prevent the local optima problem [17, 18, 19]. Given this, we believe
that by leveraging the strength of neural networks to accurately approximate
QoS parameters [20], we can apply gradient-based algorithms in tandem with
advances that reduce the likelihood of such methods getting stuck at local
optima. Prior work also establishes that neural approximators are able to
precisely model the gradients of the objective function with respect to input
using back-propagation allowing us to use them in gradient-based methods for
quick convergence [21]. When taken together, this suite of approaches should
provide a quick and efficient optimization method. In particular, we formulate
a gradient-based optimization algorithm (GOBI) which calculates the gradients
of neural networks with respect to input for optimizing QoS parameters using
advanced gradient-based optimization strategies. We establish by experiments
that our approach provides a faster and more scalable optimization strategy
for fog scheduling compared to the state-of-the-art methods.

However, simply using gradient-based optimization is not sufficient as data
driven neural models can sometimes saturate [22]. This is when feeding more
data to the neural model does not improve the performance. Further
optimization of QoS in such cases is hard and more intelligent schemes are
required. Coupled-simulation (also referred as co-simulation or symbiotic
simulation) and execution of tasks have been shown to be a promising approach
for quickly obtaining an estimate of QoS parameters in the near future [23,
24, 25]. Specifically, coupled-simulation allows us to run a simulator in the
background with the scheduling algorithms to facilitate decision making.
However, prior works use this to aid search methods and not to generate more
data to facilitate decision making of an AI model. The latter requires
development of a new interface between the scheduler and simulator. Hence, we
develop COSCO: Coupled Simulation and Container Orchestration Framework to
leverage simulated results to yield better QoS. The COSCO framework is the
first to allow a single or multi-step simulation of container migration
decisions in fog environments. It enables a scheduler to get an estimate of
the QoS parameters at the end of a future interval for better prediction and
subsequently optimum schedules. Container migration refers to the process of
moving an application between different physical or virtual hosts and resuming
computation on the target host. This allows us to run the GOBI approach,
simulate the schedule (with a predicted workload model) and provide the
objective values to another neural approximator which can then better
approximate the objective function and lead to improved performance. We call
this novel optimization loop GOBI* (Figure 1). The interactive training
dynamic between GOBI and GOBI* aides the latter to converge quickly and adapt
to volatile environments (more details in Section 7).

In summary, the key contributions of this paper are:

  * •

We present a novel framework, COSCO, which is the first to allow coupled
simulation and container orchestration in fog environments.

  * •

We propose a gradient based back-propagation approach (GOBI) for fast and
scalable scheduling and show that it outperforms the state-of-the-art
schedulers.

  * •

We also propose an extended approach (GOBI*) that leverages simulation results
from COSCO running GOBI’s decision, to provide improved predictions and
scheduling decisions with lower scheduling overheads.

Validating both GOBI and GOBI* on physical setups with real-world benchmark
data shows that, GOBI gives lower performance than GOBI*. However, GOBI is
more suitable for resource constrained fog brokers, because of its low
computational requirements. GOBI*, on the other hand, is more suitable for
setups with critical QoS requirements and powerful fog brokers.

Figure 1: The GOBI* loop.

The rest of the paper is organized as follows. Related work is overviewed in
Section 2. Section 3 provides a motivating example for the problem. Section 4
describes the system model and formulates the problem specifications. Section
5 details GOBI and Section 6 introduces the COSCO framework. Section 7
presents the GOBI* approach, integrating GOBI with COSCO’s co-simulation
feature. A performance evaluation of the proposed methods is shown in Section
8. Finally, Section 9 concludes.

TABLE I: Comparison of Related Works with Different Parameters (✓means that
the corresponding feature is present).

Work | Edge | Heterogeneous | Coupled | Stochastic | Adaptive | Method | Optimization Parameters
---|---|---|---|---|---|---|---
Cloud | Environment | Simulation | Workload | QoS | Energy | Response Time | SLO Violations | Fairness | Scheduling Time
[9, 26, 27] |  |  |  | ✓ |  | Heuristics | ✓ | ✓ | ✓ |  |
[28, 6, 29, 30] | ✓ | ✓ |  | ✓ |  | GA | ✓ | ✓ | ✓ |  |
[31, 32] |  | ✓ |  | ✓ | ✓ | MaxWeight |  | ✓ |  |  |
[33, 5, 34, 35] |  | ✓ |  |  | ✓ | Deep RL | ✓ | ✓ |  |  | ✓
[3, 36] | ✓ | ✓ |  | ✓ | ✓ | Policy Gradient | ✓ | ✓ | ✓ | ✓ |
This work | ✓ | ✓ | ✓ | ✓ | ✓ | GOBI/GOBI* | ✓ | ✓ | ✓ | ✓ | ✓

##  2 Related Work

We now analyze prior work in more detail (see Table I for an overview).

Heuristic methods: Several studies [9, 26, 27] have shown how heuristic based
approaches perform well in a variety of scenarios for optimization of diverse
QoS parameters. Methods like LR-MMT schedules workloads dynamically based on
local regression (LR) to predict which hosts might get overloaded in the near
future and select containers/tasks which can be migrated in the minimum
migration time (MMT). Both LR and MMT heuristics are used for overload
detection and task selection, respectively [9, 26]. Similarly, MAD-MC
calculates the median-attribute deviation (MAD) of the CPU utilization of the
hosts and select containers based on the maximum correlation (MC) with other
tasks [9]. However, such heuristic based approaches fail to model stochastic
environments with dynamic workloads [3]. This is corroborated by our results
in Section 8. To overcome this, GOBI and GOBI* are able to adapt to dynamic
scenarios by constantly learning the mapping of scheduling decisions with
objective values. This makes them both robust to diverse, heterogeneous and
dynamic scenarios.

Evolutionary models: Other prior works have shown that evolutionary based
methods, and generally gradient-free approaches, perform well in dynamic
scenarios [28, 6, 29, 30]. Evolutionary approaches like genetic algorithms
(GA) lie in the domain of gradient-free optimization methods. The GA method
schedules workloads using a neural model to approximate the objective value
(as in GOBI) and a genetic-algorithm to reach the optimal decision [6].
However, gradient-free methods have a number of drawbacks. They take much
longer to converge [16] and are not as scalable [15] as gradient-based
methods. Moreover, non-local jumps can lead to significant change in the
scheduling decision which can lead to a high number of migrations (as seen in
Figures 8(e)-9(d)).

MaxWeight based schedulers: Over the years, MaxWeight scheduling has gained
popularity for its theoretical guarantees and ability to reduce resource
contention [31, 32]. However, MaxWeight policies can exhibit poor delay
performance, instability in dynamic workloads and spatial inefficiency [37,
38, 39]. We use the pessimistic-optimistic online dispatch approach, POND by
Liu et al. [31] which is a variant of the MaxWeight approach [40]. POND uses
constrained online dispatch with unknown arrival and reward distributions. It
uses virtual queues for each host to track violation counts and an Upper-
Confidence Bound (UCB) policy [41] to update the expected rewards of each
allocation from the signal $\mathcal{O}(P_{t})$. The final decision is made
using the MaxWeight approach with the weights as the expected reward values.
To minimize objective value in our setup, we provide the objective score as
negative reward. Due to the inability of MaxWeight approaches to adapt to
volatile scenarios, their wait times are high.

Reinforcement Learning models: Recently, reinforcement learning based methods
have shown themselves to be robust and versatile to diverse workload
characteristics and complex edge setups [3, 35, 5, 34]. Such methods use a
Markovian assumption of state which is the scheduling decision at each
interval. Based on new observations of reward signal (negative objective score
in our setting) they explore or exploit their knowledge of the state-space to
converge to an optimal decision. A recent method, DQLCM, models the container
migration problem as a multi-dimensional Markov Decision Process (MDP) and
uses a deep-reinforcement learning strategy, namely deep Q-Learning to
schedule workloads in a heterogeneous fog computing environment [35]. The
state-of-the-art method, A3C, schedules workloads using a policy gradient
based reinforcement learning strategy which tries to optimize an actor-critic
pair of agents [3]. This approach uses Residual Recurrent Neural Networks to
predict the expected reward for each action _i.e._ , scheduling decision and
tries to optimize the cumulative reward signal. However, such methods are
still slow to adapt to real-world application scenarios as discussed in
Section 8. This leads to higher wait times and subsequently high response
times and SLO violations. Moreover, these methods do not scale well [42].

Finally, coupled or symbiotic simulation and model based control have long
been used in the modelling and optimization of distributed systems [43, 44,
25]. Many prior works have used hybrid simulation models to optimize decision
making in dynamic systems. To achieve this, they monitor, analyze, plan and
execute decisions using previous knowledge-base corpora (MAPE-k) [1]. However,
such works use this to facilitate search methods and not to generate
additional data to aid the decision making of an AI model. COSCO is developed
to leverage a seamless interface between the orchestration framework and
simulation engine to have a interactive dynamic between AI models to optimize
QoS.

For our experiments, we use LR-MMT, MAD-MC, POND, GA, DQLCM and A3C as
baselines to compare against the proposed GOBI and GOBI* models. We try to
cover the best approach(es) in each category by careful literature review. The
different categories have been selected for their complementary benefits.
Heuristic based approaches are fast but not as accurate as other methods.
Learning methods are adaptive but slow to adapt or output a scheduling
decision.

##  3 Motivating Example

Figure 2: Motivating example

As demonstrated by many prior works [3, 9, 6], for fog datacenters, the
scheduling time increases exponentially with the number of fog devices. This
can have a significant impact on response time and, correspondingly, on
Service Level Objectives (SLOs) corresponding to the task response time. To
test this, we perform a series of experiments on the iFogSim simulator [45].
We test the popular heuristic based approach LR-MMT [9] and the evolutionary
approach using genetic algorithm (GA) [6] with 50 simulated host machines
(details in Section 8.1). The former represents the broad range of heuristic
based approaches that can quickly generate a scheduling decision but lack the
ability to adapt. The latter have the ability to quickly adapt but have high
scheduling overheads. As in [6], we provide the GA the utilization metrics of
all hosts and tasks and aim to minimize the average response time.

We assume a central scheduler which periodically allocates new tasks and
migrates active tasks if required to reduce SLO violations. We assume that the
container allocation time is negligible and the total response time of a fog
task is the sum of the scheduling and execution times. We consider volatile
workloads that are generated from traces of real-world applications running in
a fog environment [3] (using the Bitbrain dataset, details in Section 8). For
the approaches considered, the scheduling time can range from 100 to 150
seconds with SLO violation rate of up to $24\%$. However, if we could bring
down the scheduling times to $10$ seconds with the same decisions as GA
(referred to as GA2), the SLO violation rate goes down to $\sim\\!\\!2\%$.
This shows how scheduling time is a key factor that limits the extent to which
SLO can be optimized (Figure 2), thus highlighting the potential for an
approach which can respond quickly in volatile scenarios and has low
scheduling overheads, leveraging the fast and scalable execution times of AI
methods.

##  4 System Model and Problem Formulation

###  4.1 System Model

We consider a standard distributed and heterogeneous fog computing environment
as shown in Figure 3. We assume a single fog datacenter with geographically
distributed edge and cloud layers as computational nodes. We consider network
latency effects for interactions between compute devices in different layers
(edge and cloud) and between compute devices and fog broker. We ignore
communication latencies among devices in the same layer.. Tasks are container
instances with inputs being generated by sensors and other IoT devices and
results received by actuators which physically manifest the intended actions.
These devices constitute the IoT layer and send and receive all data from the
fog gateway devices. All management of tasks and hosts is done by a Fog Broker
in the management layer. This includes task scheduling, data management,
resource monitoring and container orchestration. The work described in this
paper is concerned with improving the scheduler in the Fog Broker by providing
an interface between the container orchestration and resource monitoring
services with a simulator. Our work proposes discrete-time controllers, that
are commonly adopted in the literature [43, 5, 3]. The communication between
end-users and the fog broker is facilitated by gateway devices. The compute
nodes in the fog resource layer, which we refer to as “hosts”, can have
diverse computational capabilities. The hosts at the edge of the network are
resource-constrained and have low communication latency with the broker and
gateway devices. On the other hand, cloud hosts are several hops from the
users and have much higher communication latency and are computationally more
powerful. We assume that there are a fixed number of host machines in the fog
resource layer and denote them as $H=\\{h_{0},h_{1},\ldots,h_{N-1}\\}$. We
denote the collection of time-series utilization metrics, which include CPU,
RAM, Disk and Network Bandwidth usage of host $h_{i}$ as
$\mathcal{U}(h_{i}^{t})$. The collection of maximum capacities of CPU, RAM,
Disk and Network Bandwidth with the average communication latency of host
$h_{i}$ is denoted as $\mathcal{C}(h_{i})$.

Figure 3: System model

###  4.2 Workload Model

We now present our workload model, as summarized in Figure 4. We divide a
bounded timeline into equal sized scheduling intervals with equal duration
$\Delta$. The $t$-th interval is denoted by $I_{t}$ and starts at $s(I_{t})$,
so that $s(I_{0})=0$ and $s(I_{t})=s(I_{t-1})+\Delta\ \forall t>0$. In
interval $I_{t-1}$, $N_{t}$ new tasks are created by the IoT devices. The
gateway devices then send batches of these new tasks $N_{t}$ with their SLO
requirements to the Fog Broker. The SLO violations are measured corresponding
to the response time metrics of task executions as a fraction of them that
exceeds the stipulated deadlines. The set of active tasks in the interval
$I_{t}$ is denoted as $A_{t}=\\{a_{0}^{t},a_{1}^{t},\ldots,a_{|A_{t}|}^{t}\\}$
and consists of $|A_{t}|$ tasks. Here $a_{j}^{t}$ represents an identifier for
the $j$-th task in $A_{t}$. The Fog Broker schedules the new tasks to the
compute nodes and decides which of the active tasks need to be migrated. At
the end of interval $I_{t-1}$, the set of completed tasks is denoted as
$L_{t}$, hence the tasks that carry forward to the next interval is the set
$A_{t-1}\setminus L_{t}$. Thus, the broker takes a decision
$\mathcal{D}^{t}=\mathcal{D}(Y_{t})$, where $Y_{t}$ is the union of the new
($N_{t}$), active ($A_{t-1}\setminus L_{t}$) and waiting tasks ($W_{t-1}$).
This decision is a set of allocations and migrations in the form of ordered-
pairs of tasks and hosts (assuming no locality constraints). At the first
scheduling interval, as there are no active or waiting tasks, the model only
takes allocation decision for new tasks ($N_{0}$). Here, $\mathcal{D}$ denotes
the scheduler such that $\mathcal{D}:Y_{t}\mapsto Y_{t}\times H$. Only if the
allocation is feasible, _i.e._ , depending on whether the target host can
accommodate the scheduled task or not, is the migration/allocation decision
executed. Initially, the waiting queue and the set of active and leaving
actions are empty. The executed decision is denoted by $\hat{\mathcal{D}}$ and
satisfies the following properties

$\displaystyle\hat{\mathcal{D}}(A_{t})\subseteq\mathcal{D}(Y_{t}),\text{where}$
(1) $\displaystyle\forall\ (a_{j}^{t},h_{i})\in\hat{\mathcal{D}}(A_{t}),\
\mathcal{U}(a_{j}^{t})+\mathcal{U}(h_{i}^{t})\leq\mathcal{C}(h_{i}).$ (2)

We use the notation $a_{j}^{t}\in\hat{\mathcal{D}}(A_{t})$ to mean that this
task was allocated/migrated. The set of new and waiting tasks
$\hat{N}_{t}\cup\hat{W}_{t-1}\subseteq\hat{\mathcal{D}}(A_{t})$, where
$\hat{N}_{t}\subseteq N_{t}$ and $\hat{W}_{t-1}\subseteq W_{t-1}$, denotes
those tasks which could be allocated successfully. The remaining new tasks,
_i.e._ $N_{t}\setminus\hat{N}_{t}$ are added to get the new wait queue
$W_{t}$. Similarly, active tasks are denoted as $\hat{A}_{t-1}\subseteq
A_{t-1}$. Hence, for every interval $I_{t}$,

$\displaystyle A_{t}\leftarrow\hat{N}_{t}\cup\hat{W}_{t-1}\cup
A_{t-1}\setminus L_{t}$ (3) $\displaystyle
W_{t}\leftarrow(W_{t-1}\setminus\hat{W}_{t-1})\cup(N_{t}\setminus\hat{N}_{t}),\text{where}$
(4) $\displaystyle W_{-1}=A_{-1}=L_{-1}=\emptyset.$ (5)

We also denote the utilization metrics of an active task $a_{j}^{t}\in A_{t}$
as $\mathcal{U}(a_{j}^{t})$ for the interval $I_{t}$. We denote a simulator as
$\mathcal{S}:\hat{\mathcal{D}}(A_{t})\times\\{\mathcal{U}(a_{j}^{t})|\forall
a_{j}^{t}\in A_{t}\\}\mapsto\\{\mathcal{U}(h_{i}^{t})|\forall h_{i}\in
H\\}\times P$, which takes scheduling decision and container utilization
characteristics to give host characteristics and values of QoS parameters.
Here $P_{t}\in P$ is a set of QoS parameters such as energy consumption,
response times, SLO violations, etc. Similarly, execution on a physical fog
framework is denoted by $\mathcal{F}$. Hence, execution of interval $I_{t}$ on
a physical setup is denoted as

$(\\{\mathcal{U}(h_{i}^{t})|\forall h_{i}\in
H\\},P_{t})\equiv\mathcal{F}(\hat{\mathcal{D}}(A_{t}),\\{\mathcal{U}(a_{j}^{t})|\forall
a_{j}^{t}\in A_{t}\\}).$ (6)

Figure 4: Dynamic Task Workload Model TABLE II: Symbol Table

Symbol | Meaning
---|---
$I_{t}$ |  $t^{th}$ scheduling interval
$A_{t}$ | Active tasks in $I_{t}$
$W_{t-1}$ | Waiting tasks at the start of $I_{t}$
$L_{t}$ | Tasks leaving at the end of $I_{t}$
$N_{t}$ | New tasks received at the start of $I_{t}$
$H$ | Set of hosts in the Resource Layer
$h_{i}$ |  $i^{th}$ host in an enumeration of $H$
$a_{j}^{t}$ |  $j^{th}$ task in an enumeration of $A_{t}$
$\mathcal{U}(h_{i}^{t})$ | Utilization metrics of host $h_{i}$ in $I_{t}$
$\mathcal{U}(a_{j}^{t})$ | Utilization metrics of task $a_{j}^{t}$ in $I_{t}$
$Y_{t}=N_{t}\cup W_{t-1}\cup A_{t-1}\setminus L_{t}$ | Scheduler input at the start of $I_{t}$
$\mathcal{D}(Y_{t})$ or $\mathcal{D}$ | Scheduling decision at start of $I_{t}$
$\hat{\mathcal{D}}$ | Feasible sub-set of scheduling decision $\mathcal{D}$
[.5]0 $\bar{\mathcal{D}}$ | Scheduling decision of GOBI in GOBI* loop
$\mathcal{O}(P_{t})$ | Objective value at the end of $I_{t}$
$\mathcal{S}$ | Execution of an interval on simulator
$\mathcal{F}$ | Execution of an interval on physical setup

###  4.3 Problem Formulation

After execution of tasks $A_{t}$ in interval $I_{t}$, the objective value to
minimize is denoted as $\mathcal{O}(P_{t})$. $\mathcal{O}(P_{t})$ could be a
scalar value which combines multiple QoS parameters. To find the optimum
schedule, we need to minimize the objective function $\mathcal{O}(P_{t})$ over
the entire duration of execution. Thus, we need to find the appropriate and
feasible decision function $\mathcal{D}$ such that
$\sum_{t}\mathcal{O}(P_{t})$ is minimized. This is subject to the constraints
that at each scheduling interval the new tasks $N_{t}$, waiting tasks
$W_{t-1}$ and active tasks from the previous interval $A_{t-1}\setminus L_{t}$
are allocated using this decision function. The problem can then be concisely
formulated as:

$\displaystyle\underset{\mathcal{D}}{\text{minimize}}$
$\displaystyle\sum_{t=0}^{T}\mathcal{O}(P_{t})$ (7) subject to
$\displaystyle\forall\ t,Eqs.\eqref{eq:dhat}-\eqref{eq:framework_step}.$

##  5 The GOBI Scheduler

As discussed in Section 1, we now present the approach based on Gradient Based
Optimization using back-propagation to Input (GOBI). These constitute the
Scheduler module of the Fog Broker described in Figure 3. Here, we consider
that we optimize an objective function $\mathcal{O}(P_{t})$ at every interval
$I_{t}$ via taking an optimal action in the form of scheduling decision
$\mathcal{D}$. This $\mathcal{D}$ is then used by the framework/simulator to
execute tasks as described in optimization program (7).

###  5.1 Objective Function

We will now present how our optimization scheme can be used for taking
appropriate scheduling decisions in a fog environment. To optimize the QoS
parameters, we consider an objective function that focuses on energy
consumption and response time, two of the most crucial metrics for fog
environments [46, 47]. For interval $I_{t}$,

$\mathcal{O}(P_{t})=\alpha\cdot AEC_{t}+\beta\cdot ART_{t}.$ (8)

Here $AEC$ and $ART$ ($\in P_{t}$) are defined as follows.

  1. 1.

Average Energy Consumption (AEC) is defined for any interval as the energy
consumption of the infrastructure (which includes all edge and cloud hosts)
normalized by the maximum power of the hosts, _i.e._ ,

$\displaystyle AEC_{t}=\frac{\sum_{h_{i}\in
H}\int_{t=s(I_{t})}^{s(I_{t+1})}Power_{h_{i}}(t)dt}{|A_{t}|\sum_{h_{i}\in
H}Power^{max}_{h_{i}}\times(t_{i+1}-t_{i})},$ (9)

where $Power_{h_{i}}(t)$ is the power function of host $h_{i}$ at instant $t$,
and $Power_{h_{1}}^{max}$ is maximum possible power of $h_{i}$.

  2. 2.

Average Response Time (ART)111Both AEC and ART are unit-less metrics and lie
between $0$ and $1$ is defined for an interval $I_{t}$ as the average response
time for all leaving tasks ($L_{t}$), normalized by maximum response time
until the current interval, as shown below

$\displaystyle ART_{t}=\frac{\sum_{l_{j}^{t}\in L_{t}}Response\
Time(l_{j}^{t})}{|L_{t}|\max_{s\leq t}\max_{l_{j}^{s}\in L_{s}}Response\
Time(l_{j}^{s})}.$ (10)

###  5.2 Input Parameters

In concrete implementations, we can assume a finite maximum number of active
tasks, with the upper bound denoted as $M$. Thus at any interval, $|A_{t}|\leq
M$. Moreover, we consider the utilization metrics of Instructions per second
(IPS), RAM, Disk and Bandwidth consumption which form a feature vector of size
$F$. Then, we express task utilization metrics
$\\{\mathcal{U}(a_{j}^{t-1})|\forall j,a_{j}^{t-1}\in A_{t-1}\\}$ as an
$M\times F$ matrix denoted as $\phi(A_{t-1})$, where the first $A_{t-1}$ rows
are the feature vectors of tasks in $A_{t-1}$ in the order of increasing
creation intervals (breaking ties uniformly at random), and the rest of the
rows are ${0}$. We also form feature vectors of hosts with IPS, RAM, Disk and
Bandwidth utilization with capacities and communication latency of each host,
each of size $F^{\prime}$. Thus, at each interval $I_{t}$ for $|H|$ hosts, we
form a $|H|\times F^{\prime}$ matrix $\phi(H_{t-1})$ using host utilization
metrics of interval $I_{t-1}$.

Finally, as we have $N_{t},W_{t-1},A_{t-1}$ and $L_{t}$ at the start of
$I_{t}$, the decision matrix $\phi(\mathcal{D})$ is an $M\times|H|$ matrix
with the first $|N_{t}\cup W_{t-1}\cup A_{t-1}\cup L_{t}|$ rows being one-hot
vector of allocation of tasks to one of the $H$ hosts. The remaining rows
being ${0}$.

###  5.3 Model Training

We now describe how a neural model can be trained to approximate
$\mathcal{O}(P_{t})$ using the input parameters
$[\phi(A_{t-1}),\phi(H_{t-1}),\phi(\mathcal{D})]$. Consider a continuous
function $f(x;\theta)$ as a neural approximator of $\mathcal{O}(P_{t})$ with
the $\theta$ vector denoting the underpinning neural network parameters and
$x$ as a continuous or discrete variable with a bounded domain. Here, $x$ is
the collection of utilization metrics of tasks and hosts with a scheduling
decision. The parameters $\theta$ are learnt using the dataset
$\Lambda=\\{[\phi(A_{t-1}),\phi(H_{t-1}),\phi(\mathcal{D})],\mathcal{O}(P_{t})\\}_{t}$
such that a given loss function $\mathcal{L}$ is minimized for this dataset.
We form this dataset by running a random scheduler and saving the traces
generated (more details about the setup in Section 8). The loss $\mathcal{L}$
quantifies the dissimilarity between the predicted output and the ground
truth. We use Mean Square Error (MSE) as the loss function as done in prior
work [3]. Hence,

$\mathcal{L}(f(x;\theta),y)=\tfrac{1}{T}\textstyle\sum_{t=0}^{T}(y-f(x;\theta))^{2},\text{
where}(x,y)\in\Lambda.$

Thus, for datapoints $(x,y)\in\Lambda$, where $y$ is the value of
$\mathcal{O}(P_{t})$ for the corresponding $x$, we have
$\theta=\operatorname*{arg\,min}_{\hat{\theta}}{\sum_{(x,y)\in\Lambda}[\mathcal{L}(f(x;\hat{\theta}),y)]}$.
To do this, we calculate the gradient of the loss function with respect to
$\theta$ as $\nabla_{\theta}\mathcal{L}$ and use back-propagation to learn the
network parameters. By the universal approximation theorem [20], we can assume
that we already have parameters $\theta$ after network training, such that
this neural network approximates a generic function to an arbitrary degree of
precision (considering a sufficiently large parameter set $\theta$). A key
part of this ability of neural networks rests on randomly initializing a
parameterized function and changing the large number of parameters based on
the loss function.

Now, with this, we need to find the appropriate decision matrix
$\phi(\mathcal{D})$, such that $f(x;\theta)$ is minimized. We formulate the
resulting optimization problem as

$\displaystyle\underset{\phi(\mathcal{D})}{\text{minimize}}$ $\displaystyle
f(x;\theta)$ (11) subject to $\displaystyle\text{each element of
}\phi(\mathcal{D})\text{ is bounded}$ $\displaystyle\forall\
t,Eqs.\eqref{eq:dhat}-\eqref{eq:framework_step}.$

This is a reformulation of the program (7) using the neural approximator of
$\mathcal{O}(P_{t})$ as the objective function. Note that, because there is a
bounded space of inputs, there must be an optimal solution, _i.e._ , $\exists\
\hat{\phi}(\mathcal{D})$ such that

$\displaystyle
f([\phi(A_{t-1}),\phi(H_{t-1}),\hat{\phi}(\mathcal{D})];\theta)\leq$
$\displaystyle\hbox{}\qquad\qquad
f([\phi(A_{t-1}),\phi(H_{t-1}),\phi(\mathcal{D})];\theta),\ \forall\text{
feasible }\phi(\mathcal{D}).$

We solve this optimization problem using gradient-based methods, for which we
need $\nabla_{x}f(x;\theta)$. This is uncommon for neural network training
since prior work normally modifies the weights using input and ground truth
values. Thus the gradients can be calculated without having to update the
weights. Now, for a typical feed-forward artificial neural network,
$f(x;\theta)$ is a composition of linear layers and non-linear activation
functions. Just like the back-propagation approach, we can find gradients with
respect to input $x$. For simplicity, we consider non-affine functions like
tanh() and softplus() as activations in our models, with no effect to the
generality of the neural approximator. For instance, gradients for a single
linear layer with tanh() non-linearity is given in Proposition 3222Derivations
for other activation functions with a single linear layer are given in
Appendix B..

######  Proposition 1 (Finding gradients with respect to input).

For a linear layer with tanh() non-linearity that is defined as follows:

$f(x;W,b)=\textsf{tanh}(W\cdot x+b),$

the derivative of this layer with respect to $x$ is given as:

$\nabla_{x}f(x;W,b)=W^{T}\times(1-\textsf{tanh}^{2}(W\cdot x+b)).$

###### Proof.

It is well known that $\nabla_{x}\textsf{tanh}(x)=1-\textsf{tanh}^{2}(x)$,
therefore,

$\displaystyle\nabla_{x}f(x;W,b)$
$\displaystyle=\nabla_{x}\textsf{tanh}(W\cdot x+b)$
$\displaystyle=\nabla_{W\cdot x+b}\textsf{tanh}(W\cdot
x+b)\times\nabla_{x}(W\cdot x+b)$ $\displaystyle=(1-\textsf{tanh}^{2}(W\cdot
x+b))\times\nabla_{x}(W\cdot x+b)$
$\displaystyle=W^{T}\times(1-\textsf{tanh}^{2}(W\cdot x+b))\qed$

Using the chain-rule, we can find the derivative of an arbitrary neural
approximator $f$ as $f(x;\theta)$ is a composition of multiple such layers.
Once we have the gradients, we can initialize an arbitrary input $x$ and use
gradient descent to minimize $f(x;\theta)$ as

$x_{n+1}\leftarrow x_{n}-\gamma\cdot\nabla_{x}f(x_{n};\theta),$ (12)

where $\gamma$ is the learning rate and $n$ is the iteration count. We apply
Eq. (12) until convergence. The calculation of $\nabla_{x}f(x_{n};\theta)$ in
the above equation is carried out in a similar fashion as back-propagation for
model parameters. We can use momentum based methods like Adam [17] or annealed
schedulers like cosine annealing with warm restarts [19] to prevent the
optimization loop getting stuck in local optima. As we show in our
experiments, the combination of gradient calculation with respect to inputs
and advances like momentum and annealing allow _faster_ optimization
_avoiding_ local minima, giving a more robust and efficient approach.

1:

2:Pre-trained function approximator $f(x;\theta)$

3:Dataset used for training $\Lambda$; Convergence threshold $\epsilon$

4:Iteration limit $\sigma$; Learning rate $\gamma$

5:Initial random decision $\mathcal{D}$

6:procedure Minimize($\mathcal{D}$, $f$, $z$)

7: Initialize decision matrix $\phi(\mathcal{D})$; $i=0$

8: do

9: $x\leftarrow[z,\phi(\mathcal{D})]$ $\triangleright$ Concatenation

10: $\delta\leftarrow\nabla_{\phi(\mathcal{D})}f(x;\theta)$ $\triangleright$
Partial gradient

11: $\phi(\mathcal{D})\leftarrow\phi(\mathcal{D})-\gamma\cdot\delta$
$\triangleright$ Decision update

12: $i\leftarrow i+1$

13: while $|\delta|>\epsilon$ and $i\leq\sigma$

14: Convert matrix $\phi(\mathcal{D})$ to scheduling decision
$\mathcal{D}^{*}$

15: return $\mathcal{D}^{*}$

16:end procedure

17:procedure GOBI(scheduling interval $I_{t}$)

18: if (t == 0)

19: Initialize random decision $\mathcal{D}$

20: else

21: $\mathcal{D}\leftarrow\mathcal{D}^{*}$ $\triangleright$ Output for the
previous interval

22: Get $\phi(A_{t-1}),\phi(H_{t-1})$

23:
$\mathcal{D}^{*}\leftarrow\textsc{Minimize}(\mathcal{D},f,[\phi(A_{t-1}),\phi(H_{t-1})])$

24: Fine-tune $f$ with loss $=$

25:
$MSE(\mathcal{O}(P_{t-1}),f([\phi(A_{t-2}),\phi(H_{t-2}),\phi(\mathcal{D}^{t-1})];\theta))$

26: return $\mathcal{D}^{*}$

27:end procedure

Algorithm 1 The GOBI scheduler

###  5.4 Scheduling

After training the model $f$, at start of each interval $I_{t}$, we optimize
$\phi(\mathcal{D})$ by the following rule ($\gamma$ is the learning rate)
until the absolute value of the gradient is more than the convergence
threshold $\epsilon$, _i.e._ ,

$\phi(\mathcal{D})_{n+1}\leftarrow\phi(\mathcal{D})_{n}-\gamma\cdot\nabla_{\phi(\mathcal{D})}f(x_{n};\theta).$
(13)

In dynamic scenarios, as the approximated function for the objective
$\mathcal{O}(P_{t})$ changes with time we continuously fine-tune the neural
approximator as per the loss function
$MSE(\mathcal{O}(P_{t-1}),f([\phi(A_{t-2}),\phi(H_{t-2}),\phi(\mathcal{D}^{t-1})];\theta))$
(line 20 in Algorithm 1). Equation 13 then leads to a decision matrix with a
lower objective value (line 6 in Algorithm 1). Hence, gradient based iteration
with continuous fine-tuning of the neural approximator allows GOBI to adapt
quickly in dynamic scenarios. When the above equation converges to
$\phi(\mathcal{D}^{*})$, the rows represent the likelihood of allocation to
each host. We take the $\operatorname*{arg\,max}$ over each row to determine
the host to which each task should be allocated as $\mathcal{D}^{*}$. This
then becomes the final scheduling decision of the GOBI approach. The returned
scheduling decision is then run on a simulated or physical platform (as in Eq.
(6)) and tasks sets are updated as per Eqs. (3)-(5). To find the executed
decision $\hat{\mathcal{D}}$, we sort all tasks in $\mathcal{D}^{*}$ in
descending order of their wait times (breaking ties uniformly at random) and
then try to allocate them to the intended host in $\mathcal{D}^{*}$. If the
allocation is not possible due to utilization constraints, we ignore such
migrations and do not add them to $\hat{\mathcal{D}}$. At run-time, we fine
tune the trained neural model $f$, by newly generated data for the model to
adapt to new settings.

##  6 The COSCO Framework

Motivated from prior coupled-simulators [44], we now present the COSCO
framework as introduced in Section 1. A basic architecture is shown in Figure
5. Implementation details of the COSCO framework are given in Appendix A. The
hosts might correspond to simulated hosts or physical compute nodes with
Instructions per second (IPS), RAM, Disk and Bandwidth capacities with power
consumption models with CPU utilization. The workloads are either time-series
models of IPS, RAM, Disk, Bandwidth requirements in the case of simulation or
are actual application programs in the case of physical experiments. At the
beginning of each scheduling interval, $N_{t}$ workloads are created. The
framework also maintains a waiting queue for workloads that cannot be
allocated in the previous interval ($W_{t-1}$).

Figure 5: COSCO architecture

###  6.1 Simulator

The Simulator uses a Scheduler (GOBI for instance), which uses the utilization
metrics and QoS parameters to take an allocation decision for new workloads or
migration decisions for active workloads. At the start of a scheduling
interval $I_{t}$, the simulator destroys workloads completed in $I_{t-1}$,
denoted as $L_{t}$. It also gets workloads $N_{t}\cup W_{t-1}$. The Scheduler
decides which host to allocate these tasks to and whether to migrate active
tasks from $A_{t-1}\setminus L_{t}$. The Simulator object considers all
$N_{t}\cup W_{t-1}$ tasks in the order of the interval at which they were
created. If the target host is unable to accommodate a task, it is added to
the wait queue. This is done for each utilization metric of active task
$a_{j}^{t}$ in $\mathcal{U}(a^{t}_{j})$. As for new tasks, the utilization
metrics are unknown, $u\,=\,0\,\forall
u\in\mathcal{U}(n^{t}_{j})\,\forall\,n^{t}_{j}\in N_{t}$. To prevent overflow
of host resources, we compare for each new task $n_{j}^{t}$ the sum of the
maximum possible utilization metrics of the corresponding application and
target host against the host’s maximum capacity (more details in Appendix A).
Hence, at each interval, Eq. (5) holds. Instead of running the tasks on
physical machines, we use trace driven discrete-event simulation.

###  6.2 Framework

The Framework instantiates the tasks as Docker containers. Docker is a
container management platform as a service used to build, ship and run
containers on physical or virtual environments. Moreover, the hosts are
physical computational nodes in the same Virtual Local Area Network (VLAN) as
the server machine on which the Scheduler program runs. The server
communicates with each host via HTTP REST APIs [43]. At every host machine, a
DockerClient service runs with a Flask HTTP web-service [48]. Flask is a web
application REST client which allows interfacing between hosts and the server.
To migrate a container, we use the Checkpoint/Restore In Userspace (CRIU) [49]
tool. For each migration decision
$(a^{t}_{j},h_{i})\in\hat{\mathcal{D}}(A_{t})$, a checkpoint of $a^{t}_{j}$ is
created which is equivalent to a snapshot of the container. Then, this
snapshot is transferred (migrated) to the target host $h_{i}$, where the
container is resumed (restored). The allocation and migrations are done in a
non-blocking fashion, _i.e._ the execution of active containers is not halted
when some tasks are being migrated.

###  6.3 Model Interface

We now discuss the novelty of the COSCO framework. As all scheduling
algorithms and simulations are run on a central fog broker [43], it can be
easily run in fog environments which follow a master-slave topology. As
discussed in Section 4, a simulator can execute tasks on simulated host
machines to return QoS parameters $P$. To execute an interval $I_{t}$, the
simulator needs utilization metrics $\mathcal{U}(a^{t}_{j}),\forall
a^{t}_{j}\in A_{t}$, and a scheduling decision $\bar{\mathcal{D}}^{t}$ to be
executed on the simulator. Thus, at the beginning of the interval $I_{t}$, we
have $L_{t},N_{t},W_{t-1}$ and $A_{t-1}$. After checking for the possibility
of allocation/migration, we get $\hat{\bar{\mathcal{D}}}(A_{t})$,
$\hat{N}_{t}$ and $\hat{W}_{t-1}$. Now, using Eq. (3), we find $A_{t}$. Using
given utilization metrics $\mathcal{U}(a^{t}_{j})$ and
$\hat{\bar{\mathcal{D}}}(A_{t})$, we execute $A_{t}$ tasks on the simulator to
get
$\mathcal{S}(\hat{\bar{\mathcal{D}}}(A_{t}),\\{\mathcal{U}(a_{j}^{t})|\forall
a_{j}^{t}\in A_{t}\\})=\\{\mathcal{U}(h_{i}^{t})|\forall h_{i}\in
H\\},\bar{P}_{t}$. This means that at the beginning of interval $I_{t}$, the
COSCO framework allows simulation of the next scheduling interval (with an
action of interest $\bar{\mathcal{D}}$ and predicted utilization metrics) to
predict the values of the QoS parameters in the next interval $\bar{P}_{t}$.
This single step look-ahead simulation allows us to take better scheduling
decisions in the GOBI* algorithm, as shown in the next section.

1:

2:Pre-trained function approximator $f^{*}(x;\theta^{*})$

3:Pre-trained LSTM model $LSTM(\\{\mathcal{U}(a^{t^{\prime}}_{j})\forall
t^{\prime}<t\\})$

4:Dataset used for training $\Lambda^{*}$; Convergence threshold $\epsilon$

5:Learning rate $\gamma$; Initial random decision $\mathcal{D}$

6:procedure $\text{GOBI}^{*}$(scheduling interval $I_{t}$)

7: if (t == 0)

8: Initialize random decision $\mathcal{D}$

9: else

10: $\mathcal{D}\leftarrow\mathcal{D}^{*}$ $\triangleright$ Output for the
previous interval

11: Get $\phi(A_{t-1}),\phi(H_{t-1})$

12: $\bar{\mathcal{U}}(a^{t}_{j})\forall a^{t}_{j}\in A_{t}\leftarrow
LSTM(\\{\mathcal{U}(a^{t^{\prime}}_{j})\forall t^{\prime}<t\\})$

13: $\bar{\mathcal{D}}\leftarrow GOBI(I_{t})$

14: $\\{\mathcal{U}(h_{i}^{t})|\forall h_{i}\in
H\\},\bar{AEC}_{t},\bar{ART}_{t}\leftarrow$

15:
$\mathcal{S}(\hat{\bar{\mathcal{D}}}(A_{t}),\\{\bar{\mathcal{U}}(a^{t}_{j})\forall
a^{t}_{j}\in A_{t}\\})$

16:
$\mathcal{O}(\bar{P}_{t})\leftarrow\alpha\cdot\bar{AEC}_{t}+\beta\cdot\bar{ART}_{t}$

17:
$\mathcal{D}^{*}\leftarrow\textsc{Minimize}(\mathcal{D},f,[\phi(A_{t-1}),\phi(H_{t-1}),\mathcal{O}(\bar{P}_{t})])$

18: Fine-tune $f^{*}$ with loss $=$

19:
$MSE(\mathcal{O}(P_{t-1}),f([\phi(A_{t-2}),\phi(H_{t-2}),\phi(\mathcal{D}^{t-1})];\theta))+\mathbbm{1}(\mathcal{O}(\bar{P}_{t-1})<\mathcal{O}(P_{t-1}))\times
MSE(\bar{\mathcal{D}}^{t-1},\mathcal{D}^{t-1})$

20: return $\mathcal{D}^{*}$

21:end procedure

Algorithm 2 The GOBI* scheduler

##  7 Extending GOBI to GOBI*

Now that we have a scheduling approach based on back-propagation of gradients,
we extend it to incorporate simulated results as described in Section 1. To do
this, we use the following components.

  1. 1.

GOBI Scheduler: We assume that we have the GOBI scheduler which can give us a
preferred action of interest $\bar{\mathcal{D}}$. Thus, at the start of a
scheduling interval $I_{t}$, we get $\bar{\mathcal{D}}=GOBI(I_{t})$ (line 8 in
Algorithm 2). $\mathcal{D}$ now denotes the decision of GOBI*.

  2. 2.

Utilization prediction models: We train a utilization metric prediction model,
such that using previous utilization metrics of the tasks, we get a predicted
utilization metric set for the next interval. As is common in prior work [50],
we use a Long-Short-Term-Memory (LSTM) neural network for this and train it
using the same $\Lambda$ dataset that we used for training the GOBI neural
approximator. Thus, at the start of interval $I_{t}$, using
$\bar{\mathcal{D}}$ from GOBI and checking allocation possibility, we get
$\hat{N_{t}}$ and $\hat{W}_{t-1}$. Using (3), we get $A_{t}$. Then, we predict
$\bar{\mathcal{U}}(a^{t}_{j}),\forall a^{t}_{j}\in A_{t}$, using the LSTM
model (line 7 in Algorithm 2). Hence, we get the $\phi(A_{t-1}),\phi(H_{t-1})$
matrices.

  3. 3.

Simulator: Now that we have an action $\bar{\mathcal{D}}$ and predicted
utilization metrics $\bar{\mathcal{U}}(a^{t}_{j}),\forall a^{t}_{j}\in A_{t}$,
we can use the simulator to predict the QoS parameters at the end of $I_{t}$
as described in Section 6.3 (lines 9 and 10 in Algorithm 2).

Figure 6: Iteration of GOBI* approach at the start of interval $I_{t}$

Since at the start of the interval $I_{t}$, we do not have utilization models
of all containers and subsequently hosts for $I_{t}$, our GOBI model is forced
to predict QoS metrics at the end of $I_{t}$ using only utilization metrics of
the previous interval, _i.e._ , $I_{t-1}$. This can make GOBI’s predictions
inaccurate in some cases. However, if we can predict with reasonable accuracy
the utilization metrics in $I_{t}$ using the utilization values of the
previous intervals, we can simulate and get an improved estimate of the QoS
parameters during the next period $I_{t}$. Adding these as inputs to another
neural approximator for $\mathcal{O}(P_{t})$ denoted as $f^{*}(x,\theta^{*})$,
we now have
$x=[\phi(A_{t-1}),\phi(H_{t-1}),\mathcal{O}(\bar{P}_{t}),\phi(\mathcal{D})]$.

Again, using a random scheduler and pre-trained GOBI model, we generate a
dataset $\Lambda^{*}$ to train this new neural approximator $f^{*}$. At
execution time, we freeze the neural model $f$ of GOBI and fine tune $f^{*}$
with the loss function. This loss function is the MSE of objective values. We
add the MSE between the predicted action $\mathcal{D}$ by GOBI* and
$\bar{\mathcal{D}}$ by GOBI in case the estimated objective value of GOBI is
lower than that of GOBI*. Thus,

$\mathcal{L}=MSE(\mathcal{O}(P_{t-1}),f^{*}([\phi(A_{t-2}),\phi(H_{t-2}),\phi(\mathcal{D}^{t-1})];\theta^{*}))\\\
+\mathbbm{1}(\mathcal{O}(\bar{P}_{t-1})<\mathcal{O}(P_{t-1}))\times
MSE(\bar{\mathcal{D}}^{t-1},\mathcal{D}^{t-1}).$ (14)

Using this trained model, we can now provide schedules as shown in Algorithm 2
and Figure 6. At interval $I_{t}$, the previous output of GOBI*, _i.e._ ,
$\mathcal{D}^{t-1}$ is given to the GOBI model as the initial decision. The
GOBI model uses utilization metrics to output the action $\hat{\mathcal{D}}$.
Using a single-step simulation, we obtain an estimate of the objective
function for this decision. Then, GOBI* uses this estimate to predict the next
action $D$. Based on whether GOBI*’s decision is better than GOBI or not,
GOBI* is driven to the decision which has lower objective value. This
interactive dynamic should allow GOBI* to make a more informed prediction of
QoS metrics for $I_{t}$ and hence perform better than GOBI.

###  7.1 Convergence of GOBI and GOBI*

We outline two scenarios of an ideal and a more realistic case to describe the
interactive dynamic between GOBI and GOBI* and how the latter optimizes the
objective scores.

Ideal Case: Consider the case when the neural approximator of GOBI, $f$ can
perfectly predict the objective value of the next interval $I_{t}$ as
$\mathcal{O}(P_{t})$. In this case, the predicted action $\bar{\mathcal{D}}$
is optimal. In such a setting, we expect GOBI* to converge such that it
predicts the same action as $\bar{\mathcal{D}}$. Assuming an ideal simulator
which exactly mimics the real-world,
$\mathcal{O}(\bar{P}_{t})=\mathcal{O}(P_{t})$. Thus, any action other than
$\bar{\mathcal{D}}$ is sub-optimal. Hence, to minimize the loss metric, GOBI*
would directly forward $\bar{\mathcal{D}}$ and ignore all other information
and converge to GOBI (which is optimal).

Real Case: While the limited explainability of neural networks prevent us from
giving formal convergence properties, we supply of number of technical
observations that justify the convergence we have seen in practice when
applying the methods to real systems. Thus, considering the real-case, time-
bound training only gives a sub-optimal approximator $f$ for GOBI. Hence, in
general the predicted decision ${\mathcal{D}}$ is not always optimal. Assuming
GOBI* predicts a decision other than GOBI, GOBI* will sometimes get a sub-
optimal action ${\mathcal{D}}$ such that
$\mathcal{O}(\bar{P}_{t})<\mathcal{O}(P_{t})$ and other times
$\mathcal{O}(\bar{P}_{t})>\mathcal{O}(P_{t})$. The former is the case when the
action predicted by GOBI, $\bar{\mathcal{D}}$, is better and the latter is the
case when the GOBI* action, ${\mathcal{D}}$, has a lower objective score. (1)
In the case of ${\mathcal{D}}$ being better than $\bar{\mathcal{D}}$ (having
lower objective score), in an attempt to minimize the first part of the loss,

$\mathcal{L}_{1}=MSE(\mathcal{O}(P_{t-1}),f^{*}([\phi(A_{t-2}),\phi(H_{t-2}),\phi(\mathcal{D}^{t-1})];\theta^{*})),$
(15)

GOBI* would converge to avoid $\bar{\mathcal{D}}$ (considering the ideal
simulator that returns exact answers). Furthermore, the predicted action
$\mathcal{D}$ has a lower objective score, hence the optimization loop would
tend to converge to this or better scheduling decisions. (2) In the case of
$\bar{\mathcal{D}}$ being better than ${\mathcal{D}}$, which means that
$\mathcal{O}(\bar{P}_{t-1})<\mathcal{O}(P_{t-1})$, GOBI* is given an incentive
to predict $\bar{\mathcal{D}}$. This is because the latter part of the loss
makes the model converge such that it minimizes

$\mathcal{L}_{2}=MSE(\bar{\mathcal{D}}^{t-1},\mathcal{D}^{t-1}).$ (16)

This, with the former part of the loss, creates an interactive dynamic such
that the GOBI* model can find scheduling decisions even better than the one
predicted by the GOBI model. However, in cases when GOBI*’s prediction is
worse, the GOBI’s prediction aids the model to quickly converge to a better
decision (that of GOBI’s). Thus, in both cases, each model update based on the
loss in Eq. (14), yields a scheduling decision with objective score same or
lower than that given by GOBI. Assuming a sufficiently long training time,
GOBI* would eventually converge to predict $\mathcal{D}$ such that the
objective value when the decision is $\mathcal{D}$ is never greater than when
it is $\bar{\mathcal{D}}$. We observe in our experiments that in the real-case
GOBI* always performs better than GOBI in terms of objective scores. The
interactive training with simulations allows GOBI* to converge quickly and
adapt to volatile environments.

The convergence plots for GOBI* are shown in Figure 7. It demonstrates that as
the model gets trained, the probability of the GOBI*’s actions being better
than GOBI increases. This means that initially $\mathcal{L}_{2}$ has a high
contribution to the loss for model training which aids GOBI* to quickly
converge to GOBI’s performance. This can be seen by the sudden drop in
$\mathcal{L}_{1}$ in Figure 7(a). This is also shown by Figure 7(b) that
GOBI*’s loss converges faster with the additional $\mathcal{L}_{2}$ component.

(a) Components of GOBI* loss.

(b) Comparison without $\mathcal{L}_{2}$

Figure 7: Convergence plots for GOBI*.

##  8 Performance Evaluation

###  8.1 Experimental Setup

To test the efficacy of the proposed approaches and compare against the
baseline methods, we perform experiments on both simulated and physical
platforms. As COSCO has the same underlying models of task migration, workload
generation and utilization metric values for both simulation and physical
test-bench, we can test all models on both environments with the same
underlying assumptions. As in prior work [51], we use $\alpha=\beta=0.5$ in
(8) for our experiments. Moreover, we consider all tasks, to be allocated and
migrated, in batches with each batch having feature vectors corresponding to
up to $M=|H|^{2}$ tasks. If number of tasks is less than $M$, we pad the input
matrix with zero vectors. This style of inference strategy is in line with
prior work [3]. This is due to the limitation of non-recurrent neural networks
to take a fixed size input for a single forward pass, hence requiring action
inference for tasks being executed in batches.

Physical Environment: We use the Microsoft Azure cloud provisioning platform
to create a test-bed of 10 VMs located in two geographically distant
locations. The gateway devices are considered to be in the same LAN of the
server which was hosted in London, United Kingdom. Of the 10 VMs, 6 were
hosted in London and 4 in Virginia, United States. The host capacities
$\mathcal{C}(h_{i})\forall h_{i}\in H$ are shown in Table III and Table V. All
machines use Intel Haswell 2.4 GHz E5-2673 v3 processor cores. The cost per
hour (in US Dollar) is calculated based on the costs of similar configuration
machines offered by Microsoft Azure at the datacenter in the South UK
region333Microsoft Azure pricing calculator for South UK
https://azure.microsoft.com/en-gb/pricing/calculator/. The power consumption
models are taken from the SPEC benchmarks repository444More details in
Appendix D. We run all experiments for 100 scheduling intervals, with each
interval being 300 seconds long, giving a total experiment time of 8 hours 20
minutes. We average over 5 runs and use diverse workload types to ensure
statistical significance.

TABLE III: Host characteristics of Azure fog environment.

Name | Quantity | Core | MIPS | RAM | RAM | Ping | Network | Disk | Cost | Location
---|---|---|---|---|---|---|---|---|---|---
count | Bandwidth | time | Bandwidth | Bandwidth | Model
Edge Layer
Azure B2s server | 4 | 2 | 4029 | 4295 MB | 372 MB/s | 3 ms | 1000 MB/s | 13.4 MB/s | 0.0472 $/hr | London, UK
Azure B4ms server | 2 | 4 | 8102 | 17180 MB | 360 MB/s | 3 ms | 1000 MB/s | 10.3 MB/s | 0.1890 $/hr | London, UK
Cloud Layer
Azure B4ms server | 2 | 4 | 8102 | 17180 MB | 360 MB/s | 76 ms | 1000 MB/s | 10.3 MB/s | 0.166 $/hr | Virginia, USA
Azure B8ms server | 2 | 8 | 2000 | 34360 MB | 376 MB/s | 76 ms | 2500 MB/s | 11.64 MB/s | 0.333 $/hr | Virginia, USA

Simulation Environment: We consider 50 hosts machines as a scaled up version
of the 10 machines from the last subsection. Here, each category has 5 times
the instance count to give a total of 50 machines in a comparatively larger-
scale fog environment as considered in prior art [5, 52]. As we cannot place
simulated nodes in geographically distant locations, we model the latency and
networking characteristics of these nodes in our simulator as per Table III.

###  8.2 Model Training and Assumptions

For the GOBI and GOBI* algorithms we use standard feed-forward neural models
with the following characteristics adapted from [3]. We use non-affine
activation functions for our neural approximators to be differentiable for all
input values.

  * •

Input layer of size $M\times F+|H|\times F^{\prime}+M\times N$ for GOBI and
$M\times F+|H|\times F^{\prime}+M\times N+1$ for GOBI*. The non-linearity used
here is softplus555The definitions of these activation functions can be seen
at the PyTorch web-page: https://pytorch.org/docs/stable/nn.html as in [3].
Note, $|H|$ may vary from 10 in tests in the physical environment to 50 in the
simulator.

  * •

Fully connected layer of size $128$ with softplus activation.

  * •

Fully connected layer of size $64$ with tanhshrink activation.

  * •

Fully connected layer of size $1$ with sigmoid activation.

To implement the proposed approach, we use PyTorch Autograd package [53] to
calculate the gradients of the network output with respect to input keeping
model parameters constant. We generate training data for the GOBI model $f$ by
running a random scheduler for 2000 intervals on the simulator. We then run
the random scheduler on the framework for 300 intervals and fine-tune the GOBI
model on this new dataset. For GOBI*, we use a random scheduler and
predictions of the GOBI model $f$ to generate data of the form described in
Section 5 of size 2000 on simulator and fine-tune it on data corresponding to
300 intervals on the framework. The dataset was used to create the matrices
$[\phi(A_{t-1}),\phi(H_{t-1}),\phi(\mathcal{D})]$, where each column of
$\phi(A_{t-1}),\phi(H_{t-1})$ is normalized by the maximum and minimum
utilization values, and $\phi(\mathcal{D})$’s rows are one-hot decision
vectors. To train a model, we use the AdamW optimizer [54] with learning rate
$10^{-5}$ and randomly sample 80% of data to get the training set and the rest
as the cross-validation set666All model training and experiments were
performed on a system with configuration: Intel i7-10700K CPU, 64GB RAM,
Nvidia GTX 1060 and Windows 10 Pro OS.. The convergence criterium used for
model training is the loss of consecutive epochs summed over the last 10
epochs is less than $10^{-2}$. For GOBI*, we also train predictors for
utilization metrics. Specifically, we use a LSTM neural network [55] with a
single LSTM cell to achieve this and train it using the same dataset used to
train the GOBI model.

###  8.3 Workloads

To generate workloads for training the GOBI and GOBI* models and testing them
against baseline methods, we use two workload characteristics Bitbrain traces
and DeFog applications. These were chosen because of their non-stationarity,
their highly volatile workloads and their similarity with many real-world
applications.

  1. 1.

BitBrain traces. The dynamic workload is generated for cloudlets based on the
real-world, open-source Bitbrain dataset [56]777The BitBrain dataset can be
downloaded from: http://gwa.ewi.tudelft.nl/datasets/gwa-t-12-bitbrains. This
dataset consists of real traces of resource utilization metrics from 1750 VMs
running on BitBrain distributed datacenter. The workloads running on these
servers are from a variety of industry applications including computational
analytical programs used by major banks, credit operators and insurers [56]
and are commonly used for benchmarking fog-cloud models [3, 57, 58]. The
dataset consists of workload information for each time-stamp (separated by 5
minutes) including the number of requested CPU cores, CPU usage in terms of
Million Instructions per Second (MIPS), RAM requested with Network
(receive/transmit) and Disk (read/write) bandwidth characteristics. These
different categories of workload data constitute the feature values of
$\phi(A_{t-1})$ and $\phi(H_{t-1})$. As these workload traces correspond to
applications running on real infrastructure, we use these to run our
simulations and generate training data. At the start of each interval $I_{t}$,
the size of the new tasks $N_{t}$ set follows a discrete Poisson
distribution888The Poisson distribution models the number of independent
arrivals that occur in a period, so it is apt to model for a batch size if the
batch is formed by arrivals in a time window (scheduling interval in our
case). $Poisson(\lambda)$, as per prior works [3, 59]. Here, $\lambda=1.2$
jobs for $|H|=10$ and $\lambda=5$ jobs for $|H|=50$.

  2. 2.

DeFog applications. DeFog [60] is a fog computing benchmark which consists of
six real-time heterogeneous workloads such as Yolo, Pocketspinx, Aeneas,
FogLamp and iPokeMon. We use three specific heterogeneous applications of
DeFog: Yolo (Memory, Bandwidth and Compute Intensive benchmark), PockeSphinx
(Compute Intensive) and Aeneas (Bandwidth Intensive). Yolo runs with 1500 user
requests and each request uploads a unique image with different density and
can run upto three intervals. PochetSpinhx runs with 320 user requests and
Aneases with 1500. Here too, at the start of each interval $I_{t}$, the size
of the new tasks $N_{t}$ set follows a Poisson distribution $Poisson(\lambda)$
with $\lambda=1.2$ jobs. Out of the $N_{t}$ tasks, the distribution of
selection of Yolo/Pocketsphinx/Aeneas follows the probabilities of
$(p_{y},p_{p},p_{a})$ for a run. For our final comparison experiments we run
using $p_{y}=p_{p}=p_{a}=0.33$. However, to test diverse workload
characteristics, we also run using any one as $0.80$ and other two as $0.10$.
We call these workload dominant runs. We perform all our experiments to
compare with baselines using the DeFog benchmarks.

###  8.4 Baseline Models

We evaluate the performance of the proposed algorithms and compare them
against the state-of-the-art scheduling approaches. The reasons for comparing
against these baselines are described in Section 2. We consider two light-
weight heuristic based schedulers LR-MMT and MAD-MC that have low scheduling
times, but higher energy consumption, response times and SLO violations. We
also consider a deep-learning based gradient-free optimization method GA, and
two reinforcement-learning based schedulers DQLCM and A3C. Finally, we compare
against a one max-weight based allocation method POND.

(a) Average Energy Consumption

(b) Average Response Time

(c) Average Execution Time

(d) Fraction of SLO Violations

(e) Average Migration Time

(f) Average Response Time (per application)

(g) Average Wait Time (per application)

(h) Average SLO Violations (per application)

(i) Scheduling Time versus execution time

(j) Average Scheduling Time

(k) Average Wait Time

(l) Fairness

Figure 8: Comparison of GOBI and GOBI* against baselines on framework with 10
hosts

(a) Average Energy Consumption

(b) Average Response Time

(c) Execution Time

(d) Migration Time

(e) Fairness

(f) Fraction of SLO Violations

(g) Average Scheduling Time

(h) Average Wait Time

Figure 9: Comparison of GOBI and GOBI* against baselines on simulator with 50
hosts

###  8.5 Evaluation Metrics

We use the following evaluation metrics to test the GOBI and GOBI* models as
motivated from prior works [5, 3, 1, 43, 9]. We also use $AEC$ and $ART$ as in
Section 5.

  1. 1.

SLO Violations which is given as

$\frac{\sum_{t}\sum_{l^{t}_{j}\in L_{t}}\mathbbm{1}(Response\
Time(l^{t}_{j})\leq\psi(l^{t}_{j}))}{\sum_{t}|L_{t}|},$

where $\psi(l^{t}_{j})$ is the 95th percentile response time for this
application type (Yolo/PocketSphinx/Aeneas for DeFog and random/sequential for
Bitbrain) on the state of the art baseline A3C. This definition of percentile-
based SLO is defined for the response time metrics of completed tasks and is
inspired from [61].

  2. 2.

Fairness which is given as the Jain’s Fairness Index

$\frac{(\sum_{t}\sum_{l^{t}_{j}\in L_{t}}Response\
Time(l^{t}_{j}))^{2}}{(\sum_{t}|L_{t}|)\times(\sum_{t}\sum_{l^{t}_{j}\in
L_{t}}Response\ Time(l^{t}_{j})^{2})}.$

  3. 3.

Average Migration Time which is the average time for the migration of tasks
over all intervals in the run

$\frac{\sum_{t}\sum_{(a_{j}^{t},h_{i})\in\hat{\mathcal{D}}(A_{t})}Migration\
Time(a_{j}^{t},h_{i})}{\sum_{t}|\hat{\mathcal{D}}(A_{t})|}.$

  4. 4.

Scheduling Time which is the average time to reach the scheduling decision
over all intervals in the run.

  5. 5.

Average Wait Time which is the average time for a container in the wait queue
before it starts execution.

###  8.6 Results

In this section we provide comparative results, showing how GOBI and GOBI*
perform against other baselines as described in Section 8.4. We compare the
proposed approaches with respect to the evaluation metrics described in
Section 8.5. Additional results are given in Appendix E. The graphs in Figure
8 show the results for runs with length of 100 scheduling intervals viz 8
hours 20 minutes using the DeFog workloads on 10 physical Azure machines.
Figure 9 shows similar trends in the result for 50 hosts in a simulated
environment.

Figure 8(a) shows the energy consumption of Azure host machines for each
scheduling policy. Among the baseline approaches, A3C consumes the least
average interval energy of $221.63$ KW-hr. Running the GOBI approach on the
Azure platform consumes $193.11$ KW-hr, $12.86\%$ lower than A3C. Further,
GOBI* consumes the least energy $188.26$ KW-hr ($15.05\%$ lower than that of
A3C). The major reason for this is the low response time of each application,
which leads to more tasks being completed within the same duration of 100
intervals. Thus, even with similar energy consumption across all policies,
GOBI and GOBI* have a much higher task completion rate of 112-115 tasks in 100
intervals compared with only 107 tasks. Similarly, when we consider 50 host
machines in a simulated platform (Figure 9(a)), GOBI* still consumes $9.39\%$
lower than A3C. The energy consumption with GOBI is very close to A3C.

Figure 8(b) shows the average response time for each policy. Here, response
time is the time between the creation of a task from an IoT sensor and up to
the gateway receiving the response. Among the baselines models, POND has the
lowest average response time of $266.53$ seconds. Here, GOBI and GOBI* have
$226.04$ and $156.09$ seconds ($15.19\%-41.43\%$ better than POND). For the
three applications, the average response time for each policy is shown in
Figure 8(f). Clearly, among the DeFog benchmark applications, Yolo takes the
maximum time. The highest response time for Yolo among all policies is for GA
as it prefers scheduling shorter jobs first _i.e._ Pocketsphinx and Aeneas to
reduce response time. This is verified by the results which show that Aeneas
has the lowest response time when the GA policy is used. Another disadvantage
of this preference is that it leads to high wait times when running the GA
policy. However, in larger scale experiments on 50 hosts in simulation (Figure
9(b)), GA has much lower wait times leading to the best response times among
the baseline algorithms. Here, compared to GA, GOBI and GOBI* have
$17.98\%-20.87\%$ lower average response times, respectively.

Figure 14(g) shows the average waiting time (in intervals) for tasks running
on the Azure framework with each policy. As prior works have established that
RL approaches are slow to adapt in highly volatile environments [3, 62], the
A3C and DQLCM approaches are unable to adapt when a host is running at
capacity. This means that for a large number of scheduling intervals
($47.72\%$), they predict an overloaded host. Hence, the task cannot be
assigned in the same interval and has to wait until either it is assigned to
another host, or the resources of this host are released. This is also
reflected in the wait time per application (Figure 8(g)). As established in
prior work, reinforcement-learning approaches scale poorly and hence this
waiting time gets more pronounced when running with 50 hosts (Figure 15(g)).
However, as GOBI and GOBI* are able to adapt quickly to the environment,
because of the neural model update in each iteration, they do not face such
problems even on larger scale experiments.

As seen in Figure 8(d), due to the high response times of the baseline
approaches, they have a high SLO violation rate. For the experiments of
physical hosts, as POND has the lowest response time, the SLO violation rate
is also the lowest among the baselines ($2.75\%$). GOBI has only $0.9\%$ SLO
violations and GOBI* has none. This is due to the back-propagation approach
which minimizes the response time, as well as avoiding local optima using the
adaptive moment estimation approach (Adam optimizer). For GOBI, the SLO
violations are only for Yolo tasks ($4.5\%$). In the simulation environment,
due to the high wait and response times of the A3C, DQLCM and POND schedulers,
their SLO violation rates are highest among all methods. Here, GOBI has only
$1.1\%$ SLO violations. Due to the high response times of A3C and DQLCM for 50
hosts, the SLO itself is much higher giving the GA approach with low response
times only $0.2\%$ SLO violations. GOBI* has no SLO violations in this case as
well.

The main reason for low response times in GOBI and GOBI* is their low
scheduling time. Even with single-step simulation, the back-propagation based
optimization strategy with the AdamW optimizer converges faster than the
gradient-free optimization methods like A3C, DQLCM GA and POND. This is
apparent from the scheduling times seen in Figures 8(j) and 8(i) (shaded
region shows the 95% confidence interval). Here, MAD-MC has the lowest
scheduling time, with GOBI next at $2.65$ seconds and GOBI* at $5.88$ seconds.
Even with 50 hosts (Figure 9(g)), GOBI and GOBI* have one of the lowest
scheduling times across all policies (except MAD-MC).

Figure 8(e) shows the average migration times for all polices. Here, GA has
the highest migration time due to the largest number of migrations. This is as
expected due to the non-local jumps in the GA approach which lead to a high
number of migrations. Approaches like the back-propagation method (GOBI and
GOBI*) and RL based approaches (A3C and DQLCM) have comparatively low
migration times. A similar trend is also apparent with 50 hosts as seen in
Figure 9(d). Due to convergence to better optima, the execution times itself
for iterative optimization approaches including GOBI, GOBI* and GA are the
lowest among all approaches (Figures 8(c) and 9(c)). Finally, Figures 8(l) and
9(e) show that GOBI and GOBI* are the most fair schedulers.

###  8.7 Comparing GOBI and GOBI*

Now that GOBI and GOBI* have been shown to out-perform prior works, we
directly compare the two approaches. Table IV shows GOBI* has a lower
objective value ($16.4\%$) and prediction error of objective value ($14.2\%$)
for the next interval. This clearly shows that GOBI* can optimize the
objective value better than GOBI. This is because GOBI predicts the objective
value for the interval $I_{t}$ using only the utilization metrics of interval
$I_{t-1}$. However, GOBI* has more information as the LSTM models predict
utilization metrics for $I_{t}$ and the GOBI model gives a tentative action,
which is then used to simulate $I_{t}$ and get a reasonable estimate of the
objective value for $I_{t}$. This estimate with the utilization metrics of
$I_{t-1}$ aid GOBI* to have much closer predictions and hence better
scheduling decisions. However, the scheduling time of GOBI* is more than twice
that of GOBI. This makes the GOBI approach more appropriate for environments
with resource constrained servers.

TABLE IV: Comparison between GOBI and GOBI*

Algorithm | Scheduling Time | Objective Value | MSE
---|---|---|---
GOBI | 2.65$\pm$0.019 s | 0.5673 | 2.31$\pm$0.15$\times 10^{-3}$
GOBI* | 5.88$\pm$0.015 s | 0.4744 | 1.98$\boldsymbol{\pm}$0.22$\boldsymbol{\times 10^{-3}}$

##  9 Conclusions and Future Work

We have presented a coupled-simulation approach to leverage simulators to
predict the QoS parameters and make better decisions in a heterogeneous fog
setup. The presented COSCO framework allows deployment of a holistic platform
that provides an easy to use interface for scheduling policies to access
simulation capabilities. Moreover, we have presented two scheduling policies
based on back-propagation of gradients with respect to input, namely GOBI and
GOBI*. These approaches use neural approximators to model objective scores for
the scheduling decisions. GOBI* uses GOBI, predictors of utilization
characteristics and an underlying simulator to better predict the objective
values leading to better decisions. Comparing GOBI and GOBI* against state-of-
the-art schedulers using real-world fog applications, we see that our methods
are able to reduce energy consumption, response time, SLO violations and
scheduling time. Between GOBI and GOBI*, GOBI* gives better QoS values;
however, GOBI is more suitable for resource constrained servers.

For the future, we propose to extend the COSCO framework to allow workflow
models for serverless computing. Extending to serverless would allow us to
perform fine-grained auto-scaling, increase productivity and improve
flexibility and logistics [63]. For the back-propagation approach, we wish to
extend our methods to consider layer types and activations like recurrent,
convolution or residual with Rectified Linear Units (ReLU). This is because
such non-differentiable functions are increasingly being used to approximate
diverse objective functions. More advanced layer types would also allow us to
model temporal and spatial characteristics of the environment.

## Software Availability

The code is available at https://github.com/imperial-qore/COSCO. The Docker
images are available at https://hub.docker.com/u/shreshthtuli. The training
datasets and execution traces are available at
https://doi.org/10.5281/zenodo.4897944, released under the CC BY 4.0 license.

## Author Contributions

S.T. designed and implemented the COSCO framework with GOBI, and GOBI*
algorithms. S.P aided in software debugging. S.T. designed and conducted the
experiments. S.T., S.P., G.C and N.R.J analyzed the experimental results. S.T,
G.C. and N.R.J. wrote the paper. G.C., S.N.S and N.R.J supervised the project.

## Acknowledgments

S.T. is grateful to the Imperial College London for funding his Ph.D. through
the President’s Ph.D. Scholarship scheme. S.P. is supported by the European
Social Fund via IT Academy program. The work of S.T. and G.C. has been partly
funded by the EU’s Horizon 2020 program under grant agreement No 825040.

##  Appendix A Implementation of COSCO framework

Figure 10: UML class diagram of the COSCO framework

We present the implementation details of the simulator and framework with the
interface details. To implement the COSCO framework, we use object-oriented
programming model and realize it using the Python programming language. We now
provide details of various Python classes which together consolidate to the
complete framework. A UML class diagram of the COSCO framework is shown in
Figure 10.

The hosts are instantiated/simulated using the Datacenter class which provides
a list of Host objects to the simulator or framework. These Host objects might
correspond to simulated hosts or physical compute nodes with Instructions per
second (IPS), RAM, Disk and Bandwidth capacities with communication latency
and power consumption models with CPU utilization. The workloads are generated
by the Workload class. These are either time-series models of IPS, RAM, Disk,
Bandwidth requirements in the case of simulation or are actual application
programs in the case of physical experiments. At the beginning of each
scheduling interval, a Workload object creates a list of workloads ($N_{t}$)
and also maintains a waiting queue for workloads that could not be allocated
in a prior interval ($W_{t-1}$). Moreover, the Scheduler class allows taking
scheduling decisions in the form of task selection (getSelection()) and
placement (getPlacement()). Task selection function selects the containers
that need to be migrated to another host; task placement function returns the
target host for each selected or new container.

###  A.1 Modelling of Computational Utilization

The utilization metric indirectly used for our experiments is the % CPU
consumption, which is used as part of the workload and host characteristics
(input to the neural approximators). However, as part of the host capacity
characteristics, IPS is taken by running SPEC benchmark using the “perf stat”
command on real systems to obtain an approximation of how many maximum number
of instructions per second a host can execute. For host/workload utilization
characteristics, using the % CPU utilization, we get the % CPU time allocated
to a particular task for that interval. We also get the number of instructions
executed using the “perf stat” command. This allows us to calculate an
“average” number of instructions executed per second for each workload.
Summing this IPS for each host over all running workloads on that host gives
us the IPS of that host. Thus, the above-mentioned calculation in our physical
experiments gives us a proxy to the IPS metric commonly referred to in
simulated scenarios. This makes the IPS used in our model is agnostic to the
underlying infrastructure (simulator/physical setup), being taken directly
from the Bitbrain traces in our simulation experiments and being calculated
from the % CPU utilization in our physical experiments.

###  A.2 Simulator

The Simulator class consists of a Stats object, Scheduler object, lists of
Host and Task objects. A Stats object saves the utilization metrics of host
and containers, allocation decisions, QoS parameters and workload
characteristics for each scheduling interval. The Scheduler object, as
described earlier, uses the utilization metrics and QoS parameters to take an
allocation decision for new workloads or migration decisions for active
workloads. The migration time of a container is calculated by summing the
networking latency with the time it takes to transfer the container based on
its size and the network bandwidth. Naturally, if the container is on one of
the edge or cloud layers and is migrated to the same layer, we assume no
network latency, but if it is transferred across layers, we also include the
latency. At the end of each interval, the Stats object calculates the QoS
parameters like energy using the power models of each host and utilization
metrics.

###  A.3 Framework

The Framework class consists of the objects in the Simulator class with some
additional objects for container orchestration. We use the Ansible framework
[64] to autonomously provision, deploy and manage physical host machines in a
fog environment. Each Task object here is a Docker container. Docker is a
container management platform as a service used to build, ship and run
containers on physical or virtual environments [52]. Moreover, the Host
objects of Framework are physical computational nodes in the same Virtual
Local Area Network (VLAN) as the server machine on which the Python program
runs. The server communicates with each Host via HTTP REST APIs [65]. The REST
server of the Framework sends operation codes including GetHostStats,
GetContainerStats, Checkpoint, Migrate, Restore to each host to instruct a
specific activity. At every Host machine, a DockerClient service runs with a
Flask HTTP web-service [48]. Flask is web application REST client which allows
interfacing between Hosts and the server.

A Host receives operation codes from the server and returns HTTP response.
Before starting execution of containers, the server gets the utilization
metric capacities from each host ($\mathcal{C}(h_{i}),\forall h_{i}\in H$).
GetHostStats returns the host utilization metrics of host, GetContainerStats
returns utilization metrics of each individual container running in the host.
All migrations are performed in parallel using Joblib library in Python. The
allocation and migrations are done in a non-blocking fashion, i.e. the
execution of active containers is not halted when some tasks are being
migrated. All utilization metrics are synchronized among devices via a time-
series database, namely InfluxDB [66].

TABLE V: Power consumption of Azure instances with percent CPU utilization. Name | SPEC Power (Watts) for different CPU percentage usages
---|---
0% | 10% | 20% | 30% | 40% | 50% | 60% | 70% | 80% | 90% | 100%
Azure B2s server | 75.2 | 78.2 | 84.1 | 89.6 | 94.9 | 100.0 | 105.0 | 109.0 | 112.0 | 115.0 | 117.0
Azure B4ms server | 71.0 | 77.9 | 83.4 | 89.2 | 95.6 | 102.0 | 108.0 | 114.0 | 119.0 | 123.0 | 126.0
Azure B4ms server | 71.0 | 77.9 | 83.4 | 89.2 | 95.6 | 102.0 | 108.0 | 114.0 | 119.0 | 123.0 | 126.0
Azure B8ms server | 68.7 | 78.3 | 84.0 | 88.4 | 92.5 | 97.3 | 104.0 | 111.0 | 121.0 | 131.0 | 137.0

##  Appendix B Gradient with respect to Input for other activations

We present the gradients with respect to input for the softplus() and
tanhshrink() activation functions.

######  Proposition 2 (Gradient of $\textsf{softplus}()$).

For a linear layer with softplus() non-linearity that is defined as follows:

$f(x;W,b)=\textsf{softplus}(W\cdot x+b),$

the derivative of this layer with respect to $x$ is given as:

$\nabla_{x}f(x;W,b)=W^{T}\times\textsf{sigmoid}(W\cdot x+b).$

###### Proof.

It is well known that $\nabla_{x}\textsf{sofptlus}(x)=\textsf{sigmoid}(x)$,
therefore,

$\displaystyle\nabla_{x}f(x;W,b)$
$\displaystyle=\nabla_{x}\textsf{softplus}(W\cdot x+b)$
$\displaystyle=\nabla_{W\cdot x+b}\textsf{softplus}(W\cdot
x+b)\times\nabla_{x}(W\cdot x+b)$ $\displaystyle=\textsf{sigmoid}(W\cdot
x+b)\times\nabla_{x}(W\cdot x+b)$
$\displaystyle=W^{T}\times\textsf{sigmoid}(W\cdot x+b)\qed$

######  Proposition 3 (Gradient of $\textsf{tanhshrink}()$).

For a linear layer with tanhshrink() non-linearity that is defined as follows:

$f(x;W,b)=\textsf{tanhshrink}(W\cdot x+b),$

the derivative of this layer with respect to $x$ is given as:

$\nabla_{x}f(x;W,b)=W^{T}\times\textsf{sigmoid}(W\cdot x+b).$

###### Proof.

As $\textsf{tanhshrink}(x)=x-\textsf{tanh}(x)$, thus

$\displaystyle\nabla_{x}\textsf{tanhshrink}(x)$
$\displaystyle=1-\nabla_{x}\textsf{tanh}(x)$
$\displaystyle=1-(1-\textsf{tanh}^{2}(x))$
$\displaystyle=\textsf{tanh}^{2}(x),$

therefore,

$\displaystyle\nabla_{x}f(x;W,b)$
$\displaystyle=\nabla_{x}\textsf{tanhshrink}(W\cdot x+b)$ $\displaystyle=\ $
$\displaystyle\nabla_{W\cdot x+b}\textsf{tanhshrink}(W\cdot
x+b)\times\nabla_{x}(W\cdot x+b)$ $\displaystyle=\ $
$\displaystyle\textsf{tanh}^{2}(W\cdot x+b)\times\nabla_{x}(W\cdot x+b)$
$\displaystyle=\ $ $\displaystyle W^{T}\times\textsf{tanh}^{2}(W\cdot
x+b)\qed$

##  Appendix C Training GOBI and GOBI* models

Figure 11: Loss and scheduling overhead as a function of the number of hidden
layers.

###  C.1 Model search

To determine the optimum number of layers in our feed-forward neural model, we
analyze the scheduling overhead of the GOBI approach with the number of hidden
layers. The scheduling overhead is calculated as the average time it takes to
take a scheduling decision in our simulated setup. As shown in Figure 11, the
value of the loss function decreases with the increase in the number of layers
of the neural network. This is expected because as the number of layers
increase so do the number of parameters and thus the ability of the network to
fit more complex functions becomes better. The scheduling overhead depends on
the system on which the simulation is run (the fog broker), and for the
current experiments, the system used had CPU - Intel i7-10700K and GPU -
Nvidia GTX 1060 graphics card (4GB graphics RAM). As shown in the figure,
there is an inflection point at 2 hidden layers because a network with 2 or
more such layers could not fit with the input batch in the GPU graphics RAM
and had to be run on CPU, increasing inference times. Based on the available
simulation infrastructure, for the comparison with baseline algorithms, we use
the neural network with 2 hidden layers based on the above described grid
search approach.

(a) GOBI

(b) GOBI*

Figure 12: Training graphs for simulated setup with 50 nodes.

(a) GOBI

(b) GOBI*

Figure 13: Training graphs for framework setup with 10 nodes.

(a) Average CPU Utilization of hosts

(b) Average Number of active containers per interval

(c) Average Cost per container (US Dollars)

(d) Fairness per application

(e) Average number of migrations

(f) Average Migration Time with execution time

(g) Average Wait Time with execution time

(h) Average Response Time with execution time

Figure 14: Comparison of GOBI and GOBI* against baselines on framework with 10
hosts

(a) Average CPU Utilization of hosts

(b) Average Number of active containers with simulation time

(c) Average Cost per container (US Dollars)

(d) Average Scheduling Time

(e) Average number of migrations

(f) Average Migration Time with simulation time

(g) Average Wait Time with simulation time

(h) Average Response Time with simulation time

Figure 15: Comparison of GOBI and GOBI* against baselines on simulator with 50
hosts

###  C.2 Model Training

To train the neural approximator $f$ of the GOBI model, we first form a
dataset by running a random scheduler which gives us data of the form
$\Lambda=\\{[\phi(A_{t-1}),\phi(H^{t-1}),\phi(\mathcal{D})],\mathcal{O}(P_{t})\\}_{t}$.
The random scheduler selects a random number of tasks at any interval $I_{t}$
and decides to migrate them to any host uniformly at random. Using this, we
train our model $f(x;\theta)$ such that
$\theta=\operatorname*{arg\,min}_{\hat{\theta}}{\sum_{(x,\phi(\mathcal{D}))\in\Lambda}[\mathcal{L}(f(x;\hat{\theta}),\phi(\mathcal{D}))]}$.
We split the dataset into $80\%$ as training data and the rest $20\%$ for
testing. We use Mean Square Error (MSE) as the loss function with AdamW
optimizer. We use learning rate of $10^{-3}$ and weight decay of $10^{-5}$.
The size of $\Lambda$ dataset to train the GOBI model was $2000$ for both
cases of $10$ and $50$ hosts.

To train the neural approximator $f^{*}$ of the GOBI* model, we first train
LSTM models to predict the utilization metrics in $I_{t}$ using the
utilization values of the previous intervals. Using the decision output from
the GOBI model and the predicted utilization metrics, we simulate and get an
estimate of $I_{t}$’s QoS parameters. Adding these in the dataset, we now have
$\Lambda^{*}=\\{[\phi(A_{t-1}),\phi(H^{t-1}),\mathcal{O}(\bar{P}_{t}),\phi(\mathcal{D})]\\}$,
which we use to train $f^{*}(x,\theta^{*})$. Figures 12 and 13 show the loss
on the test set with epochs for different models.

As dataset generation from event-driven simulator is much faster than actual
execution on physical systems, to train models for the framework, we first
pre-train using a dataset of size $2000$ (generated using simulations) and
then fine-tune using a smaller dataset generated by running on physical setup
of size $200$. We train on the dataset generated using the simulator for $600$
epochs and till convergence on the dataset generated on the physical setup.
This accounts for the sudden change in the loss values seen in Figure 13 at
the $600$-th epoch.

##  Appendix D Power Models of Azure Hosts

The power consumption values of increments of 10% CPU utilization of Azure
virtual machine types are taken from Standard Performance Evaluation
Corporation (SPEC) benchmark repository
https://www.spec.org/cloud_iaas2018/results/ and are shown in Table V. For
intermediate CPU utilization values we use linear interpolation to calculate
power consumption.

##  Appendix E Additional Results

Figures 14 and 15 show additional results on the azure testbed (with 10 hosts)
and simulation environment (with 50 hosts). We also show the Average Cost per
container given as

$\frac{\sum_{t}\sum_{h_{i}\in
H}\int_{t=t_{i}}^{t_{i+1}}C_{h_{i}}(t)dt}{\sum_{t}|L_{t}|},$

where $C_{h_{i}}(t)$ is the cost function of host $h_{i}$ at instant $t$.

Figures 14(a) and 15(a) show the mean CPU utilization of host machines
averaged across the whole execution duration. We see that the CPU utilization
is minimum for the POND baseline with average at $8.94\%$. Both GOBI and GOBI*
have a higher average CPU utilization by $2.78\%-6.12\%$. Figures 14(b) and
15(b) show the average number of active containers for the various scheduling
approaches. GOBI and GOBI*, in both cases, have the highest number of active
containers. This is due to the efficient placement of these two approaches
capable of executing multiple containers together. Figures 14(c) and 15(c)
show the average execution cost of all policies. For 10 hosts, all policies
have negligible difference in the average cost per container. For 50 hosts,
GOBI* and GOBI have $24.7\%$ and $26.3\%$ lower cost compared to the A3C
baseline, with GOBI having the least average cost among all policies.

(a) CPU utilization (%) of active containers with time

(b) CPU utilization (%) of hosts with time

Figure 16: Visualizing utilization metrics using the Grafana toolkit.

Figure 14(d) show the fairness metric for each application for all policies.
The A3C baseline is the least fair among all policies with the Jain’s indices
for each application being in the range $0.01-0.05$. Some other observations
include MAD-MC being fair to the Pocketsphinx application and GOBI being fair
to the Aeneas application. Average fairness index across applications is
highest for the GOBI* approach being $0.034$. Figures 14(e) and 15(e) show the
average number of container migrations for each policy. GOBI and GOBI* have
consistently low number of migrations ($140-174$). GOBI* has the least average
migration count in the case of 10 hosts ($146$). However, the A3C baseline has
the least migrations in the case of 50 hosts ($486$). Figures 14(f) and 15(f)
show the variation of average migration time with time. Migration times are
lowest for GOBI, GOBI* and heuristic based methods. Figures 14(g) and 15(g)
show the variation of average wait time for tasks with time. Wait times are
fairly stable for all policies except POND, A3C and DQLCM. This is because
POND fails to converge to solutions frequently after 60-th interval. The
reinforcement learning approaches, A3C and DQLCM are unable to quickly adapt
to volatile workloads in relatively larger scale setup and hence tend to
converge to infeasible migration decision (like migrating tasks to a host
running at capacity). This leads to gradually increasing wait times for tasks
in the simulated environment with 50 nodes. These effects are not as
pronounced in the physical setup with only 10 hosts (Figure 14(g)), Figures
14(h) and 15(h) show the variation of average response time for tasks with
time. Clearly, the response times are highly volatile due to the non-
stationary nature of the workloads. Overall, GOBI and GOBI* have the least
overall response times among all policies.

##  Appendix F Visualization of Utilization Metrics

We used the Grafana toolkit [67] to visualize the utilization metrics and
check the volatility of the workloads running in the fog environment. These
graphs are dynamically generated from the data in the InfluxDB [66] database.
Screenshots of a few workload visualizations are shown in Figure 16. The
figure demonstrates the significant volatility in the resource consumption of
containers across a few hours.

## References

  * [1] S. S. Gill, S. Tuli _et al._ , “Transformative effects of IoT, Blockchain and Artificial Intelligence on cloud computing: Evolution, vision, trends and open challenges,” _Internet of Things_ , vol. 8, pp. 100–118.
  * [2] A. Toor, S. ul Islam _et al._ , “Energy efficient edge-of-things,” _EURASIP Journal on Wireless Communications and Networking_ , vol. 2019, no. 1, p. 82, 2019.
  * [3] S. Tuli, S. Ilager _et al._ , “Dynamic Scheduling for Stochastic Edge-Cloud Computing Environments using A3C learning and Residual Recurrent Neural Networks,” _IEEE TMC_ , 2020.
  * [4] N. Wang, M. Matthaiou _et al._ , “DYVERSE: dynamic vertical scaling in multi-tenant edge environments,” _Future Generation Computer Systems_ , vol. 108, pp. 598–612, 2020.
  * [5] D. Basu, X. Wang _et al._ , “Learn-as-you-go with megh: Efficient live migration of virtual machines,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 30, no. 8, pp. 1786–1801, 2019.
  * [6] K. Han, Z. Xie _et al._ , “Fog computing task scheduling strategy based on improved genetic algorithm,” _Computer Science_ , vol. 4, p. 22, 2018.
  * [7] X.-Q. Pham, N. D. Man _et al._ , “A cost-and performance-effective approach for task scheduling based on collaboration between cloud and fog computing,” _International Journal of Distributed Sensor Networks_ , vol. 13, no. 11, p. 1550147717742073, 2017.
  * [8] O. Skarlat, M. Nardelli _et al._ , “Optimized IoT service placement in the fog,” _Service Oriented Computing and Applications_ , vol. 11, no. 4, pp. 427–443, 2017.
  * [9] A. Beloglazov and R. Buyya, “Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers,” _CCPE_ , vol. 24, no. 13, pp. 1397–1420, 2012.
  * [10] T. Choudhari, M. Moh _et al._ , “Prioritized task scheduling in fog computing,” in _The ACMSE 2018 Conference_ , 2018, pp. 1–8.
  * [11] G. Fox, J. Glazier _et al._ , “Learning everywhere: Pervasive machine learning for effective high-performance computation,” in _2019 IEEE IPDPSW_. IEEE, 2019, pp. 422–429.
  * [12] S. Liu and N. Wang, “Collaborative optimization scheduling of cloud service resources based on improved genetic algorithm,” _IEEE Access_ , vol. 8, pp. 150 878–150 890, 2020.
  * [13] V. M. Johnson and L. L. Rogers, “Accuracy of neural network approximators in simulation-optimization,” _Journal of Water Resources Planning and Management_ , vol. 126, no. 2, pp. 48–56, 2000.
  * [14] G. Villarrubia, J. F. De Paz _et al._ , “Artificial neural networks used in optimization problems,” _Neurocomputing_ , vol. 272, pp. 10–16, 2018\.
  * [15] L. M. Rios and N. V. Sahinidis, “Derivative-free optimization: a review of algorithms and comparison of software implementations,” _Journal of Global Optimization_ , vol. 56, no. 3, pp. 1247–1293, 2013.
  * [16] L. Bogolubsky, P. Dvurechenskii _et al._ , “Learning supervised pagerank with gradient-based and gradient-free optimization methods,” in _NeurIPS_ , 2016, pp. 4914–4922.
  * [17] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.
  * [18] H. Pan and H. Jiang, “Annealed gradient descent for deep learning,” in _The Thirty-First Conference on Uncertainty in Artificial Intelligence_ , 2015, pp. 652–661.
  * [19] I. Loshchilov and F. Hutter, “SGDR: Stochastic gradient descent with warm restarts,” _arXiv preprint arXiv:1608.03983_ , 2016.
  * [20] F. Scarselli and A. C. Tsoi, “Universal approximation using feedforward neural networks: A survey of some existing methods, and some new results,” _Neural networks_ , vol. 11, no. 1, pp. 15–37, 1998.
  * [21] T. Nguyen-Thien and T. Tran-Cong, “Approximation of functions and their derivatives: A neural network implementation with applications,” _Applied Mathematical Modelling_ , vol. 23, no. 9, pp. 687–704, 1999.
  * [22] A. Rakitianskaia and A. Engelbrecht, “Measuring saturation in neural networks,” in _2015 IEEE Symposium Series on Computational Intelligence_. IEEE, 2015, pp. 1423–1430.
  * [23] C. Gomes, C. Thule _et al._ , “Co-simulation: a survey,” _ACM Computing Surveys (CSUR)_ , vol. 51, no. 3, pp. 1–33, 2018.
  * [24] K. Rehman, O. Kipouridis _et al._ , “A cloud-based development environment using HLA and kubernetes for the co-simulation of a corporate electric vehicle fleet,” in _2019 IEEE/SICE International Symposium on System Integration (SII)_. IEEE, 2019, pp. 47–54.
  * [25] B. S. Onggo, N. Mustafee _et al._ , “Symbiotic simulation system: hybrid systems model meets big data analytics,” in _2018 Winter Simulation Conference (WSC)_. IEEE, 2018, pp. 1358–1369.
  * [26] H. Nashaat, N. Ashry _et al._ , “Smart elastic scheduling algorithm for virtual machine migration in cloud computing,” _The Journal of Supercomputing_ , vol. 75, no. 7, pp. 3842–3865, 2019.
  * [27] A. Samanta, Y. Li _et al._ , “Battle of microservices: Towards latency-optimal heuristic scheduling for edge computing,” in _IEEE NetSoft_. IEEE, 2019, pp. 223–227.
  * [28] J. Wang, N. Wu _et al._ , “Empowering A* search algorithms with neural networks for personalized route recommendation,” in _The 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2019, pp. 539–547.
  * [29] Y. Wang, S. Wang _et al._ , “An effective adaptive adjustment method for service composition exception handling in cloud manufacturing,” _Journal of Intelligent Manufacturing_ , pp. 1–17, 2020.
  * [30] S. Tuli, S. S. Gill _et al._ , “iThermoFog: IoT-Fog based automatic thermal profile creation for cloud data centers using artificial intelligence techniques,” _Internet Technology Letters_ , vol. 3, no. 5, p. e198, 2020\.
  * [31] X. Liu, B. Li _et al._ , “POND: Pessimistic-Optimistic oNline Dispatch,” _arXiv preprint arXiv:2010.09995_ , 2020.
  * [32] S. Krishnasamy, P. Akhil _et al._ , “Augmenting max-weight with explicit learning for wireless scheduling with switching costs,” _IEEE/ACM Transactions on Networking_ , vol. 26, pp. 2501–2514, 2018.
  * [33] Q. Zhang, M. Lin _et al._ , “A double deep Q-learning model for energy-efficient edge scheduling,” _IEEE Transactions on Services Computing_ , vol. 12, no. 5, pp. 739–749, 2018.
  * [34] “saving time and cost on the scheduling of fog-based iot applications using deep reinforcement learning approach.”
  * [35] Z. Tang, X. Zhou _et al._ , “Migration modeling and learning algorithms for containers in fog computing,” _IEEE Transactions on Services Computing_ , vol. 12, no. 5, pp. 712–725, 2018.
  * [36] G. R. Ghosal, D. Ghosal _et al._ , “A deep deterministic policy gradient based network scheduler for deadline-driven data transfers,” in _2020 IFIP Networking Conference_. IEEE, 2020, pp. 253–261.
  * [37] J. Bae, J. Lee _et al._ , “Beyond max-weight scheduling: A reinforcement learning-based approach,” in _2019 International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT)_. IEEE, 2019, pp. 1–8.
  * [38] P. van de Ven, S. Borst _et al._ , “Instability of maxweight scheduling algorithms,” in _IEEE INFOCOM 2009_. IEEE, 2009, pp. 1701–1709.
  * [39] P. M. van de Ven, S. C. Borst _et al._ , “Inefficiency of maxweight scheduling in spatial wireless networks,” _Computer Communications_ , vol. 36, no. 12, pp. 1350–1359, 2013.
  * [40] M. G. Markakis, E. Modiano _et al._ , “Max-weight scheduling in queueing networks with heavy-tailed traffic,” _IEEE Transactions on networking_ , vol. 22, no. 1, pp. 257–270, 2013.
  * [41] P. Auer, N. Cesa-Bianchi _et al._ , “Finite-time analysis of the multiarmed bandit problem,” _Machine learning_ , vol. 47, no. 2-3, pp. 235–256, 2002.
  * [42] S. Nandi, S. Ghosh _et al._ , “Artificial neural-network-assisted stochastic process optimization strategies,” _AIChE journal_ , vol. 47, no. 1, pp. 126–141, 2001.
  * [43] S. Tuli, R. Mahmud _et al._ , “FogBus: A blockchain-based lightweight framework for edge and fog computing,” _Journal of Systems and Software_ , vol. 154, pp. 22–36, 2019.
  * [44] S. Bosmans, S. Mercelis _et al._ , “Testing IoT systems using a hybrid simulation based testing approach,” _Computing_ , vol. 101, no. 7, pp. 857–872, 2019.
  * [45] H. Gupta, A. Vahid Dastjerdi _et al._ , “iFogSim: A toolkit for modeling and simulation of resource management techniques in the Internet of Things, Edge and Fog computing environments,” _Software: Practice and Experience_ , vol. 47, no. 9, pp. 1275–1296, 2017.
  * [46] M. M. Mahmoud, J. J. Rodrigues _et al._ , “Towards energy-aware fog-enabled cloud of things for healthcare,” _Computers & Electrical Engineering_, vol. 67, pp. 58–69, 2018.
  * [47] A. A. Mutlag, M. K. Abd Ghani _et al._ , “Enabling technologies for fog computing in healthcare iot systems,” _Future Generation Computer Systems_ , vol. 90, pp. 62–78, 2019.
  * [48] M. Grinberg, _Flask web development: developing web applications with python_. ” O’Reilly Media, Inc.”, 2018\.
  * [49] R. S. Venkatesh, T. Smejkal _et al._ , “Fast in-memory CRIU for docker containers,” in _The International Symposium on Memory Systems_ , 2019, pp. 53–65.
  * [50] S. Gupta and D. A. Dinesh, “Resource usage prediction of cloud workloads using deep bidirectional long short term memory networks,” in _2017 IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS)_. IEEE, 2017, pp. 1–6.
  * [51] S. Tuli, N. Basumatary _et al._ , “HealthFog: An ensemble deep learning based smart healthcare system for automatic diagnosis of heart diseases in integrated IoT and Fog computing environments,” _Future Generation Computer Systems_ , vol. 104, pp. 187–200, 2020.
  * [52] A. Ahmed and G. Pierre, “Docker container deployment in fog computing infrastructures,” in _2018 IEEE International Conference on Edge Computing (EDGE)_. IEEE, 2018, pp. 1–8.
  * [53] A. Paszke, S. Gross _et al._ , “Automatic differentiation in pytorch,” 2017\.
  * [54] N. Saleh and M. Mashaly, “A dynamic simulation environment for container-based cloud data centers using containercloudsim,” in _2019 Ninth International Conference on Intelligent Computing and Information Systems (ICICIS)_. IEEE, 2019, pp. 332–336.
  * [55] S. Hochreiter and J. Schmidhuber, “Long short-term memory,” _Neural computation_ , vol. 9, no. 8, pp. 1735–1780, 1997.
  * [56] S. Shen, V. van Beek _et al._ , “Statistical characterization of business-critical workloads hosted in cloud datacenters,” in _IEEE/ACM CCGRid_. IEEE, 2015, pp. 465–474.
  * [57] J. Khamse-Ashari, I. Lambadaris _et al._ , “An efficient and fair multi-resource allocation mechanism for heterogeneous servers,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 29, no. 12, pp. 2686–2699, 2018.
  * [58] Z. Li, C. Yan _et al._ , “Bayesian network-based virtual machines consolidation method,” _Future Generation Computer Systems_ , vol. 69, pp. 75–87, 2017.
  * [59] T. He, A. N. Toosi _et al._ , “SLA-aware multiple migration planning and scheduling in SDN-NFV-enabled clouds,” _Journal of Systems and Software_ , p. 110943, 2021.
  * [60] J. McChesney, N. Wang _et al._ , “DeFog: fog computing benchmarks,” in _ACM/IEEE Symposium on Edge Computing_ , 2019.
  * [61] K. Boloor, R. Chirkova _et al._ , “Dynamic request allocation and scheduling for context aware applications subject to a percentile response time sla in a distributed cloud,” in _2010 IEEE Second International Conference on Cloud Computing Technology and Science_. IEEE, 2010, pp. 464–472.
  * [62] C. Findling, V. Skvortsova _et al._ , “Computational noise in reward-guided learning drives behavioral variability in volatile environments,” _Nature neuroscience_ , vol. 22, no. 12, pp. 2066–2077, 2019\.
  * [63] G. Casale, M. Artač _et al._ , “Radon: rational decomposition and orchestration for serverless computing,” _SICS Software-Intensive Cyber-Physical Systems_ , vol. 35, no. 1, pp. 77–87, 2020.
  * [64] L. Hochstein and R. Moser, _Ansible: Up and Running: Automating Configuration Management and Deployment the Easy Way_. ” O’Reilly Media, Inc.”, 2017.
  * [65] A. Yates, K. Beal _et al._ , “The ensembl rest api: Ensembl data for any language,” _Bioinformatics_ , vol. 31, no. 1, pp. 143–145, 2015.
  * [66] S. N. Z. Naqvi, S. Yfantidou _et al._ , “Time series databases and influxdb,” _Studienarbeit, Université Libre de Bruxelles_ , 2017.
  * [67] G. Labs, _Grafana_ , (accessed October 31, 2020). [Online]. Available: https://grafana.com/

|  Shreshth Tuli is a President’s Ph.D. Scholar at the Department of
Computing, Imperial College London, UK. Prior to this he was an undergraduate
student at the Department of Computer Science and Engineering at Indian
Institute of Technology - Delhi, India. He has worked as a visiting research
fellow at the CLOUDS Laboratory, School of Computing and Information Systems,
the University of Melbourne, Australia. He is a national level Kishore
Vaigyanik Protsahan Yojana (KVPY) scholarship holder from the Government of
India for excellence in science and innovation. His research interests include
Internet of Things (IoT), Fog Computing and Deep Learning.
---|---
|  Shivananda R Poojara is a Ph.D student at Mobile and Cloud Computing
Laboratory, University of Tartu, Estonia. He is also working as a Junior
Research Fellow in IT Academy program. His research interests are serverless
computing, edge analytics, fog and cloud computing. He is a member of IEEE,
IET and ISTE. He has a 6+ years of teaching experience and worked at Nokia R&D
Labs as an intern.
---|---
|  Satish N. Srirama is an Associate Professor at School of Computer and
Information Sciences, University of Hyderabad, India. He is also a Visiting
Professor and the honorary head of the Mobile & Cloud Lab at the Institute of
Computer Science, University of Tartu, Estonia. His current research focuses
on cloud computing, mobile cloud, IoT, Fog computing, migrating scientific
computing and large scale data analytics to the cloud. He received his PhD in
computer science from RWTH Aachen University in 2008. He is an IEEE Senior
Member and an Editor of Wiley Software: Practice and Experience journal.
---|---
|  Giuliano Casale joined the Department of Computing at Imperial College
London in 2010, where he is currently a Reader. Previously, he worked as a
research scientist and consultant in the capacity planning industry. He
teaches and does research in performance engineering and cloud computing,
topics on which he has published more than 100 refereed papers. He has served
on the technical program committee of over 80 conferences and workshops and as
co-chair for several conferences in the area of performance and reliability
engineering, such as ACM SIGMETRICS/Performance and IEEE/IFIP DSN. His
research work has received multiple awards, recently the best paper award at
ACM SIGMETRICS. He serves on the editorial boards of IEEE TNSM and ACM TOMPECS
and as current chair of ACM SIGMETRICS.
---|---
|  Nicholas R. Jennings is the Vice-Provost for Research and Enterprise and
Professor of Artificial Intelligence at Imperial College London. He is an
internationally-recognised authority in the areas of AI, autonomous systems,
cyber-security and agent-based computing. He is a member of the UK
government’s AI Council, the governing body of the Engineering and Physical
Sciences Research Council, the Monaco Digital Advisory Council, and chair of
the Royal Academy of Engineering’s Policy Committee. Before Imperial, he was
the UK’s first Regius Professor of Computer Science (a post bestowed by the
monarch to recognise exceptionally high quality research) and the UK
Government’s first Chief Scientific Advisor for National Security.
---|---