Sistemi P2P avanzati Lezione 3 Chord seconda parte.

Sistemi P2P avanzati

Lezione 3

• Chord seconda parte


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.)


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)Giustificare la risposta

m=61

810

nodi

risorse

21

24

4851

5654

3838

42

2628


Outline

• Chord Riepilogo• Join and Stabilization, • Failure and Replication (Leave) • Valutazione• Osservazioni e Conclusioni


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)

• Costo lookup O(log N) msg (whp)

m=61

810

nodi

risorse

21

2430

32

4851

5654

3838

42

26


Join e StabilizationCrea Anello Vuoto

Join n=N26,

n’=qualunque nodo attivo

Stabilizen=N26n=N21


Join e Stabilization

• Altre operazioni periodiche ma utilizzate con frequenza minore sono fix.finger e check.predecessor


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).


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


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


Vale il seguente lemma:

Se al tempo t esiste una path tra x ed y, allora per ogni t’>t ci sara’ una path tra x ed yPer 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.

x p s y

n

Chord: Risultati Join


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.

x p s y

n



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



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.



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.



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.



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



• 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’



– 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)


Chord: Failure and ReplicationRisultati

• 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

DimAffinchè 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

Altamente improbabil

e


Chord: Failure and ReplicationRisultati

• 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 sketchSe 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).


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)


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


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.”


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


il costo è O(log N) come previsto dalla teoria

la costante è 1/2

Number of Nodes

Avera

ge M

ess

ag

es

per

Looku

p

Chord: Valutazione


Chord: Incorporating GeographyChord: 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);


Chord: Incorporating GeographyChord: 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);


Incorporating geography: Chord• Chord e PRS:

L’algoritmo di routing non va semplicemente al nodo più vicino alla destinazione sulla rete di overlay, ma ad esempio potrebbe considerare i due nodi più vicini e scegliere quello con RTT minore;Le path-lenght si allungano ma rimangono O(log N);

In particolare: ad ogni passo la distanza fra il nodo destinazione e il nodo corrente si riduce da a 3/4 Nel caso peggiore la path lenght è quindi log4/3 2m.

000

101

100

011

010

001

110

111 110


Incorporating geography: Chord• Chord e PNS:

La finger table viene riempita considerando anche il RTT:l’i-esimo finger del nodo n non è semplicemente il ‘‘responsabile’’ della chiave n+2i-1 ma è il nodo più vicino(RTT) fra i nodi ‘‘responsabili’’ delle chiavi nell’intervallo [n+2i-2, n+2i-1 ].

Anche in questo caso le path-lenght si allungano ma rimangono O(log n) (dimostrazione analoga alla precedente).Anche usando simultaneamente PRS e PNS la lunghezza asintotica delle path non varia;

000

101

100

011

010

001

110

111


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)


Fine Lezione 3

Sistemi P2P avanzati Lezione 3 Chord seconda parte.

Documents

Transcript of Sistemi P2P avanzati Lezione 3 Chord seconda parte.