Caratterizzazione del tempo di risoluzione

In questa sezione definiamo il modello per ottenere il valore atteso del tempo di esecuzione di una composizione di servizi.

La definizione della variabile aleatoria che descrive il tempo di esecuzione del servizio composto `e guidata dalla struttura e dalle propriet`a dei grafi delle alternative GC ricavati dal grafo dei nodi GN.

Ogni nodo (ni, si) di GC indica l’esecuzione di un servizio si sul provider

ni della rete, mentre ogni arco ((ni, si), (nj, sj)) indica la necessit`a del pro-

vider nj di attendere il trasferimento dell’output del servizio si da parte del

nodo ni per poter eseguire il servizio sj.

Dato il vincolo posto dagli archi in ingresso al nodo affinch´e il servizio successivo possa essere eseguito, possiamo definire il tempo di completamen- to del servizio composto in modo ricorsivo.

Sia Rni,si una variabile aleatoria che esprime il tempo che intercorre dal-

l’assegnamento della richiesta di esecuzione composta, fino alla terminazione dell’esecuzione del servizio si all’interno del provider ni, dove (ni, si) `e un

nodo del grafo GC.

Coerentemente con la notazione usata nel capitolo precedente, indichia- mo con Wnh,ni il tempo di attesa per il contatto successivo (descritto nella

sezione 4.3) tra nh e nj, con Bnh,ni(k) indichiamo il tempo per trasferire dati

di grandezza k dal nodo nh, al nodo ni senza dover attendere per un contatto

(sezione 4.6), θnh,ni(k) `e invece il tempo per trasferire i dati da nh a ni, senza

infine Dq_ni e Ds_ni,si sono rispettivamente il tempo di attesa in coda per una

richiesta inviata al provider ni e il tempo di esecuzione del servizio si da

parte del nodo ni (sezioni 4.4 e 4.5).

Dato che consideriamo due metodi per trasferire dati tra due nodi diversi dal seeker coinvolti nella composizione, usando il seeker come tramite in caso di conoscenza solo locale o altrimenti con la possibilit`a di contatto diretto, usiamo nella definizione di R una variabile aleatoria chiamata θnj,sj,ni(k) che

indica il tempo di trasferimento generale di dati tra due nodi qualsiasi nj, ni

per eseguire il servizio sj. Questa variabile ha una definizione diversa a se-

conda del servizio da eseguire e della conoscenza che possiede il seeker. In Figura 5.6 vediamo come le variabili aleatorie si rapportano ad un

start,N0 {0} S3,N1 {0},{1} S1,N2 {0},{2} S2,N2 {1,2},{3} end,N0 {3} RN0,start RN1,S3 RN2,S2 RN0,end RN2,S1 ϴN1,N2+DQ,N2+DS,S2,N2 Sincronizzazione = WN0,N1+BN0,N1+DQ,N1+DS,S3,N1 ϴN2,N2+DQ,N2+DS,S2,N2 ϴN2,N0 WN0,N2+BN0,N2 +DQ,N2+DS,S1,N2 WN0,N1+BN0,N1 +DQ,N1+DS,S3,N1 = Esecuzioni parallele = WN0,N2+BN0,N2+DQ,N2+DS,S1,N2 = max{RN1,S3+ϴN1,N2,RN2,S1+ϴN2,N2}+DQ,N2+DS,S2,N2 = 0

= RN2,S2+ϴN2,N0 Tempo di risoluzione della composizione

Figura 5.6: Valori associati ad un’alternativa in Figura 5.4

grafo che indica un’alternativa di composizione. Supponiamo che il nodo n0,

Ogni arco del grafo indica un invocazione di servizio che consiste nel tra- sferimento dei dati in input, l’attesa in coda della richiesta e l’esecuzione vera e propria, al termine dell’esecuzione del servizio si passa al nodo successivo della composizione.

Cos`ı come nel Capitolo 4, il seeker pu`o valutare separatamente il tempo di trasferimento B e il tempo di attesa per poter iniziare a trasferire i dati W , quindi sugli archi uscenti dal seeker all’inizio della composizione (con- traddistinta dal servizio start) viene associato come tempo di trasferimento W + B. A questo valore deve poter essere aggiunto il tempo di attesa in coda della richiesta Dq e il tempo di esecuzione del servizio Ds.

Il trasferimento dati all’inizio della composizione non risente della diffe- renza tra conoscenza locale e non locale, dato che il trasferimento parte gi`a dal seeker, ma per i trasferimenti con gli altri nodi della rete associamo la nuova variabile θ.

Nel caso di conoscenza locale θ deve essere definita come un doppio tra- sferimento del tipo θ1 + θ2, mentre se si conoscono le statistiche di mobilit`a

relative a mittente e destinatario potrebbe assumere anche la forma di θ, scegliendo in base a quale tipo di trasferimento `e pi`u conveniente.

