L’algoritmo distribuito di J Liebeherr et al

Liebeherr descrive in [24] un algoritmo incrementale per costruire una triangolazione di Delau- nay in maniera distribuita in modo da poter utilizzarla come overlay network per applicazioni di tipo multicast. La scelta di Liebeherr in un’overlay basato su triangolazioni di Delaunay è motivato dal fatto che la triangolazione gode delle seguenti proprietà:

1. la triangolazione di Delaunay ha una serie di vie non sovrapposte per ogni coppia di nodi della rete;

2. il numero di archi da un nodo in una triangolazione di Delaunay è in media 6;

3. una volta che la rete è costruita, l’invio di un pacchetto è gestito dall’overlay senza il bisogno di utilizzare un protocollo di routing.

Si consideri una rete V : ad ogni nodo n in V è assegnato un identificatore logico e un identificatore fisico. L’identificatore logico è un codice univoco che viene realizzato in fase di configurazione della rete, e che somiglia a una serie di coordinate logiche spaziali. L’identifi- catore fisico è qualcosa di prestabilito che viene creato tramite una fusione tra l’indirizzo IP

della macchina e il numero di porta UDP.

Viene definito un ordinamento tra gli indirizzi logici, sulla base dell’algoritmo Divide et Impera di Guibas e Stolfi (Sezione 2.2). Si consideri la seguente proposizione:

Proposizione 3.4.1 (Ordinamento nella rete). Si considerino due nodi a e b appartenenti a una rete di nodi V : si dice che a < b se y_a< yb oppure ya= yb e xa< xb, dove a = (xa, ya)

e b = (x_b, yb).

L’algoritmo utilizza un sistema di rendez-vous con un server per permettere ai nodi che non appartengono alla rete di conoscere almeno un nodo che già ne fa parte. Questo meccanismo viene utilizzato in fase di join di un nuovo nodo n permettere la ricerca nella rete del nodo v più vicino a n tramite greedy routing.

L’algoritmo è temporizzato, in quanto utilizza dei timer per stabilire in quale momento la rete deve essere aggiornata inviando dei messaggi tra i nodi.

Alcuni tra i timer utilizzati sono:

• l’Hearthbeat timer, il quale stabilisce quando i nodi devono inviare i messaggi ai propri vicini. Può essere fast nel caso in cui un nodo goda dello stato di nodo Leader (il significato sarà spiegato nella prossima sezione), oppure slow. Anche il server possiede un Hearthbeat timer, il quale viene utilizzato per aggiornare la propria cache

• il Neighbor timer, allo scadere del quale ogni nodo controlla se ha ricevuto messaggi dal vicino x e, eventualmente, elimina x dalla tabella dei vicini, dando per scontato che x non partecipi più in modo attivo alla rete.

• il Cache timer, allo scadere del quale il server, il quale ha inviato un messaggio di CachePing a un nodo N e non ha ricevuto risposta da n, elimina n dalla propria cache. • il Leader timer, allo scadere del quale il server declassa n, nodo leader dal quale non ha ricevuto risposta in seguito a un messaggio di CachePing, da nodo Leader a nodo non Leader, scegliendo un nuovo Leader dalla cache.

Per il calcolo delle triangolazioni locali dei nodi viene effettuato il Neighbor Test (??): questo viene eseguito da un nodo n che viene a conoscenza di un nuovo nodo v. Il Neighbor test effettuato da n per un vicino candidato v è valido se il nodo v è un vicino di Delaunay di n. Le Definizioni 3.9 e 3.10 definiscono il Clockwise Neighbor e il CounterClockwise Neighbor di un nodo n rispetto a x.

Definizione 3.9 (Clockwise Neighbor). Si dice Clockwise Neighbor CW_x(n) di n rispetto a x il nodo b che soddisfa le seguenti proprietà:

2. il minore angolo che forma è minore di 180 gradi.

Definizione 3.10 (CounterClockwise Neighbor). Si dice CounterClockwise Neighbor CWx(n)

di n rispetto a x il nodo b che soddisfa le seguenti proprietà:

1. forma il minore angolo in senso antiorario con il nodo x avendo n come pivot. 2. il minore angolo che forma è minore di 180 gradi.

Effettuare il Neighbor test su n per il nodo v, candidato a possibile vicino di Delaunay di n, significa verificare che il quadrilatero n, CW_v(n), CCWv(n) e v con la diagonale che

congiunge n e v, sia una triangolazione di Delaunay. Più in dettaglio, questo test equivale a verificare che la somma degli angoli in CWv(n) e CCWv(n) sia minore di 180 gradi. Se ciò

avviene, allora il Neighbor Test per v è verificato, altrimenti non è verificato.

Per la memorizzazione dei vicini di Delaunay e dei nodi necessari all’esecuzione del Neighbor Test, ad ogni nodo n ∈ V è associata una tabella dei vicini divisa in tre colonne: una colonna contiene l’identificatore del vicino v, mentre le altre due i nodi CW_v(n) e CCWv(n). Esistono

dei casi speciali in cui il Neighbor Test è verificato senza che valgano le condizioni descritte sopra, che rappresentano dei casi particolari nei quali il test non può essere applicato (Figura 3.5):

Figura 3.5: In Figura: Neighbor test in M per il nodo A, per i casi in cui la proprietà equiangolare non è applicabile poiché non è possibile definire un quadrilatero convesso dei nodi M , A, CWA(M ), CCWA(M ). La figura presenta scenari in cui A è aggiunto come

vicino di Delaunay di M . Le linee solide rappresentano i vicini correnti di M , mentre le linee tratteggiate cono utilizzate per indicare il quadrilatero.

• Se N , X e B stanno sulla stessa linea, e B è vicino di X, N passa il test se è più vicino a X piuttosto che a B.

