Sistemi Peer to Peer: Sistemi Chord

Localizzare un nodo, in una rete nel quale si è mappato un particolare dato,è diventato un problema d'interesse, nell'ambito dei SISTEMI DISTRIBUITI.
Questo problema, è diventato un caso di studio, dei SISTEMI CHORD: esso va a mappare la chiave di un dato all'interno di un nodo in modo che essi possano essere facilmente localizzati.
In particolare, i CHORD, sono SISTEMI PEER TO PEER DISTRIBUITI strutturati che gestiscono le entrate ed uscite dei nodi.
La caratteristica più importante dei SISTEMI CHORD è che sono costituiti dal CONSISTENT HASHING che va a garantire l'uniformità del sistema: i singoli nodi sono informati su tutti i nodi del sistema in modo tale da gestire l'entrata ed uscita dei nodi.
Quando un N-esimo nodo entra o esce dalla rete, solo una frazione O(1/N) di chiavi viene mossa in una diversa locazione, il che è necessario per mantenere un carico bilanciato.
Inoltre, in una rete di N-nodi, ogni nodo mantiene informazioni su circa O(logN)messaggi.
Queste informazioni, vengono date attraverso un'informazione di routing.
In particolare, l'identificativo di un nodo è scelto calcolando l'hash dell'indirizzo IP del nodo.
Il Consistent Hashing assegna le chiavi ai nodi, nel seguente modo: gli identificatori dei nodi sono ordinati in un modulo 2^m.
La chiave k, viene mappata nel nodo costituito dal più piccolo identificatore id>=k, diventando quindi il suo successore e denotato come successor(k).
La Figura mostra un   “identifier circle” con m=3. Il circle ha tre nodi: 0, 1, e 3. Il
successore dell’identificativo 1 è 1, così la chiave 1 dovrebbe essere allocata al nodo
1.
Similmente la chiave 2 dovrebbe essere allocata al nodo 3, e la chiave 6 al nodo 0.

All'interno di un SISTEMA CHORD, i nodi posso entrare o uscire dal sistema ad ogni momento.

Proprio per questo motivo, le FINGER TABLE devono essere corrette.

Per semplificare i meccanismi di entrata e 

uscita, ogni nodo in Chord mantiene un puntatore al predecessore. Il puntatore al 

predecessore di un nodo contiene il Chord identifier e l’indirizzo IP dell’immediato 

predecessore di tal nodo, e può essere usato per percorrere in senso antiorario l’ 

“identifier circle”.

In particolare, l'entrata di un nodo nell'anello si svolge in tre passi:

Join: operazione che si connette al nodo conosciuto ed invia la richiesta di find_successor a tale nodo, che, in modo del tutto simile a quello descritto al caso in cui si cerca la 

locazione  di  una  chiave,  trovando  il  predecessore  dell’identificativo  del  nodo 

specificato, restituisce se stesso e  il suo successore permettendo  così al nodo di 

settare il suo predecessore (il nodo stesso) e il suo successore. 

Aggiornamento:nella fase di aggiornamento il nodo deve permettere alle finger table degli altri nodi di aggiornarsi;

Trasferimento dati: il nodo si connette al suo succesore, il quale al momento attuale tiene la responsabilità di tutti i dati che devono essere spostati.

Il nodo invece lascia il sistema, attraverso l'operazione leave:le fasi sono le stesse utilizzate per gestire l'uscita di un nodo.

Il SISTEMA CHORD, è una struttura ad anello nel quale ogni nodo ha questa struttura:

-Successore: nodo responsabile della chiave che si è mappato in esso

-Predecessore: nodo che precede il nodo selezionato

-Finger Table: tabella di m elementi che servono per l'efficienza dell'algoritmo

-Vettor delle chiavi di cui il nodo è respondabile

Posted in: casi di successo, casi di successo > informatica, progetti > informatica