Proprietà di Pastry

Di seguito sono mostrate alcune proprietà importanti di Pastry.

Località

Qui consideriamo le proprietà di località di Pastry come la proprietà delle route di Pastry relativamente alla prossimità metrica. La prossimità metrica è un valore scalare che riflette la distanza tra una coppia di nodi, come per esempio il round trip time. Si assume che una funzione esiste e consente a ciascun nodo Pastry di calcolare la distanza tra se e un nodo con un certo indirizzo IP. Considereremo le due proprietà di località di Pastry più rilevanti per Scribe.

• Short Routes

Tale proprietà è relativa alla distanza totale, in termini metrica di prossi-mità, che i messaggi percorrono lungo una Pastry routes. Ricordiamo che ogni entry nella routing table di un nodo, è scelta in riferimento al nodo

più vicino. Come risultato si ha che ad ogni step il messaggio viene inviato al nodo più vicino con cui è condiviso il prefisso più lungo.

• Routes Convergence

La Route Convergence è la proprietà relativa alla distanza percorsa da due messaggi inviati alla stessa chiave prima che le loro route convergano. Le simulazioni dimostrano che la distanza media percorsa da ciascuno dei due messaggi, prima che le loro route convergano, è approssimativamente uguale alla distanza tra i loro rispettivi nodi sorgente. Questa proprietà ha un forte impatto sulle proprietà di località dell’albero di multicast di Scribe.

Ingresso, Fallimento e Recovery di un Nodo

Un elemento chiave in Pastry è il mantenimento dello stato del nodo in maniera efficiente e dinamica, per esempio la routing table e il leaf set, in presenza di fallimento di nodi, di recovery o dell’arrivo di nuovi nodi.

• Ingresso di un nuovo Nodo

Un nodo in arrivo con un nuovo nodeID X può inizializzare il suo stato contattando il vicino nodo A (secondo la metrica di prossimità) e chiedendo ad A di comunicare un messaggio specifico usando X come chiave. Questo messaggio è instradato al nodo esistente Z con nodeID numericamente più vicino ad X. X ottiene il leaf set da Z e la i-esima riga della routing table dell’iesimo nodo incontrato lungo il percorso da A a Z. Si può dimostrare che usando questa informazione, X può correttamente inizializzare il suo stato e notificare ai nodi interessati il suo arrivo.

• Fallimento di un Nodo

Per gestire il fallimento di un nodo, i nodi vicini nello spazio degli ID dei nodi, scambiano periodicamente messaggi di keep-alive. Se un nodo non risponde per un periodo T, si presume sia fallito. Tutti i membri del leaf set del nodo fallito, vengono poi informati del fallimento del nodo e aggiornano il proprio leaf set.

• Recovery di un Nodo

Un nodo che deve fare il recovery, contatta i nodi nel suo ultimo leaf set e ottiene i loro leaf sets attuali aggiornando il proprio leaf set e aggiorna i membri del suo nuovo leaf set della sua presenza. Le entries nelle routing table che si riferiscono a nodi falliti vengono opportunamente riparate.

Pastry API

Di seguito sono riportate le principali operazioni fornite da un sistema che im-plementa Pastry:

> nodeId=pastryInit(credentials)

Causa l’ingresso del nodo locale in una rete Pastry esistente o avvia un nuovo nodo e inizializza lo stato; ritorna il nodeID del nodo locale. il parametro Credential contiene le informazioni necessarie per autenticare il nodo locale e per aggiungere in modo sicuro un nuovo nodo alla rete Pastry.

Questa operazione fa si che un messaggio sia instradato nella rete pastry al nodo con nodeID numericamente più vicino alla chiave, fra tutti i nodi pastry funzionanti.

> send(msg,IP-addr)

Fa si che Pastry invii il messaggio al nodo con indirizzo IP specifico se quel nodo è funzionante. Il messaggio è ricevuto dal nodo destinatario attraverso il metodo deliver

I livelli applicativi al di sopra di Pastry devono esportare le seguenti operazioni:

> deliver(msg,key)

Questa operazione è chiamato da Pastry quando un messaggio è ricevuto e il nodeID del nodo locale è numericamente più vicino alla chiave fra tutti i nodi funzionati.

> forward(msg,key,nextID)

Tale operazione è chiamata da Pastry appena prima che un messaggio sia inoltrato al nodo con nodeID uguale a nextID. Se nextID è pari a null allora il messaggio è destinato al nodo locale.

> newLeafs(leafSet)

Pastry chiama questa operazione ogni qualvolta si verifica un cambiamento nel leaf set.

3.3 SCRIBE

Scribe[4] è un’infrastruttura multicast a livello applicativo costruita su Pastry. Ogni nodo Scribe può creare un gruppo; altri nodi possono unirsi al gruppo, o inviare messaggi in multicast a tutti i membri del gruppo. Scribe fornisce con-segna dei messaggi in modo best-effort e non garantisce un ordine specifico di consegna. In ogni caso garantisce una forte affidabilità nella consegna e nell’ordi-ne di consegna dei messaggi ai membri del gruppo. I nodi possono creare, inviare messaggi e unirsi a molti gruppi. I gruppi possono avere più sorgenti di messaggi in multicast e un numero ampio di membri. Scribe può supportare molti gruppi simultaneamente, ciascuno con molti membri, e un alto tasso di turn-over dei membri.

Scribe API

Scribe offre alle applicazioni delle API molto semplici: > create(credentials,groupId)

Crea un gruppo con groupId, le credenziali sono usate per controllare l’accesso.

> join(credentials,groupId,messageHandler)

Serve al nodo locale per aggiungersi al gruppo con id uguale a groupId. Tutti i messaggi ricevuti in seguito per quel gruppo vengono passati al messageHandler specificato.

Permette ad un nodo locale di lasciare un gruppo con id pari a groupId > multicast(credential,groupId,msg)

Con questa operazione un messaggio viene inviato in multicast nel gruppo con id uguale a groupId

Scribe usa Pastry per gestire la creazione e l’ingresso nei gruppi e per costruire un albero di multicast usato per la disseminazione di messaggi nel gruppo. Pastry e Scribe sono completamente decentralizzati: tutte le decisioni si basano su informazioni locali e ogni nodo ha capacità identiche. Ogni nodo può agire come sorgente multicast, come radice o nodo generico di un albero di multicast, come membro del gruppo o come combinazione delle precedenti situazioni. Gran parte della scalabilità e affidabilità sia di Scribe che di Pastry deriva dal modello peer-to-peer.