Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Stefano Russo » 21.Sistemi distribuiti peer-to-peer - Parte seconda


Chord

Si basa su un overlay ad anello con N=2m GUID.

Il nodo responsabile di una determinata chiave K è quello con il primo identificativo W tale che W succede K in senso orario.

Ogni nodo x in Chord mantiene informazioni su:

gli  m  successori più  il predecessore

  • predecessore
    • per robustezza (v. stabilize)
  • fingers: un insieme di m nodi distanziati esponenzialmente dal nodo x, vale a dire l’insieme dei nodi che si trovano a distanza 2da x, con 0 ≤ i≤ m-1
    • per lookup e stabilizzazione

Chord


Chord


Chord


Chord

La correttezza di Chord si basa sul presupposto che ogni peer conosca esattamente i successori e i finger.
Tale requisito può essere compromesso dalla dinamicità dei peer.
Per mantenere la correttezza dei dati di routing sono eseguiti periodicamente appositi algoritmi di stabilizzazione.


Chord

Ogni nodo conserva informazioni su (m+1) nodi (→ O(log N)).
L’operazione di lookup richiede m messaggi (→ O(log N)).
In caso di connessione alla rete o abbandono della rete il numero di messaggi è Ω(log2N).

Pastry

Anche Pastry usa un overlay ad anello.
Ad ogni nodo è assegnato un GUID a 128-bit, ottenuto applicando una funzione hash alla chiave pubblica.
Ad ogni file è assegnato un GUID a 128-bit, ottenuto applicando una funzione hash al nome del file stesso.
I GUID sono distribuiti in maniera random tra 0 e 2128-1.

Pastry

Per determinare i nodi vicini, Pastry utilizza delle metriche di località (hop count o round-trip latency).
Sfrutta la vicinanza numerica dei nodi.
Ogni query di un dato con chiave k viene istradata verso il nodo vicino il cui GUID è numericamente più vicino a k.


Pastry

Ogni nodo dispone delle seguenti strutture.

  • Leaf Set (L), contiene informazioni dei peer più vicini, l con GUID più piccolo e l con GUID più grande. Se si utilizzasse solo tale struttura per fare instradamento si avrebbe una complessità O(N).
  • Routing Table (R), strutturata ad albero, contiene GUID e indirizzi IP di alcuni dei 2128 peer, con densità maggiore per i vicini. La tabella ha 32 righe (cifre esadecimali in 128 bit), ciascuna con 15 entry (possibili valori di ciascuna cifra eccetto quella del GUID locale).

Pastry

Algoritmo di routing eseguito dal nodo A per il messaggio M destinato al nodo D

Algoritmo di routing eseguito dal nodo A per il messaggio M destinato al nodo D


Pastry


Pastry

Pastry utilizza un meccanismo di heartbeat per rilevare i fallimenti e, quindi, riparare i leaf set.
Periodicamente i peer scambiano messaggi di PING, il peer che non risponde entro un certo timeout è considerato fallito.
Il nodo che ha scoperto il fallimento, contatta il peer numericamente successivo a quello fallito, chiedendo una copia del suo leaf set.
Il leaf set ricevuto avrà delle sovrapposizioni con quello in possesso dal peer che ha iniziato la procedura, ma anche validi peer per sostituire quello fallito.
I peer vicini sono informati del fallimento e eseguono la stessa procedura.

Pastry

Mediamente, la tabella di routing di ciascun nodo ha log16N righe; inoltre c’è il leaf set (16•log16N+L → O(log N)).
L’operazione di lookup richiede O(log N) messaggi.
In caso di connessione alla rete o abbandono della rete il numero di messaggi è O(log N).

Confronto DHT


Freenet

Freenet migliora le prestazioni del flooding strutturando scarsamente l’overlay network:

  • ogni dato è identificato da una chiave
  • dati con chiavi simili tendono a raggrupparsi su un simile insieme di peer, così da ridurre i peer da visitare per il lookup.

Ogni nodo presenta due liste di chiavi:

  • quella dei propri dati
  • quella delle locazioni dei dati noti.

Freenet

Il peer A avvia il flooding di richieste per un dato detenuto da D.

Quando D riceve la richiesta, non contatta direttamente A, ma ripercorre al contrario il percorso di lookup.

Ogni nodo contattato memorizza nella seconda lista la chiave e il next_hop così da definire una scorciatoia (routing short-cut) per successive query dello stesso dato.


I materiali di supporto della lezione

S. Ratnasamy, S. Shenker, and I. Stoica. “Routing algorithms for DHTs: Some open questions”. In In 1st International Peer To Peer Systems Workshop (IPTPS02).

I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek, H. Balakrishnan, “Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications”. In IEEE/ACM Trans. on Networking, 2003.

www.napster.com

www.gnutella.com

www.gnutella2.com

www.openp2p.com

www.overnet.com

chord

shareaza

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion