∎

11institutetext: C. Guerrero (Corresponding author), I. Lera, C. Juiz
22institutetext: Computer Science Department, University of Balearic Islands,
Crta. Valldemossa km 7.5, E07122 Palma, Spain
Tel.: +34-971172965
Fax: +34-971173003
C. Guerrero
22email<EMAIL_ADDRESS>
I. Lera
22email<EMAIL_ADDRESS>
C. Juiz
22email<EMAIL_ADDRESS>
# A Lightweight Decentralized Service Placement Policy for Performance
Optimization in Fog Computing††thanks: This research was supported by the
Spanish Government (Agencia Estatal de Investigación) and the European
Commission (Fondo Europeo de Desarrollo Regional) through grant number
TIN2017-88547-P (MINECO/AEI/FEDER, UE).

Carlos Guerrero  Isaac Lera  Carlos Juiz

(Received: date / Accepted: date)

###### Abstract

A decentralized optimization policy for service placement in fog computing is
presented. The optimization is addressed to place most popular services as
closer to the users as possible. The experimental validation is done in the
iFogSim simulator and by comparing our algorithm with the simulator’s built-in
policy. The simulation is characterized by modeling a microservice-based
application for different experiment sizes. Results showed that our
decentralized algorithm places most popular services closer to users,
improving network usage and service latency of the most requested
applications, at the expense of a latency increment for the less requested
services and a greater number of service migrations.

###### Keywords:

Fog computing Service placement Performance optimization

##  1 Introduction

The emerging of application development for Internet of Things (IoT) has
revitalized the popularity of wearables, logistics, smart cities, or e-health
environments (Atzori et al, 2010; Li et al, 2015; Ko et al, 2016; Darwish et
al, 2017). The number of users in these systems, and their performance
requirements, is increasing continuously. Those requirement increments were
initially satisfied by integrating IoT and cloud architectures (Botta et al,
2016; Diaz et al, 2016). The combination of both technologies allows, firstly,
IoT applications to dispose of unlimited computational and storage capacities,
and secondly, to expand the scope of cloud systems by dealing with real-life
components (Cavalcante et al, 2016; Darwish and Hassanien, 2017). But the
integration of IoT and cloud generates new problems, as for example the
increase in the service latency that is a critical requirement for some
e-health or gaming IoT applications (Dastjerdi and Buyya, 2016). Fog computing
emerged to cover these limitations and it opened a broad range of renewed
challenges in topics such as security, reliability, sustainability, scaling,
IoT marketplaces, or resource management (Varghese and Buyya, 2017; Mahmud et
al, 2018; Chiang and Zhang, 2016).

Fog computing exploits resource capacities of networking components to
allocate services or to store data. Therefore, firstly, services are closer to
the clients and, secondly, data do not need to be transfered in its whole to
the cloud. Both issues have a notable performance impact, reducing the network
latency and usage. Resource managers are important components to improve this
performance.

On the one hand, fog data managers need to deal with the selection of the data
that is stored in the cloud providers and which is stored in fog devices. For
the latter case, placement policies need to be considered to optimize the use
of the storage capacities of the fog layer. On the other hand, fog service
orchestrators need to decide the allocation of the services in the fog devices
to improve the Quality of Service (QoS) and the usage of the fog layer
considering scalability and dynamicity requirements (Wen et al, 2017). They
should deal with the placement and scalability of user-shared services by
creating, in the fog devices, additional instances of services already
available in the cloud.

IoT environments, as for example smart cities, usually have thousands, even
millions, of devices, clients or services. Centralized management could reach
in a non-affordable optimization. Previous solutions to solve the Fog Service
Placement Problem (FSPP) are based on centralized solutions, with the
following main drawbacks: (a) scalability, as the execution time of a global
optimization algorithm is usually increased as the number of devices to manage
is increased; (b) network overhead, as the fog devices need to send their
performance data to the centralized broker; (c) reliability, as the broker is
a single point of failure (SPOF); (d) decision latency, as the decisions need
to be transmitted from the centralized broker to each device; and (e)
heterogeneity, as the central broker needs to deal with data from very
different types of fog devices, and the communication protocol or the
orchestrating mechanism could be also very different.

We propose to address the problem of service placement in a decentralized way,
where each device takes the local optimization decisions, by considering only
its own resource and usage data and consequently, the execution time is
independent of the number of devices, the performance data is not send between
devices, SPOF are avoid, the decision are taken locally and all the resources
and the inputs of the algorithm are homogeneous inside of the same device. We
propose to base the decisions of the algorithm in placing the most popular
services as closer as possible to the clients, using the hop distance as the
indicator of this proximity.

We raise two research questions: (RQ1) Is it possible to define a local and
decentralized optimization algorithm that would be able to place the most
popular services in the fog devices with smallest hop distances to the
clients?; (RQ2) Would this placement policy result in an optimization of the
performance of the fog computing architecture in terms of, for example,
service latency or network usage?

The three main contributions of our work are: (a) An up-to-date brief survey
of researches addressed to optimize the Fog Service Placement Problem (FSPP);
(b) A decentralized and low overhead proposal to reduce the network usage in a
fog computing architecture; (c) An experimental validation based on a
microservice-based application.

##  2 Related Work

Previous fog service management algorithms have explored a wide range of
optimization techniques, such as heuristics, greedy algorithms, linear
programming, or genetic algorithms, between others. These service managers
have defined several aspects of the fog resources, such as placement,
scheduling, allocation, provisioning, or mapping for services, resources,
clients, tasks, virtual machines, or even fog colonies. These solutions have
been defined for environments such as industrial IoT, smart cities, eHealth,
or mobile micro-cloud.

The characteristics of the related work have been summarized in Table 1, by
indicating the IoT scope for which the solution was proposed (column Scope),
the optimization purpose (column Objective functions), the elements that the
optimization algorithm manages to improve the objective functions (column
Decision variables), if the broker manager is centralized or not (column
Broker), the optimization algorithm (column Alg.), and the technique or tool
used in the validation (column Val.). The related studies are grouped in terms
of their optimization algorithms.

We explain the related researches grouped by their optimization algorithms.

Table 1: Summary of the brief survey for Fog Service Placement Problem
approaches.

Authors |  Scope111 _Scope:_ G- General IoT systems; I - Industrial IoT systems; H - eHealth IoT systems; C - Crowdsensing apps; E- Embedded systems; M - Mobile Micro-Clouds (MMC). |  Objective functions |  Decision variables |  Broker222 _Broker:_ C - Centralized; D - Decentralized; Ds - Distributed ; H - Hierarchical (Two broker levels, global and fog colonies). |  Alg.333 _Algorithm:_ ILP - Integer Linear Programming; MILP - Mixed integer linear programming; GA - Genetic Algorithm; MDP - Markov Decision Process; D-MDP - Decoupled Markov Decision Process; MWIS - Maximum Weighted Independent Set; ADMM - Alternating Direction Method of Multipliers; VM - Virtual Machine; PN - Petri Nets; MC - Monte Carlo; Cons. - Consensus algorithm; SP - Shortest-path; Heur. - Heuristics; BP - Binary programming; D - Decomposition; BET - Benchmarking, Evaluation and Testing; Own - Own algorithm. |  Val. 444 _Validation:_ O - Own simulation; F - iFogSim; A - Analytically; B - Benchmarking; P - PuLP and Gurobi Optimizer; T - Testbed.
---|---|---|---|---|---|---
Arkian 2017 |  C |  Cost |  Client association, Resource provisioning , Task distribution, VM placement |  C |  MILP |  O
Gu 2017 |  H |  Cost |  Base station association, Task distribution, VM placement |  C |  ILP |  O
Velasquez 2017 |  G |  Network latency, Service migrations |  Service placement |  C |  ILP |  —
Huang 2014a; 2014b |  G |  Communication power consumption |  Service merging and placement |  C |  ILP, MWIS |  O
Souza 2016 |  G |  Service delay |  Service placement |  C |  ILP |  P
Skarlat 2017b |  G |  Deadline violations, Cost, Response time |  Service placement |  C |  ILP |  F
Zeng 2016 |  E |  Task completion time |  Task scheduling, Task image placement, Workload balancing |  D |  MILP |  O
Barcelo 2016 |  G |  Power consumption |  Service placement |  C |  ILP |  O
Wen 2017 |  G |  Response time, QoS |  Service placement |  C |  GA |  O
Skarlat 2017a |  F |  Resource waste, Execution times |  Fog colony service placement |  H |  GA |  F
Yang 2016 |  M |  Cost, Latency and Migration |  Service placement and Load dispatching |  C |  Greedy, ILP, GA |  O
Ni 2017 |  G |  Response time, Cost |  Resource allocation and scheduling |  C |  PN |  O
Urgaonkar 2015a |  G |  Queue length, cost |  Service migration |  C |  D-MDP |  O
Brogi 2017; 2017 |  G |  Resource consumption, QoS |  Service placement |  C |  MC |  O
Colistra 2014 |  G |  Resource usage |  Resource allocation |  Ds |  Cons. |  O
Wang 2015; 2015b |  M |  Cost |  Look-ahead service placement |  C |  SP and MDP |  O
Billet 2014 |  G |  Resource usage, Power consumption and Load balancing |  Task placement |  C |  BP Heur. Greedy |  O
Taneja 2017 |  G |  Network usage, Power consumption, Latency |  Service placement |  C |  Own |  F
Wang 2017 |  M |  Load balancing |  Service placement |  C |  Own |  O
Bittencourt 2017 |  G |  Network usage and delay |  Service placement |  C |  Own |  F
Farris 2015 |  F |  Executed tasks |  Resource provisioning |  C |  Own |  O
Deng 2015 |  G |  Power consumption, Response time |  Workload placement |  C |  D |
Saurez 2016 |  G |  Latency |  Service placement and migration |  C |  Own |  B
Venticinque 2018 |  G |  Performance |  Service placement |  C |  BET |  T
Gupta 2017 |  G |  Energy, Network usage, Latency |  Sevice placement |  D |  FIFO |  F
[This work] |  G |  Hop count |  Service placement |  D |  Own |  F

