Capitolo 3

(1)

Capitolo 3

Descrizione dell’analisi sperimentale e dei risultati

della sperimentazione

Nel presente capitolo vengono presentati gli esperimenti effettuati sull’algoritmo ALL-BRIDGE per studiarne il comportamento al variare di alcuni parametri e per confrontarlo con soluzioni alternative. Lo scopo è stato quello di confrontare la tecnica dell’algoritmo che calcola un arco sostitutivo (swap edge ottimo) per ogni possibile interruzione di collegamento diretto (link failure) rispetto a quella comunemente adottata che, in presenza di fault su un link, ricalcala ex-novo tutti gli SPT coinvolti, utilizzando l’algoritmo distribuito PT-construction definito in [3].

Poiché l’algoritmo ALL-BRIDGE elabora a priori lo swap edge ottimo di ogni arco verso ogni possibile destinazione, trovando quindi un

(2)

CAPITOLO 3. DESCRIZIONE DELL’ANALISI SPERIMENTALE E DEI RISULTATI DELLA SPERIMENTAZIONE

percorso alternativo rispetto al fallimento di ogni possibile link, per confrontarlo con una tecnica che cerca di risolvere lo stesso problema, utilizzando l’ algoritmo PT-construction, è stato deciso di simulare sistematicamente e in maniera ciclica la caduta di ogni arco, appartenente all’SPT con radice “r”, e ricalcolare ogni volta l’SPT ottimo radicato in “r”. Questo per ogni SPT avente come radice un nodo diverso, cioè per ogni possibile destinazione del grafo.

3.1 Grafi random

Nel presente lavoro è stata utilizzata una tecnica per la generazione di grafi casuali su cui poi eseguire gli algoritmi con l’obiettivo di eseguire i passi della sperimentazione. Tale tecnica è stata anche utilizzata in una sperimentazione condotta da Proietti e al. i quali per la soluzione del medesimo problema hanno però preso in considerazione gli algoritmi sequenziali [2].

