Recent Changes - Search:
Labsoftel /

TesinaKad

Principi di funzionamento della rete KAD

Protocollo KADEMLIA

Salve a tutti!! Questa è una breve presentazione della topologia e della metrica usata dalla rete Kad, che si basa sul protocollo di Kademlia.. Buona lettura..Ivan

1 - Generalità

Kademlia è un protocollo di rete per reti peer-to-peer ideato da Petar Maymounkov e David Mazières della New York University. Specifica la struttura della rete, regola la comunicazione tra i nodi ed il modo in cui lo scambio di informazioni deve essere effettuato. I nodi Kademlia comunicano tra loro utilizzando il protocollo di trasporto UDP. Kademlia si basa sulla tecnologia a tabelle di hash distribuite (in inglese distributed hash tables, indicate anche come DHTs). Queste sono una classe di sistemi distribuiti decentralizzati che partizionano l’appartenenza di un set di chiavi tra i nodi partecipanti, e possono inoltrare in maniera efficiente i messaggi all’unico proprietario di una determinata chiave.

2 - DHT

Le DHT sono tipicamente progettate per gestire un vasto numero di nodi, anche nei casi in cui ci siano continui ingressi o improvvisi guasti di alcuni di essi. Questo tipo di infrastruttura può essere utilizzata per implementare servizi complessi appunto come sistemi peer-to-peer di file sharing. Originariamente la ricerca sulle DHT fu in parte motivata da sistemi peer-to-peer quali Napster, Gnutella e Freenet, che si basavano su risorse distribuite in Internet per offrire l’applicazione desiderata. Questi sistemi differivano tra loro in come essi trovavano i dati contenuti dai rispettivi peers . Napster aveva un indice in un server centralizzato: ogni nodo, al suo ingresso, mandava una lista dei files che possedeva localmente al server, il quale si sarebbe occupato di effettuare le ricerche ed indicare ai richiedenti i nodi che conservavano i dati desiderati. Questa componente centralizzata rendeva il sistema vulnerabile ad attacchi. Gnutella e reti simili si spostarono verso un modello che prevedeva il flooding : ciascuna ricerca era di fatto costituita in un messaggio che veniva trasmesso a tutte le altre macchine della rete. Sebbene questo metodo evitasse la possibilità di un singolo punto di rottura, il meccanismo risultava assai meno efficiente rispetto a Napster. Infine ci fu Freenet che prevedeva un meccanismo completamente distribuito, ma impiegando un indirizzamento euristico basato sulle chiavi nel quale ciascun file era associato ad una chiave, e files con chiavi simili tendevano a raggrupparsi in set di nodi simili tra loro. Risultava pertanto verosimile che le richieste venissero inoltrate attraverso la rete in direzione di questi set di nodi senza dover visitare molti peers. Tuttavia, Freenet non offriva la certezza di trovare i dati richiesti. Le tabelle di hash distribuite utilizzano un tipo di routing basato sulle chiavi maggiormente strutturato al fine di ottenere sia la decentralizzazione di Gnutella e Freenet, sia l’efficienza e l’affidabilità nelle ricerche offerte da Napster. Un aspetto negativo è che, come in Freenet, le DHT offrono una ricerca solo per titoli esatti e non su parole chiave, sebbene questo tipo di funzionalità possa essere inserita in uno strato superiore della DHT. Le prime quattro DHT – CAN (Content Addressable Network), Chord, Pastry e Tapestry – vennero presentate tutte nello stesso periodo, nel 2001. Da allora, questo settore di ricerca è abbastanza attivo. Al di là degli studi accademici, la tecnologia DHT è stata adottata come un componente di BitTorrent, eMule etc.. Le caratteristiche delle DHT enfatizzano le seguenti proprietà:

  • Decentralizzazione: i nodi formano collettivamente il sistema senza alcun coordinamento centrale.
  • Scalabilità: il sistema è predisposto per un funzionamento efficiente anche con centinaia di milioni di nodi.
  • Tolleranza ai guasti: il sistema dovrebbe risultare affidabile anche in presenza di nodi che entrano, escono dalla rete o sono soggetti a malfunzionamenti con elevata frequenza.

