Capitolo 1

(1)

Capitolo 1

Presentazione dell’algoritmo

In questo capitolo viene descritto in maniera dettagliata l’algoritmo distribuito ALL-BRIDGE presentato in [1].

1.1 Definizioni e terminologia

Vengono qui riportate alcune definizioni universalmente note, ma di fondamentale importanza per gli aspetti trattati.

Un grafo semplice G è definito come l’unione degli insiemi che costituiscono i suoi vertici (V) ed i suoi archi (E): G=(V,E) con un numero di vertici pari a n=|V| ed un numero di archi pari a m=|E|. Il grafo considerato in questo lavoro possiede archi bidirezionali.

(2)

CAPITOLO 1. PRESENTAZIONE DELL’ALGORITMO

Sia G’=(V’,E’) un grafo semplice anch’esso con archi bidirezionali. Se

V

V'⊆ e E'⊆E allora G’ si dice essere sottografo di G. Se V’=V allora

G’ è detto sottografo di copertura di G. Un sottografo P di G tale che

l’insieme dei suoi vertici sia Vp={v1,…,vs} in cui vi≠vj per i≠j e l’insieme

dei suoi archi Ep sia formato dalle coppie (vi,vi+1) per 1 ≤ i ≤s-1, è

detto percorso. Il sottografo P è un ciclo se v1=vs. Un grafo G è

connesso se eliminando uno qualunque dei suoi archi, G viene diviso in due sottografi. Un grafo G è biconnesso se per dividerlo in due sottografi occorre rimuovere almeno due archi. Quindi un albero può essere definito come un grafo connesso e privo di cicli.

Ad ogni arco e di G è associata una funzione non negativa |e| chiamata peso. La lunghezza di un qualsiasi percorso P di G è data dalla somma dei pesi degli archi che lo compongono. Si consideri un sottografo connesso G’ di G; la lunghezza minima del percorso tra due vertici x e

y di G’ è denotata da dG’(x,y). Per semplicità, in seguito, verrà usata la

dicitura d(x,y) al posto di dG’(x,y), senza perdere di significato. Alla

luce delle definizioni appena date, è ora possibile definire l’albero di copertura dei cammini di costo minimo radicato in r di G, detto anche SPT. Questo è un albero di copertura per G radicato nel vertice r, detto anche Tr, in cui ogni percorso tra r e qualsiasi altro nodo è

(3)

Figura 1: (a) grafo pesato biconnesso G. (b) l’albero dei cammini di costo minimo TA radicato in A; gli archi tratteggiati (H,B) e (F,M) rappresentano

gli swap-edge ottimi rispettivamente per l’arco (E,D) e per l’arco (F,D).

Vista la proprietà di un albero Tr di essere connesso, la rimozione di uno qualunque dei suoi archi e ne provocherà la disconnessione in due sottoalberi distinti. Se il grafo G, di cui Tr è l’albero di copertura dei cammini di costo minimo, è biconnesso, esisterà sempre almeno un arco di G capace di riconnettere i due sottoalberi per formare un nuovo albero di copertura Tr’ di G. Tale arco, che appartiene all’insieme E(G)\E(Tr), è chiamato swap edge per l’arco rimosso e. L’insieme dei possibili swap edge per e è denotato da Sr(e).

3 4 4 5 7 8 7 6 5 4 10 1 1 1 1 1 1 1 1 (b) C B D E F G A H M (a) C B D E F G A H M

(4)

Come definito in [1] uno swap edge ottimo (detto anche bridge) per un arco e=(u,v) è un arco che appartiene all’insieme Sr(e) e tale che la distanza di u da r del nuovo albero di copertura T’ è minima; cioè lo

