FaaS

    Function-as-a-Service
IaaS

    Infrastructure-as-a-Service
PaaS

    Platform-as-a-Service
BaaS

    Backend-as-a-Service
HPC

    High-Performance Computing
SLO

    Service-Level Objective
SLA

    Service-Level Agreements
RTT

    Round Trip Time
VU

    Virtual User
RT

    Response Time
MMS

    Minimum Memory Sum
MOC

    Minimum Overall Cost
CSP

    Cloud Service Provider

# Estimating the Capacities of Function-as-a-Service Functions

*This is the preprint version of the accepted paper at CloudAM’21 workshop (UCC)

Anshul Jindal  0000-0002-7773-5342 Technical University of
MunichBoltzmannstraße 3Garching (near Munich)BavariaGermany85748
<EMAIL_ADDRESS>,  Mohak Chadha  Technical University of
MunichBoltzmannstraße 3Garching (near Munich)BavariaGermany85748
<EMAIL_ADDRESS>,  Shajulin Benedict  Indian Institute of Information
TechnologyKottayamKeralaIndia<EMAIL_ADDRESS>and  Michael Gerndt
Technical University of MunichBoltzmannstraße 3Garching (near
Munich)BavariaGermany85748<EMAIL_ADDRESS>
(2021)

###### Abstract.

Serverless computing is a cloud computing paradigm that allows developers to
focus exclusively on business logic as cloud service providers manage resource
management tasks. Serverless applications follow this model, where the
application is decomposed into a set of fine-grained Function-as-a-Service
(FaaS) functions. However, the obscurities of the underlying system
infrastructure and dependencies between FaaS functions within the application
pose a challenge for estimating the performance of FaaS functions. To
characterize the performance of a FaaS function that is relevant for the user,
we define Function Capacity (FC) as the maximal number of concurrent
invocations the function can serve in a time without violating the Service-
Level Objective (SLO).

The paper addresses the challenge of quantifying the FC individually for each
FaaS function within a serverless application. This challenge is addressed by
sandboxing a FaaS function and building its performance model. To this end, we
develop FnCapacitor – an end-to-end automated Function Capacity estimation
tool. We demonstrate the functioning of our tool on Google Cloud Functions
(GCF) and AWS Lambda. FnCapacitor estimates the FCs on different deployment
configurations (allocated memory & maximum function instances) by conducting
time-framed load tests and building various models using statistical: linear,
ridge, and polynomial regression, and Deep Neural Network (DNN) methods on the
acquired performance data. Our evaluation of different FaaS functions shows
relatively accurate predictions with an accuracy greater than 75% using DNN
for both cloud providers.

Serverless Computing, Function-as-a-Service, Function Capacity

††journalyear: 2021††price: 15.00††ccs: Computer systems organization Cloud
computing

##  1\. Introduction

With the advent of Amazon Web Services (AWS) Lambda in 2014, serverless
computing has gained popularity and more adoption in different application
domains such as machine learning (Chadha et al., 2020; Carreira et al., 2019),
linear algebra computation (Shankar et al., 2018; Chard et al., 2019), and
map/reduce-style jobs (Jonas et al., 2017). Function-as-a-Service (FaaS), a
key enabler of serverless computing, allows a traditional application to be
decomposed into fine-grained functions that are executed in response to event
triggers or HTTP requests on a FaaS platform (Castro et al., 2019). The FaaS
platform is responsible for deploying and providing resources to the FaaS
functions.

Since serverless computing environments abstract the underlying system
infrastructure configurations away from the users, most of the public cloud
providers in their FaaS offerings allow users to configure only a small set of
configuration parameters: memory allocation and the maximum number of function
instances, also called as concurrency (AWS, [n. d.]; Goo, [n. d.]; Azu, [n.
d.]). Moreover, cloud providers speedup function execution when a higher
memory is configured (Lloyd et al., 2018). Furthermore, the heterogeneity in
the underlying nodes can lead to variations in the execution time of the FaaS
functions (Chadha et al., 2021; Jindal et al., 2021b). Therefore, estimating
the maximum number of requests the deployed functions can handle such that the
response times adhere to the SLOs constraints poses a set of challenges.
Towards this, we define the maximal number of concurrent invocations that a
FaaS function can serve within a time interval without violating the SLOs when
deployed with particular memory configuration and fixed maximum function
instances as the Function Capacity (FC). In this paper, we consider the
$95^{th}$ percentile execution time of a FaaS function as the SLO.

(a) Effect of memory on the FC with fixed function concurrency of 100.

(b) Effect of memory on the with fixed function concurrency of 100.

(c) Function concurrency effect on the FC with fixed memory.

Figure 1.  AWS lambda and Google Cloud Function (GCF) FCs variation with
memory configurations, and concurrency.

To highlight the effects of various parameters configuration on the
performance and the Function Capacities of FaaS functions, we deployed a
compute-intensive (calculates prime numbers till $10000000$) serverless
function written in Python on AWS Lambda and Google Cloud Function (GCF) (Goo,
[n. d.]). We fixed the $95^{th}$ percentile execution time of the function to
20 seconds. Figure 1(a) shows how the Function Capacity (i.e., the maximum
number of requests per second the function can handle) first increases with
varying memory sizes upto a certain point (2048MB). After that, it becomes
constant when the function concurrency is fixed to 100 for both the cloud
providers. The same Figure 1(a) also shows the variation in FC with cloud
providers. The variation in the system resources causes differences in
performance between the identical function deployments for the same FaaS
platforms. Figure 1(b) shows the execution time of corresponding runs, and one
can see that it decreases with the increase in memory, and after a point
(2048MB), it also becomes constant. Lastly, Figure 1(c) shows the linear
increase in FC with the increase in function concurrency, keeping the memory
fixed.

The examples above highlight some factors that can affect the performance and
the FCs. However, they are many other factors such as cold starts, I/O and
network conditions, type of container runtimes, and co-location with other
functions affecting the performance and FCs which the users are not aware of
(Wang et al., 2018; Espe. et al., 2020). Additionally, the dependencies
between the functions within a serverless application can also affect the FCs.
To this end, we develop FnCapacitor, a tool that can estimate the FCs of the
functions adhering to the given SLOs, the specified memory configurations, and
function concurrency. Our key contributions are as follows:

  * •

We develop and present a novel python-based tool called FnCapacitor for
automatic estimation of Function Capacities of FaaS functions within a
serverless application (§3).

  * •

As part of FnCapacitor, we present a functions sandboxing method which can be
used to sandbox individual functions from the overall serverless application
(§3.1).

  * •

We showcase the effect of different deployment configurations : memory
allocation (§5.1) and function concurrency (§5.3), on the Function Capacity
for different FaaS functions within a sample application. To the best of our
knowledge, none of the previous works involving FaaS (Shahrad et al., 2019;
Lee et al., 2018; Wang et al., 2018; Jindal et al., 2021c; Akhtar et al.,
2020; Eismann et al., 2021) considered function concurrency parameter.

  * •

Although our approach is generic and FnCapacitor can be easily extended to
support other commercial and open-source FaaS platforms, we demonstrate the
functioning of FnCapacitor with Google Cloud Functions (GCF) and AWS Lambda
(§5) on a sample serverless application consisting of 8 functions. We further
present the performance results of the formulated FC estimation models on each
of them (§5.4).

  * •

We open source the collected data and developed tool for further
research111https://github.com/ansjin/faas_capacitor.

Paper Organization Section 2 introduces the basic FaaS function invocation
procedure and Function Capacity concept. In Section 3 the developed tool
FnCapacitor is described. Section 4 describes the experimental setup and the
hyper-parameters of the different algorithms. In Section 5, our evaluation
results are presented. Section 6 describes some of the prior works in this
domain. Finally, Section 7 concludes the paper.

##  2\. Taxonomy

###  2.1. FaaS function invocation procedure

Figure 2. Typical FaaS function invocation procedure.

Function-as-a-Service based function is a piece of code containing a handler
method responsible for processing the events that are passed to the function
when invoked and these are executed within a FaaS platform. FaaS based
functions can be invoked by a user’s HTTP request or another type of event
created within the FaaS platform or the cloud infrastructure. These include
changes to data in a database, files added to a storage system, or a new
virtual machine instance is created. The FaaS platform is responsible for
providing resources for function invocations and performs automatic scaling.
This is done by creating an execution environment which provides a secure and
isolated runtime environment for the function. The functions can be written
using various languages, and a language-specific environment called runtime is
created in the execution environment. The runtime relays invocation events,
context information, and responses between the FaaS platform and the function.