La tecnica chiave utilizzata per raggiungere questi scopi è costituita dal fatto che ciascun nodo ha bisogno di rimanere in contatto solo con un piccolo numero di altri nodi della rete, in questa maniera la rete è sottoposta ad una minima quantità di lavoro per ogni modifica che avviene nel set di nodi che la costituiscono. Alcune strutture di DHT cercano di implementare meccanismi di sicurezza per contrastare nodi partecipanti malevoli e consentire ai nodi di rimanere anonimi, sebbene ciò sia meno comune rispetto agli altri sistemi peer-to-peer (specialmente per quanto riguarda il file sharing). Una DHT è costruita attorno ad un keyspace astratto, come un set di stringhe di 160-bit. L’appartenenza al keyspace è divisa tra i nodi partecipanti in base ad un ben definito schema per il partizionamento. L’overlay network connette i nodi, consentendo loro di trovare il proprietario di una determinata chiave nel keyspace. Con queste posizioni, il tipico funzionamento di una DHT per immagazzinare e poi recuperare un dato potrebbe avvenire nel seguente modo. Si supponga che il keyspace sia un set di stringhe di 160-bit. Per immagazzinare nella DHT un file caratterizzato dai parametri filename e data, viene inizialmente calcolato l’SHA1 hash del filename, producendo così una chiave k di 160-bit. In seguito, un messaggio put(k,data) può essere inviato ad un qualsiasi nodo della rete DHT. Il messaggio è inoltrato di nodo in nodo attraverso l’overlay network fino a che esso non raggiunge il singolo nodo che è responsabile per la chiave k in accordo alle regole per il partizionamento del keyspace,in quel nodo la coppia (k,data) sarà immagazzinata. Qualsiasi altro client può quindi successivamente recuperare i contenuti del file calcolando a sua volta l’hash del filename per ottenere k e chiedere ad un qualsiasi nodo della rete DHT di trovare il dato associato a k tramite un messaggio get(k). Il messaggio verrà quindi inoltrato attraverso l’overlay verso il nodo responsabile per k, che risponderà con una copia del dato immagazzinato.

2.1 - Partizionamento del Keyspace

Molte DHT usano alcune varianti del consistent hashing per mappare le chiavi ai nodi. Questa tecnica impiega una funzione δ(k1,k2) che definisce la nozione astratta di distanza tra la chiave k1 e la chiave k2 . A ciascun nodo è assegnata una chiave che è detta identificativo (ID). Ad un nodo con ID i appartengono tutte le chiavi per cui i è l’ID più vicino, misurando in base a δ. Ad esempio l’algoritmo Chord considera le chiavi come punti su una circonferenza, e δ(k1,k2) è la distanza percorsa (in senso orario) sul cerchio tra k1 e k2. Perciò, il keyspace circolare è diviso in segmenti contigui i cui punti terminali sono gli identificativi di nodo. Se i1 e i2 sono due IDs adiacenti, allora il nodo con ID i2 è proprietario di tutte le chiavi che cadono tra i1 e i2.

2.1.1 - Hash table e Consistent hashing

Il primo passo per realizzare algoritmi di ricerca tramite hashing è quello di determinare la funzione di hash: il dato da indicizzare viene trasformato da un'apposita funzione di hash in un intero compreso tra 0 ed n-1 che viene utilizzato come indice in un array di lunghezza n. Idealmente, chiavi diverse dovrebbero essere trasformate in indirizzi differenti, ma poiché non esiste la funzione di hash perfetta, è possibile che due o più chiavi diverse siano convertite nello stesso indirizzo. Il caso in cui la funzione hash applicata a due chiavi diverse genera un medesimo indirizzo viene chiamato collisione e può essere gestito in vari modi. La scelta di una buona funzione di hash è indispensabile per ridurre al minimo le collisioni e garantire prestazioni sempre ottimali. Il risultato migliore si ha con funzioni pseudo-casuali che distribuiscono i dati in input in modo uniforme. Molto spesso però, una buona funzione di hash non può bastare, infatti le prestazioni di una hash table sono fortemente legate anche al cosiddetto fattore di carico (load factor) calcolato come Celle libere/Elementi presenti e che ci dice quanta probabilità ha un nuovo elemento di collidere con uno già presente nella tabella. Questa probabilità, in realtà, è più alta di quanto si possa pensare, è bene dunque mantenere il load factor il più basso possibile (di solito un valore di 0.75 è quello ottimale) per ridurre al minimo il numero di collisioni. Questo può essere fatto, ad esempio, ridimensionando l'array ogni volta che si supera il load factor desiderato.
Il consistent hashing ha la caratteristica fondamentale che la rimozione o l’addizione di un nodo modifica solo il set di chiavi posseduti dai nodi con IDs adiacenti, senza coinvolgere tutti gli altri nodi. Tutto ciò al contrario di una tradizionale, nella quale l’addizione o la rimozione di un bucket causa un rimappaggio di quasi tutto l’intero keyspace. Dal momento che ogni modifica nel set di chiavi di cui un nodo è responsabile corrisponde tipicamente ad un intenso (per quanto riguarda la larghezza di banda) movimento da un nodo all’altro di oggetti immagazzinati nella DHT, una minimizzazione di questi movimenti di riorganizzazione è necessaria al fine di far fronte in maniera efficiente a nodi che hanno un comportamento molto dinamico (elevato numero di ingressi, uscite o malfunzionamenti).