Linear programming is a common approach for resource optimization. Arkian et
al (2017) formulated a mixed-integer non-linear program that was linearized
into a mixed integer linear program for the optimization of cost. Gu et al
(2017) also used this optimization approach. They integrated medical cyber-
physical systems and fog computing and optimized the cost by considering the
base station association, task distribution and virtual machine placement. The
work of Velasquez et al (2017) was addressed to reduce the number of service
migrations and the network latency.

Huang et al (2014a) presented a quadratic programming formulation for the
problem of reducing the power consumption in fog architectures by co-locating
neighboring services on the same devices. (Huang et al, 2014b) also presented
a previous work where the problem was modeled as a Maximum Weigthed Independen
Set problem (MWIS). Souza et al (2016) studied an allocation algorithm based
on Integer Linear Programming that minimized the service latencies in a fog
computing environment, while the fulfillment of capacity requirements were
guaranteed. Skarlat et al (2017b) studied the service placement problem by
considering the QoS requirements of the applications executed in a fog
architecture. Zeng et al (2016) proposed to manage the task scheduling, the
task storage placement and the I/O balanced use to reduce the task completion
time in software-defined embedded systems. Barcelo et al (2016) formulated a
service placement optimization to reduce power consumption in IoT environments
as a minimum mixed-cost flow problem.

A second set of studies were implemented with genetic algorithms (GA). Wen et
al (2017) presented a parallel GA to reduce the response time. Skarlat et al
(2017a) introduced the concept of fog colonies for a hierarchical optimization
process. Each colony used a GA to decide the services that were placed in the
colonies and which ones were propagated to neighbor colonies. Yang et al
(2016) compared three optimization algorithms based on a greedy heuristic, a
linear programming and a GA. Additionally, a model to predict the distribution
of user’s future requests was also presented to adapt the service location.

Linear programming and GA are the most popular solutions, but there are also
an important number of related researches exploring other alternatives, such
as, Petri nets, Markov decision or new and own algorithms. Ni et al (2017)
proposed to use priced timed Petri nets (PTPNs) for resource allocation in fog
computing. Their proposal optimized price and time costs to complete a task.
Their simulation results showed a higher efficiency than static allocation
strategies. Urgaonkar et al (2015a) addressed the objective of minimizing the
operational costs of service placement in fog, while the performance was
guaranteed. They modeled the scenario as a sequential decision using a Markov
Decision Process (MDP), decoupling de problem into two independent MDPs and,
finally, optimizing with the Lyapunov technique. Brogi et al. presented the
tool FogTorch in two research works (Brogi and Forti, 2017; Brogi et al,
2017). The first one presented the model for the QoS-aware deployment of
multicomponent IoT applications in fog infrastructures. The second one
presented the results of using Monte Carlo simulations in the FogTorch tool,
classifying the deployments in terms of QoS and resource consumptions. Do et
al (2015) proposed a decentralized algorithm for resource allocation in fog
environments for the specific case of video streaming. Their solution was
based on the proximal algorithm and alternating direction method of
multipliers. The model was validated analytically. Colistra et al (2014)
adapted the consensus algorithm to allow devices to cooperate in the
distributed resource allocation problem to adequately share the resources.
Wang et al (2015) presented a service placement algorithm that used predicted
costs for look-ahead optimizing the total provider cost for a given period of
time. The authors validated their proposal using real-world user-mobility
traces in simulations. Urgaonkar et al (2015b) also proposed a solution for
this last scenario but considering a Markov Decision Process. Billet and
Issarny (2014) formulated the task allocation problem in IoT as a binary
linear optimization that its computational cost was reduced by including a
heuristic and a greedy algorithm.

Ni et al (2017) proposed to use priced timed Petri nets (PTPNs) for resource
allocation in fog computing. Their proposal optimized price and time costs to
complete a task. Urgaonkar et al (2015a) addressed the objective of minimizing
the operational costs of service placement in fog, while the performance was
guaranteed. They modeled the scenario as a sequential decision using a Markov
Decision Process (MDP), decoupling the problem into two independent MDPs and,
finally, optimizing with the Lyapunov technique. Brogi et al. presented the
tool FogTorch in two research works ( (Brogi and Forti, 2017; Brogi et al,
2017)). The first one presented the model for the QoS-aware deployment of
multicomponent IoT applications in fog infrastructures. The second one
presented the results of using Monte Carlo simulations in the FogTorch tool,
classifying the deployments in terms of QoS and resource consumptions.
Colistra et al (2014) adapted the consensus algorithm to allow devices to
cooperate in the distributed resource allocation problem to adequately share
the resources. Wang et al (2015) presented a service placement algorithm that
used predicted costs for look-ahead optimizing the total provider cost for a
given period of time. The authors validated their proposal using real-world
user-mobility traces in simulations. Urgaonkar et al (2015b) also proposed a
solution for this last scenario but considering a Markov Decision Process.
Billet and Issarny (2014) formulated the task allocation problem in IoT as a
binary linear optimization that its computational cost was reduced by
including a heuristic and a greedy algorithm.

Taneja and Davy (2017) proposed a service placement algorithm for efficient
use of the network and power consumption. The algorithm sequentially assigned
the highest demanding application modules to the nodes with biggest
capacities. Wang et al (2017) proposed, a first optimization stage modeled as
linear graphs to be later extended to tree application models using algorithms
with polynomial-logarithmic ratios. Bittencourt et al (2017) compared three
service allocation algorithms to illustrate that these strategies depend on
the demand coming from mobile users and can take advantages of fog proximity
and cloud elasticity. Farris et al (2015) proposed that the edge nodes
orchestrated the provisioning of resources in micro-cloud federations using a
decomposer module. Deng et al. 2015 studied the trade-off between power
consumption and delay in fog computing. They decomposed the initial allocation
problem into three subproblems independently solved with convex optimization,
ILP and Hungarian method. Saurez et al (2016) presented a service migration
algorithm based on the mobility pattern of the sensors and the dynamic
computational needs of the applications. The solution was built using
containers and the experimental results showed improvements in the migration
latencies. Venticinque and Amato (2018) presented a methodology based on three
phases: Benchmarking, Evaluation and Testing. This methodology helps
developers to meet application requirements and to optimize performance and
utilization of available resources.

The developers of the iFogSim simulator implemented a decentralized service
placement policy called Edgewards (Gupta et al, 2017). It placed the services
in each single path between clients and the cloud. The services were placed in
a First-In-First-Allocated policy. Services from different paths were merged
if they were placed in the same device and migrated to upper devices if
necessary. Additionally, instances from other paths in upper devices of a
candidate service were considered and it was placed in the upper device to
merge both instances even when closer devices had enough resources. Despite
the placement algorithm was decentralized, it needed some general information
of the placement status, such as the already placed services for each path
between the clients and the cloud. Their experiments compared the results with
the allocation of all the services in the cloud provider.

Most of those previous works were modeled as a centralized broker or
orchestrator that needs information from all the components in the system (fog
devices, clients, cloud, services) and takes global decisions to optimize the
service placement. Problems with the scalability and the computational
complexity of the algorithm are clear when the number of elements is very high
such as, for example, in smart cities. Decentralized service orchestration in
fog computing arises as a current open challenge. It is necessary to define
solutions that deal with a smaller number of elements, as in the case of fog
colonies (Skarlat et al, 2017a), or even completely decentralized
optimizations. We propose a decentralized service placement orchestrator to
minimize the hop count of the most requested services.

##  3 Architecture Proposal

Fog computing is an architecture pattern where clients request services to
cloud providers through a network composed by fog devices. These devices have
computational and storage capacities that allow them to allocate data and
instances of the cloud services. Therefore, data and service management
policies are needed to decide when and where to place the services and the
data. Our architecture proposal is focused on the Fog Service Placement
Problem (FSPP).

A general fog computing architecture is represented in Figure 1 where three
layers can be identified: cloud layer, fog layer and client layer. The
architecture can be modeled as a graph where the nodes are the devices and the
edges the direct network links between devices. Three types of devices can be
differentiated: a device for the cloud provider of the cloud layer; the
gateways, that are the access points for the clients; the fog devices, the
network devices between the cloud provider and the gateways. All the devices
have resources to allocate and execute services.

Figure 1: Fog computing architecture.

We consider that the applications follows a microservice based development
pattern, that is increasingly being used in IoT applications (Vogler et al,
2016; Krylovskiy et al, 2015; Saurez et al, 2016). This type of applications
are modeled as a set of small and stateless services that interoperate between
them to accomplish a complex task (Balalaie et al, 2016). Thus, the services
can be easily scale up, by downloading the code and executing it, or scale
down, by just stopping the execution of the service. We assume that there is
at least one instance of each service running in the cloud provider.

We base our proposal on the idea that the best placement of the services is in
devices as closer as possible to the clients’ gateways. In an unreal scenario
with unlimited resources in the fog devices, the optimal service placement
would be to place instances of each service in all the gateways. Since the
resource capacity limits the number of service instances in the devices, some
services need to be migrated to other devices. Our proposal migrates those
services to devices within the shortest path between the gateway and the cloud
provider.

Migrating the services along the devices in the shortest path with the cloud
provider, instead of any other devices around them, is based on the idea that,
sooner or later, the execution flow of the interrelated services would need to
execute some service in the cloud provider. Moreover if data need to be stored
in a centralized place. Thus, if the migrated services are placed in devices
out of the shortest path, the total path to the cloud provider will be
increased. Figure 2 illustrates an example where a service, $S_{2}$ is
migrated from a device $D_{1}$. The application communication times is one
step bigger when service $S_{2}$ is placed in $D_{2}$, a device out of the
shortest path between $D_{1}$ and the cloud provider, with regard to the case
of placing it in the next device in the shortest path, $D_{3}$.

Figure 2: Example of network delay benefits for a service migration scheme
within the shortest path.

We propose a priority rule by placing first the most popular services, in
terms of service requests, in the devices that are closer to the clients, and
migrating the less requested to upper devices in the shortest path with the
cloud provider in case that the closest device does not have enough free
resources. For the sake of simplicity, in the rest of the article upper
devices refers to any of the devices that are in the shortest path between the
device and the cloud provider.

We finally consider that once that a service is migrated to an upper device,
it is also better to migrate all its interoperated services, to avoid device
loops in the service execution flow. An illustrative example is showed in
Figure 3. Consider a service execution flow as $S_{1}\rightarrow
S_{2}\rightarrow S_{3}\rightarrow S_{4}$ and that the service $S_{2}$ needs to
be migrated to the upper device $D_{3}$. If we only migrate service $S_{2}$ to
device $D_{3}$, the application makespan will be increased in two
communication steps, with regard to the case of also migrating service $S_{3}$
to $D_{3}$, which will keep the same application makespan. This strategy is
reinforced with the idea that once that a service has been migrated to an
upper devices due to not enough free resources, the placement of any of the
remaining services will be also very unlikely in the lower device.

Figure 3: Example of network delay benefits for a service migrating scheme
with migration of interoperated services.

We propose to execute a decentralized service broker in each device to
implement our strategy. Figure 4 shows the components of the device broker:
Service Usage Monitor (SUM), gathers information of the services’ performance
and resource usage and the information about the services interoperability;
Service Migration (SM), sends allocation requests to other devices; Service
Placement Request Manager (SPRM), is the local and decentralized optimization
algorithm that decides if a given service is allocated or, on the contrary,
migrated to other device; and Service Popularity Monitor (SPM), gathers
information about the request rate of each service.

Figure 4: Decentralized service placement manager.

When a new client is connected to one leaf device, or gateway, one Service
Allocation Request (SAR) is sent to the gateway for each service the client
requires. All these requests are received by the SPRM and it decides if the
service is placed in the current device or whether the SAR is shifted to upper
devices, based on the algorithm explained in Sect. 4.2. If the SAR is accepted
by the SPRM, a service image is downloaded from the cloud provider to be
executed in the current device. The placement process could generate
deallocation of other services already instantiated in the device. A SAR is
sent to upper devices for each deallocated service instance. Deallocated
instances are just deleted from the device, as the new instances in the upper
devices would be downloaded from the cloud provider. All this process is
repeated recursively in the upper devices when a SAR is shifted.

The algorithm is running in each fog device, and the algorithm only considers
variables that are obtained locally in the device by the defined monitors (SPM
and SUM), such as the device service request rate, or the device resources
(demanded, used or available), between others. Sending performance or system
data between the devices is not necessary and delays in the decision due to
network transmission or overheads in the network are avoid. Additionally, the
overall computational complexity of the algorithm is very low, and the
placement decision is obtained in a limited period of time and, moreover, this
time is not increased as the number of devices is scaled up.

##  4 Problem Statement

###  4.1 System Model

The Fog Service Placement Problem (FSPP) considers a set of clients $C_{n}$
that request applications that are hosted in a cloud provider $D_{cloud}$. The
applications are modeled as a set of services modules, $S_{x}$ that are
related through a many-to-many consumption relationships,
$cons:\\{S_{x}\\}\rightarrow\\{S_{x^{\prime}}\\}$, as the microservice-based
application development model defines (Balalaie et al, 2016). This model has
been also proposed to deploy applications in fog computing (Vogler et al,
2016; Krylovskiy et al, 2015; Saurez et al, 2016). Applications are defined as
a directed graph, where the nodes are the services and the edges indicate the
services that are requested by other ones, i.e. their interoperability.

For an easier explanation of our algorithm in Sect. 4.2, we also consider the
transitive closure of a service represented as $T^{+}_{S_{x}}$. In graph
theory, the transitive closure of a node is the set of nodes than can be
achieve from that node, i.e., there is at least one path between both nodes
(Munro, 1971). In our particular case, the transitive closure of a service
represents all the services that need to be executed when the service is
requested. Figure 5 shows an example of an application and each of the
transitive closures, $T^{+}_{S_{x}}$, obtained for each service.

Figure 5: Example of transitive closures for each service of an application.

The clients request the applications in the cloud provider through a set of
interconnected network devices, $D_{i}$. These network devices have processing
capacities, and they are able to allocate service modules to reduce the
network latency or hop distance between clients and services. The physical
interconnections of the devices create a graph structure where the nodes are
the devices and the edges are the direct network links between devices.

For a clearer explanation of the algorithm in Sect. 4.2, we also defined
$SP_{S_{x}}^{cloud}$ as the shortest path between a device and the cloud
provider, that is a path of ordered devices whose sum of the network distances
of its constituent network links is the minimum for all the paths between the
device and the cloud provider. Additionally, we defined the father of a
device, $father(D_{1})$, as the first device in the shortest path to the cloud
provider.