Si pu`o procedere in questo modo fino agli archi entranti nel vertice con il servizio end, che segna il terime della composizione. Per quest’insieme di archi, il tempo di attesa in coda e il tempo di esecuzione dei servizi possono essere omessi, con il solo tempo di trasferimento che viene associato all’arco. Il tempo di esecuzione dell’intera composizione `e esprimibile come una variabile aleatoria Rend,n0 pu`o essere definita ricorsivamente come il tempo

necessario per eseguire tutti i servizi della composizione a cui va aggiunto il tempo per trasferire i dati richiesti verso n0. Il tempo necessario per l’esecu-

zione della composizione pu`o essere definito allo stesso modo come il tempo necessario per eseguire tutti i passi precedenti a cui va aggiunto il tempo per trasferire l’input per eseguire l’ultimo passo di composizione. Questa defi- nizione pu`o essere espansa fino alla risoluzione di Rstart,n0 che indica l’inizio

della composizione.

Nell’esempio in Figura 5.6 il servizio end ha un solo arco entrante, quindi dovr`a attendere il completamento del solo servizio S2 e il trasferimento dei

risultati. Invece il servizio S2 ha necessit`a di ricevere dati dai nodi S1 ed

S3, quindi si viene a creare un punto di sincronizzazione per cui il tempo

necessario per eseguire S3 dipende dal calcolo del massimo dei tempi di com-

pletamento dei cammini di composizioni precedenti.

Ora formalizziamo queste considerazioni per ricavare la formulazione di Rend,n0. Innanzitutto diamo una definizione per il tempo di trasferimento θ

a seconda dei casi rilevabili in un’alternativa di composizione: • θnh,sh,ni(k) = Wnh,ni+ Bnh,ni(k) se sh = start

• θnh,sh,ni(k) = θnh,ni(k) se sh 6= start e il seeker ha a disposizione la

conoscenza della mobilit`a relativa alla coppia di nodi della rete (nh, ni)

e se θnh,n0(k) + θn0,ni(k) > θnh,ni(k)

• θnh,sh,ni(k) = θnh,n0(k) + θn0,ni(k) se sh 6= start e il seeker n0 ha a

disposizione solo la conoscenza rilevabile in locale riguardo la mobilit`a di rete e per effettuare il trasferimento dei dati deve utilizzare s´e stesso come tramite tra i nodi della composizione, oppure se sfruttando la conoscenza non locale si ha θnh,n0(k) + θn0,ni(k) < θnh,ni(k).

A partire dalla definizione delle variabili aleatorie che compongono le fasi di risoluzione di un servizio composto, il valore di Rni,si `e determinabile a

partire dagli m nodi (sj, nj) con j = {1, ..., m} che hanno archi in ingresso

in (si, ni), tramite la seguente formulazione:

• Rni,end= max{Rnj,sj + θnj,sj,ni(kj)|j = 1, .., m}

• Rni,si = max{Rnj,sj + θnj,sj,ni(kj)|j = 1, .., m} + Dqni + Dsni,si se si 6=

start ∧ si 6= end

• Rni,start = 0

Data questa formulazione, la variabile aleatoria che esprime il tempo che in- tercorre tra l’inizio e la fine della risoluzione della richiesta, `e Rend,n0 dove n0

`

e il nodo seeker che ha generato la richiesta.

composta da un operatore di massimo applicato su un numero di variabi- li aleatorie con distribuzioni che non sono dello stesso tipo. Poich`e non `e possibile sfruttare la descrizione della distribuzione delle singole variabili `e necessario usare le formule generali per il calcolo del valore atteso:

Sia X una variabile aleatoria definita come X = max{X1, ..., Xn} e as-

sumiamo per semplicit`a che X1, ..., Xn siano indipendenti. Il calcolo del suo

valore atteso equivale alla media pesata sulle probabilit`a del valore atteso di ogni componente: E[X] = n X i=1 E[Xi] ∗ P {Xi = max{X1, ..., Xn}} Con: P {Xi = max{X1, ..., Xn}} = Z ∞ 0 P {Xi ≥ t|X1 ≤ t ∧ ... ∧ Xn≤ t}∗ ∗P {X1 ≤ t ∧ ... ∧ Xn ≤ t}dt = Z ∞ 0 (1 − FXi|X1≤t∧...∧Xn≤t(t)) ∗ n Y j=1,j6=i FXj(t)dt

Tornando alla formula per il valore atteso abbiamo:

E[X] = n X i=1 E[Xi] ∗ Z ∞ 0 (1 − FXi(t)) ∗ n Y j=1,j6=i FXj(t)dt

Dato che le funzioni cumulative di probabilit`a FXi non hanno una forma

ulteriormente manipolabile non `e possibile arrivare ad una formula chiu- sa per la produttoria e conseguentemente per l’integrale e la sommatoria. Quindi non `e possibile esprimere esplicitamente il valore di E[Rn0,end] e non

`

e possibile per l’algoritmo di valutazione calcolare E[Rn0,end] senza l’ausilio

di risolutori matematici.

Se invece consideriamo le composizioni sequenziali, il problema risulta trattabile, come mostrato nella sezione successiva.