2.2 - Overlay network

Ciascun nodo mantiene un set di links agli altri nodi (i suoi vicini). Tutti insieme questi nodi formano l’overlay network, e vengono organizzati in modo strutturato, dando così forma alla topologia della rete. Tutte le topologie di DHT condividono qualche variante della proprietà più essenziale: per ciascuna chiave k, o il nodo possiede k oppure ha un collegamento ad un nodo che è più vicino a k in termini di distanza nel keyspace, come definito precedentemente. A questo punto risulta quindi facile inoltrare un messaggio al proprietario di una qualsiasi chiave k utilizzando il seguente algoritmo greedy: ad ogni passo successivo, inoltra il messaggio al vicino il cui ID è più vicino a k. Quando non esiste un vicino con queste caratteristiche, allora si è giunti al nodo effettivamente più vicino, il quale deve essere il proprietario di k in accordo con quanto definito sopra. Questo tipo di routing viene talvolta definito come key based routing.

3 - Parametri

La rete Kademlia è caratterizzata da tre costanti chiamate alpha, B e K. La prima e l’ultima sono termini standard mentre la seconda si introduce perché alcune implementazioni di Kademlia usano lunghezze diverse per le chiavi.

  • Alpha è un numero piccolo che rappresenta il grado di parallelismo nelle chiamate di rete, tipicamente vale 3.
  • B è la dimensione in bits delle chiavi usate per identificare i nodi, memorizzare e restituire i dati; in Kademlia di base vale 160.
  • K è il massimo numero di contatti memorizzati nel bucket, normalmente è pari a 20.

Conviene comunque introdurre alcune altre costanti anche se non si trovano nelle pubblicazioni originali di Kademlia quali:

  • tExpire = 86400 s, il tempo dopo il quale la coppia chiave/valore muore, è il time-to-live (TTL) della data di pubblicazione originale.
  • tRefresh = 3600 s, tempo dopo il quale il bucket deve essere aggiornato.

Kademlia ha un numero di caratteristiche eccellenti che non veniva offerto simultaneamente da nessun altro sistema peer-to-peer precedente. Minimizza il numero di nodi di comunicazioni, le informazioni di configurazione si trasmettono automaticamente come un effetto collaterale della lettura delle chiavi. I nodi hanno abbastanza conoscenza e la flessibilità per indirizzare domande attraverso percorsi di basso-latenza. Kademlia usa consultazioni parallele, asincrone per evitare ritardi dovuti alla fine del tempo disponibile da nodi mal funzionanti. L'algoritmo col quale i nodi registrano l’esistenza l'uno dell'altro resiste agli attacchi DoS.

3.1 - DoS

E’ la sigla di denial of service, letteralmente negazione del servizio. In questo tipo di attacco si cerca di portare il funzionamento di un sistema informatico che fornisce un servizio, ad esempio un sito web, al limite delle prestazioni, lavorando su uno dei parametri d'ingresso, fino a renderlo non più in grado di erogare il servizio. Gli attacchi vengono abitualmente attuati inviando molti pacchetti di richieste, di solito ad un server Web, FTP o di posta elettronica saturandone le risorse e rendendo tale sistema "instabile", quindi qualsiasi sistema collegato ad Internet e che fornisca servizi di rete basati sul TCP è soggetto al rischio di attacchi DoS.

3.2 - Metrica XOR