Several instances, $S^{y}_{x}$, of the same service, $S_{x}$, can be allocated
across the system, i.e., the services can be horizontally scaled and clients,
or other services, can request any of these instances. The allocation function
is defined as a many-to-many relationship
$alloc:\\{S_{x}\\}\rightarrow\\{D_{i}\\}$, if we refer to the services, or as
a many-to-one relationship $alloc:\\{S^{y}_{x}\\}\rightarrow\\{D_{i}$}, if we
refer to the instances. Similarly, the many-to-many relationship that
represents the services allocated in a device is defined as
$alloc:\\{D_{i}\\}\rightarrow\\{S_{x}\\}$.

The clients need to be connected to the network to request the service
modules. These clients are connected to one and only one leaf device, but
several clients can be connected in the same leaf device. These clients are
mobile devices, sensors, actuators, or others. This connection is modeled
through a many-to-one relationship $conn:\\{C_{n}\\}\rightarrow\\{D_{i}\\}$.
Additionally, each client $C_{n}$ in the system is characterized by its
service request rate, $\lambda^{C_{n}}_{S_{x}}$. Consequently, each device
$D_{i}$ in the system can be also characterized by the request rates that it
receives for each service, $\lambda^{D_{i}}_{S_{x}}$, and calculated as the
summation of request rates of the clients whose shortest paths to the cloud
providers ($SP_{C_{n}}^{cloud}$) include that device $D_{i}$:

$\lambda^{D_{i}}_{S_{x}}=\sum^{C_{n}}\lambda^{C_{n}}_{S_{x}}\quad\forall\
C_{n}\ |\ D_{i}\ \in\ SP_{C_{n}}^{cloud}$ (1)

The devices are characterized by their resource capacities. These resources
are defined as a set of n-values, one for each resource element, such as
processor, memory, or storage. We represent the capacity of a device $D_{i}$
as a n-tuple $R^{cap}_{D_{i}}=<r_{0},r_{1},...r_{n-1}>$. For the sake of
simplicity, we have only considered one resource in this present study, the
computational capacity of a device. Thus, the resource capacity is defined as
$R^{cap}_{D_{i}}=<r_{cpu}>$. Services allocated in a device generate a
resource consumption that can be defined as a tuple
$R^{con}_{S_{x}}=<r_{0},r_{1},...r_{n-1}>$ where the consumption of each
individual resource element is indicated. As we have mentioned before, we only
consider the CPU consumption in this study, so $R^{con}_{S_{x}}=<r_{cpu}>$.
The cloud provider is consider as an special device where resources are
unlimited as they can be scaled horizontally as much as it is necessary. The
cloud resource capacity is defined as $R_{cloud}=<\infty>$. The total resource
usage of a device, $R^{u}_{D_{i}}$, can be consequently calculated as the sum
of the resource consumptions of all its allocated services multiplied by the
request rate of each services:

$R^{u}_{D_{i}}=\sum^{S_{x}}R^{con}_{S_{x}}\times\lambda^{D_{i}}_{S_{x}}\quad\forall\
S_{x}\ |\ S_{x}\ \in\ alloc(D_{i})$ (2)

Table 2 summarizes the list of the variables defined in the system model, that
are used in the following sections of the article.

Table 2: Summary of the variables of the system model. Variable |  Description
---|---
$C_{n}$ |  A client in the system
$S_{x}$ |  A service in the system
$S^{y}_{x}$ |  An instance of a service $S_{x}$
$T^{+}_{S_{x}}$ |  The set of services executed when $S_{x}$ is requested
$cons(S_{x})$ |  Function that returns the list of services that are requested by a given service $S_{x}$
$D_{i}$ |  A fog device in the system
$D_{cloud}$ |  Identification of the cloud provider
$SP_{S_{x}}^{cloud}$ |  The shortest path between $S_{X}$ and the cloud provider
$\mathit{father}(D_{x})$ |  Function that returns, the first element in the shortest path between $S_{x}$ and the cloud provider
$alloc(S_{x})$ |  Function that returns the set of devices where a given service $S_{x}$ is allocated
$alloc(S^{y}_{x})$ |  Function that returns the device where a given service instance $S^{y}_{x}$ is allocated
$alloc(D_{i})$ |  Function that returns the set of services that a given device $D_{i}$ allocates
$R^{cap}_{D_{i}}$ |  Tuple for the resource capacities of a device $D_{i}$
$R^{con}_{S_{x}}$ |  Tuple for the resource consumption required by a service $S_{x}$
$R^{u}_{D_{i}}$ |  Tuple for the total resource usage in a device $D_{i}$
$\lambda^{C_{n}}_{S_{x}}$ |  The request rate generated by a client $C_{n}$ over a service $S_{x}$
$\lambda^{D_{i}}_{S_{x}}$ |  The request rate that arrives to a device $D_{i}$ for the service $S_{x}$
$conn(D_{i})$ |  Function that returns the list of clients connected to a given leaf device $D_{i}$
$hop(D_{i},D_{i^{\prime}})$ |  Hop count, number of devices, between $D_{i}$ and $D_{i^{\prime}}$

###  4.2 Optimization Model

The optimization algorithm is based on the idea of placing the most popular
services closer to the client as it has been done traditionally in other
architecture, as for example, in content delivery networks with the most
popular contents (Borst et al, 2010; Vakali and Pallis, 2003)) or in web
caching (Guerrero et al, 2013). We use the service request rate to measure the
most popular services.

The algorithm analyzes the request rates of each service in each device, and
take local decisions by migrating the less requested services in the device to
upper devices —any device in the shortest path between the current device and
the cloud provider–. This decision is based on the idea explained in Sect. 3
and Figure 2, that considers that once that a service is migrated from the
desired device, it is better to bring it closer to the cloud provider, i.e., a
device in the shortest path.

Additionally, if a service is migrated, all its interoperated services, that
are allocated in the same device, are also migrated. This is based on the idea
of the device loops also explained in Sect. 3 and in Figure 3.

Algorithm 1 shows the pseudo code of our optimization policy. The SAR is only
considered when the candidate service is not already allocated in the device
(Line 1). The service is directly allocated when the device is the cloud
provider (Line 1) or it has enough free resources (Line 1). Additionally, the
service allocation can be done only if the total capacity of the device is
enough to satisfy the requirements of the service (Line 1), on the contrary,
the SAR is shifted to the upper father device (Line 1).

If those previous conditions are met, it is necessary to deallocate other
services from the device. Since our policy migrates all the interoperated
services, instead of a single service, the set of candidates for the
migration, $\mathbb{M}_{D_{i}}$, is formed by all the possible subsets of
interoperated services that are currently allocated in the device. Each subset
of this candidates’ set is obtained from the intersection between the services
allocated in the device and each of their transitive closures:

$\mathbb{M}_{D_{i}}=\left\\{M_{S_{x}}^{D_{i}},\ \forall\ S_{x}\in
alloc(D_{i})\right\\}$ (3)

where

$M_{S_{x}}^{D_{i}}=\left\\{alloc(D_{i})\ \cap\ T^{+}_{S_{x}}\right\\}$ (4)

For example, if we recover the example in Figure 5 and we suppose that a given
device currently allocates services $S_{1}$, $S_{2}$, $S_{5}$, and $S_{6}$,
the migration candidate set is formed by the following service subsets:
$\mathbb{M}_{D_{i}}=\\{\ \\{S_{1},S_{2},S_{5},S_{6}\\},$ $\
\\{S_{2},S_{6}\\},$ $\ \\{S_{5},S_{6}\\},\ \\{S_{6}\\}\ \\}$.

Our proposal migrates the candidates by ascending order of the request rates.
This is done in line 1 of Algorithm 1, where , $M_{min}$, is the services’
subset in $\mathbb{M}_{D_{i}}$ with the smallest request rate, and
$\Lambda^{{M}_{min}}$ this smallest request rate. Thus, the sets in
$\mathbb{M}_{D_{i}}$ are sequentially selected and deallocated from the less
requested one to the most popular, until the freed resources are enough to
allocate the candidate service in the device (Line 1) or until the remaining
candidates have higher request rates (Line 1).

The deallocation is not done straightforward, because the algorithm needs to
guarantee that the sets of services with lower rates release enough resources
to satisfy the requirements of the candidate service. Thus, a list of pre-
released services, $\mathbb{M}_{deallocate}$, is created (Line 1) and they are
finally deallocated only if the freed resources are enough (Lines 1–1).

The request rate of a services’ subset, $\Lambda^{M_{S_{x}}^{D_{i}}}$ , is
calculated just by the summation of the single request rates, for that fog
device, of each service in the $M_{S_{x}}^{D_{i}}$:

$\Lambda^{M_{S_{x}}^{D_{i}}}=\sum^{\forall\ S_{x}\in
M_{S_{x}}^{D_{i}}}\lambda^{D_{i}}_{S_{x}}$ (5)

The allocation process starts with each new client connection to a leaf
device. The Service Popularity Monitor (SPM) creates a SAR each time that a
new client is detected. This detection is performed by analyzing the services
requests that are received from the client.

We consider that the hop count is a good indicator to measure the service
proximity. The hop count is the number of devices that a request of a client
pass through to achieve the device where the requested service is placed. Our
algorithm’s optimization objective is to reduce the hop count, but favoring
the more popular services. We consider the weighted average hop count as an
indicator to measure the proximity of the most popular services. We define it
as the average of the distance between each service and the clients weighted
with their popularity, in terms of request rate:

$Weighted\ Average\ Hop\
Count=\sum^{D_{i},S^{y}_{x}}\frac{\lambda^{D_{i}}_{S_{x}}}{\sum^{D_{i^{\prime}},S^{y}_{x^{\prime}}}\lambda^{D_{i^{\prime}}}_{S_{x^{\prime}}}}\times
hop(C_{n},D_{i})\ $ (6)

where $hop(C_{n},D_{i})$ is the number of fog devices between the clients and
the device that allocates a given instance of a service. A value of 1.0 for
the hop count means that all the services are placed in the gateways or leaf
devices. The maximum value for the hop count is the number of levels in the
network.

The hypothesis of our second research question is that performance metrics,
such as network usage or service latency, are improved when the average hop
count is reduced.

Input: $S^{y}_{x}$, $D_{i}$

1

2if  _$D_{i}\notin alloc(S_{x})$_ then

/* service not allocated in device */

3

4 if  _$D_{i}$ $=$ $D_{cloud}$_ then

/* device is cloud provider */

5 $alloc(S^{y}_{x})\leftarrow D_{cloud}$

6

7 else

8

9 if  _$R^{con}_{S_{x}}\times\lambda^{D_{i}}_{S_{x}}$ $<$
$R^{cap}_{D_{i}}-R^{u}_{D_{i}}$_ then

/* service demanded resources < device available resources */

$alloc(S^{y}_{x})\leftarrow D_{i}$

/* device allocates the service */

10

11

12 else

13 $D_{father}\leftarrow father(D_{i})$

if  _$R^{con}_{S_{x}}\times\lambda^{D_{i}}_{S_{x}}$ $<$ $R^{cap}_{D_{i}}$_
then

/* service resources $<$ device resources */

14

Placement($S^{y}_{x}$, $D_{father}$)

/* candidate service migrated to father device */

15

16 else

17

$R^{toFree}\leftarrow R^{con}_{S_{x}}\times\lambda^{D_{i}}_{S_{x}}$ \-
$(R^{cap}_{D_{i}}-R^{u}_{D_{i}})$

/* service demanded resources - device available resources */

18 $\mathbb{M}_{deallocate}\leftarrow\emptyset$

19 $\mathbb{S}_{allocated}\leftarrow alloc(D_{i})$

20 $\lambda^{D_{i}}\leftarrow
calculateM_{D_{i}}RequestRates(\mathbb{M}_{D_{i}})$

21 $\mathbb{M}_{ordered}\leftarrow
orderAscBy(\mathbb{M}_{D_{i}},\lambda^{D_{i}})$

/* calculate request rate of each subset and order them */

22

23 while  _$M_{min},\Lambda_{min}\leftarrow\mathbb{M}_{ordered}.next(),$_ do

24

if  _$\lambda^{D_{i}}_{S_{x}}$ $>$ $\Lambda_{min}$_ then

/* candidate service has higher request rate */

25

26

$\mathbb{M}_{deallocate}\leftarrow\mathbb{M}_{deallocate}\cup\mathbb{M}_{min}$

/* add service set to released list */

$\mathbb{S}_{allocated}\leftarrow\mathbb{S}_{allocated}-\mathbb{M}_{min}$

/* remove released services */

27

for  _$S^{y}_{x^{\prime}},\forall\ S^{y}_{x^{\prime}}\in\mathbb{M}_{min}$_ do

/* released services from device */

28

29

30 $R^{toFree}\leftarrow R^{toFree}$ \-
$R^{con}_{S_{x^{\prime}}}\times\lambda^{D_{i}}_{S_{x^{\prime}}}$

31

32 else

33

34 break

35

36 if  _$R^{toFree}$ $<=$ 0.0_ then

/* enough resources once lower request rate services released */

37 for  _$S^{y}_{x^{\prime}},\forall\
S^{y}_{x^{\prime}}\in\mathbb{S}_{deallocate}$_ do

Placement($S^{y}_{x^{\prime}}$, $D_{father}$)

/* released services migrate to father device */

38

39 else

40

Placement($S^{y}_{x}$, $D_{father}$)

/* candidate service migrated to father device */

41

Algorithm 1 Algorithm for module placement in devices

##  5 Evaluation

The evaluation of our proposal was done by simulating a microservice-based
application in the iFogSim simulator (Gupta et al, 2017). The simulator’s
service placement policy was modified by extending the class ModulePlacement.
The results of our algorithm were compared with the ones obtained with the
simulator’s built-in placement policy (Edgewards), since it was, to the best
of our knowledge, the only previous decentralized service placement policy.

Several scenario settings were considered by modifying the number of clients,
the number of applications and the number of fog devices. Table 3 includes a
summary of the simulation settings.

The experiments were characterized with the same configuration parameters than
in the study of the simulator’s developers (Gupta et al, 2017). Those
experiments considered a tree-based network topology where the number of
devices was varied in two dimensions, by ranging the number of levels in the
tree, and by ranging the number of children of each fog device. Although our
model allows to model the fog architecture as a graph network, the iFogSim
only allows to define the architecture like a tree555The devices of the
iFogSim are related with a list of children identificators and just one
father, as it can be seen in lines 59 and 68 of class
https://github.com/Cloudslab/iFogSim/blob/master/src/org/fog/entities/FogDevice.java.

The resource capacities for the cloud were defined high enough to behave as a
device with unlimited resources. The memory and the bandwidth of the fog
devices were also high enough to be able to allocated as many services as
necessary, keeping the computational capacity the only resource limitation in
the service placement, since we only considered CPU resources (Sect. 4.2).

A microservice-based application were modeled in the simulator as this type of
development pattern is also common in IoT applications (Vogler et al, 2016;
Krylovskiy et al, 2015; Saurez et al, 2016). We modeled the Socks Shop
(Weaveworks and ContainerSolutions, 2016) applications, a microservice-based
demo that was developed to test the benefits of deploying applications in a
container platform. Its characterization and modeling parameters were obtained
from previous research works (Guerrero et al, 2017). Figure 6 shows the
application graph. The number of applications was varied by replicating the
same application several times, but considering different request rate for
each replica.

Table 3: Summary of experimental settings. Element | Parameter | Units | Value
---|---|---|---
Cloud | CPU | MIPS | 4480000
| RAM | MB | 4000000
| BandWith (Up/Down) | bytes/ms | 20000+20000
| Link latency | ms | 100
Fog devices | CPU | MIPS | 2800
| RAM | MB | 4000
| BandWith (Up/Down) | bytes/ms | 20000+20000
| Link latency | ms | 2
Applications | # applications | – | [1, 2, 3, 4, 5]
Services | RAM | MB | 1
Service edges | CPU | Instr. $\times\ 10^{6}$ | 1000
| BandWith | bytes | 10
| Selectivity | Fractional | 1
Users | Request rate | req/ms | [$\frac{1}{10}$, $\frac{1}{20}$, $\frac{1}{25}$, $\frac{1}{30}$, $\frac{1}{35}$]
| # user per gateway | – | [1, 2, 3, 4, 5]
Network topology | # levels | – | [1, 2, 3, 4, 5]
| # child devices | – | [1, 2, 3, 4, 5]
Figure 6: Services, interoperability and application edges settings for Sock
shop demo application.

##  6 Results

Our results are presented in terms of average hop count, Equation 6, network
usage, and service latency. The equations for the calculation of the two
latter metrics, Equations 7 and 8, were obtained from the analysis of the
source code of the iFogSim simulator666 Obtained from the analysis of the
source code available in https://github.com/harshitgupta1337/fogsim.

$Network\
Usage=\frac{\sum^{Req_{u}(D_{i},D_{i^{\prime}})}(T^{lat}_{D_{i},D_{i^{\prime}}}\times
NetSize_{Req_{u}(D_{i},D_{i^{\prime}})})}{Simulation\ Time}$ (7)

where $T^{lat}_{D_{i},D_{i^{\prime}}}$ is the network latency between the
devices that are the origin and the target of the request, and
$NetSize_{Req_{u}(D_{i},D_{i^{\prime}})}$ is the total size of the request
sent by the network. The network usage is calculated as the sum of the network
usages generated by each request $Req_{u}(D_{i},D_{i^{\prime}})$ sent during
the total simulation time.

The service latency is measured in the simulator as the average time to
execute a path of interoperated services, called application edge loop. This
service latency is calculated as the time between the point in time the
request for the first service in the path arrives, $t_{S_{first}}$, and the
point in time the last service in the path ends its execution, $t_{S_{end}}$:

$Service\
Latency=\frac{\sum^{Req_{u}}(t_{S_{end}}-t_{S_{first}})}{|Req_{u}|}\quad\forall\
Req_{u}\in Loop(S_{first},S_{end})$ (8)

In the following figures, the results obtained with our algorithm are labeled
as Pop and the ones for the Edgewards policy of the iFogSim are labeled as
Edge.

The first set of figures (Figures 7, 8, 9, and 10) includes four subfigures
one for each of the size variations in the execution settings: (a) variations
in the number of users connected to each gateway to evaluate different levels
of workload; (b) variations in the number of applications available in the
system to evaluate different number of services to place, i.e., different
number of fog devices allocating services; (c) variations in the number of
levels of fog devices between the users and the cloud provider to evaluate the
influence of the path length; and finally, (d) variations in the number of
children devices that each fog device is connected to with the objective of
evaluating the influence of the number of devices.

Figure 7: Results for hop count.

Figure 7 shows the results for the hop count. It plots the weighted average
—calculated with Equation 6 and labeled as weighted— and the arithmetic mean
—labeled as arithmetic—. The arithmetic mean represents the overall proximity
between the users and all the services. On the contrary, the weighted mean
represents how closer the most requested services are to the clients.

Figure 8: Results for network usage.

Figure 9: Results for service latency for the service loop edge, frontend,
orders, accounts of the applications with the highest and the lowest request
rates.

Figure 8 shows the results calculated by the simulator with respect to the
network usages. Figure 9 shows the latency results for a representative
service loop of the application. We chose the loop of edge, frontend, orders,
and accounts services as it includes the service with the higher rate, the
accounts with 3.0 requests for each request that arrives to the edge. The
value that the simulator calculates for the loop represents the time between
the edge server is requested and the accounts one finishes. To illustrate the
benefits of our algorithm for the services with the highest request, the plots
represent the service latency for the loops of the applications with the
lowest, labeled as lowest, and highest request rate, labeled as highest.

Figure 10: Results for the number of migrations.

Figure 10 represents the total number of migrations performed during the
service placement process. It is important to remember that the applications
are defined as stateless services and consequently a migration consist on
removing the current service instance and downloading a new instance from the
cloud to the new device.

The last set of figures (Figures 11, 12, and 13) represent the relationship of
the distance between the IoT devices and the service placement distribution,
measured in terms of the hop count, in regard with the popularity of the
services (request rate), the number of services in a device and the CPU usage.
Those distributions are represented in one independent plot for each
experiment size. Consequently, they are grouped in sets of five plots, one for
each single size of a variation set. Thus, there are four sets of five plots
of figures for each of the three cases (request rate, number of services, and
CPU usage). We present only some representative cases of those plots,
particularly, we include the cases for the children variations.

Figure 11: CPU usage of the devices with regard to their topology
distribution. Experiment with 2 applications, 2 users, and 2 levels of fog
devices.

Figure 11 shows the CPU usage of the devices by classifying the devices by
their distance from the IoT devices (sensors). The distance is measured in
terms of hop count (x-axis) and the CPU usage is the rate between consumed and
total resources (y-axis). Each point of the plot represents a device with its
corresponding usage value. The number of each point indicates the total number
of samples (devices) with the same hop count and CPU usage. The figure
includes the results for the experiment with a size of 2 applications, 2 users
per IoT gateway, 2 fog devices levels and a range of 1 to 5 children devices
per device.

Figure 12: Number of services in the devices with regard to their topology
distribution. Experiment with 2 applications, 2 users, and 2 levels of fog
devices.

Figure 12 is very similar to the previous one, with the only difference that
it represents the number of services allocated in the devices instead of the
CPU usage.

Figure 13: Distribution of the services across the device topology with regard
to their request rate. Experiment with 2 applications, 2 users, and 2 levels
of fog devices.

Finally, Figure 13 represents how the services are distributed across the
devices in the topology (classified by the hop count with the user) with
regard to their request rate (y-axis). The request rate is measured in terms
of frequency (the inverse of the time unit). Consequently, each point of the
plot represent a service with its allocation in the topology (the hop count of
the device where it is allocated) and its request rate.

##  7 Discussion

We use the weighted average hop count as an indicator of the proximity between
the clients and the most popular services. On the contrary, the arithmetic
average hop count is an indicator of the proximity between all the services
and the clients, independently of their request ratios. Therefore, the first
research question (RQ1) is answered by the analysis of the series labeled as
weighted in Figure 7. This metric is, in general terms, smaller for the case
of our policy than for the Edgewards, obtaining an overall improvement of the
12%. There are only two cases in which the Edgewards policy shows smaller
values (2 users, 3 levels and 2 applications). On the contrary, Edgewards
policy shows smaller values for the arithmetic average hop count. It means
that our policy obtains better proximity for the most requested services, at
the expense of increasing the overall distance of the services. We finally
observe that cases with only 1 user can be managed by placing all the services
in the leaf devices (gateways), since the hop count value is 1.0.

The second research question (RQ2) is answered by the analysis of results in
Figures 8 and 9. Firstly, our policy’s network usage is always smaller than
the Edgewards. The improvement in this metric is measured with an speedup
between 23% and 362%, with an mean value of 114%. Secondly, the analysis of
the service latency is separately done for the case of the applications with
the highest and the lowest request rates. In general terms, our policy shows
an improvement of the service latency for the application with the highest
rate, at the expense of degradation for the application with the lowest
request rate in some experiments.

The benefit of our policy for the application with the highest request rate is
observed in Figure 9 where the series Pop (highest) are the ones with the
smallest values. Our policy’s improvement is measured in a speedup around 300%
and 500%, obtaining even an speedup of 1300% for the second last case of the
number of users variations.

The degradation of our policy for the less requested application is observed,
mainly, for the experiments where the number of applications is increased,
i.e. the cases with higher workload in the system. On the contrary, our policy
is better even for the low requested services when the workload of the system
is low. This is expected since the more application replicas, the more devices
allocating services, and consequently, the less requested applications are
much further from the clients, and their latencies are increased. Edgeward
policy shows improvements ranging from 60% to 250% for this second type of
applications in the high workload experiments.

From the analysis of the number of migrations required for the deployment of
the services (Figure 10), it is observed that our solution clearly needs a
higher number of migrations (or service deployments from the cloud provider).
This generates a higher network usage due to the download of the services from
the cloud provider. It is important to highlight that this process is just
performed during the deployment of the application. This migration cost is
made up with the benefits of our service distribution, except for the cases
with high rates of application deployments.

It is important to highlight that the number of devices does not influence in
the latency neither the hop count in the experiments for the variation in the
number of levels or children. This is explained because all the service
placements are done in devices in the lowest levels, and devices from upper
levels are not necessary and, consequently, the service latency is constant as
the number of devices is increased. This is also validated with the results
of, for example, Figure 12, where the number of allocated services is 0 for
the devices with a hop count higher than 2. On the contrary, the network usage
is influenced because the number of connections between the devices is varied,
and this metric is influenced by the number of those connections.

