Kademlia
Da Wikipedia, l'enciclopedia libera.
Kademlia è un protocollo P2P 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.
Esso si basa sulla tecnologia Distributed Hash Table (DHT). Su un LAN/WAN (come Internet) già esistente, un nuovo network virtuale viene creato ed 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 scopi legati al suo funzionamento.
Un nodo che vuole entrare nella rete, deve prima di tutto iniziare un processo denominato "bootstrap". In questa fase, il nodo necessita 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.
L'algoritmo Kademlia è basato sul calcolo della "distanza" tra due nodi.
Questa "distanza" non ha nulla a che vedere con la localizzazione geografica, ma rappresenta la distanza in uno spazio di ID e viene calcolata mediante l'or esclusivo tra gli identificatori dei due nodi. Quindi può accadere, per esempio, che un nodo situato in Italia ed uno situato in Australia siano "vicini" sulla rete.
L'informazione sulla rete Kademlia è memorizzata nei così detti "valori", ad ogni valore viene assegnato una "chiave".
Quando si cerca una chiave, l'algoritmo esplora la rete in passi successivi ed 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.
[modifica] Uso nelle reti di file sharing
Kademlia è usata da molti programmi di file sharing. Facendo ricerche per parole chiavi si possono trovare informazioni così da poterle scaricare. Poiché non c'è un riferimento centrale dove memorizzare un indice dei file esistenti, è un compito che viene diviso parimenti tra tutti i clients: 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 in 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 ad una intrinseca ridondanza dell'informazione su Kademlia questi contatti vengono replicati in diversi nodi.
[modifica] Software che usano Kademlia
È attualmente implementato, a vari livelli e con vari scopi, nei client peer-to-peer:
- rete Kad
- 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
[modifica] Collegamenti esterni
(EN) (PDF) *Kademlia: A Peer to peer information system Based on the XOR Metric