Kademlia usa gli approcci di base di molti sistemi peer-to-peer, le chiavi opache sono formate da 160 bits e ogni computer che partecipa ha un NodeIDs nel keyspace. La coppia chiave/valore è immagazzinata nei nodi con IDs “vicino” alla chiave tramite nozioni di ristrettezza. Alla fine l’algoritmo di instradamento basato su NodeIDs lascia localizzare qualunque server vicino alla chiave di destinazione. Molti risultati ottimali di Kademlia vengono dall’utilizzo della metrica XOR per il calcolo della distanza tra i punti del keyspace. Lo XOR è simmetrico e permette ai partecipanti di Kademlia di ricevere interrogazioni dalle stesse distribuzioni di nodi contenute nelle loro tabelle di instradamento . Senza questa proprietà sistemi come Chord non riescono ad immagazzinare utili informazioni di instradamento dalle interrogazioni che ricevono. Peggio ancora,a causa dell’asimmetria della metrica di Chord, le sue tabelle di instradamento sono rigide. Ogni nuovo nodo inserito nelle tabelle di Chord deve conoscere, immagazzinare il nodo dell’intervallo precedente nello spaceID. Ogni nodo sarà più grande delle chiavi nell’intervallo, e anche molto lontano da esse. Kademlia, al contrario, può spedire delle richieste a qualsiasi nodo nell’intervallo, permettendo a questi di scegliere dei percorsi di instradamento basandosi sull’invio parallelo asincrono. Per localizzare nodi vicini ad un particolare ID, Kademlia usa un solo algoritmo dall’inizio alla fine. Al contrario, altri sistemi usano un algoritmo per portarsi vicino agli ID dell’obbiettivo e un algoritmo per l’ultima fase. Dei sistemi esistenti l’algoritmo di Kademlia assomiglia molto a quello utilizzato nella prima fase da Pastry che cerca i nodi lontani con una tecnica molto simile alla metrica XOR. Nella seconda fase, comunque, Pastry cambia la distanza metrica con la differenza numerica che però causa discontinuità e un calo delle prestazioni. I NodeIDs sono costruito come in Chord, ma per semplificare presumiamo che il computer scelga un casuale ID di 160bits quando si sta inserendo nel sistema. Ogni comunicazione che un nodo emette include il suo nodo ID, permettendo al destinatario di registrare l'esistenza del mittente se necessario. Kademlia conta su una nozione di distanza tra due identificatori per pubblicare e trovare la coppia <chiave\valore>. Dati due identificatori di 160bits, x e y, Kademlia definisce la distanza tra loro come il loro or esclusivo o (XOR) interpretato come un numero intero: d (x; y) = x xor y. Per prima cosa notiamo che XOR è una metrica valida benché non sia Euclidea. E’ ovvio che d(x; x) = 0, d(x; y) > 0 se x ≠ y, e che ∀ x,y : d(x; y) = d(y; x). XOR ha anche una proprietà triangolare importante:

  • d(x; y) + d(y; z) ≥ d(x; z)
  • d(x; y)  d(y; z) = d(x; z)

e si ha anche:

∀a ≥ 0, b ≥ 0 : a + b ≥ a xor b.

Come la metrica circolare destrorsa di Chord, XOR è unidirezionale: per ogni dato punto x e una distanza ∆ > 0, esiste esattamente un punto y tale che d(x,y)= ∆. ∀ 0 ≤ i < 160, ogni nodo tiene una lista con la tripletta <indirizzo IP; porta UDP; NodeIDs> dei nodi ad una distanza compresa tra 2i e 2i+1 da lui. Questa lista viene chiamata k-bucket. Ogni k-bucket è ordinato in modo da avere il nodo visto meno di recente in testa e quello visto più di recente in coda . Per bassi valori di i i k-bucket sono generalmente vuoti, mentre per grandi valori di i le liste cominciano ad avvicinarsi all’ordine di grandezza di k. All'interno di questo metodo, le differenze in distanza tra bit posti in posizione più alta saranno più grandi rispetto a quelle di bit posti in posizioni più bassa.

Il nodo S calcola le distanze tra se e altri quattro bits in uno spazio a 4 bits. Si vede chiaramente che gli oggetti che stanno nello stesso sottoalbero sono più vicini rispetto ad altri oggetti posizionati su sottoalberi diversi. L'albero binario è una rappresentazione semplificata di una routing table calcolata con la metrica XOR. In figura il nodo iniziale S calcola la sua distanza con la metrica XOR con i nodi 1, 2, 3 e 4. Di conseguenza il nodo 3 è il più vicino al nodo S con un XOR pari a 1.

4 - Tabelle di instradamento

La tabella d’instradamento organizza i contatti di un nodo in diversi k-bucket. A loro volta questi k-bucket sono divisi in zone d’instradamento che sono i nodi dell’albero. Ogni k-bucket rappresenta un sotto albero e ha k contatti rappresentativi.

4.1 - Contatti