Figure 12 also shows us that our policy migrates more services to upper
devices, than the Edgewards algorithm. This is because we do not migrate only
one service but also all the consumed services ($M_{S_{x}}^{D_{i}}$) to avoid
device loops in the service execution flow. By this, the less requested
services are placed in the devices with a hop distances of 2, and the most
requested one in the devices with hop distance of 1. Consequently, we can also
observed how the devices in the lower levels of the topology have smaller
usages than in the case of the Edgewards (Figure 11). This offers a side
effect of a lower saturation of the devices and an evenly distribution of
services.

Finally, Figure 13 reflects how the services that are placed in lower devices
(devices with a hop count of 1) have higher rates in the case of our policy
with regard to the Edgewards. Likewise, the devices with a hop count of 2
allocate services with lower request rates.

To sum up, we can conclude that our policy reduces the distance between the
clients and the most requested services (RQ1), and the latency of those
services and the overall network usage are improved (RQ2). On the contrary,
the latency of the less requested application is degraded in experiments with
the highest workloads. This is obtained by increasing the number of service
migrations.

##  8 Conclusions

We have presented a decentralized algorithm for the Fog Service Placement
Problem to optimize the distance between the clients and the most requested
services. The algorithm is locally executed in each fog device, by considering
only performance and usage data obtained in the device itself. The decision of
the service placement is addressed to migrate services with smaller request
rates to upper devices, as new placements are necessary. The interoperability
between the services is considered and the migration of a service also
involves the migration of all its consumed services.

We have evaluated our placement policy with the iFogSim simulator by modeling
a microservice-based application with several experiment sizes. Our results
have been compared with the simulator’s built-in policy, Edgewards. The
results showed that our policy reduces the distance between the clients and
the most requested services, measured in terms of the weighted average hop
count. Consequently, the network usage and the service latency of those
services are improved. These improvements are obtained at the expense of an
increment of the latency in the less requested services.

Our proposal shows that decentralized placement optimization in fog computing
is able to improve the overall performance of the system. This opens new
challenges to apply other optimization techniques to decentralized managers to
avoid, between others, scaling problems of the centralized ones.

