Stato di Avanzamento dello sviluppo del modulo Concretizator

Danilo Ardagna, Valerio Manzoni

20/7/2005

Sommario

Richiamo della formulazione del problema ottimizzazione

Ri-ottimizzazione periodica Peeling dei cicli Risultati sperimentali Architettura software del Concretizator Demo

MAIS Concretizator

Obiettivi: • determinare a tempo di esecuzione

l’insieme di servizi concreti in modo da ottimizzare la QoS percepita dall’utente per l’esecuzione dell’istanza del singolo processo applicativo

• Ottimizzazione globale e garanzia di vincoli globali

Variabilità di ambiente e contesto:• Variabilità delle performance dei servizi

concreti (carico, availability, nuovi servizi,…)• Context switch dell’end-user• Variabilità sul numero di esecuzione dei cicli

Ri-ottimizzazione periodica del piano di esecuzione

Scenari di esecuzione

HP: unfolding dei cicli

Execution Path ep2 75%

t1

t2t4

t7

t3

t6

t1

t2t4

t5

t7

t3

t6

Composite Service

C1 not(C1)

25% 75%

Execution Path ep1 25%

t1

t2t4

t5

t7

t3

Formulazione del Problema: funzione obiettivo

Il valore aggregato di QoS associato ad ogni Execution Path è ottenuto con tecnica SAW (normalizzazione e somma pesata)Obiettivo: massimizzare la QoS considerando tutti i possibili scenari di esecuzione

Funzione obiettivo

Valore di qualità aggregato di un execution path

Formulazione del Problema: vincoli

Sono garantiti per ogni scenario di esecuzione i seguenti vincoli:

• Tempo di esecuzione ≤ R

• Tempo di esecuzionef ≤RD

• Availability ≥A

• Price ≤ B

• Reputation ≥T

• Data Quality ≥Q

HP: la formulazione MILP richiede che le regole di valutazione delle dimensioni di qualità per il servizio composto introducano somme

pesate (medie), prodotti, minimo e massimo

Formulazione del Problema

Il problema è NP-Hard, è equivalente ad un problema di zaino Multiple Choice Multiple Dimension

Riottimizzazione

Differenza tra valore corrente e predizione dimensioni

qualità, |Qk-Qk|>k (variabilità delle prestazioni)

Fallimento dell’invocazione di un’operazione (piano sub-ottimo)

Periodicamente, con periodo adattativo in una time window (variabilità dei servizi disponibili)

Context switch dell’utente (diversa scelta dei pesi)

Dopo la valutazione di una condizione di switch (piano sub-ottimo)

Al termine dell’esecuzione di un ciclo (se il numero di iterazioni è inferiore al massimo atteso, il piano individuato è sub-ottimo)

^

Cicli

Vincoli aggiuntivi per le dimensioni di qualità che per i servizi composti vengono valutate come media (reputation e data quality)

Peeling dei cicli e distribuzione di probabilità

t1

1-p0

p0

t2

1-p1

p1

1-p2

p2

.

.

.

t

C1

not(C1)<process> <sequence> <while cond=C1> <invoke t> </invoke> </while> </sequence><process>

Tecniche di ottimizzazione

Tecnica 1: Effettuare il peeling del ciclo corrente, unfolding degli altri cicli sulla base del numero massimo di iterazioni

Tecnica 2: Effettuare il peeling di tutti i cicli. Problema: il numero di cammini cresce in modo esponenziale

Tecnica 3: non viene effettuato il peeling ma solo l’unfolding dei cicli (Zeng et al., Canfora, Barreiro)

Implementazione della Tecnica 1, Tecniche 2 e 3 benchmark

Peeling dei cicli risultati preliminari

Distribuzioni di probablità di riferimento: geometrica, Poisson e uniforme

Geometric distribution

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0 5 10 15 20

Cycle number of iterations

Pro

bab

ility

den

sity

p=0.2 p=0.5 p=0.6

Poisson distribution

0

0.05

0.1

0.15

0.2

0.25

0 5 10 15 20

Cycle number of iterations

Pro

bab

ility

den

sity

l=3 l=6 l=9

Uniform distribution

0