• Se il quadrilatero formato da N , CW_X(N ), CCWX(N ) e X è concavo o è un triangolo,

N passa il test.

Tipi di nodi della rete

I nodi della rete possono essere di due tipi:

• i nodi LEADER, cioè nodi che hanno coordinate maggiori tra le coordinate di tutti i loro vicini conosciuti

• i nodi NON LEADER, cioè tutti gli altri nodi

Inoltre, i nodi possono assumere lo stato di Candidate Neighbors di altri nodi. Segue la definizione di candidate neighbors.

Definizione 3.11 (Candidate Neighbor). Un nodo N è detto Candidate Neighbor di un nodo X se N non è nella tabella dei vicini di X e N è il neighbor test per N effettuato da X è verificato.

Ancora, i nodi possono essere stabili o non stabili. Un nodo N è stabile se nella sua tabella dei vicini ogni CW neighbor e CCW neighbor compare anche nella colonna dei vicini, altrimenti è detto non stabile.

Messaggi

In questa sezione sono definiti alcuni tipi di messaggi che garantiscono la correttezza dell’al- goritmo. Alcuni di questi sono inviati tra nodi della rete, altri invece vengono inviati al server per notificare a questo la presenza di un determinato nodo nella rete o per effettuare la join del nodo. Distinguiamo i seguenti messaggi:

• i messaggi di HelloNeighbor e HelloNotNeighbor. Il primo viene inviato da ogni nodo, allo scadere del proprio Heartbeat, a tutti i nodi nella propria tabella dei vicini, e ai nodi candidate neighbors di cui si è venuti a conoscenza. Il messaggio di HelloNotNeighbor può essere inviato per tre motivi:

– per fare aggiornare la tabella dei vicini del ricevente.

– per dare qualche informazione in più al ricevente sul proprio vicinato, poiché tale messaggio contiene informazioni sui CW e CCW neighbors.

– per risolvere problemi dovuti al fatto che più nodi hanno lo stesso indirizzo logico (cosa possibile poiché gli indirizzi logici vengono assegnati in fase di configurazio- ne).

• il messaggio di Goodbye viene inviato da un nodo N nel momento in cui sta per effettuare la Leave. Dal momento in cui N invia tale messaggio, risponderà fino alla sua uscita con tale messaggio ad ogni nuovo messaggio che gli si presenta.

• il messaggio di NewNode, che viene inviato da un nodo N a un nodo X che, in fase di join, è appena venuto a conoscenza di quest’ultimo già presente nella rete. Questo messaggio può essere inviato da X già presente nella rete a un nodo più vicino di se stesso all’originario mittente del messaggio nel caso in cui N fallisca il neighbor test per X.

Algoritmo

L’algoritmo viene descritto in termini di due procedure differenti: una per la fase di Join e una per la fase di disconnessione volontaria dalla rete dei nodi.

La procedura di Join di un nodo n consiste nei seguenti punti:

• il nodo n, non ancora presente nella rete, contatta il server inviando un messaggio di ServerRequest, con lo scopo di venire a conoscenza di un nodo già presente nella rete. Il server cerca nella sua cache list, che contiene un insieme di nodi conosciuti, e risponde a n con un messaggio ServerResponse contenente un nodo x scelto casualmente nella sua cache list;

• il nodo n invia un messaggio NewNode al nodo x;

• il nodo x effettua il neighbor test per n. Se fallisce, inoltra il messaggio NewNode al prossimo nodo nella sua tabella dei vicini che sa essere più vicino a n, altrimenti invia un messaggio di HelloNeighbor a n. Tale messaggio conterrà i nodi CCW_x(n) e CWx(n);

• il nodo n riceve il messaggio di HelloNeighbor da parte di x, venendo a conoscenza di due nuovi elementi che saranno candidati a essere vicini (candidate neighbors). Quindi, allo scadere del timer HeartBeart, n invia messaggi di HelloNeighbor a tutti i suoi vicini, per notificare loro che è ancora attivo nella rete, e al più vicino dei suoi candidate neighbors. I vicini e il candidate neighbor effettueranno quindi il neighbor test e risponderanno a n con un nuovo messaggio HelloNeighbor, il quale può contenere nuovi probabili candidate neighbors per n.

• se N non ha più candidate neighbors, il suo inserimento nella rete è terminato. Co- munque, allo scadere dell’Heartbeat, n continua a inviare messaggi di HelloN eighbor a tutti i suoi vicini.

• n vuole uscire dalla rete, quindi invia messaggi di Goodbye a tutti i suoi vicini e al server. Da quel momento, n risponderà con messaggi di Goodbye a tutte le richieste che gli arriveranno.

• il server riceve il messaggio Goodbye, quindi rimuove n dalla sua cache.

• i vicini di n ricevono il messaggio Goodbye, quindi rimuovono n dalla loro tabella dei vicini. Comunque, n potrebbe essere stato salvato come CounterClockwise neighbor o come Clockwise neighbor di qualche nodo. Per definizione, n adesso è un candidate neighbor dei propri vicini, quindi allo scadere del loro Heartbeat essi invieranno mes- saggi di HelloNeighbor a n. Inoltre, essi inviano messaggi di helloNeighbor a tutti i loro vicini, in modo da aggiornare i CounterClockwise neighbors e i Clockwise neighbors di tutti i nodi della rete. (Non contengono più N poiché N è declassato a candidate neighbor).

• n riceve messaggi di HelloNeighbor dagli ex-vicini, quindi risponde loro con messaggi di Goodbye.

• la rete si auto-ripara grazie a messaggi di HelloNeighbor inviati da tutti i nodi allo scadere dei loro Heathbeat.