swap edge ottimo per e=(u,v) è l’arco e’=(u’,v’) ∈ Sr(e) tale che

) , ' ( | ) ' , ' ( | ) ' , ( ) , ( _' ' u r d u u u v d v r d_T = _T + + _Tr è minima.

A tale proposito, si prenda come esempio il grafo biconnesso G di figura 1.a e l’albero di copertura dei cammini di costo minimo con radice A mostrato in figura 1.b. È semplice constatare che lo swap edge ottimo per l’arco e=(E,D) è l’arco e’=(H,B).

Il problema conosciuto come “optimal swap edge” per Tr si traduce nel problema di calcolare uno swap edge ottimo e’ per ogni arco e appartenente a Tr.

Come è già stato accennato, un algoritmo sequenziale efficiente che risolve questo tipo di problema è presentato in [4]. Ora l’interesse è spostato verso una soluzione distribuita per il problema dell “optimal swap edge”. Una proposta si trova in [1] e la analizzeremo attraverso la descrizione e l’analisi dell’algoritmo ALL-BRIDGE. Si noti che sostituire il cosiddetto “optimal swap edge” all’arco che subisce un

(5)

aggiornato dopo il guasto dell’arco, perché l’albero può, nel caso pessimo, cambiare completamente rispetto all’originale. Qui semplicemente si sostituisce l’arco che subisce un guasto con un arco selezionato per minimizzare la distanza dal punto di guasto alla radice. Come vedremo nei risultati sperimentali questa strategia dà una buona approssimazione rispetto all’SPT ottimo, è molto meno costosa e particolarmente adatta a guasti temporanei.

A questo scopo è considerata una topologia di rete G, sulla quale è mappato un sistema di computazione distribuito. Ad ogni elemento della rete G, è associata una entità computazionale x che possiede proprie capacità di elaborazione e memorizzazione, conosce i suoi archi incidenti e il loro peso ed è capace di comunicare con le entità vicine attraverso la trasmissione di sequenze di bit di lunghezza fissa dette messaggi. Il tempo di comunicazione che include elaborazione, accodamento, e ritardi di trasmissione, è considerato finito ma impredicibile. In altre parole il sistema è asincrono.

Ogni entità esegue lo stesso insieme di regole, detto algoritmo distribuito o protocollo.

(6)

1.2 Alcune proprietà di nodi ed archi

Nell’algoritmo ALL-BRIDGE si fa uso di alcune proprietà conosciute degli alberi radicati definite in [1,5,6] che sono qui riportate per completezza.

Nell’SPT Tr ogni nodo, eccetto la radice, ha un genitore “unico” ed ogni arco collega un nodo interno al suo genitore.

proprietà 1: l’ordine parziale indotto dalla relazione “genitore” ha

dimensione al massimo 2.

Si consideri l’etichettatura alfa:Và {1,….,n}2_{definita come segue:}

dato Tr, per ogni x∈V sia α(x)=(a,b) la funzione di etichettatura, in

cui il primo elemento, a, corrisponde al numero d’ordine rispetto ad una visita preorder traversal di Tr; e il secondo, b, è il numero d’ordine rispetto ad una visita inverted preorder traversal di Tr, in cui l’ordine di visita dei figli è invertito.

Sia Tr[x] il sottoalbero di Tr radicato in x. Ogni nodo y nel

(7)

dei discendenti di x in Tr; si noti che per definizione x appartiene a questo insieme.

È interessante notare che l’ordinamento lessicografico “f” tra le

etichette assegnate da α determina in maniera univoca la relazione di

discendenza in un albero radicato:

proprietà 2: un nodo y è discendente di un nodo x in Tr se e solo se

α(y) fα(x).

La proprietà 2 può essere facilmente verificata ed è usata comunemente per verificare la relazione tra i nodi di un albero. Ad ogni modo, esiste una semplice relazione tra swap edge e discendenti, che viene mostrata dalla seguente proprietà.

Proprietà 3: un arco (u,v)∈E\E(Tr) è uno swap edge per ex∈E(Tr) se e

solo se u oppure v, ma non entrambi, appartiene a Descr(x).

Per brevità, l’insieme Sr(ex) di tutti gli swap edge per ex, verrà

denotato semplicemente con S(x), e con InS(x)⊆S(x) l’insieme di

questi archi che sono incidenti in x. L’ultima proprietà constata che

l’insieme degli swap edge per ex consiste da tutti e soli gli swap edge

(8)

Proprietà 4: ∀x∈V , S(x) _y ₍_Desc₍_x₎₎InS(y)

r ∈

=U .

Le proprietà 2,3,4 forniscono un insieme valido di strumenti per determinare quali archi sono i possibili candidati per essere optimal swap edge.

1.3 L’algoritmo

Di seguito è riportata la descrizione dell’algoritmo ALL-BRIDGE proposto in [1].

Nella definizione dell’algoritmo è stato necessario imporre che ogni nodo potesse essere a conoscenza di alcune informazioni riguardo alla rete, nella fattispecie è stato imposto che ogni nodo x del grafo conosca il peso dei propri archi incidenti, e possa distinguere quali di questi fanno parte dell’albero Tr da quelli che non ne fanno parte; fra questi, può distinguere quello che lo collega al genitore e quelli che lo collegano ai figli; inoltre ogni nodo x conosce la propria distanza da r,

(9)

le distanze dei propri vicini da r, la propria coppia di etichette α (a,b)

così come quelle dei propri vicini.

Un’ipotesi di questo tipo è lecita perché nel caso che non fossero disponibili, queste informazioni potrebbero essere calcolate facilmente.

Nell’algoritmo distribuito ALL-BRIDGE, ogni nodo elabora il proprio optimal swap edge per l’arco che lo collega al genitore, cioè lo swap

edge per ex nel cammino di costo minimo da x a r in E\{ex}. Un nodo x

contribuisce, se necessario, all’elaborazione degli swap edge di altri nodi, in particolare dei suoi antenati nel percorso di costo minimo verso la radice.

Viste le proprietà 2 e 3, dire se un arco è uno swap edge, vuol dire esaminare la relazione “discendente”, che a sua volta è univocamente

determinata dalle etichette α. Per questo, in seguito, verrà usato

anche il termine “feasible per α(x)” per dire “swap edge per ex” senza

perdere di significato.

Dell’algoritmo ALL-BRIDGE proposto in [1] viene ora presentata una descrizione sotto forma di insieme di regole stato-evento-azione in cui è specificato quale azione un nodo deve intraprendere se si trova in un dato stato a seconda del verificarsi di un determinato evento.

(10)

I possibili stati in cui un nodo si può venire a trovare nel corso dell’esecuzione dell’algoritmo sono tre: COMPUTING, SWAPPED e WAITING.

Inizialmente, cioè prima che l’esecuzione dell’algoritmo abbia inizio, tutti i nodi sono in stato COMPUTING. Ogni nodo x mantiene una lista L(x) di possibili swap edge. Inizialmente L(x) contiene tutti gli archi incidenti in x che non fanno parte dell’albero SPT, che quindi sono candidati ad essere optimal swap edge.

Nodo in stato SWAPPED Nodo in stato COMPUTING

Nodo in stato WAITING

C B D E F G A H M

(11)

Ad ogni arco e=(w,z) appartenente a L(x) dove w è discendente di x

(può succedere che x=w), verrà associata la distanza d[e] = d(x,w) + |(w,z)| + d(z,r).

L’insieme L(x) è mantenuto ordinato rispetto alle distanze in maniera crescente. È da notare che mentre ogni nodo conosce la propria distanza dalla radice, questa potrà cambiare inserendo uno swap edge. La nuova distanza può essere ricalcolata in maniera molto semplice: quando uno swap edge viene trasmesso da un figlio u al padre v lungo l’arco (u,v), insieme alla distanza di u alla radice che include lo swap edge, il nodo v (il destinatario) incrementerà la distanza di |(u,v)|.

FOGLIA:

nello stato COMPUTING le foglie elaborano il loro swap edge in modo locale: una foglia x, attraverso la funzione “chooseMin(a,b)” sceglie come swap edge l’arco incidente di costo minimo appartenente a L(x), feasible con le proprie etichette alfa. In questo caso la funzione chooseMin(a,b) restituisce il primo elemento di L(x).

Quindi la foglia invia al suo genitore un messaggio “Choice” che contiene il risultato di chooseMin(a,b).

(12)

A questo punto passa in stato SWAPPED, in cui rimane in attesa di ricevere dei messaggi di richiesta dal genitore (“Request”, (p,q)), per calcolare uno swap edge rispetto ad etichette diverse; in questo caso invia al genitore il risultato della funzione chooseMin(p,q) e rimane nello stato SWAPPED;

msg msg

msg

msg msg

C B D E F G A H M msg = Choice

(13)

NODO INTERNO:

nello stato COMPUTING, un nodo interno x aspetta di ricevere gli swap edge elaborati da tutti i suoi figli. In particolare appena riceve un messaggio “Choice” contenente la coppia (edge, distance) controlla se “edge” è uno swap edge anche per se stesso, chiamando la funzione booleana Feasible(edge, (a,b)) (per definizione restituisce TRUE se edge = NIL).

Sia edge = (z,w). La “feasibility” dell’arco “edge” rispetto al nodo x, è testata confrontando (a,b), cioè le etichette alfa del nodo

x, con le coppie α(w) e α(z), per verificare, come definito dalla

proprietà 3, che uno solo tra w e z sia discendente di x. In altre parole, questo si può fare utilizzando l’ordinamento fra le

etichette: se α(z) fα(x) oppure (esclusivo) α(w) fα(x) allora

(14)

Figura 2: SPT con relative etichette alfa del grafo proposto. Come si può notare, benché l’arco (F,M) sia lo swap edge per l’arco (F,D), non lo è per l’arco (D,A), perché le etichette di F e M rispettivamente (9,3) e (8,5), decretano il fatto che entrambi i nodi sono discendenti di D, che ha come etichette la coppia (5,2), infatti sia (9,3) che (8,5) sono f di (5,2) e questo è in contraddizione con la proprietà 3.

Al contrario, l’arco (H,B), è lo swap edge dell’arco (E,D), perché le etichette di H e B, confermano che solo uno dei due è discendente del nodo E: (7,6) f (6,4) e (2,8) f/ (6,4)

Se il test da esito positivo, la coppia ricevuta viene memorizzata in L(x) , che viene mantenuto ordinato per distanza.

In caso contrario, x invia una richiesta al figlio esplicitando la

3 (8,5) (7,6) (9,3) (6,4) (3,9) (4,7) (5,2) (1,1) C B D E F G A H M (2,8) 1 1 1 1 4 4 5 7 8 7 6 5 4 10 1 1 1 1 C B D E F G A H M

(15)

Quando x ha ricevuto per ogni figlio, un swap edge “feasible”

con il proprio α(x), allora elabora il proprio swap edge e lo invia

al genitore.

Tale elaborazione è effettuata come nel caso di una foglia, chiamando la funzione chooseMin(a,b).

Choice

msg

C B D E F G A H M

msg = “Request” perché lo swap edge ricevuto non è feasible

(16)

A questo punto passa nello stato SWAPPED in cui si mette in attesa di ricevere dei messaggi, (“Request”, (p,q)) dal genitore; al contrario di una foglia che può elaborare lo swap edge richiesto in locale, un nodo interno coinvolge nell’elaborazione della “Request” tutti i suoi figli, infatti, per ogni figlio y di x, controlla se l’arco ricevuto da tale figlio è feasible con (p,q). Ad ognuno dei figli il cui controllo sullo swap-edge ha dato esito negativo, invia una richiesta (“Request”, (p,q)) e passa allo stato WAITING in attesa delle loro risposte. Una volta ricevute le risposte, esegue la funzione chooseMin(p,q) e invia il miglior swap edge feasible con (p,q) al genitore; ritorna in stato SWAPPED.

Choice

C B D E F G A H M

Nodo in stato WAITING

Choice

Request

C B D E F G A H M Request

(17)

Se nessuno dei test sugli swap edge dei figli fallisce, non ha

bisogno di inviare richieste ai figli e può scegliere lo swap edge = (chooseMin(p,q)) da inviare al genitore in modo

locale; rimane in stato SWAPPED.

C B D E F G A H M

(18)

1.4 Estensione dell’algoritmo

Quello descritto nella sezione precedente, come è facile osservare, non è un algoritmo distribuito che può essere direttamente implementato perché manca delle condizioni per la terminazione. Il contributo personale è iniziato quindi con la definizione delle condizioni di terminazione e di altri punti dell’implementazione non specificati in [1], lavoro non del tutto banale e d'altronde necessario per il raggiungimento degli obiettivi per questo lavoro di tesi.

Come si può notare dalla descrizione dell’algoritmo, visto che ogni nodo invia il proprio optimal swap edge, elaborato in locale, al suo genitore, nel momento in cui il genitore è il nodo radice ed ha ricevuto lo swap edge da ognuno dei propri figli, l’algoritmo deve terminare, perché la radice, come si può intuire facilmente, si comporta in modo diverso da un nodo interno all’albero. Nella fattispecie, la radice dell’albero quando riceve uno swap edge da un figlio, lo memorizza senza passare attraverso il test di feasibility su quell’arco. Questo perché la radice non deve calcolare un proprio swap edge perché oltre essa non c’è alcun genitore da raggiungere. A questo punto la radice deve far partire un messaggio di terminazione, che si deve diffondere

(19)

a tutti i nodi della rete, per rendere noto che l’algoritmo ha avuto fine.

Quindi l’algoritmo viene esteso nel seguente modo:

viene aggiunto uno stato “DONE” all’insieme dei possibili stati in cui ogni nodo si può trovare. Inoltre vengono specificate le azioni che deve intraprendere il nodo radice dorante l’esecuzione dell’algoritmo e le azioni che devono essere intraprese dai nodi quando viene ricevuto un messaggio di terminazione.

RADICE: attende da ognuno dei propri figli un messaggio contenente

lo swap edge calcolato. Quando li ha ricevuti tutti, l’algoritmo deve terminare, quindi invia a tutti i suoi figli un messaggio (“Done”), che poi verrà propagato su tutti i nodi della rete in maniera sistematica dai figli a loro volta ai loro figli e passa in stato DONE. “Done” “Done” “Done” C B D E F G A H M

(20)

FOGLIA: quando si trova in stato SWAPPED e riceve un messaggio

(“Done”) dal genitore, capisce che l’algoritmo è terminato e passa in stato DONE.

NODO INTERNO: quando un nodo interno x si trova in stato

SWAPPED e riceve un messaggio (“Done”) dal genitore, invia ad ogni figlio y di x, lo stesso messaggio ricevuto dal genitore, in modo che si propaghi su tutto il suo sottoalbero. Quindi passa in stato DONE.

“Done” “Done”

“Don e”

Nodo in stato SWAPPING Nodo in stato DONE

C B D E F G A H M

(21)

A questo punto quando tutti i nodi si trovano in stato DONE l’algoritmo è terminato.

1.5 Come si ricalcola il routing

Quello appena descritto è un modo distribuito di elaborare in maniera efficiente l’optimal swap edge per ogni arco di un singolo SPT di un grafo biconnesso. Quindi per trovare gli optimal swap edge di ogni arco per ogni possibile SPT del grafo, l’algoritmo ALL-BRIDGE deve essere eseguito per tutti gli n possibili shortest-path-tree, ognuno avente come radice un differente vertice del grafo, in modo da coprire tutti i casi possibili.

Nodo in stato DONE

C B D E F G A H M

(22)

È in questo modo che si costruisce una tabella di routing persistente fault-tollerance. A questo punto il problema è quello di capire come la tabella di routing è estesa e come le informazioni memorizzate devono essere usate in presenza di fault di archi incidenti. La tabella di routing del nodo u oltre a contenere tutte le informazioni necessarie per raggiungere ogni possibile destinazione r, nella fattispecie, il vicino v, nel cammino di costo minimo da u a r (determinato con SPT Tr), grazie all’esecuzione dell’algoritmo ALL-BRIDGE, contiene anche l’optimal swap edge (u’,v’) in Tr. Questa informazione è accessibile con RT[u,r].bridge.

dest Next-hop bridge

r u,v u’,v’

k u,y u,z

… … …

Figura 2: esempio di tabella di routing del nodo x

Utilizzando una tabella di routing di questo tipo è possibile fornire un servizio di “point of failure rerouting”.

(23)

Si consideri un messaggio M con destinazione r che arriva a u dove l’arco al next-hop v è fallito. In questo caso saranno eseguiti i seguenti passi:

1. viene recuperato l’optimal swap edge (u’,v’) per (u,v) attraverso RT[u,r].bridge;

2. il messaggio M viene inviato a u’ lungo il percorso di costo minore da u a u’ (backtraking);

3. il messaggio M viene trasmesso da u’ sull’arco (u’,v’);

4. il messaggio M viene inviato da v’ alla sua destinazione finale usando le informazioni della tabella di routing.

C’è da notare che l’optimal swap edge può essere incidente a u: in questo caso u e u’ coincidono e il passo 2 non viene eseguito.

Se così non fosse, il passo 2 viene effettuato consultando la tabella di routing ma con destinazione finale per il messaggio M diversa da r; infatti in questo caso il messaggio deve prima essere instradato verso u’ e poi da lì deve continuare verso la sua destinazione originale. Questo può essere fatto sfruttando la stessa tabella di routing cercando il percorso migliore da u a u’. Il messaggio dovrà però portare con se le informazioni relative alla sua reale destinazione così che una volta arrivato ad u’ possa essere ripristinata.

(24)

In questo modo si vengono a creare due modi diversi in cui il messaggio si può venire a trovare viaggiando all’interno della rete ed è per questo che è bene fare una distinzione su tali modi:

- normal mode, in cui il messaggio M segue il normale algoritmo di

percorso minimo di routing verso la sua destinazione finale

- backtraking mode, in cui il messaggio M, segue il normale

algoritmo di percorso minimo di routing verso una destinazione temporanea (da u a u’ nel passo 2) e attraversa l’optimal swap edge ((u’,v’), nel passo 3).

Quindi ogni messaggio deve contenere un bit in più per specificare il modo di routing (0-normale, 1-backtraking) e quando si fa backtraking le informazioni sullo swap edge (u’,v’) devono essere aggiunte al messaggio; queste informazioni contengono anche la destinazione temporanea u’. in altre parole il formato del messaggio è questo:

• <0, destinazione, M> normal mode>

(25)

figura 3: esempio di rerouting in presenza del fallimento di un arco

Figura Sorgente Destinazione Arco danneggiato Bridge Routing mode Formato messaggio 3.a F A F,D F,M 0 <0,A,M> 3.b E A E,D H,D 1 <1,(H,D),A ,M>

Quando un nodo u scopre un fallimento su uno dei suoi archi, legge nella tabella di routing il bridge (u’,v’) per quell’arco; poi nel caso in cui u’ sia differente da u, modifica l’etichetta del messaggio che vorrebbe passare per l’arco fallito e lo invia al next-hop per la destinazione u’. Altrimenti viene inviato direttamente a v’, senza cambiare il modo.

C B D E F G A H M C B D E F G A H M (a) (b)