The first time the function is invoked, the FaaS platform creates an instance
of the function (execution environment) and runs its handler method in it to
process the event. When the handler exits or returns a response, it stays
active and becomes available to handle other events. If the function is
invoked again while the first event is being processed, the FaaS platform
creates another instance, and the two events are processed concurrently. As
more events come in, the FaaS platform routes them to available instances and
creates new instances as needed. When the number of requests decreases, the
FaaS platform stops unused instances to have free scaling capacity for other
functions. FaaS platforms usually have an upper limit on how many maximum
concurrent instances called function concurrency can be created, such as 1000
for AWS lambda and 3000 for GCF. Figure 2 summarizes the overview of the
typical FaaS function request procedure.

###  2.2. Function Capacity (FC)

We define the Function Capacity (FC) as the maximal number of concurrent
invocations that a FaaS function when deployed on a FaaS platform with a
certain memory configuration and fixed maximum function instances, can serve
within a time interval without violating the SLOs when deployed. Ideally, if
an instance $i$ serves $n_{i}^{t}$ number of invocations within a time
interval $t$ and $C$ is the function concurrency for the FaaS platform, then
the $FC(f)$, where $f$ is any function, can be calculated by the equation (1).

(1) $FC(f)=n_{i}^{t}\times C$

However, in practice, there are many other factors such as cold starts, I/O
and network conditions, type of container runtimes, and co-location with other
functions affecting the performance and FCs of FaaS functions (Wang et al.,
2018). Therefore, we follow a modeling approach to estimate the capacities of
the FaaS functions. In this paper, we consider the $95^{th}$ percentile
execution time of a FaaS function as the SLO.

##  3\. FnCapacitor

To estimate the capacities of the FaaS functions within a serverless
application, we have developed FnCapacitor, a python-based automated end-to-
end function capacity estimation tool. Given the SLO requirements, FnCapacitor
is responsible for estimating the FCs of FaaS functions at different
deployment configurations (memory allocation and function concurrency). Figure
3 provides an overview of the high-level architecture of FnCapacitor and the
interaction between its components.

Figure 3. High-level architecture of the FnCapacitor.

FnCapacitor takes a YAML file as input that specifies the initial FaaS
platform configuration parameters (minimum memory allocation and functions
timeout) for the function deployment, serverless application to be deployed,
and configuration parameters for the load generator and the modeling (step 1).
Since a serverless application consists of multiple functions and the
performance of one function could affect the others depending upon it,
therefore in the next step, the individual functions from the given
application are segregated (step 2). These sandboxed functions are then
deployed on the FaaS platform with some initial configurations (step 3). After
the deployment, FnCapacitor repeatedly changes the functions configurations
(steps 4 \- 5) and generates a user workload to the function’s API endpoint
(step 6) for collecting various monitoring metrics data (§4.2). The collected
metrics data is stored in InfluxDB, which is used for creating the function
performance models (step 7). The created function models are then used for
estimating the Function Capacities for different deployment configurations
(step 8).

We now describe the sub-components of FnCapacitor:

###  3.1. Functions Sandboxing

Usually, a serverless application consists of multiple functions, and the
performance of one function could affect the others depending upon it.
Therefore to measure the pure performance of the functions i.e., where their
performance is not affected by others, we build this component for sandboxing
individual functions through a mockup of their neighbors. It isolates each
function and substitutes its direct neighbors with dummy functions accepting
the requests and sending the responses in the same format, but without any
additional processing allowing to measure the pure performance of only that
function and build models using this data.

Firstly, this component for each function within the serverless application
replaces the calls to other functions with calls to a proxy-function. This
proxy-function serves as an intermediator between the sandboxed function and
other functions and takes the originally called function names from the
sandboxed function and the input payload to them as the input. This allows
every invocation to other functions to go through this proxy-function and this
dummy proxy-function then will invoke the following functions based on the
input received. At the same time, copies of these requests and responses are
stored in the FnCapacitor’s MongoDB database for creating function mockups. It
is to be noted that, Backend-as-a-Service (BaaS) services such as database,
storage, queues, etc., are out of the scope of this work for sandboxing as it
is assumed that these BaaS services provides high scalability and serve the
user requests within the defined SLOs. Following this, each function receives
its own sandboxed deployment where mockup functions replace the direct
neighbors. These mockup functions will respond with the response stored in
MongoDB. As a result, the time taken by the dependent functions to respond
becomes negligible and therefore allows to build a pure performance model of
the functions.

###  3.2. Function Deployer, Destroyer and Updater

As the name suggests, it is responsible for deploying, destroying, and
updating the functions to be modeled on the GCF and AWS Lambda using the
serverless framework (Serverless, 2020). For deployment and updating,
different configuration parameters: memory configurations and function
concurrency are taken into account. The deployed functions are scaled
automatically by adding multiple function instances by the FaaS platform. This
component automatically deletes the functions when the test is finished to
free up the resources.

###  3.3. Load Generator

The Load Generator is implemented using a load testing tool - k6. It uses a
script for running the tests where the function endpoint and request
parameters are specified. As part of each test, the number of requests per
second (RPS) generated by k6 is varied and depends on the number of Virtual
Users (VUs) and the time taken by each request to complete. VUs are the
entities in k6 that execute the test and make HTTP(s) requests. The load
generation metrics from k6 and FaaS platform monitoring metrics data from the
cloud providers are exported and stored inside an InfluxDB instance.

###  3.4. Performance Modeler & Capacity Estimation

This is the main component of FnCapacitor and is responsible for analyzing the
correlation between the different monitoring metrics (§4.2) and the deployment
configurations. It uses the collected data stored in InfluxDB to create models
of the functions and estimate their Function Capacities. Modeling approaches
used in this work are categorized under two categories:

  * •

Statistical Approaches: We consider linear, polynomial, ridge, and random
forest regression for modeling the relationship.

  * •

Deep Neural Networks (DNNs): DNNs are designed to solve complex problems by
building relationships among multiple dependent and independent variables. As
a result, we use them for formulating the models.

The collected data from InfluxDB is pre-processed by removing outliers and
dividing the data into training and test set. Following this, different
models, i.e., statistical and DNNs, are trained on the training data set. Due
to the training data being sparse, k-fold cross-validation (in our case k=6)
is followed for training the model (Yadav and Shukla, 2016).

Lastly, Function Capacities are estimated on the new or test dataset using the
trained models. The prediction accuracy is computed using the $R^{2}$ score
value from the actual and predicted Function Capacities for the test dataset.

##  4\. Experimental Configuration

In this work, we have fixed the total duration of a test to 30 minutes for the
deployed serverless application. A test consists of the memory allocation
configurations: <256MiB, 512MiB, 1GiB, 2GiB and 4GiB> and function
concurrency: <10, 20, 30, 40 and 50>. AWS functions are deployed in the
europe-central1 region, and GCF functions are deployed in the eu-west3 region.
The number of VUs during the load generation are varied from 5 to 500
depending on the number of requests the functions can serve. As a result, for
each function, $5$ (total memory configurations) $\times$ $5$ (function
concurrency configurations) $=25$ tests were conducted.

We partition the collected data into training and test set (33% of the total
data). We used a part of the training data set as a validation set for
selecting the hyperparameters of the different models. We select the
hyperparameters through an exhaustive grid search. For the DNN model, we use a
12-layer fully connected neural network architecture, with each layer having
64 units. We use the Rectified Linear Unit (ReLU) as activation function
(Krizhevsky et al., 2017). We use mean absolute error as the loss function for
training the DNN model with Adam as the optimizer.

###  4.1. Application used for evaluation

Figure 4. High level workflow of the evaluated application.

To investigate the performance of each deployment configuration, we used a
subset of the benchmarks provided with the FaaSProfiler (Shahrad et al.,
2019). We created an application shown in Figure 4 for our use case. The
functions used as part of this application are summarized in Table 1.

Table 1.  Functions comprising the evaluated application.  Functions |  Description |  Runtime
---|---|---
nodeinfo |  Gives basic characteristics of node like CPU count, architecture, uptime. |  Node.js 14
primes-python |  Calculates prime numbers till $100000$. |  Python3
linpack |  It solves a dense linear system of equations in double precision and returns the results in GFlops. Problem size (number of equations) is fixed to 100. |  Python3
dd |  It is based on Unix dd command-line utility for converting and copying files. 128bytes as a block size and 5 times conversion is used as parameters. |  Python3
gzip-compression |  It first creates a file filled with random numbers of size 1MB and then compresses it using gzip compression scheme. |  Python3
lr-prediction |  It first downloads a linear regression model trained on user reviews data from the storage bucket along with the test data and performs prediction on it. |  Python3
nodejs-endpoint |  It is a simple REST endpoint which returns the current time along with the time zone. |  Node.js 14
sentiment-analysis |  Analyzes the sentiment of a provided string using the Python TextBlob library |  Python3

The application flow starts with the nodeinfo function, which exposes an HTTP
endpoint and provides the user with basic information about the system such as
hostname, underlying architecture, number of CPUs, etc. This then invokes the
compute-intensive primes-python function to judge the built models’ abilities
on compute-intensive applications, and it further invokes linpack and dd
asynchronously and waits for their response to come back. dd invokes gzip-
compression. It further invokes lr-prediction in a sequence. lr-prediction
queries the model and data from the google cloud storage (created in the
google compute platform in the europe-west3 region, AWS lambda functions also
use this storage bucket) and then performs prediction. Once the response is
available to primes-python function from both the invocations, it sends back
the response to nodeinfo function, which in turn invokes nodejs-endpoint and
nodejs-endpoint further invokes sentiment-analysis function. We use these
eight heterogeneous functions to test the accuracy of the modeling on
different types of functions.

###  4.2. Monitoring Metrics

We extracted following monitoring metrics from the GCF and AWS
lambda222https://docs.aws.amazon.com/lambda/latest/dg/monitoring-metrics.html
with the data sampling rate as one minute:

  * •

concurrent_instances: Number of concurrent function instances.

  * •

invocations: Number of times the function is executed.

  * •

execution_duration: Amount of time function code spends in processing an
event.

  * •

memory_usage: Function’s maximum memory usage.

  * •

allocated_memory: Memory allocated to the function.

  * •

function_concurrency: Maximum number of concurrent instances allowed for
processing events.

##  5\. Experimental Results

In this section, we first describe the impact of heterogeneity in the memory
allocations on function’s execution_duration and concurrent_instances, and
then the effect of function_concurrency on the Function Capacities for both
the cloud providers and on different functions. Following this, we present
results of FCs estimation using the different modeling approaches.

###  5.1. Memory effect on function execution duration

Figure 5. execution_durations of the sandboxed functions when executed with a
load of $50$ RPS with five different memory configurations and no limit on the
function_concurrency.

Figure 5 shows the execution_durations of the load testing of $50$ invocations
per second on the application when the functions are sandboxed and deployed
with five different memory configurations on GCF and AWS lambda platforms. We
observe the following:

Decrease in execution_duration with the increase in memory and becoming
constant: From Figure 5, we can see that for most of the functions and across
two FaaS platforms, there is a general trend of decrease in execution_duration
with the increase in memory, and after a certain point (2048MB memory
configuration), either it is becoming constant (for all functions running on
AWS, and lr-regression, sentiment, and linpack on GCF) or increasing (for all
other functions on GCF). This can be attributed to an increase (2x) in the
number of allocated clock cycles for a memory configuration of $4096$MB as
compared to $2048$MB (GoogleCloud, [n. d.]).

In general, AWS lambda has a lower execution duration for most of the
functions at all memory configurations as compared to GCF: We can observe from
the Figure 5 that, for most of the functions except the three compute-
intensive functions at a lower memory configuration ($256MB$ and $512MB$), AWS
lambda process function events faster than the GCF. For example, for dd
microbenchmark at $256MB$ configuration, AWS lambda takes $5.2x$ times less
than the GCF at the same memory allocation, and even it can process faster
than GCF allocated with $4GB$. nodeinfo, sentiment, linpack, and web-endpoint
took almost the same amount across different memory configurations and FaaS
platforms.

###  5.2. Memory effect on function’s concurrent instances

Figure 6. concurrent_instances of the sandboxed functions for handling the
load of $50$ RPS with five different memory configurations and no limit on the
function_concurrency.

Figure 6 shows the concurrent_instances per function in the serverless
application when it is load tested with a load of $50$ invocations per second
on GCF and AWS lambda platform for five different memory configurations. We
observe the following:

Figure 7. Function Capacity of the functions when deployed on the two FaaS
platforms for different function_concurrency with memory configuration fixed
to 256MB.

AWS lambda creates more concurrent_instances as compared to GCF: From Figure
6, we can see that, for most of the functions and across different memory
configurations, AWS creates a higher number of concurrent_instances as
compared to GCF for handling the same amount of load.

Decrease in number of concurrent_instances with the increase in memory
configuration: As the memory is increased for each function, the number of
functions concurrent_instances for both the FaaS platforms either remain
constant or has decreased. This trend can be attributed to the fact that a
higher resource instance can serve the requests faster and hence can process
more requests per unit time. Therefore, fewer instances are required to handle
the same amount of load when allocated with lower memory configurations.

Slow-processing functions are scaled to higher number of concurrent_instances
to match up with the fast-processing functions : From Figure 5, we can observe
that, lr-regression and gzip have the highest function execution_time as
compared to the other functions and when observing the number of
concurrent_instances for those two functions in Figure 6, we can see that they
are the highest. This concludes that the compute-intensive (slow-processing)
functions require higher scaling to match up the other fast-processing
functions to handle the same amount of load. Such visualization can also be
used to understand the bottleneck function in the serverless application; for
example, in our case, it is lr-regression.

###  5.3. Effect of function concurrency on the FC

Figure 7 shows the actual capacity measurements for the two FaaS platforms for
different function_concurrency configurations with memory configuration fixed
to 256MB for all the functions. The capacities depicted are the average of the
five runs for both FaaS platforms. In general, it can be inferred that for
most of the functions, FCs vary linearly with the function_concurrency for
both the FaaS platforms. Also, a single instance of AWS lambda can process a
higher number of requests than the single instance on GCF. However, for the
two compute-intensive functions namely: gzip-compression, ml-lr-prediction we
see a similar FCs for both the platforms at different function_concurrency. In
case of GCF, for simple web-based functions : sentiment-analysis, nodeinfo,
and nodejs-endpoint the linear increasing slope is not constant. From Figure
7, one can see that, for the three FaaS functions the linear slope changed
after function_concurrency of 6. This means that, after the
function_concurrency of 6, each instance can process more number of requests
as compared to the instance used when the function_concurrency is less than 6.
In general, the trend is linear for all other functions and both FaaS
platforms. However, they are not exactly following the ideal lines. Therefore,
one needs modeling approaches for the estimation of FCs for both the FaaS
platforms.

###  5.4. Function Capacity estimation

On analyzing the impact of varying memory configurations on the performance of
the different FaaS functions, we use the metrics ¡concurrent_instances,
execution_duration, allocated_memory, memory_usage, function_concurrency¿
obtained from the collected load test data as input parameters for the
different models (§3.4). For a given set of input parameters, all models
predict <function invocations> which is equivalent to the FC.

Table 2 shows the comparison of the accuracy results for estimated FCs for the
different modeling approaches (§3.4) with the best ones underlined for both
the FaaS platforms. For determining the accuracy of the formulated models, we
use the $R^{2}$ score (r2s, [n. d.]).

Table 2.  Comparison of accuracy results ($R^{2}$ score) for estimated FCs for the different modeling approaches. Function | LR | PLR | RR | RFR | DNN
---|---|---|---|---|---
| GCF | AWS | GCF | AWS | GCF | AWS | GCF | AWS | GCF | AWS
dd | 81.9 | 98.1 | 88.27 | 97.7 | 82.2 | 98.0 | 88.5 | 98.1 | 91.1 | 98.2
gzip | 83.5 | 91.4 | 89.8 | 94.8 | 83.6 | 91.4 | 93.0 | 94.6 | 93.6 | 94.9
primes | 75.8 | 95.4 | 78.6 | 95.1 | 76.4 | 95.6 | 83.1 | 96.7 | 85.0 | 96.5
linpack | 86.3 | 58.7 | 87.7 | 75.9 | 86.4 | 76.3 | 88.5 | 87.2 | 88.8 | 92.4
sentiment | 65.6 | 33.6 | 72.9 | 92.9 | 52.2 | 24.9 | 76.0 | 97.4 | 74.4 | 96.2
lr-pred. | 90.9 | 99.4 | 93.0 | 99.5 | 90.7 | 99.4 | 95.4 | 98.7 | 94.7 | 99.5
nodeinfo | 80.6 | 87.5 | 88.4 | 87.6 | 79.6 | 87.9 | 89.6 | 88.2 | 90.2 | 87.6
endpoint | 77.2 | 36.5 | 80.8 | 67.9 | 76.3 | 35.7 | 82.8 | 81.0 | 77.8 | 80.2

