Meet Genetic Algorithms in Monte Carlo:

Meet Genetic Algorithms in Monte Carlo:

Optimised Placement of Multi-Service Applications in the Fog

Antonio Brogi, Stefano Forti Department of Computer Science,

University of Pisa, Italy

Carlos Guerrero, Isaac Lera Department of Computer Science, University of Balearic Islands, Spain IEEE INTERNATIONAL CONFERENCE ON EDGE COMPUTING

JULY 8-13, 2019, MILAN, ITALY

Embedded AI Autonomous

driving Drones for

deliveries Energy

production Smart Cities

2

CONTINUOUS IOT GROWTH

3

microservices

multi -co mpon ent

osmotic

LARGE HIGHLY DISTRIBUTED SOFTWARE SYSTEMS

4

mist cloud

micro-cloud fog

IoT

edge

PERVASIVELY DISTRIBUTED INFRASTRUCTURES

5

STRINGENT QoS REQUIREMENTS

How to deploy (and re-deploy)

LARGE HIGHLY DISTRIBUTED SOFTWARE SYSTEMS

to

PERVASIVELY DISTRIBUTED INFRASTRUCTURES

so to guarantee their

STRINGENT QoS REQUIREMENTS

?

7

It’s NP-hard!

Research Question

8

Which is the best deployment (i.e. placement)?

* A. Brogi, S. Forti, C. Guerrero, I. Lera. "How to Place Your Apps in the Fog-State of the Art and Open Challenges." arXiv:1901.05717 (2019).

Much work has been done in this field* but mostly focussing on single application deployment.

We target simultaneous deployment of multiple microservice-based applications.

Previously…

Monte Carlo

QoS-, cost- and context-aware application deployments, considering

network QoS variations

Genetic Algorithms

(Meta-)heuristic approach for ranking eligible deployments as solutions to multi-objective optimisation problems.

Brogi et al., How to best deploy your Fog applications, probably.

ICFEC17, Madrid, 2017

Guerrero et al., Genetic algorithm for multi-objective optimization of container allocation in cloud architecture.

Journal of Grid Computing, 2018.

FogTorchΠ (Monte Carlo)

☺ Can assess eligible deployments against varying infrastructures

 Shows exp-time complexity (𝑶 𝑵𝒐𝒅𝒆𝒔 ^{|𝑺𝒆𝒓𝒗𝒊𝒄𝒆𝒔|}

Predictive Analysis to Support Fog Application Deployment Fog and Edge Computing: Principles and Paradigms, Wiley, 2019.

Genetic Algorithms

Deployments as chromosomes (i.e. services → nodes) 0) Initial random population

1) Fitness function & Selection

2) Cross-over 3) Mutation

𝟎. 𝟖 𝟎. 𝟐 𝟎. 𝟗

☺ Very fast convergence in practice

 Does not consider infrastructure variations

☺ Assess eligible deployments against varying infrastructures

☺ Very fast convergence in practice

+ = ?

Can we have our cake and eat it too?

Objective

Fitness Function

Given a bag of deployments 𝐷 (one per application), over a state of a Fog infrastructure 𝐼’:

● maximise QoS-assurance

● minimise Fog resource consumption

● minimise monthly deployment costs

MC+GA

1. Find two (Pareto-optimal) solution deployments sets – 𝐷 ^{𝑏𝑒𝑠𝑡} and 𝐷 ^{𝑤𝑜𝑟𝑠𝑡} – by using GA in the best and worst infrastructure conditions, and

2. Assess 𝐷 ^{𝑏𝑒𝑠𝑡} and 𝐷 ^{𝑤𝑜𝑟𝑠𝑡} by using Monte Carlo simulations to make infrastructure conditions vary in all possible ways.

We implemented and open-sourced this combo in FogTorchΠ!

https://github.com/di-unipi-socc/FogTorchPI/tree/genetic-algs

Experimental evaluation

Example application (4 services)

Experimental evaluation (1)

On two infrastructures:

- SMALL SCALE (5 nodes + 2 apps)

Results (Small-Scale)

26,623 sol.s

24 sol.s

Experimental evaluation (2)

On two infrastructures:

- SMALL SCALE (5 nodes, 2 apps)

- LARGE SCALE (200 nodes, 10 apps)

A. Medina, A. Lakhina, I. Matta, and J. Byers, “BRITE: an approach to universal topology generation,” in MASCOTS 2001, , pp. 346–353. > Barabasi- Albert Model

x10

Results (Large-Scale)

Analysis

PERFORMANCE Small-Scale Large-Scale

Exhaustive Search 67s -

Genetic Algorithm 1.5s 40s

Number of SOLUTIONS Small-Scale Large-Scale

Exhaustive Search 26623 -

Genetic Algorithm 24 37

☺ Assess eligible deployments against varying infrastructures

☺ Very fast convergence in practice

+ = ?

Can we have our cake and eat it too?

Objective

Concluding Remarks

Our MC+GA approach showed substantial performance improvements with respect to exhaustive search.

Indeed, it finds the best candidate deployment solutions in a significantly lower execution time (40x on a small-scale experiment), and shows better scalability over large problem instances.

Future Work

- Include more sophisticated GAs and compare their performance

- Assess predictions against actual application deployments.

Thank you for your attention. Questions?

Acknowledgments :

● This work was partly supported by the project “DECLWARE” (PRA201866) funded by the University of Pisa.

● 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).

References :

● A. Brogi and S. Forti, “QoS-aware deployment of IoT applications through the fog,” IEEE Internet of Things Journal. vol. 4, no. 5, pp.

1185–1192, 2017.

● C. Guerrero, I. Lera, I. and C. Juiz. “Genetic algorithm for multi-objective optimization of container allocation in cloud architecture”. Journal of Grid Computing, 16(1): 113--135, Springer, 2018.

Antonio Brogi, Stefano Forti Department of Computer Science, University of Pisa, Italy

Carlos Guerrero, Isaac Lera Department of Computer Science, University of Balearic Islands, Spain