## References

  * Arkian et al (2017) Arkian HR, Diyanat A, Pourkhalili A (2017) Mist: Fog-based data analytics scheme with cost-efficient resource provisioning for iot crowdsensing applications. Journal of Network and Computer Applications 82(Supplement C):152 – 165, DOI https://doi.org/10.1016/j.jnca.2017.01.012, URL http://www.sciencedirect.com/science/article/pii/S1084804517300188
  * Atzori et al (2010) Atzori L, Iera A, Morabito G (2010) The internet of things: A survey. Computer Networks 54(15):2787 – 2805
  * Balalaie et al (2016) Balalaie A, Heydarnoori A, Jamshidi P (2016) Microservices architecture enables devops: Migration to a cloud-native architecture. IEEE Software 33(3):42–52, DOI 10.1109/MS.2016.64
  * Barcelo et al (2016) Barcelo M, Correa A, Llorca J, Tulino AM, Vicario JL, Morell A (2016) Iot-cloud service optimization in next generation smart environments. IEEE Journal on Selected Areas in Communications 34(12):4077–4090, DOI 10.1109/JSAC.2016.2621398
  * Billet and Issarny (2014) Billet B, Issarny V (2014) From task graphs to concrete actions: A new task mapping algorithm for the future internet of things. In: 2014 IEEE 11th International Conference on Mobile Ad Hoc and Sensor Systems, pp 470–478, DOI 10.1109/MASS.2014.20
  * Bittencourt et al (2017) Bittencourt LF, Diaz-Montes J, Buyya R, Rana OF, Parashar M (2017) Mobility-aware application scheduling in fog computing. IEEE Cloud Computing 4(2):26–35, DOI 10.1109/MCC.2017.27
  * Borst et al (2010) Borst S, Gupta V, Walid A (2010) Distributed caching algorithms for content distribution networks. In: 2010 Proceedings IEEE INFOCOM, pp 1–9, DOI 10.1109/INFCOM.2010.5461964
  * Botta et al (2016) Botta A, de Donato W, Persico V, Pescape A (2016) Integration of cloud computing and internet of things: A survey. Future Generation Computer Systems 56(Supplement C):684 – 700
  * Brogi and Forti (2017) Brogi A, Forti S (2017) Qos-aware deployment of iot applications through the fog. IEEE Internet of Things Journal 4(5):1185–1192, DOI 10.1109/JIOT.2017.2701408
  * Brogi et al (2017) Brogi A, Forti S, Ibrahim A (2017) How to best deploy your fog applications, probably. In: 2017 IEEE 1st International Conference on Fog and Edge Computing (ICFEC), pp 105–114, DOI 10.1109/ICFEC.2017.8
  * Cavalcante et al (2016) Cavalcante E, Pereira J, Alves MP, Maia P, Moura R, Batista T, Delicato FC, Pires PF (2016) On the interplay of internet of things and cloud computing: A systematic mapping study. Computer Communications 89-90(Supplement C):17–33, DOI https://doi.org/10.1016/j.comcom.2016.03.012, URL http://www.sciencedirect.com/science/article/pii/S0140366416300706, internet of Things: Research challenges and Solutions
  * Chiang and Zhang (2016) Chiang M, Zhang T (2016) Fog and iot: An overview of research opportunities. IEEE Internet of Things Journal 3(6):854–864, DOI 10.1109/JIOT.2016.2584538
  * Colistra et al (2014) Colistra G, Pilloni V, Atzori L (2014) The problem of task allocation in the internet of things and the consensus-based approach. Computer Networks 73(Supplement C):98 – 111, DOI https://doi.org/10.1016/j.comnet.2014.07.011, URL http://www.sciencedirect.com/science/article/pii/S1389128614002655
  * Darwish and Hassanien (2017) Darwish A, Hassanien AE (2017) Cyber physical systems design, methodology, and integration: the current status and future outlook. Journal of Ambient Intelligence and Humanized Computing DOI 10.1007/s12652-017-0575-4, URL https://doi.org/10.1007/s12652-017-0575-4
  * Darwish et al (2017) Darwish A, Hassanien AE, Elhoseny M, Sangaiah AK, Muhammad K (2017) The impact of the hybrid platform of internet of things and cloud computing on healthcare systems: opportunities, challenges, and open problems. Journal of Ambient Intelligence and Humanized Computing DOI 10.1007/s12652-017-0659-1, URL https://doi.org/10.1007/s12652-017-0659-1
  * Dastjerdi and Buyya (2016) Dastjerdi AV, Buyya R (2016) Fog computing: Helping the internet of things realize its potential. Computer 49(8):112–116, DOI 10.1109/MC.2016.245
  * Deng et al (2015) Deng R, Lu R, Lai C, Luan TH (2015) Towards power consumption-delay tradeoff by workload allocation in cloud-fog computing. In: 2015 IEEE International Conference on Communications (ICC), pp 3909–3914, DOI 10.1109/ICC.2015.7248934
  * Diaz et al (2016) Diaz M, Martin C, Rubio B (2016) State-of-the-art, challenges, and open issues in the integration of internet of things and cloud computing. Journal of Network and Computer Applications 67(Supplement C):99 – 117, DOI https://doi.org/10.1016/j.jnca.2016.01.010, URL http://www.sciencedirect.com/science/article/pii/S108480451600028X
  * Do et al (2015) Do CT, Tran NH, Pham C, Alam MGR, Son JH, Hong CS (2015) A proximal algorithm for joint resource allocation and minimizing carbon footprint in geo-distributed fog computing. In: 2015 International Conference on Information Networking (ICOIN), pp 324–329, DOI 10.1109/ICOIN.2015.7057905
  * Farris et al (2015) Farris I, Militano L, Nitti M, Atzori L, Iera A (2015) Federated edge-assisted mobile clouds for service provisioning in heterogeneous iot environments. In: 2015 IEEE 2nd World Forum on Internet of Things (WF-IoT), pp 591–596, DOI 10.1109/WF-IoT.2015.7389120
  * Gu et al (2017) Gu L, Zeng D, Guo S, Barnawi A, Xiang Y (2017) Cost efficient resource management in fog computing supported medical cyber-physical system. IEEE Transactions on Emerging Topics in Computing 5(1):108–119, DOI 10.1109/TETC.2015.2508382
  * Guerrero et al (2013) Guerrero C, Lera I, Juiz C (2013) Performance improvement of web caching in web 2.0 via knowledge discovery. Journal of Systems and Software 86(12):2970 – 2980, DOI https://doi.org/10.1016/j.jss.2013.04.060, URL http://www.sciencedirect.com/science/article/pii/S0164121213001209
  * Guerrero et al (2017) Guerrero C, Lera I, Juiz C (2017) Genetic algorithm for multi-objective optimization of container allocation in cloud architecture. Journal of Grid Computing DOI 10.1007/s10723-017-9419-x, URL https://doi.org/10.1007/s10723-017-9419-x
  * Gupta et al (2017) Gupta H, Vahid Dastjerdi A, Ghosh SK, Buyya R (2017) 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 47(9):1275–1296, DOI 10.1002/spe.2509, URL http://dx.doi.org/10.1002/spe.2509, spe.2509
  * Huang et al (2014a) Huang Z, Lin KJ, Yu SY, jen Hsu JY (2014a) Co-locating services in iot systems to minimize the communication energy cost. Journal of Innovation in Digital Ecosystems 1(1):47 – 57, DOI https://doi.org/10.1016/j.jides.2015.02.005, URL http://www.sciencedirect.com/science/article/pii/S2352664515000061
  * Huang et al (2014b) Huang Z, Lin KJ, Yu SY, Hsu JYj (2014b) Building energy efficient internet of things by co-locating services to minimize communication. In: Proceedings of the 6th International Conference on Management of Emergent Digital EcoSystems, ACM, New York, NY, USA, MEDES ’14, pp 18:101–18:108, DOI 10.1145/2668260.2668270, URL http://doi.acm.org/10.1145/2668260.2668270
  * Ko et al (2016) Ko IY, Ko HG, Molina AJ, Kwon JH (2016) Soiot: Toward a user-centric iot-based service framework. ACM Trans Internet Technol 16(2):8:1–8:21, DOI 10.1145/2835492, URL http://doi.acm.org/10.1145/2835492
  * Krylovskiy et al (2015) Krylovskiy A, Jahn M, Patti E (2015) Designing a smart city internet of things platform with microservice architecture. In: 2015 3rd International Conference on Future Internet of Things and Cloud, pp 25–30, DOI 10.1109/FiCloud.2015.55
  * Li et al (2015) Li S, Xu LD, Zhao S (2015) The internet of things: A survey. Information Systems Frontiers 17(2):243–259
  * Mahmud et al (2018) Mahmud R, Kotagiri R, Buyya R (2018) Fog Computing: A Taxonomy, Survey and Future Directions, Springer Singapore, Singapore, pp 103–130
  * Munro (1971) Munro I (1971) Efficient determination of the transitive closure of a directed graph. Information Processing Letters 1(2):56 – 58, DOI https://doi.org/10.1016/0020-0190(71)90006-8, URL http://www.sciencedirect.com/science/article/pii/0020019071900068
  * Ni et al (2017) Ni L, Zhang J, Jiang C, Yan C, Yu K (2017) Resource allocation strategy in fog computing based on priced timed petri nets. IEEE Internet of Things Journal 4(5):1216–1228, DOI 10.1109/JIOT.2017.2709814
  * Saurez et al (2016) Saurez E, Hong K, Lillethun D, Ramachandran U, Ottenwälder B (2016) Incremental deployment and migration of geo-distributed situation awareness applications in the fog. In: Proceedings of the 10th ACM International Conference on Distributed and Event-based Systems, ACM, New York, NY, USA, DEBS ’16, pp 258–269, DOI 10.1145/2933267.2933317, URL http://doi.acm.org/10.1145/2933267.2933317
  * Skarlat et al (2017a) Skarlat O, Nardelli M, Schulte S, Borkowski M, Leitner P (2017a) Optimized iot service placement in the fog. Service Oriented Computing and Applications DOI 10.1007/s11761-017-0219-8, URL https://doi.org/10.1007/s11761-017-0219-8
  * Skarlat et al (2017b) Skarlat O, Nardelli M, Schulte S, Dustdar S (2017b) Towards qos-aware fog service placement. In: 2017 IEEE 1st International Conference on Fog and Edge Computing (ICFEC), pp 89–96, DOI 10.1109/ICFEC.2017.12
  * Souza et al (2016) Souza VBC, Ramírez W, Masip-Bruin X, Marín-Tordera E, Ren G, Tashakor G (2016) Handling service allocation in combined fog-cloud scenarios. In: 2016 IEEE International Conference on Communications (ICC), pp 1–5, DOI 10.1109/ICC.2016.7511465
  * Taneja and Davy (2017) Taneja M, Davy A (2017) Resource aware placement of iot application modules in fog-cloud computing paradigm. In: 2017 IFIP/IEEE Symposium on Integrated Network and Service Management (IM), pp 1222–1228, DOI 10.23919/INM.2017.7987464
  * Urgaonkar et al (2015a) Urgaonkar R, Wang S, He T, Zafer M, Chan K, Leung KK (2015a) Dynamic service migration and workload scheduling in edge-clouds. Performance Evaluation 91(Supplement C):205 – 228, DOI https://doi.org/10.1016/j.peva.2015.06.013, URL http://www.sciencedirect.com/science/article/pii/S0166531615000619, special Issue: Performance 2015
  * Urgaonkar et al (2015b) Urgaonkar R, Wang S, He T, Zafer M, Chan K, Leung KK (2015b) Dynamic service migration and workload scheduling in edge-clouds. Perform Eval 91(C):205–228, DOI 10.1016/j.peva.2015.06.013, URL https://doi.org/10.1016/j.peva.2015.06.013
  * Vakali and Pallis (2003) Vakali A, Pallis G (2003) Content delivery networks: status and trends. IEEE Internet Computing 7(6):68–74, DOI 10.1109/MIC.2003.1250586
  * Varghese and Buyya (2017) Varghese B, Buyya R (2017) Next generation cloud computing: New trends and research directions. Future Generation Computer Systems DOI https://doi.org/10.1016/j.future.2017.09.020, URL http://www.sciencedirect.com/science/article/pii/S0167739X17302224
  * Velasquez et al (2017) Velasquez K, Abreu DP, Curado M, Monteiro E (2017) Service placement for latency reduction in the internet of things. Annals of Telecommunications 72(1):105–115, DOI 10.1007/s12243-016-0524-9, URL https://doi.org/10.1007/s12243-016-0524-9
  * Venticinque and Amato (2018) Venticinque S, Amato A (2018) A methodology for deployment of iot application in fog. Journal of Ambient Intelligence and Humanized Computing DOI 10.1007/s12652-018-0785-4, URL https://doi.org/10.1007/s12652-018-0785-4
  * Vogler et al (2016) Vogler M, Schleicher JM, Inzinger C, Dustdar S (2016) A scalable framework for provisioning large-scale iot deployments. ACM Trans Internet Technol 16(2):11:1–11:20, DOI 10.1145/2850416, URL http://doi.acm.org/10.1145/2850416
  * Wang et al (2015) Wang S, Urgaonkar R, Chan K, He T, Zafer M, Leung KK (2015) Dynamic service placement for mobile micro-clouds with predicted future costs. In: 2015 IEEE International Conference on Communications (ICC), pp 5504–5510, DOI 10.1109/ICC.2015.7249199
  * Wang et al (2017) Wang S, Zafer M, Leung KK (2017) Online placement of multi-component applications in edge computing environments. IEEE Access 5:2514–2533, DOI 10.1109/ACCESS.2017.2665971
  * Weaveworks and ContainerSolutions (2016) Weaveworks, ContainerSolutions (2016) Socks shop - a microservices demo application. URL https://microservices-demo.github.io/
  * Wen et al (2017) Wen Z, Yang R, Garraghan P, Lin T, Xu J, Rovatsos M (2017) Fog orchestration for internet of things services. IEEE Internet Computing 21(2):16–24, DOI 10.1109/MIC.2017.36
  * Yang et al (2016) Yang L, Cao J, Liang G, Han X (2016) Cost aware service placement and load dispatching in mobile cloud systems. IEEE Transactions on Computers 65(5):1440–1452, DOI 10.1109/TC.2015.2435781
  * Zeng et al (2016) Zeng D, Gu L, Guo S, Cheng Z, Yu S (2016) Joint optimization of task scheduling and image placement in fog computing supported software-defined embedded system. IEEE Transactions on Computers 65(12):3702–3712, DOI 10.1109/TC.2016.2536019