Ogni nodo ha una lista di nodi conosciuti, chiamati contatti. Il numero massimo di contatti di un nodo è limitato ad una variabile pari a 5000. Ogni nodo ha una data di creazione e una data di scadenza, che contribuisce ad eliminare un nodo che non risponde. Inoltre ha anche le variabili Type e Type Last Set che sono responsabili del grado di disponibilità nel tempo. La variabile inUse indica quante azioni correnti sta svolgendo quel contatto. Ciò impedisce di annullare un contatto, quando è inclusa in essa un processo di lookup. La variabile Type ha una scala da 0 a 4, dove lo 0 è il parametro migliore e significa che il client ha un ottima disponibilità nel tempo. Al contrario il parametro 4 significa che questo client è collegato raramente e probabilmente sarà eliminato all'occasione seguente.

Quando un nuovo nodo è creato la variabile Type è inizializzata a 3. In seguito, quando il client riceve un segno dal contatto passa a 2 altrimenti gli verrà assegnato a 4. Per esempio quando un client riceve un messaggio da un contatto che è già presente per più di due ore nella relativa tabella di routing, il contatto otterrà il tipo 0. I client sono conservati nel file nodes.dat, che può essere letto dalla maggior parte dei clienti di Kademlia come eDonkey, eMule e aMule(all-platforms eMule). Normalmente non ci dovrebbe essere un cliente con il tipo 4 nel file,ma comunque se ce n’è uno, sarà ignorato dalla lettura della lista del contatto.

4.2 - Struttura

La tabella di instradamento di Kademlia è un albero binario corretto, cioè o ha due figli o nessuno. Ma non è un albero binario perfetto cioè non tutte le foglie hanno la stessa profondità. Grazie a questa proprietà la routing table ha bisogno di conoscere solo un piccolo sottoinsieme di nodi nella rete.

All’inizio il Kad calcola la distanza XOR con i propri clientID. Di conseguenza la distanza tra il nodo e se stesso è pari a 0 mentre con gli altri è un numero di 128 bits. La tabella di instradamento reale del protocollo Kad quando è completa è come quella mostrata nella figura sottostante, il che vuol dire che contiene circa 6360 contatti. Ma in realtà non è possibile raggiungere un numero tale, perché questo vorrebbe dire avere 2128 nodi con un unico hash ID.

Kad divide la struttura della tabella in livelli e posizioni. I livelli indicano gli strati che cominciano dalla radice, che ha livello zero. Di conseguenza, un Kad-Space a 128 bits ha massimo 128 livelli. La posizione indica il numero di nodi presenti in un livello che comincia dal nodo zero. Quindi il livello quattro ha nodi che vanno dalla posizione 0 fino alla 15. I livelli più alti sono limitati da 0 fino a 9. La tavola di instradamento completa attraversa 128 livelli.

Nel livello 4 la zona che va dalla posizione 5 alla 15 rappresenta il k-bucket mentre la zona che va da 0 a 4 continua con un altro sottoalbero. Dal livello 5, compreso, in poi le posizioni di ognuno dei livelli seguenti è limitato massimo a 10. Questo fa pesare l'albero più al lato del proprietario del nodo che ha una distanza XOR 0 rispetto a lui.

Il numero massimo di contatti possibili organizzati nella tabella di routing sono calcolati nel seguente modo:

  • Contatti totali = (foglie di livello 4 + foglie con livelli che vanno da 5 a 127 + foglie di livello 128) * K
  • Contatti totali = (11 + 123*5 + 10) * 10 = 6360

Quindi il massimo numero di contatti nella routing table è 636 che poi moltiplicato per k = 10 mi da 6360.

4.3 - Inserimento di un nodo

Per inserire un contatto nuovo, il cliente scorre la tabella di instradamento secondo la distanza del contatto. Perciò cerca l’n-esima posizione del numero a 128 bit, dove n è il livello corrente della zona di instradamento. Se il valore è zero esso continuerà nel figlio corretto che contiene i contatti più vicini. Quando copro la distanza con una foglia, ci sono due possibilità; o la foglia, che è una k-bucket, contiene meno di k contatti ed il nodo nuovo è inserito in questo bucket. Altrimenti, quando il bucket è pieno (ha gia k contatti), la foglia è divisa.

Il frazionamento di una foglia a livello n, aggiungerà due foglie al livello n+1. Tutti i contatti che hanno bit = 1 al livello n+1 saranno aggiunti sulla foglia sinistra mentre quelli con bit = 0 saranno aggiunti sulla foglia destra con i contatti vicini.