0.05

0.1

0.15

0.2

0.25

0.3

0 2 4 6 8 10

Cycle number of iterations

Pro

bab

ility

den

sity

a=3 a=6 a=9

Peeling dei cicli risultati preliminari

Confronto tecniche 1 e 3 (Peeling ciclo corrente vs. unfolding)

Il miglioramento ottenibile con il peeling sono più evidenti quando i vincoli sono più stringenti

I risultati preliminari mettono in evidenza che il peeling è più efficiente per distribuzioni geometriche e uniforme

Miglioramento variabile tra il 5 e 45%

Vantaggi: se il numero di iterazioni è inferiore al valor medio allora è possibile evitare di effettuare il re-planningIl peeling consente di ridurre l’overhead dovuto

alla ri-ottimizzazione

Tempi di Esecuzione (CPLEX)

Negoziazione

Obiettivi:

• Identificare una soluzione ammissibile se il problema di ottimizzazione iniziale non ammette soluzione

• Migliorare un piano di esecuzione negoziando i parametri di esecuzione dei servizi

Identificare una soluzione ammissibile

HP: esiste un vincolo di budget ed è soddisfacibile Complessivamente il problema ha N vincoli Individuare il massimo numero K di vincoli che ammette

soluzione valutando al più i 2(N-1)-2 rilassamenti del problema (analisi esaustiva delle combinazioni di vincoli)

Negoziazione multi attributo per le dimensioni dei restanti N-K-1 vincoli violati

Ripartizione del margine di prezzo:• Tra i vincoli proporzionalmente in base alla violazione

percentuale• All’interno dello stesso vincolo, principio bottleneck

removal: • qualità positive: in modo inversamente proporzionale al

valore assunto dalla dimensione di qualità • qualità negative: in modo proporzionale al valore assunto

dalla dimensione di qualità

Esempio

Max Data Quality

• Tempo di esecuzione ≤ 7

• Availability ≥0.99

• Price ≤ 1000

• Reputation ≥0.8

t1

t2

Il problema non ammette soluzione

Il rilassamento che introduce unicamente il vincolo di prezzo è ammissibile, Price=200

Vengono valutati i seguenti rilassamenti:

• Price + T esec OK

• Price + Avail OK

• Price + Rep OK

• Price + Tesec + Avail No

• Price + Tesec + Rep No

• Price + Avail + Rep OK

Rilassamento Price+Avail+Rep

Price=800

Margine prezzo 200

Soluzione: WS11, WS21

t11+t21=6+2=8>7

Negoziazione:

• margine t11 proporzionale a 6/8

• margine t21 proporzionale a 2/8

Migliorare un piano di esecuzione

Esiste una soluzione ottima del problema

Negoziare il valore delle dimensioni di qualità dell’ottimo individuato in modo da migliorare il valore della funzione obiettivo

Il margine di prezzo viene ripartito tra le dimensioni di qualità proporzionalmente al valore

delle derivate f/ Qkj della funzione obiettivo

rispetto al valore della dimensione di qualità k assunta dalla soluzione ottima del task j

Formulazione del Problema

Ripartizione del margine di prezzo

Il valore di qualità per la soluzione ottima del task j è intermedio tra i valori ammissibili di qualità del task (Qkj,min<Qkj<Qkj,max):

La dimensione di qualità è positiva e per il task j l’ottimo globale coincide con l’ottimo locale:

La dimensione di qualità è positiva e Qkj=Qkj,min:

La dimensione di qualità è negativa e per il task j l’ottimo globale coincide con l’ottimo locale:

La dimensione di qualità è negativa e Qkj=Qkj,max:

Architettura Software Concretizator

Process TranslatorProcess Translator

lp_Solve / CPLEXlp_Solve / CPLEX

Ranking ProcedureRanking Procedure

XML file:●vincoli (istanza)●pesi

Formulazione problema MILP

Global Plan (selezione WS)

WS Ranking

SpecificaBPEL4WS semplificata

XML file:●Distribuzione numero iter. while e switch

XML file:●WS candidati●Associazione task/WS

NegotiatorNegotiator MAIS

registry

Local Constr. Enforcement

