Lezione 3
• Chord seconda parte
Sistemi P2P avanzati
Facciamo un piccolo test
• Quanti successori ha un ring nel protocollo Chord?
(m) (1) (log N) (nessun prec.)
• Considerate il protocollo Chord definito con (log
N) predecessori e 1 successore, dimostrare che il
protocollo è tollerante ai fallimenti
• Aumentando il numero di identificatori in un anello,
le performance del protocollo
(+) (-) (=) (nessun prec.)
Sistemi P2P avanzati
Lezione 3
• Dato l’anello in figura mostrare i passi della procedura lookup
da 56 a 38
• Mostrare la tabella dei finger del nodo 48
• Quanti messaggi impiega in genere la procedura lookup?
(2) (O(m)) (log N-1) (nessun prec)
m=6
nodi
Giustificare la risposta
1
8
risorse
56
54
51
48
21
42
Sistemi P2P avanzati
10
38
38
24
28 26
Outline
•
•
•
•
•
Chord Riepilogo
Join and Stabilization,
Failure and Replication (Leave)
Valutazione
Osservazioni e Conclusioni
Sistemi P2P avanzati
Chord: Ricapitolando
• Le chiavi sono mappate su un array circolare costituito da 2m
identificatori;
• Il nodo responsabile di una determinata chiave è il primo nodo che
la succede in senso orario;
• Ogni nodo n di Chord mantiene la connessione con r=log N
successori (successors) del nodo n più il predecessore
• Inoltre, ogni nodo conosce, al più, altri O(log N) w.h.p, nodi nel
sistema (fingers)
• In totale ogni nodo mantiene log N +1 + O(log N)=O(log N)
connessioni (whp)
nodi
1
• Costo lookup O(log N) msg (whp)
risorse
56
54
51
48
m=6
8
21
42
Sistemi P2P avanzati
10
38
38
24
26
32 30
Join e Stabilization
Crea Anello Vuoto
Join
n=N26,
n’=qualunque nodo attivo
Stabilize
n=N26
n=N21
Sistemi P2P avanzati
Join e Stabilization
• Altre operazioni periodiche ma utilizzate con
frequenza minore sono fix.finger e check.predecessor
Sistemi P2P avanzati
Chord: Join
• Abbiamo visto che la procedura join appena definita non
completa l’aggiornamento di tutti i link necessari.
• Al fine di aggiornare tutti i link del nodo sono necessari alcuni
runs di stabilize (che comprende inoltre la notify) e m (log N
whp) runs della procedura fix.finger (sia da parte del nodo che
ha effettuato la join sia da parte di altri nodi che devono
aggiornare uno dei finger al nuovo nodo)
– Chord non è simmetrico (Se un nodo n ha un finger su n’ non è detto
che n’ ha un finger su n)
• Non è possibile avvertire i nodi che devono aggiornare i fingers
• E’ inoltre necessario far migrare le risorse al nuovo
responsabile (il protocollo Chord non gestisce questo
problema e lo rimanda all’applicazione).
Sistemi P2P avanzati
Chord: Join
• La correttezza dei link al successore basta a
garantire la correttezza delle lookup
• Lazy Join
– Inizializza solo il successore
– Periodicamente verifica successore e predecessore
– Periodicamente (ma meno spesso) rinfresca il
contenuto della tavola dei finger
Sistemi P2P avanzati
Chord: Join e Lookup
• Cosa succede alla lookup a seguito di
operazioni di Join?
– L’operazione di Join è completamente terminata ->
nessun problema
– L’operazione di Join è parzialmente terminata -> la
lookup potrebbe essere rallentata
– L’operazione di Join è incompleta (puntatori errati
oppure le risorse si trovano in una posizione
inconsistente rispetto ai link nella rete) -> la
lookup potrebbe fallire
Sistemi P2P avanzati
Chord: Risultati Join
n
Vale il seguente lemma:
x
p
s
y
Se al tempo t esiste una path tra x ed y, allora per ogni
t’>t ci sara’ una path tra x ed y
Per induzione sul tempo.
Supponiamo che dopo t il nodo n effettua una join tra p e s due nodi nella
path da x a y. L’arco tra p ed s non viene toccato dalla join e quindi permane.
Supponiamo avvenga una stabilize.
Consideriamo il momento in cui il nodo p cambia successore (stabilize di p)
da s ad n. Questo avviene perchè p ha contattato s ed s gli ha detto di n.
Inoltre p<n<s.
Sistemi P2P avanzati
Chord: Risultati Join
n
x
p
s
y
s ha saputo di n ad un tempo precedente e questo può essere
avvenuto solo perchè s è stato un successore diretto di n (cioè
dopo la stabilize di n).
Per ipotesi induttiva se esisteva un path tra n ed s, esiste un path
tra n ed s in tutti gli istanti successivi.
In particolare nell’istante in cui p cambia il successore. Essendo
p<n<s il cambiamento del successore di p non influisce in alcun
modo sulla path tra p ed s.
Inoltre anche dopo il cambiamento esiste una path tra p ed s.
Sistemi P2P avanzati
Chord: Risultati Join
Tutti le path tra x ed y, che utilizzavano l’arco tra p ed s, erano
tali che p ed s erano interni ad x y. Ma tutti i nodi aggiunti
all’arco p s sono interni a p s ed a maggior ragione interni ad x
y.
Se un nodo è capace di risolvere una query, sarà sempre capace
di farlo in futuro
Ad un tempo prefissato dopo l’ultima join i puntatori al
successore saranno corretti per tutti i nodi
Sistemi P2P avanzati
Chord: Risultati Join
E’ possibile mostrare il seguente teorema:
Se ogni operazione di join è alternata con quella di
stabilizzazione, allora dopo un fissato tempo dall’ultima join i
puntatori al successore formano un ciclo su tutti i nodi della
rete.
Sistemi P2P avanzati
Chord: Risultati Join
E’ possibile mostrare il seguente teorema:
Se abbiamo una rete stabile con N nodi ed effettuiamo N join
alla rete, e se tutti i puntatori ai successori sono corretti, allora il
Lookup di una risorsa avrà necessità di O(log N) hops con alta
probabilità.
In altre parole se il tempo richiesto per aggiustare tutti i fingers è
minore del tempo richiesto dalla rete per raddoppiare in taglia
allora la lookup non viene asintoticamente rallentata.
Sistemi P2P avanzati
Chord: Risultati Join
Dim
Se utilizziamo i vecchi finger arriviamo in O(log N) hops al
vecchio predecessore della risorsa. Con alta probabilità tra due
vecchi nodi ci saranno al più O(log N) nuovi nodi.
Se i successori dei nuovi nodi sono corretti, in al più O(log N)
passi la risorsa sarà raggiunta.
Sistemi P2P avanzati
Chord: Failure and Replication
• Abbiamo detto che la correttezza del routing è garantita dal
fatto che ogni nodo conosce in ogni istante il proprio
successore
• Tuttavia questa invariante può essere compromessa dal fatto
che i nodi possono “cadere”
• Per migliorare la robustezza del protocollo ogni nodo utilizza
una lista di r successori (di solito r=log N)
• Quando il successore di un nodo n cade, n sostituisce tale
successore con la seconda entry nella tabella dei successori e
successivamente provvede a ricercare il successore r-esimo.
• In particolare, è possibile “rompere” il sistema solo se tutti e r i
successori di un nodo cadono quasi conteporaneamente
Sistemi P2P avanzati
Chord: Failure and Replication
• Assumiamo che r sia la probabilità che un nodo cade
all’istante t. La probabilità che r successori cadono
contemporaneamente è pr
• La presenza della tabella dei successori richiede
alcuni cambiamenti nel protocollo:
– La procedura stabilize si deve preoccupare di mantenere corretta la
tabella dei successori
• Il nodo n copia la tabella dei successori dal suo succesore s ignora
l’ultima entry e aggiunge in testa a tale tabella il proprio successore
s
• Quando qualche successore fallisce il nodo n contatta il primo
successore vivo s’ e successivamente ripristina la tabella dei
successori utilizzando la tabella di s’
Sistemi P2P avanzati
Chord: Failure and Replication
– E possibile inoltre modificare la procedura closest preceding
finger in modo da valutare oltre alla tabella dei fingers anche i
successori. (si ottengono miglioramenti ma il costo della
lookup rimane O(log N))
– Inoltre è necessario modificare la procedura lookup
(findsuccessor) che fallisce se incontra un successore down (la
procedura infatti viene rilanciata dopo un breve intervallo di
tempo, che dovrebbe servire a ripristinare il link al successore)
Sistemi P2P avanzati
Chord: Failure and Replication
Risultati
• Assumiamo che la lista dei successori è lunga
r=(log N)
• Teorema
– In una rete inizialmente stabile, se assumiamo che
ciascun nodo cade con probabilità ½, allora la lookup
sarà corretta
Dim
Affinchè la lookup sia corretta è necessario che l’anello
non sia rotto. L’anello si rompe con probabilità
(1/2)r=1/Nk se r= k log N
Sistemi P2P avanzati
Altamente
improbabil
Chord: Failure and Replication
Risultati
• Assumiamo che la lista dei successori è lunga
r=(log N)
• Teorema
– In una rete inizialmente stabile, se assumiamo che
ciascun nodo cade con probabilità ½, allora la lookup
impiega O(log N) msg
Dim sketch
Se ogni nodo è caduto con probabilità 1/2 , ogni due link ne
funziona almeno 1,
Se il finger di cui abbiamo necessità è caduto possiamo usare un
finger più corto: invece di dimezzare la distanza la riduciamo a
circa ¾ della distanza precedente. Ma log4/3 N = O(log N).
Sistemi P2P avanzati
Chord: Failure and Replication
• Consisten Hashing
– Il fatto che l’assegnazione degli ID avviene utilizzando consistent
hashing, non è possibile per un avversario creare dei nodi in una
posizione prefissata del ring.
• Non è possibile appropriarsi di una risorsa
• Non è possibile rompere l’anello utilizzando r nodi fittizi
• Siccome abbiamo visto che gli r successori di un nodo n cadono
contemporaneamente con bassissima probabilità è naturale pensare
a questi nodi per repliche delle risorse gestite dal nodo n.
– Altre possibilità
• Diverse funzioni hash
• Repliche in posizioni speculari (Es r repliche)
(ID, ID+2m/r mod 2m, ID+2 2m/r mod 2m, , ID+(r-1) 2m/r mod 2m)
Sistemi P2P avanzati
Chord: Leave
• Siccome il protocollo descritto finora è corretto anche in
caso di fallimenti per i nodi potremmo gestire la leave
come un fallimento, tuttavia è preferibile, per migliorare
le prestazioni del sistema, adottare alcuni accorgimenti,
quando un nodo si disconnette volontariamente dalla rete
– Il nodo che lascia la rete
• trasferisce le proprie risorse al suo successore
• Notifica ai propri vicini (predecessore e successore) che sta
uscendo dal sistema. In particolare comunica il predecessore
al suo successore e il successore al suo predecessore, in
questo modo i due vicini possono connettersi senza utilizzare
la stabilize/notify
Sistemi P2P avanzati
Chord: Realistic Analysis
• Il sistema appena descritto è un sistema dinamico
particolarmente difficile da analizzare analiticamente
(senza esemplificazioni). In particolare tutte le
dimostrazioni analizzate partono da una configurazione
stabile, tuttavia:
“a Chord ring will never be in a stable state;
instead, joins and departures will occur continuously,
interleaved with the stabilization algorithm. The ring
will not have time to stabilize before new changes
happen.”
Sistemi P2P avanzati
Chord: Valutazione
• lookup veloci in sistemi di grandi dimensioni
• Variazione contenuta del costo di lookup
• Robusto rispetto a molti fallimenti
• Gli esperimenti confermano i risultati teorici
Sistemi P2P avanzati
Chord: Valutazione
il costo è O(log N) come previsto dalla teoria
Average Messages per Lookup
la costante è 1/2
Sistemi P2P avanzati
Number of Nodes
Chord: Incorporating Geography
• Alcune tecniche:
– Geographic Layout: Usare un algoritmo per attribuire le
chiavi ai nodi in modo che nodi “fisicamente” vicini abbiano
identificatori simili. (Controindicazioni: Bilanciamento del
carico, Routing Hot Spots e Sicurezza);
– PNS(Proximity neighbor selection) La scelta dei vicini non
dipende solo dalla distanza fra i nodi sulla rete di overlay ma
è influenzata anche dalle distanze reali.
– PRS(Proximity routing selection) Durante la ricerca
l’algoritmo di routing non sceglie il successivo step basandosi
solo sulla distanza fra i nodi nella rete di overlay; considera
anche la distanza effettiva fra i nodi (in termini di RTT);
Sistemi P2P avanzati
Chord: Incorporating Geography
• Osservazioni:
– PRS e PNS sono i sistemi più usati,(sembra che PNS offre
prestazioni migliori di PRS);
– PRS e PNS partono dal presupposto che è possibile
conoscere il RTT con ogni altro nodo (non è fattibile, ma è
possibile ottenere delle stime a un costo relativamente basso);
Sistemi P2P avanzati
Incorporating geography: Chord
• Chord e PRS:
000
L’algoritmo di routing non va
semplicemente al nodo più vicino
111rete di110
alla destinazione sulla
overlay, ma
001ad esempio potrebbe
considerare i due nodi più vicini e scegliere quello con RTT
minore;
110
010
Le path-lenght si allungano ma rimangono O(log N);
101 passo la distanza
011
In particolare: ad ogni
fra il nodo destinazione
e il nodo corrente si riduce da
 a 3/4 
100
Nel caso peggiore la path lenght è quindi log4/3 2m.
Sistemi P2P avanzati
Incorporating geography: Chord
• Chord e PNS:
000
La finger table viene111
riempita considerando anche il RTT:
001
l’i-esimo finger del nodo n non è semplicemente il
‘‘responsabile’’ della chiave n+2i-1 ma è il nodo più
010chiavi
vicino(RTT) fra110
i nodi ‘‘responsabili’’ delle
nell’intervallo [n+2i-2, n+2i-1 ].
Anche in questo caso
le path-lenght si allungano ma rimangono
101
011
O(log n) (dimostrazione analoga alla precedente).
100
Anche usando simultaneamente PRS e PNS la lunghezza
asintotica delle path non varia;
Sistemi P2P avanzati
Conclusioni
• A differenza dei sistemi precedenti, Chord si adatta ad
ambienti dinamici (tipici dei sistemi P2P)
• Based on theoretical work (Consistent Hashing)
• Proximity-based routing
• Chord è uniforme (routing greedy è ottimale)
• Chord non è simmetrico
– Alcune procedure causano utilizzo di banda anche se non ci
sono cambiamenti nella rete
• La Join costa O(log2 N)
Sistemi P2P avanzati
Fine Lezione 3
Sistemi P2P avanzati