Tenendo i contatti più grandi e “vivi”, i k-bucket massimizzano la probabilità che i nodi che li contengono rimangano online. Un altro beneficio dei k-bucket è che offrono una particolare resistenza agli attacchi DoS: non è possibile intasare lo stato di instradamento dei nodi inondando il sistema con nuovi nodi, infatti nuovi nodi vengono inseriti in Kademlia solo quando i vecchi nodi lasciano il sistema.

4.4 - Localizzazione di un nodo

Se il nodo 1 vuole contattare il nodo 5: 1. Nodo 1 manda FIND_NODE(5) a uno dei nodi nel k-bucket 1-- (perche il bucket 1– è il più vicino a 5) inoltre si suppone che 5 non sia nei k-bucket di 1.

2. Il nodo 6 ritorna al nodo 1 l’indirizzo del nodo 4 (il più vicino a 5) supponendo che 5 non sia nei k-bucket di 6 3. Il nodo 1 manda una FIND_NODE(5) al nodo 4

4. Il nodo 4 risponde infine al nodo 1 dicendogli l’indirizzo del nodo 5. 5. Il nodo 1 può contattare il nodo 5.

E’ possibile dimostrare che il numero di passi per localizzare un nodo è logaritmico. Nell’algoritmo reale vengono inviate più richieste in parallelo cioè un numero di richieste < k. In questo modo si evitano problemi con i timeout dei nodi offline. Le risposte alle richieste contengono i k nodi più vicini. L’algoritmo ricorsivo termina quando i k nodi più vicini al nodo destinazione hanno risposto.

5 - Processi di inizializzazione

La connessione di un nodo nella rete richiede la sistemazione dello stato del nodo. Quindi il processo di inizializzazione è collocare il nodo nella rete, dopodiché il processo di sistemazione consiste nel mantenere il collegamento.

5.1 - Bootstrapping

Per connettersi alla rete Kad un nodo deve superare un processo di bootstrap prima. Perciò un cliente di Kademlia ha bisogno almeno di un nodo attivo nella rete Kad con la sua < IPaddress: messageport >. Ad una richiesta di bootstrap il nodo interrogato risponderà con un elenco di ulteriori nodi dalla rete. Grazie a questo archivio i processi di inizializzazione saranno veloci e facili. Un cliente di aMule lavora autonomamente e trova i nodi che sono di interesse per la sua tabella di instradamento.

Il nodo che vuole fa bootstrap con un altro nodo spedisce i suoi dati all'interno del KADEMLIA_BOOTSTRAP_REQ nella configurazione: < ClientID: senderIP: messageport: serviceport: type > al nodo < targetIP: targetmessageport >. Il type del nodo è impostato a zero perché il nodo ricevente calcolerà il valore di type quando il nodo di mittente è aggiunto alla sua tavola di instradamento. Dopo avere ricevuto la richiesta il nodo risponderà col KADEMLIA _BOOTSTRAP _RES nella configurazione: < n * < ClientID: senderIP: messageport: serviceport>>. N definisce la quantità di nodi casuali che la tabella di instradamento fornirà. Dopo avere completato l’operazione con successo, il nodo richiedente aggiunge i contatti nuovi nella sua tabella di instradamento.

5.2 - Handshake

Quando un cliente ottiene dati di contatto nuovi, dopo un bootstrapping, compierà un processo di handshaking (letteralmente stretta di mano). Questa è una procedura tipica di client o nodi per entrare in contatto ed assicurare che l'altro ancora è vivo. Perciò un nodo invia una KADEMLIA_REQ <Type : targetID: receiversclientID> al nuovo contatto. Come risposta, se questo è ancora online, risponderà con un KADEMLIA_RES <Type*<targetID:Type:Peer>>. Se l’handshake è eseguito dopo l’avvio da parte del client, allora egli invierà un messaggio di controllo sul firewall (descritto dopo). Quando il controllo sul firewall è terminato il client invierà un KADEMLIA_HELLO_REQ al nodo opposto. In risposta egli ritornerà un KADEMLIA_HELLO_RES.

Il client di aMule controlla, se i suoi contatti sono ancora vivi ogni minuto. Perciò spedisce una KADEMLIA _HELLO_REQ ad ogni contatto di ogni foglia della tabella di instradamento. In dettaglio, prima rimuove tutti i contatti che hanno superato la loro data di scadenza. Poi prende il contatto con la data di scadenza più vicina e gli spedisce una HELLO_REQ.

5.3 - Firewall

Lo stato di “firewalled” indica l’accessibilità delle porte e corrisponde allo stato di eDonkey di “id basso”. Il firewall blocca ogni tipo di messaggio entrante in un nodo, quando un host è posto dietro ad una rete privata e ha il suo indirizzo IP mascherato, messaggi sconosciuti non possono essere recapitati al nodo di destinazione. Una soluzione è aprire le porte corrispondenti nel firewall. Il protocollo Kad ha un suo proprio processo per scoprire se le porte dei client possono essere accedute direttamente. Questo controllo sul firewall è eseguito immediatamente dopo aver stabilito la connessione alla rete Kad. Dopo il controllo iniziale il timer effettuerà questo controllo ogni ora. Perciò il timer imposta una variabile per notificare al cliente che il processo di controllo del firewall è attivo. Ci sono poi tre possibilità di provocare questo processo. Una richiesta è spedita direttamente dopo un messaggio iniziale ed è incluso nella normale comunicazione tra due nodi. Questo assicura che è molto probabile che il nodo contattato sia ancora vivo.

Quando il processo di controllo sul firewall è avviato, il nodo mittente spedisce il KADEMLIA_FIREWALLED_REQ includendo la sua porta TCP. Poi il nodo ricevente mette gli indirizzi IP entranti nel pacchetto di risposta KADEMLIA_FIREWALLED_RES e rispedisce il pacco. Quando al nodo di verifica arriva la risposta, egli confronta il suo indirizzo IP con quello visto dal cliente che risponde. Il controllo sarà fermato dopo quattro risposte entranti. Inoltre il client che risponde tenterà di fare un collegamento col cliente di verifica. Evidentemente, solamente nodi che non sono firewalled possono stabilire un collegamento di prova. Se il collegamento ha successo, il nodo spedirà un KADEMLIA_FIREWALLED_ACK. Il client di verifica non indica firewalled, quando ha ricevuto più di due risposte positive.

6 - Protocolli - RPCs

Il protocollo di Kademlia consiste di quattro RPCs (RPC, o Remote Procedure Call): PING, STORE, FIND NODE, and FIND VALUE. L'espressione chiamata di procedura remota (RPC) consente a un programma di eseguire subroutine "a distanza" su computer "remoti" (accessibili però attraverso una rete). Essenziale al concetto di RPC è anche l'idea di trasparenza: la chiamata di procedura remota deve essere infatti eseguita in modo il più possibile analogo a quella della tradizionale chiamata di procedura "locale"; i dettagli della comunicazione su rete devono essere quindi "nascosti" (resi trasparenti) all'utilizzatore del meccanismo. Il paradigma RPC risulta particolarmente adatto per il calcolo distribuito basato sul modello client-server; la "chiamata di procedura" corrisponde alla "richiesta" inviata dal "client", e il "valore restituito" della procedura corrisponde alla "risposta" inviata dal "server".

  • PING:
Questa procedure implica l’invio da parte di un nodo di un messaggio PING ad un altro nodo, che presumibilmente risponderà con un messaggio PONG. Deve essere possibile inviare e ricevere un RPC PING per forzare o permettere al mittente di aggiungere informazioni addizionali sul destinatario. Questa può essere un indirizzo IP diverso o un protocollo destinato a comunicazioni future.
  • STORE:
L’emittente della chiamata STORE fornisce una chiave ed un blocco dei dati e richiede al ricevente di immagazzinare i dati e renderli disponibili per recuperi futuri tramite questa chiave. E’ chiaro che il messaggio di STORE iniziale deve contenere, oltre al messaggio ID, almeno i dati per essere immagazzinato (incluso la sua lunghezza) e la chiave associata. il trasporto può essere UDP, il messaggio ha bisogno di contenere anche almeno il nodeID del mittente, e la replica del nodeID del destinatario. La replica ad alcune RPC dovrebbe contenere anche un'indicazione del risultato dell'operazione. Per esempio, nella STORE anche se la lunghezza massima di dati è stata specificata, chiaramente è possibile che il ricevitore non sia capace di immagazzinare i dati, o a causa di mancanza di spazio o a causa di un errore di I/O.
  • FIND_NODE
Un FIND_NODE RPC include chiavi pari a B=160bits. Il destinatario dell’RPC ritorna k triplette (IP address, port, nodeID) di quei contatti che sono più vicini alla chiave. Il destinatario ritornerà le triplette fin quando gli sarà possibile. Può ritornare meno di k triplette solo se sta riportando tutti I contatti di cui è a conoscenza. Il nome di questo RPC è ingannevole. Anche se la chiave dell'RPC è il nodeID di un contatto esistente o effettivamente se è il nodeID del destinatario in se, il destinatario è ancora tenuto a restituire K triplette (IP address, port, nodeID).Un nome più significativo potrebbe essere FIND_CLOSE_NODES.Il destinatario di un FIND_NODE non dovrebbe restituire mai una tripletta che contiene il nodeID del richiedente. Se il richiedente riceve una tale tripletta, dovrebbe scartarla.
  • FIND_VALUE