In general, it was found that the accuracy measurements for Function Capacity
estimation for AWS lambda are higher than the GCF for most of the FaaS
functions since AWS lambda exhibits more linear behavior as compared to GCF (
Figure 7). Linear Regression (LR) leads to best results when the parameters
are linearly correlated to the FC. For most FaaS functions, the parameters are
linearly correlated to FC, leading to an accuracy value greater than $80$%.
For both the FaaS platforms, the accuracy for the nodejs-endpoint, and
sentiment-analysis FaaS functions is comparatively less as compared to other
FaaS functions since most parameters in them are non-linearly correlated with
FC. Polynomial Linear Regression (PLR) leads to highly accurate results for
most of the function types due to its ability to model non-linear relations
among the parameters. With PLR, the estimated FC accuracies are higher than
the linear regression, which is attributed to most parameters being non-
linearly correlated. Ridge Regression (RR) produced approximately the same
results as that of linear regression and worked well for certain function
types. On the other hand, Random Forest Regression (RFR) can provide the best
results among the statistical approaches.

The Deep Neural Network(DNN) method outperformed all the statistical
approaches for most of the FaaS functions since it is capable of modeling the
linear and non-linear correlation between the parameters. For most function
types, the FC estimation accuracy is approximately above $75\%$. In Figure 8,
we show the prediction accuracy percentage for k-folds in the case of DNN on
the test data using the box plot for both FaaS platforms, and all the FaaS
functions.

Figure 8. Box plot showing the prediction accuracy on the test data across
k-folds using DNN model for both FaaS platforms.

##  6\. Related Work

FaaS is priced as per the pay-as-you-go model, where they charge the number of
function invocations and memory. The majority of the prior work is based on
optimizing the scalability, cost, execution time, integration support, and the
constraints associated with FaaS services such as AWS Lambda, GCF, and Azure
Functions (AF) provided by public cloud providers (Grogan et al., [n. d.];
Fan. et al., 2020; Jindal et al., 2021c, a; Jindal and Gerndt, 2021). However,
there is no prior research for quantifying and estimating the FCs based on the
different deployment configurations using GCF and AWS Lambda. We present prior
work from two aspects:

###  6.1. Performance impact of the underlying system

FaaSProfiler (Shahrad et al., 2019) is the first to take a bottom-up approach
in analyzing the architectural implication to unwrap the server-level
overheads in the FaaS model. They analyzed the difference between native and
in-FaaS function execution and calculated the additional server-level
overheads like computational overheads, memory consumption, bandwidth usage,
and management overheads like orchestration, queuing, scheduling, and power
consumed. Furthermore, Lee et al. (Lee et al., 2018) compared the performance
of various serverless computing environments offered by public cloud providers
by showcasing the results of throughput, network bandwidth, file I/O and
compute performance on concurrent function invocations. Wang et al. (Wang et
al., 2018) performed an in-depth study of resource management and performance
isolation with three popular serverless computing providers: AWS Lambda, Azure
Functions, and GCF. Their analysis demonstrates a reasonable difference in
performance between the FaaS platforms. Moreover, the deployed function
instances are associated with VMs having a variety of configurations with
different underlying host micro-architectures. In this work, we showcase a
strong correlation between the function’s performance and the resources
allocated to it based on the different configurations.

Additionally, Figiela et al. (Figiela et al., 2018) developed a cloud function
benchmarking framework. Compute-intensive functions were deployed in major
cloud providers’ FaaS platforms. The authors observe variation in response
time duration based on the different underlying hardware and runtime
environment. These observations encouraged us to proceed with estimating the
FCs of functions when deployed with different deployment configurations.

###  6.2. Performance modeling of the FaaS application

Pawlik et al. (Pawlik et al., 2018) state that to assess the feasibility of
running an application on the FaaS platform, we have to determine the SLO of
the application. This can be achieved by constructing a reliable performance
model capable of analyzing a function performance, which requires knowledge
about the performance of the infrastructure. Cloud service providers abstract
details such as the number of cores, memory available, and network I/O
capacity in the underlying hardware, usually limiting the available
information to function time limit, maximum memory. The allocated memory also
affects the provisioned CPU quota (Lloyd et al., 2018). In our previous work
(Jindal et al., 2019), we developed a tool for estimating the capacity of a
microservice application when it is sandboxed. We followed the similar
approach in this work for the capacities estimation of the FaaS functions.

##  7\. Conclusion and Future Work

In this paper, we demonstrated the impact of various configuration parameters
on the Function Capacity of the two FaaS platforms(AWS Lambda and GCF). The
methodology and the tool FnCapacitor introduced in this paper aim to solve the
problem of estimating the Function Capacity at a specific deployment
configuration. In summary, FnCapacitor can be used in two ways:

  * •

By application developers in an offline manner for estimating the FCs of FaaS
functions within their application for different deployment configurations.
Based on the estimated FCs and the requirements, the developer can deploy the
functions with the right configurations.

  * •

By application developers in an online manner, the tool collects the
monitoring data of the already existing FaaS functions. It automatically
builds the models in the background without additional load testing. The built
models can then be used to update the deployment configurations of the
functions depending on the required SLOs.

In the future, we plan to extend FnCapacitor with other public serverless
compute providers and to open source FaaS platforms. Creating a function
scheduling framework based on the estimated FCs, the functions can be created
with the suitable deployment configurations is another future direction.

###### Acknowledgements.

This work was supported by the funding of the German Federal Ministry of
Education and Research (BMBF) in the scope of the Software Campus program.
Google Cloud credits in this work were provided by the Google Cloud Research
Credits program with the award number Grant #NH93G06K20KDXH9U.

