Kademlia

Kademlia è un protocollo di rete peer-to-peer ideato da Petar Maymounkov e David Mazières della New York University, per un network di computer decentralizzato.

Specifica la struttura del network, regola la comunicazione tra i nodi ed il modo in cui lo scambio di informazioni deve essere effettuato. I nodi Kademlia comunicano tra di loro utilizzando il protocollo di trasporto UDP.

Uso nelle reti di file sharing

Kademlia è usata da molti programmi di file sharing per la sua caratteristica di essere basata su tabelle distribuite su nodi della rete senza server centrali. Su Kademlia possono essere effettuate ricerche per parole chiave per reperire il file ricercato e il compito di memorizzare l'indice dei file esistenti viene diviso paritariamente tra tutti i client. Il nodo che possiede un file che vuole condividere, lo analizza e ne calcola un numero hash che identificherà quel file sulla rete di file sharing. Gli hash e gli ID devono avere la stessa lunghezza.

Il nodo ricerca tra tutti gli altri nodi quello che possiede l'ID con la minima distanza dall'hash del file, e memorizza il proprio indirizzo IP su quel nodo. Il client che avvia la ricerca userà Kademlia per cercare l'ID del client che ha la distanza minima dall'hash del file che sta cercando, quindi recupererà l'elenco dei contatti (cioè gli IP) che sono memorizzati in quel nodo. I contatti memorizzati nella rete sono in continuo cambiamento poiché i nodi si connettono e si disconnettono. Grazie a un'intrinseca ridondanza dell'informazione su Kademlia questi contatti vengono replicati in diversi nodi.

Caratteristiche

Kademlia si basa sulla tecnologia Distributed Hash Table (DHT). Su una LAN/WAN (come Internet) già esistente, viene creato un nuovo network virtuale in cui ogni nodo è identificato da un numero ("ID nodo"). Questo numero non serve solo ai fini del riconoscimento di un nodo, ma l'algoritmo Kademlia lo usa per localizzare valori (ad esempio il codice hash del filename oppure una keyword/parola chiave) in quanto l'ID del nodo consente di mappare i valori che debbono essere memorizzati.

La rete definisce un concetto di distanza che permette di stabilire la prossimità tra due nodi cosicché, dato un nodo "A" è sempre possibile determinare se un nodo "B" risulta più vicino di un nodo "C". Ogni nodo ha una conoscenza della rete Kademlia che diminuisce all'aumentare della distanza dal nodo stesso, e, quindi, ha una conoscenza molto dettagliata della rete nei propri dintorni, una discreta conoscenza della rete a media distanza e solo una conoscenza sparsa dei nodi molto lontani.

Lo scopo di Kademlia è memorizzare e ritrovare valori che possono essere di qualunque tipo ma, di solito, sono puntatori a file. I valori sono indicizzati tramite "Chiavi" ("Keys"). ID nodo e Chiavi hanno lo stesso formato, per cui è possibile calcolare la distanza esattamente come tra due nodi. Ne consegue che ogni nodo è in grado di calcolare la distanza tra se stesso e due chiavi "K1" e "K2", capendo quale delle due sia più vicina. Nello stesso modo il nodo "A" è capace di determinare quale delle due chiavi "K1" e "K2" è più vicina ad un nodo "B". "A" e "B" sono sempre concordi in questo calcolo.

Per memorizzare un valore, il nodo richiedente:

• calcolerà la chiave corrispondente (generalmente l'hash del valore da memorizzare),
• cercherà nella rete i nodi con "ID nodo" più prossimi all'hash del valore da memorizzare,
• richiederà la memorizzazione del valore in tutti questi nodi.

Quando si cerca una chiave, l'algoritmo esplora la rete in passi successivi e ad ogni passaggio ci si avvicina sempre più alla chiave cercata finché il nodo contattato non restituisce il valore oppure non ci sono più nodi da interrogare. Il numero di nodi contattati durante la ricerca dipende solo marginalmente dalla dimensione della rete: se il numero dei partecipanti alla rete raddoppia, allora il nodo di un utente deve interrogare solo un nodo in più per ogni ricerca, non il doppio di quelli che ha contattato prima.

Ulteriori vantaggi si trovano in particolare nella struttura decentralizzata che chiaramente aumenta la resistenza contro attacchi denial of service. Anche se un intero insieme di nodi sono presi di mira si avranno effetti molto limitati sulla rete, che supererà automaticamente il problema isolando la rete intorno a questi nodi problematici.

Dettagli di funzionamento

La prima generazione di reti peer-to-peer per lo scambio di file, come Napster ad esempio, si basava su un database centralizzato per coordinare le attività di ricerca e memorizzazione all'interno del network. La seconda generazione, come ad esempio Gnutella, esegue una ricerca massiva dell'informazione interrogando ogni nodo conosciuto della rete. La terza generazione fa ricorso alle Distributed Hash Table (DHT) per ricercare i file nel network. Le DHT memorizzano valori (ossia gli indirizzi della risorse da condividere) e li rendono disponibili a tutto il network. L'obiettivo principale di questi protocolli è la velocità nella ricerca dell'informazione.

L'algoritmo di Kademlia è basato sul calcolo della distanza tra due nodi. La distanza è calcolata come XOR tra due "ID Nodo" e assumendo come intero il valore risultante. "ID Nodo" e "Chiavi" hanno lo stesso formato e la stessa lunghezza, così da poter calcolare le distanze tra i nodi e tra quelli e le chiavi esattamente nello stesso modo.

La distanza così calcolata non ha nulla a che vedere con la distanza geografica e due nodi che risultano vicini per l'algoritmo possono essere localizzati in due continenti differenti.

L'algoritmo procede iterativamente nella ricerca delle chiavi attraverso la rete, avvicinandosi di un bit al risultato ad ogni passo compiuto. Ne consegue che una rete Kademlia con $2^{n}$ nodi, richiederà al massimo n passi per trovare il nodo cercato.

Tabella di Indirizzamento (Routing Table)

La tabella di indirizzamento di Kademlia consiste di una lista per ogni bit del "ID Nodo" (cioè se l'"ID nodo" è lungo 128 bit, il nodo conserverà 128 di queste liste). Ogni lista ha molte entry. Ogni entry della lista contiene le informazioni necessarie a localizzare un nodo; i dati principali sono l'indirizzo IP, la porta e il "ID Nodo" di un altro nodo della rete. Ogni lista corrisponde a una specifica distanza dal nodo. I nodi che finiscono nella ennesima lista devono avere almeno l'ennesimo bit differente da quello del nodo: i primi n-1 bit devono essere uguali a quelli del nodo considerato. Questo significa che è possibile candidare al riempimento della prima lista la metà dei nodi che si trovano più distanti dal nodo in esame. La lista successiva può usare 1/4 dei nodi nel network che sono più vicini di un bit, e così via.

Con un "ID Nodo" di 128 bits, ogni nodo può essere classificato in una della 128 possibili distanze, una per ogni bit di differenza.

Quando si incontrano nodi nella rete Kademlia, questi sono aggiunti alle liste della tabella di indirizzamento. Questo avviene nel corso delle operazioni di ricerca e memorizzazione e anche nel corso di attività d'aiuto alla ricerca per conto di un altro nodo. Ogni nodo incontrato sarà candidato all'inclusione nelle liste. Ne segue che la conoscenza della rete è molto dinamica, consente di mantenere informazioni aggiornate e fornisce resistenza verso anomalie ed attacchi.

Nella letteratura di Kademlia la lista è chiamata k-bucket, dove k è un valore costante per tutta la rete (genericamente k = 20). Ogni k-bucket è perciò una lista contenente fino a k entry (nel nostro caso 20) che fanno riferimento a k nodi distanti k bit dal nodo considerato.

Poiché i numero di possibili nodi per un determinato k-bucket diminuisce velocemente al diminuire della distanza, i k-buckets con bit più basso descrivono completamente la rete circostante al nodo. Poiché il numero dei possibili ID nodo è molto maggiore di ogni possibile popolazione di nodi appartenenti alla rete, alcuni k-buckets corrispondenti a brevi distanze dal nodo rimarranno vuote.

Un esempio di partizionamento della rete

Consideriamo la rete rappresentata nella figura a lato. Con n = 3, i possibili "ID Nodo" sono 8, dal binario 000 al 111. In questa rete semplificata ci sono sette nodi rappresentati dai cerchietti in basso: il nodo in esame è il sei ed è rappresentato dal cerchietto nero ("ID nodo" = 110). Il nodo con il cerchietto nero (e anche gli altri) dispone di 3 k-bucket. I nodi zero, uno e due (ossia 000, 001 e 010) sono candidati ad essere inclusi nel primo k-bucket; i nodi quattro e cinque (100 e 101) sono candidati ad essere inclusi nel secondo k-bucket; il terzo k-bucket contiene solo il nodo sette. I k-bucket sono racchiusi nei cerchi grigi. Se la dimensione del k-bucket fosse 2 (k = 2), il primo 2-bucket conterrebbe solo due dei possibili nodi, il secondo tutti e due, mentre il terzo avrebbe una sola entry valorizzata.

È statisticamente noto che i nodi che sono collegati alla rete da più tempo hanno maggiori probabilità di rimanere collegati per un maggior tempo nel futuro. A causa di questa distribuzione statistica, Kademlia seleziona i nodi connessi da maggior tempo per essere memorizzati in un k-bucket. Ciò aumenta la conoscenza di nodi validi nel futuro e rende più stabile la rete.

Quando un k-bucket è pieno ed è scoperto un nuovo nodo per quel determinato k-bucket, il nodo visto meno recentemente viene PING-ato; se il nodo è ancora vivo, il nuovo nodo è messo in una lista di rimpiazzo (cache di rimpiazzo). La lista di rimpiazzo è utilizzata solo se un nodo di un k-bucket smette di rispondere. In altre parole i nuovi nodi sono utilizzati solo quando i vecchi nodi smettono di rispondere.

Messaggi del protocollo

Kademlia ha quattro messaggi:

• PING - utilizzato per verificare che un nodo sia vivo;
• STORE - per archiviare una coppia (chiave, valore) in un nodo;
• FIND_NODE - per cercare nodi; il nodo ricevente il messaggio fornisce i k nodi che sono contenuti nel proprio k-bucket più prossimo al "ID nodo" ricercato;
• FIND_VALUE - come FIND_NODE, ma se il ricevente dispone della chiave richiesta, al posto dei k nodi fornisce il valore corrispondente alla chiave.

Ogni messaggio RPC include un valore random generato dall'inizializzatore della richiesta. Tale valore è utilizzato per assicurare che la risposta sia relativa alla domanda effettuata.

Localizzazione di un Nodo

La ricerca di un nodo può procedere in modo asincrono. La quantità di ricerche simultanee è denotato da α ed è tipicamente tre. Un nodo inizia una ricerca inviando una richiesta FIND_NODE ai nodi contenuti nel k-bucket più vicino al "ID Nodo" da trovare. Quando i nodi riceventi ricevono il messaggio, ricercano nei propri k-bucket e restituiscono le k chiavi più vicine al nodo desiderato. Sulla base delle risposte ricevute il richiedente aggiorna la propria lista delle risposte, salvando solo le k migliori risposte (ossia i k "ID nodi" più vicini al nodo cercato). A questo punto il richiedente reitera la richiesta verso i nuovi nodi risultanti fin tanto che non esistono ulteriori nodi più vicini al nodo cercato. Poiché nel corso della ricerca la conoscenza della rete intorno al valore cercato diventa sempre più precisa, l'algoritmo converge velocemente verso i k "ID nodo" più vicini al valore cercato.

Quando non è possibile trovare nodi più vicini, l'algoritmo di ricerca termina restituendo i k-valori più vicini al nodo cercato (incluso eventualmente il nodo stesso, se esiste).

Le informazioni contenute nel nodo possono essere arricchite con il Round Trip Time o RTT. Questa informazione sarà utilizzata per determinare il time-out delle richieste inviate ad uno specifico nodo. Quando una richiesta va in time-out è possibile inoltrare un'ulteriore richiesta evitando così di superare il numero α di richieste contemporanee.

Localizzazione dei Valori

Le informazioni sono localizzate tramite la mappatura in una chiave. Tale mappatura avviene con algoritmo che calcola l'hash del valore e lo utilizza come chiave. Il nodo memorizzatore ha ottenuto il valore per mezzo di un precedente messaggio di STORE. La localizzazione del valore avviene cercando il nodo con "ID nodo" più vicino alla chiave del valore, con l'eccezione che la ricerca termina quando viene trovato un nodo che contiene la chiave del valore cercato: in questo caso il nodo in questione restituisce il valore corrispondente alla chiave.

I valori sono memorizzati (ridondati) in più nodi per permettere ad ogni singolo nodo di entrare e uscire dalla rete senza che questo pregiudichi il funzionamento della stessa. Ad intervalli temporali regolari un nodo che memorizza un valore esplorerà la rete alla ricerca dei k nodi più vicini alla chiave del valore e vi replicherà il valore stesso (per mezzo di un'istruzione STORE). Questo processo permette di prevenire la scomparsa dei nodi. Questa nuova memorizzazione è chiamata cache. I valori più popolari e ricercati avranno la possibilità di essere distribuiti su più nodi in prossimità del valore della chiave ricercata, evitando la concentrazione delle richieste su pochi nodi. In certe implementazioni la cache è a sua volta replicata da un processo iterativo nei nodi vicini a quello che detiene la cache, contribuendo così a distribuire i valori attraverso il network. Le informazioni presenti nella cache sono cancellate dopo un determinato periodo di tempo in funzione della distanza dalla chiave, consentendo così alla rete di eliminare i valori non più aggiornati. Poiché anche al termine della richiesta anche il richiedente possiede il valore, se ne deriva che le richieste più popolari sono accelerate dalla disponibilità dell'informazione presso molti nodi.

Alcune implementazioni (KAD) non dispongono di meccanismi di replica e caching perché è importante eliminare immediatamente le informazioni obsolete. Solo il nodo che vuole condividere il file provvede al refresh periodico delle informazioni nella rete (attraverso un'operazione di NODE_LOOKUP e STORE). Quando tutti i nodi che posseggono il file lasciano la rete, l'informazione non è più replicata e scompare dalla rete.

Entrare nella rete

Un nodo che vuole entrare nella rete deve prima di tutto iniziare un processo denominato bootstrap. In questa fase, il nodo ha bisogno di conoscere l'indirizzo IP di un altro nodo (ottenuto dall'utente o da una lista memorizzata) che stia già partecipando alla rete di Kademlia. Se il nodo che deve fare il bootstrap non ha mai partecipato alla rete, calcola un numero identificativo casuale che non sia ancora stato assegnato ad un altro nodo. Usa questo ID finché non lascia la rete.

Il nodo entrante inserisce il nodo di partenza in uno dei suoi k-bucket, poi procede all'autoricerca. In questo modo l'ID del nodo entrante è memorizzato nei k-bucket dei nodi che partecipano alla ricerca, mentre le risposte popoleranno i k-bucket con gli ID dei nodi compresi nel percorso tra il nodo di bootstrap ed il nodo entrante. A questo punto il processo viene completato con la ricerca di un valore casuale più lontano del nodo di bootstrap dal nodo entrante.

Ricerca Accelerata

Kademlia calcola le distanze tra nodi utilizzando una metrica XOR. Il calcolo della distanza è effettuato eseguendo un'operazione di XOR (OR esclusivo) tra due ID Nodo oppure tra un ID Nodo e una chiave: il risultato, in binario, è assunto come distanza.

Per ogni bit, la funzione XOR restituisce 0 se i due bit sono uguali oppure 1 se i due bit sono differenti. Nella Metrica XOR resta valida la seguente disuguaglianza triangolare valida nella geometria classica: la distanza tra due punti A e B è minore o uguale alla somma delle distanze tra A ed un punto C qualsiasi ed alla distanza tra C e B.

La metrica XOR permette a Kademlia di estendere le tabelle di indirizzamento oltre al limite dei singoli bit. Gruppo di Bits possono essere raggruppati in K-buckets. Per un dato prefisso di m-bits ci saranno 2m-1 k-buckets. Il k-bucket mancante è l'ulteriore estensione dell'albero di indirizzamento che contiene il node-ID. Un prefisso di m-bit riduce il numero delle ricerche nella tabella di indirizzamento massime da log2 n a log2b n. Il numero medio delle ricerche sarà molto minore dato l'aumento delle possibilità di trovare un nodo nel proprio k-bucket che condivide molti bit oltre al proprio prefisso.

Software che usano Kademlia

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

• rete Kad
  • aMule: dalla versione 2.1.0
  • eMule: dalla versione 0.40
  • MLDonkey: dalla versione 2.5-28
  • iMule
  • lphant
• rete Overnet
  • KadC: libreria in C per ottenere e mandare informazioni dalla/alla rete Overnet
  • MLDonkey
  • Overnet: ora incorporato in eDonkey2000
• altre implementazioni
  • Azureus: dalla versione 2.3.0.0
  • BitComet: dalla versione 0.59
  • 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
  • RevConnect: dalla versione 0.403
  • BitSpirit: versione 3.2.2.215
  • Osiris:dalla versione 0.6
  • RevConnect: mod di DC++

Collegamenti esterni

• (EN) Kademlia: A Peer to peer information system Based on the XOR Metric (PDF), su cs.rice.edu. URL consultato l'11 luglio 2005 (archiviato dall'url originale l'11 dicembre 2005).
• (EN) Kademlia, su kademlia.scs.cs.nyu.edu (archiviato dall'url originale il 22 marzo 2003).