PhD Defence

1 downloads 198 Views 894KB Size Report
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