## References

  * (1)
  * AWS ([n. d.]) [n. d.].  AWS Lambda, https://docs.aws.amazon.com/lambda/latest/dg/invocation-scaling.html.  Accessed on 09/24/2020.
  * Azu ([n. d.]) [n. d.].  Azure Functions hosting options, https://docs.microsoft.com/en-us/azure/azure-functions/functions-scale.  Accessed on 02/18/2021.
  * Goo ([n. d.]) [n. d.].  Cloud Functions Overview.  https://cloud.google.com/functions/docs/concepts/overview.  (Accessed on 08/22/2020).
  * r2s ([n. d.]) [n. d.].  The regression score, https://scikit-learn.org/stable/modules/generated/sklearn.metrics.r2_score.html.  Accessed on 12/17/2020.
  * Akhtar et al. (2020) Nabeel Akhtar, Ali Raza, Vatche Ishakian, and Ibrahim Matta. 2020\.  COSE: Configuring Serverless Functions using Statistical Learning. In _IEEE INFOCOM 2020 - IEEE Conference on Computer Communications_. 129–138.  https://doi.org/10.1109/INFOCOM41043.2020.9155363
  * Carreira et al. (2019) Joao Carreira, Pedro Fonseca, Alexey Tumanov, Andrew Zhang, and Randy Katz. 2019.  Cirrus: A serverless framework for end-to-end ml workflows. In _Proceedings of the ACM Symposium on Cloud Computing_. 13–24.
  * Castro et al. (2019) Paul Castro, Vatche Ishakian, Vinod Muthusamy, and Aleksander Slominski. 2019.  The Rise of Serverless Computing.  _Commun. ACM_ 62, 12 (Nov. 2019), 44–54.  https://doi.org/10.1145/3368454
  * Chadha et al. (2020) Mohak Chadha, Anshul Jindal, and Michael Gerndt. 2020\.  Towards Federated Learning Using FaaS Fabric. In _Proceedings of the 2020 Sixth International Workshop on Serverless Computing_ (Delft, Netherlands) _(WoSC’20)_. Association for Computing Machinery, New York, NY, USA, 49–54.  https://doi.org/10.1145/3429880.3430100
  * Chadha et al. (2021) Mohak Chadha, Anshul Jindal, and Michael Gerndt. 2021\.  Architecture-Specific Performance Optimization of Compute-Intensive FaaS Functions.  _CoRR_ abs/2107.10008 (2021).  arXiv:2107.10008 https://arxiv.org/abs/2107.10008
  * Chard et al. (2019) Ryan Chard, Tyler J. Skluzacek, Zhuozhao Li, Yadu Babuji, Anna Woodard, Ben Blaiszik, Steven Tuecke, Ian Foster, and Kyle Chard. 2019.  Serverless Supercomputing: High Performance Function as a Service for Science.  arXiv:1908.04907 [cs.DC]
  * Eismann et al. (2021) Simon Eismann, Long Bui, Johannes Grohmann, Cristina L. Abad, Nikolas Herbst, and Samuel Kounev. 2021\.  Sizeless: Predicting the optimal size of serverless functions.  arXiv:2010.15162 [cs.DC]
  * Espe. et al. (2020) Lennart Espe., Anshul Jindal., Vladimir Podolskiy., and Michael Gerndt. 2020.  Performance Evaluation of Container Runtimes. In _Proceedings of the 10th International Conference on Cloud Computing and Services Science - CLOSER,_. INSTICC, SciTePress, 273–281.  https://doi.org/10.5220/0009340402730281
  * Fan. et al. (2020) Chen-Fu Fan., Anshul Jindal., and Michael Gerndt. 2020\.  Microservices vs Serverless: A Performance Comparison on a Cloud-native Web Application. In _Proceedings of the 10th International Conference on Cloud Computing and Services Science - CLOSER,_. INSTICC, SciTePress, 204–215.  https://doi.org/10.5220/0009792702040215
  * Figiela et al. (2018) Kamil Figiela, Adam Gajek, Adam Zima, Beata Obrok, and Maciej Malawski. 2018.  Performance evaluation of heterogeneous cloud functions.  _Concurrency and Computation: Practice and Experience_ 30, 23 (2018).
  * GoogleCloud ([n. d.]) GoogleCloud. [n. d.].  Cloud Functions Pricing.  https://cloud.google.com/functions/pricing.  (Accessed on 08/22/2020).
  * Grogan et al. ([n. d.]) Jake Grogan, Connor Mulready, James McDermott, Martynas Urbanavicius, Murat Yilmaz, Yalemisew Abgaz, Andrew McCarren, Silvana MacMahon, Vahid Garousi, Pooyan Jamshidi, et al. [n. d.].  An analysis of Function-as-a-Service (FaaS): vendors, challenges and implications for software developers.  ([n. d.]).
  * Jindal et al. (2021a) Anshul Jindal, Mohak Chadha, Michael Gerndt, Julian Frielinghaus, Vladimir Podolskiy, and Pengfei Chen. 2021a.  Poster: Function Delivery Network: Extending Serverless to Heterogeneous Computing. In _2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS)_. 1128–1129.  https://doi.org/10.1109/ICDCS51616.2021.00120
  * Jindal et al. (2021b) Anshul Jindal, Julian Frielinghaus, Mohak Chadha, and Michael Gerndt. 2021b.  Courier: Delivering Serverless Functions Within Heterogeneous FaaS Deployments. In _2021 IEEE/ACM 14th International Conference on Utility and Cloud Computing (UCC’21)_ (Leicester, United Kingdom) _(UCC ’21)_. Association for Computing Machinery, New York, NY, USA, 10 pages.  https://doi.org/10.1145/3468737.3494097
  * Jindal and Gerndt (2021) Anshul Jindal and Michael Gerndt. 2021.  From DevOps to NoOps: Is It Worth It?. In _Cloud Computing and Services Science_ , Donald Ferguson, Claus Pahl, and Markus Helfert (Eds.). Springer International Publishing, Cham, 178–202.
  * Jindal et al. (2021c) Anshul Jindal, Michael Gerndt, Mohak Chadha, Vladimir Podolskiy, and Pengfei Chen. 2021c.  Function delivery network: Extending serverless computing for heterogeneous platforms.  _Software: Practice and Experience_ 51, 9 (2021), 1936–1963.  https://doi.org/10.1002/spe.2966 arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/spe.2966
  * Jindal et al. (2019) Anshul Jindal, Vladimir Podolskiy, and Michael Gerndt. 2019\.  Performance modeling for cloud microservice applications. In _Proceedings of the 2019 ACM/SPEC International Conference on Performance Engineering_. 25–32.
  * Jonas et al. (2017) Eric Jonas, Qifan Pu, Shivaram Venkataraman, Ion Stoica, and Benjamin Recht. 2017.  Occupy the cloud: Distributed computing for the 99%. In _Proceedings of the 2017 Symposium on Cloud Computing_. 445–451.
  * Krizhevsky et al. (2017) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. 2017\.  ImageNet Classification with Deep Convolutional Neural Networks.  _Commun. ACM_ 60, 6 (May 2017), 84–90.  https://doi.org/10.1145/3065386
  * Lee et al. (2018) Hyungro Lee, Kumar Satyam, and Geoffrey Fox. 2018\.  Evaluation of production serverless computing environments. In _2018 IEEE 11th International Conference on Cloud Computing (CLOUD)_. IEEE, 442–450.
  * Lloyd et al. (2018) W. Lloyd, S. Ramesh, S. Chinthalapati, L. Ly, and S. Pallickara. 2018.  Serverless Computing: An Investigation of Factors Influencing Microservice Performance. In _2018 IEEE International Conference on Cloud Engineering (IC2E)_. 159–169.  https://doi.org/10.1109/IC2E.2018.00039
  * Pawlik et al. (2018) Maciej Pawlik, Kamil Figiela, and Maciej Malawski. 2018\.  Performance evaluation of parallel cloud functions.  _Poster Presented at ICPP_ (2018).
  * Serverless (2020) Serverless. 2020\.  Documentation.  https://serverless.com/framework/docs/.  [Online; Accessed: 4-Feburary-2020].
  * Shahrad et al. (2019) Mohammad Shahrad, Jonathan Balkind, and David Wentzlaff. 2019\.  Architectural implications of function-as-a-service computing. In _Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture_. 1063–1075.
  * Shankar et al. (2018) Vaishaal Shankar, Karl Krauth, Qifan Pu, Eric Jonas, Shivaram Venkataraman, Ion Stoica, Benjamin Recht, and Jonathan Ragan-Kelley. 2018.  Numpywren: Serverless linear algebra.  _arXiv preprint arXiv:1810.09679_ (2018).
  * Wang et al. (2018) Liang Wang, Mengyuan Li, Yinqian Zhang, Thomas Ristenpart, and Michael Swift. 2018.  Peeking behind the curtains of serverless platforms. In _2018 $\\{$USENIX$\\}$ Annual Technical Conference ($\\{$USENIX$\\}$$\\{$ATC$\\}$ 18)_. 133–146.
  * Yadav and Shukla (2016) Sanjay Yadav and Sanyam Shukla. 2016.  Analysis of k-fold cross-validation over hold-out validation on colossal datasets for quality classification. In _2016 IEEE 6th International conference on advanced computing (IACC)_. IEEE, 78–83.

  *[SLO]: Service-Level Objective
  *[BaaS]: Backend-as-a-Service
  *[SLOs]: Service-Level Objective


# A Resources Representation For Resource Allocation In Fog Computing Networks

Amine Abouaomar∗1,2, Soumaya Cherkaoui∗1, Abdellatif Kobbane∗2, Oussama
Abderrahmane Dambri∗1 1 INTERLAB, Engineering Faculty, Université de
Sherbrooke, Canada.
2 Rabat IT Center, ENSIAS, Mohammed V University of Rabat, Morocco.

###### Abstract

Fog computing is emerging as a new paradigm to deal with latency-sensitive
applications, by making data processing and analysis close to their source.
Due to the heterogeneity of devices in the fog, it is important to devise
novel solutions which take into account the diverse physical resources
available in each device to efficiently and dynamically distribute the
processing. In this paper, we propose a resource representation scheme which
allows exposing the resources of each device through Mobile Edge Computing
Application Programming Interfaces (MEC APIs) in order to optimize resource
allocation by the supervising entity in the fog. Then, we formulate the
resource allocation problem as a Lyapunov optimization and we discuss the
impact of our proposed approach on latency. Simulation results show that our
proposed approach can minimize latency and improve the performance of the
system.