Local Constr. Enforcement Process Tuner

Process Tuner

Vincoli aggiuntivi

Log file (re-opt):● ultimo task eseguito (stato)

BPEL4WS Semplificato

BPEL

Attività primitive• invoke• receive• replay• wait• assign• throw• terminate• empty

Attività strutturate• sequence• switch• while• pick• flow• scope

BPEL-like

Attività primitive• element

Attività strutturate• sequence• switch• while

• flow

Un esempio

t1

t2 t4

t5

t9

t3

t6t7

t8

Rappresentazione XML

<?xml version="1.0" ?>

<sequence name = "sequenza 1"> <element name = "elemento 1"> </element><switch name = "switch 1">

<sequence name = "sequenza 2"> <element name = "elemento 2">

</element><switch name = "switch 2">

<element name = "elemento 5"> </element>

<element name = "elemento 6"> </element>

</switch></sequence><element name = "elemento 3"> </element><sequence name = "sequenza 3">

<element name = "elemento 4"> </element>

<while name = "while 1"><element name = "elemento

7"> </element><element name = "elemento

8"> </element></while>

</sequence></switch><element name = "elemento 9"> </element>

</sequence>

Qualità dei WS ed associazione task/WS

<?xml version="1.0" ?><webServices>

<webService name="ws_1"><maxTime value="6.767389" /><minTime value="5.767389" /><price value="0.123061776" /><reputation value="0.82627237" /><availability value="0.9903379" /><dataQuality value="0.9857625" />

</webService><webService name="ws_2">

<maxTime value="7.9125476" /><minTime value="5.767389" /><price value="0.45754516" /><reputation value="0.9279902" /><availability value="0.9791445" /><dataQuality value="0.91493726" />

</webService>...</webServices>

<?xml version="1.0" ?>

<tasks><task name = "task_1">

<webService name = "ws_1"> </webService>

<webService name = "ws_2"> </webService>

<webService name = "ws_3"> </webService>

<webService name = "ws_22"> </webService></task>

<task name = "task_2"><webService name = "ws_1">

</webService><webService name = "ws_4">

</webService><webService name = "ws_19">

</webService></task>

.

.

.</tasks>

WS candidati Associazione task/WS

Vincoli, pesi, distribuzioni di probabilità

<?xml version="1.0" ?>

<Users><User name = "XXX">

<avTimeWeight value = "1"> </avTimeWeight><priceWeight value ="0"> </priceWeight><reputationWeight value = "0"> </reputationWeight><availabilityWeight value = "0"> </availabilityWeight><dataQualityWeight value = "0"> </dataQualityWeight><restarTime value = "0.5"> </restarTime><avTimeConstraint value = "2000"> </avTimeConstraint><priceConstraint value ="15"> </priceConstraint><reputationConstraint value = "0.0005"> </reputationConstraint><availabilityConstraint value =

"0.00000001"> </availabilityConstraint><dataQualityConstraint value = "0.01"> </dataQualityConstraint><degDurationConstraint value =

"20000000"> </degDurationConstraint>

</User></Users>

Pesi e vincoli

<?xml version="1.0" ?>

<bounds><switch name = "switch 1">

<branch number = "1" value = "0.1"> </branch><branch number = "2" value = "0.1"> </branch><branch number = "3" value = "0.8"> </branch>

</switch><switch name = "switch 2">

<branch number = "1" value = "0.7"> </branch><branch number = "2" value = "0.3"> </branch>

</switch><while name = "while 1">

<probability number = "0" value = "0.049"></probability><probability number = "1" value = "0.15"></probability><probability number = "2" value = "0.22"></probability><probability number = "3" value = "0.22"></probability><probability number = "4" value = "0.17"></probability><probability number = "5" value = "0.1"></probability>

</while></bounds>

Annotazione specifica BPEL

DEMO

To dos

Analisi Sperimentali!

Estensione del modello: considerare l’invocazione di una singola operazione ed introdurre nuovi vincoli (provider dei servizi)

Offrire il Concretizator come Web Service

Rendere configurabile la scelta dell’ottimizzatore MILP (lp_solve, CPLEX, Symphony,COIN-OR, …)