Dec 8, 2017 - Virtual Machine Allocation in Fog Computing : â» Multiple resources are needed : RAM, CPU, Bandwidth, etc
Stochastic Models for Resource Allocation in Large Distributed Systems Guilherme THOMPSON Advisor: Philippe ROBERT
Paris,
INRIA Paris of December 2017
08th
G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
1/40
Agenda
1. Introduction 2. Resource Allocation with Downgrading 3. Multi-resource Cooperation in the framework of Cloud Computing 4. Conclusion
G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
2/40
Introduction Stochastic Modelling of Large Distributed Systems
G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
3/40
Introduction Stochastic Modelling of Large Distributed Systems Cloud Computing and its new architectures
G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
3/40
Introduction Stochastic Modelling of Large Distributed Systems Cloud Computing and its new architectures Decentralisation of data centres — smaller processing facilities — closer to end-user
G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
3/40
Introduction Stochastic Modelling of Large Distributed Systems Cloud Computing and its new architectures Decentralisation of data centres — smaller processing facilities — closer to end-user
Fog Computing, VoD, IoT, VNF...
G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
3/40
Introduction . Motivation Decentralisation PM 1 VM VM VM VM VM VM VM VM VM VM VM VM VM VM VMVM VM VM VM VM VM VM VM VMVM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VMVM VM VM VM VM VM VM VM VM VM VM
PM 2
PM N
DC
N Physical Machines
G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
4/40
Introduction . Motivation Decentralisation
PM 1
PM 1
PM N1
PM 2
DC 1
VM VMVM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VMVM VM VM VM VMVM VM VM VM VM VM VM VMVM VM VM VM VM VMVM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VMVM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VMVM VM VM VM VM VM VM VM VM VM VMVM VM VM VM VM VM VMVM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VM VMVM VM VM VM VM VM VM
PM N2
PM 2
DC 2
N1 + N2 = N Physical Machines G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
4/40
Introduction . Motivation Stochastic Modelling of Large Distributed Systems
Distributing processing facilities results in — lower: costs, delays, energy consumption... — higher: load variability, mismatch of load and capacity
G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
5/40
Introduction . Motivation Stochastic Modelling of Large Distributed Systems
Distributing processing facilities results in — lower: costs, delays, energy consumption... — higher: load variability, mismatch of load and capacity Congestion Control Mechanisms — Cooperation among processing facilities — Adaptation to incoming requests
G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
5/40
Introduction . Motivation Stochastic Modelling of Large Distributed Systems Resource allocation in Cloud Computing I I I I
static : load balancing, knapsack problems... resource sharing (fairness): DRF, BF... scheduling : PoC, redundancy... others : energy, network use...
G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
6/40
Introduction . Motivation Stochastic Modelling of Large Distributed Systems Resource allocation in Cloud Computing I I I I
static : load balancing, knapsack problems... resource sharing (fairness): DRF, BF... scheduling : PoC, redundancy... others : energy, network use...
but few papers on... I I
multi-resource systems no queueing applications (loss systems)
G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
6/40
Introduction . Topics of this PhD Stochastic Modelling of Large Distributed Systems
I
Allocation schemes with downgrading
I
Offloading in Fog Computing : — Probabilistic — Trunk reservation
I
Cooperative Schemes in the framework of multi-resource Cloud Computing
G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
7/40
Introduction . Topics of this PhD Stochastic Modelling of Large Distributed Systems
I
Allocation schemes with downgrading
I
Offloading in Fog Computing : — Probabilistic — Trunk reservation
I
Cooperative Schemes in the framework of multi-resource Cloud Computing
G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
7/40
Resource Allocation with Downgrading
G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
8/40
Resource Allocation with Downgrading Link congestion control policy
VoD traffic rapid growth : live transmissions — Different types of resolutions (video quality) — MPEG-DASH : bit rate adaptation
G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
9/40
Resource Allocation with Downgrading Link congestion control policy
VoD traffic rapid growth : live transmissions — Different types of resolutions (video quality) — MPEG-DASH : bit rate adaptation Bottom-line : customers prefer lower quality than rejection
G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
9/40
Algorithm
I
Files encoded in several resolutions (bit-rate)
I
Link capacity is C
G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
10/40
Algorithm
I
Files encoded in several resolutions (bit-rate)
I
Link capacity is C
I
Algorithm definition : for fixed threshold C0 < C I
If the link utilisation is X, upon arrival of a request of b > 1 : I
I
I
if X < C0 : — the request receives b if C0 ≤ X < C : — the request receives 1 if X = C : — the request is rejected
G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
10/40
Algorithm . Deployment for J=2 C Low Quality
High Quality C0
Arrivals
L = (15, (13, 10) (14, 09) G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
11/40
Algorithm . Deployment for J=2 C Low Quality
High Quality C0
Arrivals
L = (15, (13, 10) (14, 09) G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
11/40
Algorithm . Deployment for J=2 C Low Quality
High Quality C0
Arrivals
L = (15, (13, 10) (14, 09) G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
11/40
Algorithm . Deployment for J=2 C Low Quality
High Quality C0
Arrivals
L = (15, (13, 10) (14, 09) G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
11/40
Algorithm . Performance questions
Three things need to be answered : — How many customers are served at requested rate? — How many customers are rejected? — How should the threshold be set?
G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
12/40
Mathematical modelling I
System capacity is C
I
J types of requests Customer of type j, for 1 ≤ j ≤ J :
I
I I I
request Aj servers, with A1 = 1 and A1 ≤ Aj arrive as Poisson at rate λj are served with rate µj
G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
13/40
Mathematical modelling I
System capacity is C
I
J types of requests Customer of type j, for 1 ≤ j ≤ J :
I
I I I
I
request Aj servers, with A1 = 1 and A1 ≤ Aj arrive as Poisson at rate λj are served with rate µj
Saturation assumption : PJ
Aj λj /µj > C,
I
overloading :
I
stable with minimum requirement :
j=1
G. Thompson
PJ
j=1
λj /µ1 < C
PhD Defence: INRIA Paris, 08/12/2017
13/40
Mathematical modelling I
System capacity is C
I
J types of requests Customer of type j, for 1 ≤ j ≤ J :
I
I I I
I
I
request Aj servers, with A1 = 1 and A1 ≤ Aj arrive as Poisson at rate λj are served with rate µj
Saturation assumption : PJ
Aj λj /µj > C,
I
overloading :
I
stable with minimum requirement :
j=1
PJ
j=1
λj /µ1 < C
Notation : I I I
Lj (t) nb. of type j customers in the system at time t PJ m(t) = j=1 Aj Lj (t) − C0 occupation around C0 ρj = λj /µj load of customer of type j G. Thompson
PhD Defence: INRIA Paris, 08/12/2017
13/40
Mathematical modelling . A Markov Process
The process (L(t)) = ((Lj (t)), t ≥ 0) is Markov with transitions, for ` = (`j ) ∈ NJ , ` → ` + e1 ` → ` + ej ` → ` − ej def.
where m =
PJ
P λ1 + Jj=2 λj 1{m≥0} 1{m