Un FIND_VALUE RPC include chiavi pari a B=160bits. Se un valore corrispondente è presente nel destinatario, vengono restituiti i dati associati. Altrimenti l’RPC è equivalente ad un FIND_NODE ed è restituita una serie di k triplette (IP address, port, nodeID).

7 - Software che usano Kademlia

È attualmente implementato, a vari livelli e con vari scopi, nei client peer-to-peer:

  • eMule: dalla versione 0.40
  • aMule: dalla versione 2.1.0
  • MLDonkey: dalla versione 2.5-28
  • BitTorrent: dalla versione 4.1.0 supporta la rete Kademlia per i torrent trackerless basata su un'implementazione di Khashmir
  • μTorrent: dalla versione 1.2

8 - Chord

Il progetto Chord si prefigge di sviluppare sistemi distribuiti scalabili e robusti sfruttando le idee del peer-to-peer . Il componente base del progetto Chord è l'algoritmo di ricerca distribuita basata su tabelle di hash (DHT). Chord è completamente decentralizzato e simmetrico e può trovare dati usando soltanto log(N) messaggi, dove N è il numero di nodi nel sistema. L'algoritmo di ricerca di Chord è provatamente robusto in presenza di nodi guasti o riconnessioni.

Chord è ancora in fase di sviluppo presso il MIT, dove è disponibile la dococumentazione ufficiale sul protocollo ed inoltre è anche possibile scaricare parte del codice che cmq non è ancora stato rilasciato ufficialmente.

CHORD realizza un DHT con le seguenti caratteristiche:

  • Load balance: CHORD distribuisce uniformemente le chiavi fra i nodi
  • Scalabilità: le operazioni di lookup sono efficienti
  • Robustezza: CHORD è in grado d modificare dinamicamente le routing table dei nodi per riflettere i mutamenti della rete (nodi che entrano o escono)

Se N è il numero di nodi presenti sulla rete, al variare di N si desidera che:

  • La quantità di dati da rimappare nel sistema sia bassa
  • Si garantisca l’uniformità della distribuzione delle chiavi sui nodi

Gli ID dei nodi sono i codici hash ottenuti dagli indirizzi IP, mentre gli ID delle chiavi sono i codici hash ottenuti dalle chiavi. Una funzione di hash (tipo SHA-1) assegna a ciascun nodo un identificatore a m bit, così come ogni oggetto è identificato da una chiave a m bit. Gli identificatori dei nodi sono ordinati in un cerchio modulo 2m.La chiave k è assegnata al primo nodo in senso orario il cui identificatore è ≥ k. Tale nodo è detto il nodo successore della chiave k.

Ciascun nodo conosce il nodo con l’identificatore immediatamente superiore. Una query per una certa chiave viene propagata in senso orario fino al primo nodo il cui identificatore è ≥ alla chiave. La risposta alla query fa il cammino inverso, fino all’originatore della query. Seguendo questo approccio, il numero di nodi da attraversare se la rete è composta da N nodi è O(N).

Ciascun nodo n mantiene una routing table con un massimo di m entry, detta finger table. La i-esima entry è: n.finger[i] = successor(n + 2i-1). Utilizzando la finger table per trovare il nodo il cui identificatore precede quello del nodo successore della chiave cercata, il numero di nodi da attraversare se la rete è composta da N nodi è O(logN) con elevata probabilità.

Per assicurare una corretta esecuzione dell’algoritmo di ricerca anche quando l’insieme dei nodi della rete cambia, Chord prevede un protocollo di stabilizzazione che ciascun nodo dovrebbe eseguire periodicamente in background, per aggiornare la finger table. La correttezza del protocollo Chord si basa sul fatto che ciascun nodo conosce almeno il suo successore. Purtroppo, può succedere che un nodo si disconnetta inavvertitamente (senza seguire la procedura dettata dal protocollo). Per una maggiore robustezza, ciascun nodo Chord mantiene una successor list che contiene i puntatori ai primi r successori del nodo stesso.

8 - Riferimenti

Petar Maymounkov and David Mazières
In 1st International Workshop on Peer-to-peer Systems
Specifiche dul protocollo Kademlia
DHTs