Ricordiamo che la densità d(G) degli archi di un grafo biconnesso G è data da: ) 3 ( ) ( 2 ) ( − − = n n n m G δ , 0≤δ(G)≤1[2].

(3)

Un grafo G con densità δ(G) pari a 0 è un ciclo Hamiltoniano e con

densità δ(G) pari a 1 è un grafo completo.

Per testare l’algoritmo sono stati eseguiti due cicli di esperimenti su grafi pesati biconnessi generati in maniera casuale.

Nel primo insieme di esperimenti sono stati presi in considerazione grafi con 50 nodi e densità variabile δ(G)=i/10, i=1,…10, mentre il

secondo insieme di esperimenti ha avuto come oggetto grafi con densità fissa δ(G)= 0,5, aventi un numero di nodi variabile n=25*i,

i=1,…6.

Per fare in modo che il grafo generato sia biconnesso come punto di partenza è stato considerato un ciclo hamiltoniano a cui sono stati aggiunti, in modo casuale, archi fino alla densità voluta. Il peso degli archi è stato scelto in maniera casuale all’interno dell’intervallo (1,50).

(4)

3.2 Tipi di esperimenti

Gli esperimenti sono stati condotti secondo i seguenti passi:

1. applicazione dell’algoritmo distribuito ALL-BRIDGE a tutti gli alberi di copertura dei cammini di costo minimo della rete simulata, ognuno con una diversa radice per ottenere tabelle di routing resistenti al guasto di un arco (1-fault tolerant);

2. memorizzazione del numero effettivo di messaggi scambiati dai nodi della rete durante l’esecuzione di ogni istanza dell’algoritmo ALL-BRIDGE per valutare la complessità dell’algoritmo distribuito in termini di numero di messaggi.

(Si noti che nel caso di algoritmi distribuiti la complessità di tempo non è indicativa dell’efficienza, perché trattasi di algoritmi asincroni).

3. prendendo in considerazione l’SPT radicato nel nodo r, sono stati calcolati tre valori significativi che poi verranno confrontati con quelli ottenuti ricalcolando gli SPT:

(5)

- distanza media tra il nodo in cui si verifica il fallimento e la radice,

- media dei pesi degli alberi di copertura alternativi del grafo, - media delle distanze da ogni nodo dalla radice dell’albero eliminando ciclicamente un arco dell’albero, per simularne il fallimento.

Questo procedimento è stato eseguito considerando di volta in volta un SPT radicato in un nodo diverso della rete per coprire tutti i casi possibili;

4. sempre considerando un SPT alla volta, radicato ad ogni iterazione in un nodo diverso, è stata simulata la situazione in cui ogni arco, ciclicamente, è soggetto ad un fallimento ed ogni volta è stato ricalcolato l’SPT ottimo con l’algoritmo PT-construction. Quindi sono stati calcolati gli stessi valori indicati nel punto 3.

Sulla serie dei dati derivati dall’applicazione di entrambi gli algoritmi ai grafi generati (passi 3 e 4) è stata calcolata la media aritmetica per ottenere i dati significativi per il confronto da effettuare, per ogni grafo considerato.

(6)

Tenendo presente che uno degli obiettivi centrali di questa tesi è quello di analizzare i tre aspetti fondamentali dell’algoritmo ALL-BRIDGE sono state necessarie le seguenti azioni:

1- quantificare la differenza, in termini di aumento del peso dei percorsi verso ogni possibile destinazione che esiste utilizzando l’algoritmo ALL-BRIDGE rispetto all’algoritmo distribuito che ricalcola gli SPT ottimi quando un arco è soggetto ad un fallimento;

2- verificare il miglioramento in termini di numero di messaggi scambiati dai nodi nell’esecuzione dell’algoritmo ALL-BRIDGE rispetto all’algoritmo che ricalcola tutti gli alberi SPT quando in modo ciclico gli archi dell’SPT cadono;

3- misurare in maniera sperimentale la complessità reale in termini di messaggi scambiati dai nodi che eseguono l’algoritmo ALL-BRIDGE rispetto all’analisi teorica effettuata in [1] in cui viene valutato solo il caso pessimo.

(7)

3.3 Complessità teoriche

Per quello che riguarda la complessità dell’algoritmo ALL-BRIDGE nel caso pessimo, calcolata come numero di messaggi così come definito in [1], essa è pari a (n-1)(n-2) + (n-1).

Questo risultato proviene dallo studio della complessità dell’algoritmo nel caso pessimo: c’è una prima fase in cui ogni nodo, dopo aver calcolato il proprio bridge lo invia al genitore, la quale comporta n-1 messaggi.

Dato che si sta considerando il caso peggiore che possa verificarsi, occorre mettersi nella condizione in cui nessuno dei messaggi “Choice”, inviati dai figli ai genitori, è Feasible con le etichette del genitore il quale deve inoltrare un numero di messaggi di “Request” pari al numero dei propri figli i quali a loro volta risponderanno con un ulteriore messaggio di “Choice”. Quindi per ogni nodo x, che ha un numero di nodi discendenti pari a Desc(x), verranno generati un numero di messaggi pari a 2*|Desc(x)|.

(8)

Di conseguenza per completare l’algoritmo All-Bridge ogni nodo, eccetto la radice, deve calcolare il proprio swap-edge; tale processo richiederà al massimo un numero di messaggi pari a

∑

≠ = − = r x x r n x Ance x Desc( )| 2(| ( )| 1) 2 * | 2

dove Ance(x) rappresenta l’insieme degli antenati di x. Denotiamo con *

r

n il numero di archi contenuti nella chiusura transitiva

dell’insieme Tr \ {r}; 0≤n*≤(n−1)(n−2)/2.

A questo punto per ottenere il valore della complessità è sufficiente sommare i due fattori con il seguente risultato:

) 1 ( ) 2 )( 1 ( ) 1 ( 2 ) 2 )( 1 ( 2 ) 1 ( 2 *+ − = − − + − = − − + − n n n n n n n n_r

Per i motivi introdotti nel primo capitolo, in cui è mostrato come l’algoritmo ALL-BRIDGE nella sua veste originale deve essere esteso per poter essere messo in esecuzione, è necessario introdurre un ulteriore fattore di (n-1) messaggi di terminazione per portare

(9)

l’algoritmo a compimento. Quindi la complessità definitiva di ALL-BRIDGE è (n-1)(n-2) + 2(n-1), cioè n2_-n.

Come già descritto in precedenza per costruire le tabelle di routing fault-tollerance occorre eseguire n volte l’algoritmo ALL-BRIDGE, prendendo in considerazione ogni volta un albero di copertura dei cammini minimi radicato in un diverso nodo della rete, la complessità totale dell’intera computazione diventa n(n2_{-n), cioè n}3_-n2_.

Invece la complessità dell’algoritmo distribuito PT-construction, definito in [3], che elabora l’albero di copertura dei cammini di costo minimo radicato in un dato nodo della rete, anch’essa calcolata nel caso pessimo, è 2n2_{+4m-3n+1 [3]. Ricalcolare tutte la tabelle di}

routing, significa quindi eseguire l’algoritmo PT-construction n volte, ogni volta con un diverso nodo della rete come radice dell’albero. L’intera computazione ha una complessità pari a 2n3_-3n2_+(4m+1)n.

Si noti che sebbene la complessità teorica dei due algoritmi sia dello stesso ordine e l’algoritmo PT-construction garantisca sempre la soluzione ottima in termini di cammini minimi, quest’ultimo algoritmo, applicato al problema del “rerouting” di messaggi, richiede dopo il

(10)

fallimento di un arco la ricostruzione completa delle tabelle di routing, mentre ALL-BRIDGE può memorizzare l’arco swap nella tabelle che si mantengono inalterate dopo il fallimento di un arco.

3.4 Analisi dei risultati

In questa sezione sono presentati i risultati degli esperimenti ottenuti attraverso l’algoritmo distribuito ALL-BRIDGE rispetto all’algoritmo PT-construction che ricalcola l’SPT ottimo quando un arco cade.

Tutti gli esperimenti sono stati fatti eseguendo il codice java scritto per la simulazione dell’esecuzione dell’algoritmo distribuito sulla rete virtuale all’interno dell’ambiente di programmazione ECLIPSE di IBM, su un PC con processore Intel Pentium III 800 MHz, con 640 MBytes di RAM e con sistema operativo Windows XP.

Per ogni grafo random, il primo passo è stato quello di eseguire il preprocessing, dopodiché, una volta per ogni albero SPT radicato in un nodo diverso è stato eseguito l’algoritmo distribuito ALL-BRIDGE, che

(11)

calcola uno swap edge per ogni arco che compone l’SPT; di seguito è stato eseguito n volte l’algoritmo che ricalcola gli SPT quando un arco dello stesso cade.

Per ottenere uno scenario realistico, come arco che cade è stato scelto uno alla volta, in maniera ciclica, un arco facente parte dell’SPT radicato nel nodo i-esimo.

Ad ogni iterazione e per ogni algoritmo sono stati calcolati tre valori: - distanza media tra il nodo in cui si verifica il fallimento e la

radice,

- media dei pesi degli alberi di copertura alternativi del grafo, - media delle distanze da ogni nodo verso tutte le possibili

destinazioni.

La scelta è caduta su questi tre valori, perché nel caso specifico rappresentano tre possibili indicatori circa la bontà dell’algoritmo All-Bridge verso l’obiettivo per cui è stato progettato, cioè trovare il miglior percorso alternativo possibile, senza ricalcolare gli SPT ed avere una complessità paragonabile a quella di un algoritmo distribuito che ricalcola ex-novo gli alberi di copertura di costo minimo.

(12)

Ciò significa che per definizione i percorsi alternativi trovati da All-Bridge saranno sicuramente peggiori di quelli che si possono ottenere ricalcolando gli SPT. Tale differenza in termini di lunghezza dei percorsi è minima e scaturisce dal modo in cui l’algoritmo è stato progettato e soprattutto dalle modalità con le quali seleziona l’arco alternativo a quello su cui si verifica il guasto.

Inoltre per l’algoritmo distribuito ALL-BRIDGE è stato calcolato il numero totale di messaggi scambiati tra i nodi.

Come detto in precedenza gli esperimenti hanno avuto come oggetto due serie di grafi, una con grafi a densità variabile e numero di nodi fisso (50) e l’altra con densità fissa (0,5) e numero di nodi variabile. Come ci si poteva aspettare e come si può notare dai grafici 1 e 2 che riportano i risultati ottenuti su grafi a densità variabile, le medie delle distanze dal nodo in cui si verifica il fallimento alla radice, calcolate utilizzando il percorso che sfrutta lo swap edge per l’algoritmo ALL-BRIDGE e il miglior percorso possibile, per l’algoritmo PT-CONSTRUCTION, sono di poco a favore dell’algoritmo che ricalcala gli SPT.

(13)

Distanze medie tra i nodi in cui si verifica il fallimento e la radice in grafi con numero fisso di nodi (50)

e densità variabile 0 2 4 6 8 10 12 14 16 18 1 2 3 4 5 6 7 8 9 10 densità/10 distanza ALL-BRIDGE PT-CONSTRUCTION Grafico 1

Rapporto tra le distanze medie fra i nodi in cui si verifica il fallimento e la radice, calcolate con l'algoritmo

All-Bridge e con Pt-Construction

1 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,9 2 0 0,2 0,4 0,6 0,8 1 1,2 densità rapporto Grafico 2

Anche per quello che riguarda i grafi a densità fissa pari a 0,5 e numero di nodi variabile, grafici 3 e 4, l’algoritmo

(14)

PT-CAPITOLO 3. DESCRIZIONE DELL’ANALISI SPERIMENTALE E DEI RISULTATI DELLA SPERIMENTAZIONE

CONSTRUCTION rimane seppur di poco in vantaggio rispetto a ALL-BRIDGE.

Distanze medie tra i nodi in cui si verifica il fallimento e la radice in grafi a densità fissa (0,5) e numero di nodi variabile

1 2 3 4 5 6 7 8 9 10 11 20 40 60 8 0 100 120 140 numero nodi peso All.Bridge Pt-Construction Grafico 3

Rapporto tra le distanze medie tra i nodi in cui si verifica il fallimento e la radice utilizzando l'algoritmo

All-Bridge e Pt-Construction 1 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 0 20 40 60 80 100 120 140 160 numero nodi rapporto Grafico 4

In relazione al peso degli alberi calcolato considerando l’arco di swap al posto dell’arco guasto, i risultati confrontati con quelli ottenuti ricalcolando l’SPT senza considerare l’arco fallito sono pressoché

(15)

simili. Essi concordano con i precedenti confermando una minima prevalenza dell’algoritmo PT-CONSTRUCTION rispetto a ALL-BRIDGE, sia per grafi a densità fissa (grafici 5 e 6) sia per grafi a densità variabile (grafici 7 e 8).

Medie dei pesi degli alberi di copertura su grafi a densità variabile e numero fisso di nodi (50)

100 200 300 400 500 600 1 2 3 4 5 6 7 8 9 10 densità/10 peso All-Bridge Pt-construction Grafico 5

Rapporto tra le medie dei pesi degli alberi di copertura calcolate con All-Bridge e Pt-Construction 1 1,005 1,01 1,015 1,02 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 1,1 densità rapporto Grafico 6

(16)

Media dei pesi degli alberi su grafi a densità fissa pari a 0,5

145 165 185 205 225 245 265 285 305 325 20 40 60 80 100 120 140 numero nodi peso All-Bridge Pt-Construction Grafico 7

Rapporto tra le medie dei pesi degli alberi calcolati con l'algoritmo All-Bridge e con l'algoritmo PT-Construction

su grafi a densità fissa pari a 0,5

1 1,005 1,01 1,015 1,02 1,025 1,03 0 20 40 60 80 100 120 140 160 numero nodi rapporto Grafico 8

Come ci si poteva aspettare inoltre, anche la media delle distanze di tutti i nodi da ogni possibile destinazione, ottenuta con la tecnica dello swapping, è maggiore ma non di molto rispetto a quella ottenuta

(17)

ricalcolando ogni volta gli SPT (che per definizione sono i cammini di costo minimo che si possano trovare).

Come si può vedere dai grafi 9 e 10, il rapporto fra i due algoritmi sulla media delle distanze è molto vicino ad uno, il che vuol dire che in termini assoluti, la media delle distanze ottenute con la tecnica dello swapping è di poco superiore a quella ottenuta ricalcolando gli SPT ottimi, che però a loro volta necessita di scambiare un numero di messaggi molto maggiore per eseguire l’algoritmo.

Rapporto Swap-Edge / SPT

sulla media delle distanze da ogni nodo a tutte le possibili destinazioni su un grafo di 50 nodi

0,98 0,99 1 1,01 1,02 1,03 1,04 1,05 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0

densità del grafo

(18)

Rapporto Swap-Edge / SPT

sulla media delle distanze da ogni nodo a tutte le possibili destinazioni su grafi con densità pari a 0,5 0,9 0,95 1 1,05 1,1 20 40 60 80 100 120 140 160 numero di nodi Grafico 10

I grafici 11 e 12 mostrano la complessità del caso pessimo valutata come numero di messaggi scambiati dai nodi coinvolti nell’esecuzione dei due algoritmi distribuiti, soprattutto nel caso di grafi con densità variabile, si evince che la complessità dell’algoritmo ALL-BRIDGE oltre al fatto di essere migliore rispetto al PT-construction, è insensibile alla densità degli archi del grafo.

(19)

Numero di messaggi scambiati (caso peggiore) in un grafo di 50 nodi a densità variabile

0 50000 100000 150000 200000 250000 300000 350000 400000 450000 500000 550000 0 0,2 0,4 0,6 0,8 1 1,2 densità n. messaggi ALL-BRIDGE PT-construction

grafico 11: valore teorico della complessità come numero di messaggi scambiati fra i nodi nell’esecuzione dei due algoritmi su grafi a densità variabile e numero di nodi fisso, nel caso peggiore.

Numero di messaggi scambiati (caso peggiore) in grafi con densità fissa 0,5 e numero di nodi variabile 0 2000000 4000000 6000000 8000000 10000000 12000000 14000000 16000000 0 50 100 150 200 n. nodi n. messaggi ALL-BRIDGE PT-construction

grafico 12: valore teorico della complessità come numero di messaggi scambiati fra i nodi nell’esecuzione dei due algoritmi su grafi a densità fissa e numero di nodi variabile, nel caso peggiore.

Inoltre, come si vede del grafico 12, anche su grafi a densità fissa pari a 0,5 il numero di messaggi scambiati nel caso pessimo è di gran

(20)

lunga minore per l’algoritmo ALL-BRIDGE rispetto all’algoritmo PT-construction.

Numero di messaggi scambiati dall'algoritmo ALL-BRIDGE su un grafo di 50 nodi

4500 5000 5500 6000 6500 7000 0 0,2 0,4 0,6 0,8 1 densità n. messaggi

grafico 13: valore reale della complessità come numero di messaggi scambiati fra i nodi nell’esecuzione dell’algoritmo ALL-BRIDGE su grafi con densità variabile e numero di nodi fisso.

Numero di messaggi scambiati dall'algoritmo ALL-BRIDGE su grafi a densità fissa 0,5

0 10000 20000 30000 40000 50000 60000 70000 0 20 40 60 80 100 120 140 160 180 numero nodi n. messaggi

(21)

Eseguendo la serie dei test è emerso che l’effettivo numero di messaggi scambiati fra i nodi che eseguono l’algoritmo ALL-BRIDGE è di gran lunga minore rispetto al caso pessimo studiato a livello teorico in [1] . Infatti nel caso di grafi con 50 nodi e densità variabile, la complessità reale, (grafico 13), rimane nell’intervallo (5363,6962) notando un netto miglioramento con l’aumentare della densità del grafo, mentre la complessità calcolata, sia pure nel caso pessimo, risulta essere 122500 messaggi scambiati, indipendentemente dalla densità del grafo.

Invece nel caso di grafi con densità fissa e numero di nodi variabile, la complessità reale (grafico 14) si attesta tra i 1562 messaggi di un grafo con 25 nodi e i 62090 messaggi di un grafo con 170 nodi, mentre la complessità calcolata nel caso pessimo si posiziona tra i 15000 messaggi di un grafo con 25 nodi e i 4884100 messaggi di un grafo con 170 nodi, con la differenza fra numero di messaggi che si fa maggiore all’aumentare del numero di nodi.