###### Index Terms:

Edge Computing, Resources Representation Model, Resource allocation, Lyapunov
optimization.

##  I Introduction

In the last few years, fog computing attracted the attention of both academia
and industrial. Fog computing is an emerging paradigm consisting in extending
cloud-based computing, storage and networking capabilities to the edge of the
network [1, 22]. Fog computing main purpose is reducing the latency and
ensuring an optimized use of available resources at the edge of the network.
Therefore, resources of fogs need to be managed and used appropriately.

The fog is built-up on fog nodes [2, 15, 13]. Each fog node is an aggregation
of edge devices such as routers, switches, and edge devices [14, 21]. From the
perspective of location, the devices forming fog nodes are, usually, outside
the premises of the operator, which makes their management and maintenance
difficult. From the architectural perspective, these devices may have
different designs and diverse capabilities. Also, there can be different types
of devices in the fog. We distinguish for example, routers, servers, switches
[20]. Consequently, some edge devices may have specialized or powerful
processing resources such as Graphical Processing Units (GPUs), which make
them able to perform complex and heavy computational tasks. Other devices may
have big storage space, making them more suitable for caching and storing at
the edge of the network. Finally, devices such as routers and switches, with
moderate processing but with powerful networking capabilities can handle more
traffic than others.

The unavailability of information about devices’ capabilities at the fog nodes
might cause an unnecessary delay; because some devices might be required to
perform tasks they are not the best suited for performing. Therefore, exposing
the resources of fog devices to the supervising entity will help distributing
the fog tasks in an optimal manner. Indeed, the supervising entity can build
adequate resource allocation schemes from these information.

Fog computing generally relies on virtualization because of its capacity to
represent heterogeneous systems. The concept of virtualization allows running
an entire Operating System (OS) with its applications on a virtual machine
(VM). However, VMs need a significant startup time to run on hardware
platforms, which may cause an unnecessary delay for resources consumption in
fog nodes. This delay can be avoided by using containers. Containers have been
proposed as a lightweight virtualization platform, which offers much more
advantages than those offered by traditional virtualization. Containers have a
lower response time since their startup time is much smaller than VMs
(Milliseconds VS Seconds). Containers are superior to VMs in terms of CPU,
memory, and disk performance. Also, VMs’ network performance in term of
response time is lower than that of containers (microseconds) [19].

In this paper, we propose a resource representation model, and we test the
ability to discover and represent resource information independently of the
operating system, the architecture or the manufacturer. In this work,
resources of interest are processing, storage, memory and networking
capabilities. We also formulate the resource allocation optimization problem
aiming at minimizing the system latency, and we use a Lyapunov model to solve
it. In order to evaluate the performance of the proposed approach, we perform
simulations for two scenarios with Docker containers [7], a scenario with
resource representation and a scenario without resource representation.

The main contributions of this paper are summarized as follows:

  * •

We propose a resource representation model for physical resources in a fog
environment which adheres to European Telecommunications Standards Institute
(ETSI) standard ETSI-GS-MEC-009. We use this model to represent various types
of resources (processors, memory, storage, and networking) of fog nodes and
their capacities.

  * •

We propose a resource allocation model based on Lyapunov optimization to
minimize the experienced delay. Additionally, we use containers as a
lightweight virtualization mechanism to simulate our proposed method.

To the best of our knowledge, this is the first paper to study resource
representation and its usage to optimize resource allocation at the fog level.
The rest of this paper is organized as follows: we presents the system model
in Section II. Section III is dedicated to the discussion of the proposed
approach. Section IV details the simulations and the corresponding results.
Related works are discussed in Section V. Finally we conclude the paper in
Section VI.

##  II System Model

Figure 1: Generic Fog Computing architecture.

The fog computing architectural deployment consists of three layers, as
depicted in Fig. 1. At the bottom, the end users, we distinguish two types of
users. The first type is the data producers; all kind of devices capable of
intercepting data about the environment and transform it into an information
(sensors, actuators, phones, …etc). The second type of users is the data
consumers such as mobile devices, applications or even sensors.
The second layer is the fog layer, where devices are aggregated to form fog
nodes. These devices could be servers, computers, mobile devices or edge
routers and switches. This layer is dedicated to perform the data pre-
processing and real-time analytics. It is the perfect placement for the
latency-sensitive application to do processing. It could serve as caching
infrastructure in caching use cases.
Finally, on the top, the cloud and data centers layer, devoted to long-term
analytics (latency non-sensitive applications) and for permanent storage use
cases.

Let $\mathcal{U}$ be the set of users.

$\mathcal{U}=\\{u_{1},u_{2},...,u_{N}\\}$

distributed over a geographical area, covered by fog nodes. Let $\mathcal{FN}$
be the set of fog nodes.

$\mathcal{FN}=\\{fn_{1},fn_{2},...,fn_{M}\\}$

Each fog node serves a sub set of $\mathcal{U}$. A fog node is formed with $K$
devices, with $K$ is variable depending on which fog.

$\mathcal{D}_{i}=\\{d_{(i,1)},d_{(i,2)},...,d_{(i,K)}\\}$

Each device has a set of resources denoted $\mathcal{R}_{(i,j)}$.

$\mathcal{R}_{(i,j)}=\\{r_{(i,j)}^{1},r_{(i,j)}^{2},...,r_{(i,j)}^{P}\\}$

where $r_{(i,j)}^{k}$ represent the $k^{th}$ resource of the $j^{th}$ device
in the $i^{th}$ fog node.
where $r_{(i,j)}^{k}$ $\in$ $\\{Processing,Storage,Networking\\}$, and $P$ is
the number of resources.
Each device host a number $Q$ of containers denoted by $\mathcal{C}_{(i,j)}$,
in the $i^{th}$ fog node at the $j^{th}$ device. $Q$ the number of containers
at each device differs from the others.

$\mathcal{C}_{(i,j)}=\\{c_{(i,j)}^{1},c_{(i,j)}^{2},...,c_{(i,j)}^{Q}\\}$

##  III Proposed Approach

In this section we will present the proposed resources representation model
and how the entities communicate.

###  III-A Unified Resources Representation

In this paper we are interested in the physical resources (processing unites,
memory, storage and networking) of the devices forming the fog nodes. We
distinguish three types of resources. Resources dedicated to processing,
including the CPU, GPU and other computing units plus the memory. The other
type of resources is devoted to storing such as hard disks (HDD) and solid
state disks (SSD). Finally, the networking resources.

Figure 2: An overview of the resources families from a general point of view.

To discover these resources, we first need to get information about it. To do
so, we used low-level operations and commands such as CPUID to get the CPU
properties such as the architecture, number of cores and the frequency. We
also used commands such cpuinfo and meminfo for Linux based machines to get
the current state of the CPU usage and memory respectively. For the Windows
based devices, wmic command provide the same information. And so on for the
majority of the used OS in the devices forming the edge layer.

Gathering all these commands within the same program that, depending on the
Operating System used, it get the information about the devices and their
available resources. Fig. 3 shows an example of a device response when the
supervisor requested information about the CPU capabilities. The output is an
XML response with all the different information about the CPU such as the
family, the frequency, number of cores and the architecture.

Figure 3: Example of a response generated by a device being requested for CPU
information.

As described in the standard IETF RFC 3986 [5] and the ETSI MEC APIs ETSI-GS-
MEC-009 described in [6] for developing edge computing APIs. The supervising
entity uses the program to get the resources availability of the devices
forming the fog node. It performs a request over the nodes and get the whole
information or just the needed ones. The nodes expose their resources in XML
format. After that the supervisor decide what strategy to adopt in the process
distributing.

Figure 4: Overview of the system model

As illustrated in Fig. 4, users depicted at the bottom side of the figure
request tasks from the fog environment (ex. processing tasks to render a
virtual reality environment). The requests will be forwarded to the fog nodes’
supervising entity. The devices in the fog expose their resources through ETSI
MEC APIs to the supervising entity which, in turn, adequately distributes the
requested task to the suitable containers based on the information gathered
from the fog devices.

###  III-B Resources Allocation

For each container, a portion of the hosting device’s resources is allocated.
Let $\gamma_{r_{(i,j)}^{k}}$ be a binary variable to denote if the resource
$r_{(i,j)}^{k}$ is allocated to the container. And let
$\theta_{r_{(i,j)}^{k}}$ be the amount of resource $r_{(i,j)}^{k}$ allocated
to the container $c_{i,j}^{l}$. We can express the amount of resources
allocated to all the containers at the instant $t$ as follows :

$Allocated(c_{(i,j)},t)=\sum_{o\in
R_{(i,j)}}\gamma_{r_{(i,j)}^{o}}.\theta_{r_{(i,j)}^{o}}$ (1)

where $\gamma_{r_{(i,j)}^{k}}=1$ if the $r_{(i,j)}^{k}$ is allocated, and
equal to $0$ otherwise. The overall load on a device $j$ is the difference
between its maximum capacity and the sum of all containers allocated resources
:

$Load(d_{(i,j)},t)=max(r_{(i,j)})-\sum_{c\in\mathcal{C}_{(i,j)}}Allocated(c,t)$
(2)

Considering that the communication links are reliable, the experienced delay
at a given node, depend essentially on the size of the task and the size of
the queue at the container of the requested service. Let $\lambda_{(i,j)}^{k}$
be the mean of a Poisson Process of the requests arrival at the $i^{th}$ fog
and the $j^{th}$ device for the container $k$. The experience delay at the
instant $t$ is expressed as follows:

$Delay_{(i,j)}(t)=\frac{\lambda_{(i,j)}^{k}}{C_{i,j}^{max}}+Queue_{(i,j)}^{k}(t)$
(3)

where $C_{i,j}^{max}$ is the capacity of resources allocated to the container
$k$. And $Queue_{(i,j)}^{k}(t)$ is the queue size of the same container. Let
the set $Req_{i}$ be the set of requests to be processed by the fog node
$fn_{i}$. Inspired from [9], we formulated the queue dynamic for a given
container $c_{(i,j)^{k}}$ hosted at a device $j$ as follows :

$\omega_{(i,j)}^{k}(t+1)=\omega_{(i,j)}^{k}(t)-Rq_{(i,j)}(t)+\sum_{Requests}Rq_{(i,j)}^{k}(t)$
(4)

where $Rq_{(i,j)}^{k}(t)$ and $Rq_{(i,j)}(t)$ are the requests for the
container $k$ at the device $d_{(i,j)}$ of the fog node $fn_{i}$ and the total
requests to be processed by the fog node $fn_{i}$ at the instant $t$. In order
to distribute, the supervisor of the fog node needs to adopt a distribution
policy first, this distributed policy depends essentially on the exposed
resources by the devices that the supervising entity consult in real time to
get informed.
Let $\pi_{i}$ be the distribution policy adopted by the supervisor to be
applied to a fog node $fn_{i}$. The queuing dynamic of the fog node $fn_{i}$
is given by :

$U_{(i,j)}(t+1)=max(U_{(i,j)}(t)-\mu_{(i,j)}(\pi_{i}(t)),0)+Rq_{ij}(t)$ (5)

Where $\mu_{(i,j)}(\pi_{i}(t))$ is the demand rate for a service handled by a
container hosted in a device $d_{(i,j)}$. In [9] they proposed that the
service rate could be derived from the processor frequency assignment. In our
case, the resources representation service is used to get the information
about the different resources as discussed in the previous section.

For each container, $c_{(i,j)^{k}}$ the supervisor chooses the number of the
requests to be handled by the device $d_{(i,j)}$. This number is the solution
of the following problem :

$Maximize~{}:~{}Rq_{(i,j)(t)}[V\alpha_{(i,j)}-\omega_{(i,j)}(t)]$ (6a)
$subject~{}to~{}:~{}Rq_{(i,j)}(t)\leq Rq_{(i,j)}^{new}(t)$ (6b)

$V$ is a non-negative control parameter chosen by the supervisor to specify
the rate of a trade-off between the performance and the delay.
$\alpha_{(i,j)}$ is the weight of the accepted requests average demand,
$U_{(i,j)}(t)$ and $\omega_{(i,j)}(t)$ are evolving in time and represent, the
queue backlog of the fog node and the queue of the container respectively. The
solution for the problem in (6a) could be solved by fixing thresholds. We
suppose for example that the requests are admitted if :

$\omega_{(i,j)}(t)>V.\alpha_{(i,j)}$

and are not admitted if we have :

$\omega_{(i,j)}(t)\leq V.\alpha_{(i,j)}$

In order to allocate the resources, let $\pi_{i}(t)$ the policy that represent
the solution of the following optimization problem.

$Minimize~{}:~{}\lim\limits_{t\to\infty}\frac{1}{t}\sum_{\tau=0}^{t-1}\mathbf{E}\left[Delay_{(i,j)}(\tau)\right]U_{(i,j)}(t)$
(7a) $subject~{}to~{}:~{}Delay_{(i,j)}(t)\leq D^{max}$ (7b)

Where $D^{max}$ is the maximum delay experienced by the users when requesting
a service offered by a container hosted at the device $d_{(}i,j)$ at the peak
period, it is also the maximum experienced delay when the demand rate is for a
given service is high.

##  IV Simulations and Results

Figure 5: The average requests arrival, the admitted requests and requests on
pending.

We simulated a network of $10$ fog nodes. Each fog is formed by a number of
devices varying between $5$ and $50$, where each device is hosting from $10$
to $100$ containers. We consider that the requests arrive at a rate within $0$
and $100$ per time slot. The capacity of processing vary between $5$ to $10$
request per time slot. The simulation duration is $500$ time slot. We
simulated the system in $3$ cases of the $V$ parameter configuration
$(0.2,0.5,0.9)$.

Fig. 5 illustrate the requests arrival with the accepted, admitted and pending
requests, respectively on the top, middle and bottom.

Figure 6: The impact of the parameter V on the queue size, in both approaches.
V={0.2, 0.5, 0.9}

.

On the requests arrival, the supervising entity check the available resources
of each device through the ETSI MEC API. The response is the set of maximum
capacities and the available resources of each device, also, checking for the
containers queue state based on the equation (3). Once having the required
information, the supervisor based solve the Lyapunov optimization in (7b) to
get the adequate policy $\pi_{i}$ (demand rate) to perform the tasks
distribution and allocate the require resources.

Figure 7: Delay evolution in time. (a) a zoomed view of the experienced delay
between the time slots 400 and 600. (b) The average experienced delay (time
slots)

We are interested in the experienced delay while processing requests on
different fog nodes. We compared a custom approach, where no resource
representation is considered, and our approach where the resource
representation is considered. We enabled the resource representation using
Lyapunov optimization, where requests are processed within lower delay and
with a maximum number of requests processed as shown from the queue size in
Fig. (6). The parameter $V$ ensures the trade-off between the experienced
delay and the performance. The performance is characterized by the number of
requests that a fog node can hold, in other words, it is the load of the node
as described in (1). The more we have requests in the queue, the more delay
increases. With a custom approach the queue size has more requests, which
means that the number of requests to be processed is higher than when adopting
a policy based on Lyapunov resource allocation policy. In addition, a small
queue implies a lower delay, but in the case of a lower $V$ parameter, the
users will not be interested in the delay, thus, more interested in what they
are requesting. In this case, the queue size becomes bigger.

Fig. 7 shows the delay evolution in the different cases from the requests
arrival, processing to response. Fig. (7-a) shows the average experience delay
in the time. In the custom approach adopted for resource allocation, the delay
is high and the number of requests on pending goes high as well, and that
because some devices are requested to perform tasks they are not capable to
accomplish. Fig. (7-b) is a zoomed view to reflect the details of the results
obtained by applying Lyapunov approach, theoretically and applicably. The
results show that the theoretical approach of the proposed Lyapunov approach
give better results than results of applicative one by approximatively $\sim
5\%$. The degradation of performance is due to the hardware losses. The
results shown that the delays is decreased by approximately $\sim 20\%$ in
some cases.

##  V Related Works

The work in [11] proposed a model to represent resources such as computing,
memory, storage, and communication within a cloud computing context. The
proposed model is useful in order to characterize cloud applications, servers
and even VMs.

A holistic taxonomy on resource management at the edge of the network was
proposed by [12]. They present the terminology and the different types of
architectures to characterize the state of the art in the edge computing
paradigm. The paper discussed the resources management from four different
perspectives, resource type, resource management objectives, resource location
and resource use.

Many papers proposed the utilization of containers at the edge of the network.
In fact, using containers instead of the virtual machines could significantly
reduce the overhead and response time. The authors in [16] propose an
evaluation of the Docker containers technology as an Edge Computing platform.
They evaluated the deployment, resources and service management, fault
tolerance and finally the caching. They concluded that Docker containers
provide fast deployment and good performance. This would make of containers a
viable Edge Computing platform. Moreover, [10] within the containers
technologies context at the Edge. They presented a novel architecture for
tasks’ management $-$selection and scheduling$-$ at the edge of using
container-as-a-service (CoaaS). Finally, they proposed a container migration
(internal and external) technique in real-time for minimizing the energy
consumption.

Lyapunov optimization was investigated by [17] to solve the resource
allocation problem. The authors investigate the adaptive resource allocation
with Lyapunov optimization for time-varying wireless networks. They proposed a
dynamic resource allocation (DRA) algorithm is to maintain the wireless
network dynamics. Also, the authors investigate the tracking error between the
results of DRA algorithm and the desired optimal resource allocation solution.
Based on the results, they also develop an adaptive-compensation resource
allocation (ACRA) algorithm, which iterates only once when the network state
changes for saving the huge iteration overheads. Moreover, they proved that
the ACRA algorithm asymptotically tracks the moving equilibrium point with no
tracking errors.

Authors in [8] used Lyapunov optimization to reduce the energy consumption for
reconfiguration in Cloud datacenters, while ensuring resources elasticity in
order to ensure high availability of the platform. The servers capabilities
were enhanced using the overclocking technique and Lyapunov optimization to
ensure the the stability of the design and to minimize the energy cost.

The game theory is a power mathematical framework widely used to solve the
resource allocation problems. In [18] the authors, consider a fog computing
architecture, where a set of data service operators (DSO) controls the fog
nodes (FN), providing data service requested by a set of data service
subscribers (DSS). The authors proposed a joint optimization framework for all
FN, DSO and DSS to achieve an optimal resource allocation scheme in a
distributed fashion. The proposed approach consists of the pricing problem
analyze for all DSOs and the resource allocation for DSSs. Moreover, a many-
to-many matching game is applied to investigate the pairing problem between
the DSOs and the FNs. Finally, within the same DSO, another many-to-many
matching game was proposed to solve the FN-DSS pairing problem.

Authors in [19] build a new task-scheduling model within a containers
architecture. They proposed a task-scheduling algorithm to ensure that the
completion of tasks and the number of concurrent tasks for the fog node.
Finally, a reallocation mechanism was proposed to reduce the latency in
accordance with the characteristics of the containers.

##  VI Conclusion

In this paper, we proposed a resource representation for fog computing through
MEC APIs which allow exposing, at any time, information (i.e. CPU, memory,
storage and networking) about the physical resources the fog devices. This
information is used by the supervising entity of the fog to make the best
decisions on distributing tasks to each node of the network. Moreover, we
modeled the problem of latency minimization and proposed a corresponding
Lyapunov-based optimization for resource allocation of the fog nodes.
Simulation shows that the proposed approach, combining both the resource
representation and the resource allocation optimization, allows minimizing the
latency, thus, enhancing system performance.

## References

  * [1] C. Mouradian et al., ”A Comprehensive Survey on Fog Computing: State-of-the-Art and Research Challenges,” in IEEE Communications Surveys & Tutorials, vol. 20, no. 1, pp. 416-464, Firstquarter 2018.
  * [2] Eva Marin Tordera et al., ”What is a Fog Node A Tutorial on Current Concepts towards a Common Definition” arXiv:1611.09193 [cs.NI] 2016.
  * [3] Minxian Xu et al., ”A Survey on Load Balancing Algorithms for VM Placement in Cloud Computing” arXiv:1607.06269 [cs.DC] 2017.
  * [4] Prateek Sharma et al., ”Containers and Virtual Machines at Scale: A Comparative Study,” In Proceedings of the 17th International Middleware Conference (Middleware ’16). ACM, New York, NY, USA, Article 1, 13 pages. DOI: https://doi.org/10.1145/2988336.2988337
  * [5] ETSI et al., ”Mobile Edge Computing (MEC); General principles for Mobile Edge Service APIs”; July 2017 (White paper)
  * [6] Yun Chao Hu et al., ”Mobile Edge Computing A key technology towards 5G”, September 2015 (ETSI White Paper)
  * [7] Christopher Negus. et al., ”Docker Containers” (2nd ed.). Addison-Wesley Professional. 2015
  * [8] O. Chakroun et al., ”Reducing Energy Consumption for Reconfiguration in Cloud Data Centers,” 2016 IEEE 84th Vehicular Technology Conference (VTC-Fall), Montreal, QC, 2016, pp. 1-6.
  * [9] O. Chakroun et al., ”Resource Allocation for Delay Sensitive Applications in Mobile Cloud Computing,” 2016 IEEE 41st Conference on Local Computer Networks (LCN), Dubai, 2016, pp. 615-618.
  * [10] K. Kaur et al., ”Container-as-a-Service at the Edge: Trade-off between Energy Efficiency and Service Availability at Fog Nano Data Centers,” in IEEE Wireless Communications, vol. 24, no. 3, pp. 48-56, June 2017.
  * [11] M. Guzek et al., ”A Holistic Model for Resource Representation in Virtualized Cloud Computing Data Centers,” 2013 IEEE 5th International Conference on Cloud Computing Technology and Science, Bristol, 2013, pp. 590-598.
  * [12] Klervie Toczé et al., ”A Taxonomy for Management and Optimization of Multiple Resources in Edge Computing,”” Wireless Communications and Mobile Computing, vol. 2018, Article ID 7476201, 23 pages, 2018.
  * [13] A. Abouaomar et al., ” _Caching, device-to-device and fog computing in 5th cellular networks generation : Survey,_ ” 2017 International Conference on Wireless Networks and Mobile Communications (WINCOM), 2017, pp. 1-6, doi: 10.1109/WINCOM.2017.8238174.
  * [14] M. Azizian et al., ” _An Optimized Flow Allocation in Vehicular Cloud,_ ” in IEEE Access, vol. 4, pp. 6766-6779, 2016, doi: 10.1109/ACCESS.2016.2615323.
  * [15] A. Abouaomar et al., ” _Users-Fogs association within a cache context in 5G networks:Coalition game model,_ ” 2018 IEEE Symposium on Computers and Communications (ISCC), 2018, pp. 00014-00019, doi: 10.1109/ISCC.2018.8538500.
  * [16] B. I. Ismail et al., ”Evaluation of Docker as Edge computing platform,” 2015 IEEE Conference on Open Systems (ICOS), Bandar Melaka, 2015, pp. 130-135.
  * [17] W. Wu et al., ”Adaptive Resource Allocation Algorithm of Lyapunov Optimization for Time-Varying Wireless Networks,” in IEEE Communications Letters, vol. 20, no. 5, pp. 934-937, May 2016.
  * [18] H. Zhang et al., ”Computing Resource Allocation in Three-Tier IoT Fog Networks: A Joint Optimization Approach Combining Stackelberg Game and Matching,” in IEEE Internet of Things Journal, vol. 4, no. 5, pp. 1204-1215, Oct. 2017.
  * [19] L. Yin et al., ”Tasks Scheduling and Resource Allocation in Fog Computing Based on Containers for Smart Manufacturing,” in IEEE Transactions on Industrial Informatics, vol. 14, no. 10, pp. 4712-4721, Oct. 2018.
  * [20] E. D. N. Ndih et al., ” _On Enhancing Technology Coexistence in the IoT Era: ZigBee and 802.11 Case,_ ” in IEEE Access, vol. 4, pp. 1835-1844, 2016, doi: 10.1109/ACCESS.2016.2553150.
  * [21] M. Azizian et al., ” _Vehicle Software Updates Distribution with SDN and Cloud Computing,_ ” in IEEE Communications Magazine, vol. 55, no. 8, pp. 74-79, Aug. 2017, doi: 10.1109/MCOM.2017.1601161.
  * [22] A. Rachedi et al., ” _IEEE Access Special Section Editorial: The Plethora of Research in Internet of Things (IoT),_ ” in IEEE Access, vol. 4, pp. 9575-9579, 2016, doi: 10.1109/ACCESS.2016.2647499.