b'\n_START_ARTICLE_\nKademlia\n_START_PARAGRAPH_\nKademlia \xc3\xa8 un protocollo di rete peer-to-peer ideato da Petar Maymounkov e David Mazi\xc3\xa8res della New York University, per un network di computer decentralizzato._NEWLINE_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.\n_START_SECTION_\nUso nelle reti di file sharing\n_START_PARAGRAPH_\nKademlia \xc3\xa8 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\xc3\xa0 quel file sulla rete di file sharing. Gli hash e gli ID devono avere la stessa lunghezza._NEWLINE_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\xc3\xa0 Kademlia per cercare l\'ID del client che ha la distanza minima dall\'hash del file che sta cercando, quindi recuperer\xc3\xa0 l\'elenco dei contatti (cio\xc3\xa8 gli IP) che sono memorizzati in quel nodo. I contatti memorizzati nella rete sono in continuo cambiamento poich\xc3\xa9 i nodi si connettono e si disconnettono. Grazie a un\'intrinseca ridondanza dell\'informazione su Kademlia questi contatti vengono replicati in diversi nodi.\n_START_SECTION_\nDettagli di funzionamento\n_START_PARAGRAPH_\nLa 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\xc3\xa0 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 \xc3\xa8 la velocit\xc3\xa0 nella ricerca dell\'informazione._NEWLINE_L\'algoritmo di Kademlia \xc3\xa8 basato sul calcolo della distanza tra due nodi. La distanza \xc3\xa8 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\xc3\xac da poter calcolare le distanze tra i nodi e tra quelli e le chiavi esattamente nello stesso modo._NEWLINE_La distanza cos\xc3\xac 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._NEWLINE_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  nodi, richieder\xc3\xa0 al massimo n passi per trovare il nodo cercato.\n_START_SECTION_\nTabella di Indirizzamento (Routing Table)\n_START_PARAGRAPH_\nLa tabella di indirizzamento di Kademlia consiste di una lista per ogni bit del "ID Nodo" (cio\xc3\xa8 se il "ID nodo" \xc3\xa8 lungo 128 bit, il nodo conserver\xc3\xa0 128 di queste liste). Ogni lista ha molte entrate. Ogni entrata 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 \xc3\xa8 possibile candidare al riempimento della prima lista la met\xc3\xa0 dei nodi che si trovano pi\xc3\xb9 distanti dal nodo in esame. La lista successiva pu\xc3\xb2 usare 1/4 dei nodi nel network che sono pi\xc3\xb9 vicini di un bit, e cos\xc3\xac via._NEWLINE_Con un "ID Nodo" di 128 bits, ogni nodo pu\xc3\xb2 essere classificato in una della 128 possibili distanze, una per ogni bit di differenza._NEWLINE_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\xc3\xa0 d\'aiuto alla ricerca per conto di un altro nodo. Ogni nodo incontrato sar\xc3\xa0 candidato all\'inclusione nelle liste. Ne segue che la conoscenza della rete \xc3\xa8 molto dinamica, consente di mantenere informazioni aggiornate e fornisce resistenza verso anomalie ed attacchi._NEWLINE_Nella letteratura di Kademlia la lista \xc3\xa8 chiamata k-bucket, dove k \xc3\xa8 un valore costante per tutta la rete (genericamente k = 20). Ogni k-bucket \xc3\xa8 perci\xc3\xb2 una lista contenente fino a k entrate (nel nostro caso 20) che fanno riferimento a k nodi distanti k bit dal nodo considerato._NEWLINE_Poich\xc3\xa9 i numero di possibili nodi per un determinato k-bucket diminuisce velocemente al diminuire della distanza, i k-buckets con bit pi\xc3\xb9 basso descrivono completamente la rete circostante al nodo. Poich\xc3\xa9 il numero dei possibili ID nodo \xc3\xa8 molto maggiore di ogni possibile popolazione di nodi appartenenti alla rete, alcuni k-buckets corrispondenti a brevi distanze dal nodo rimarranno vuote._NEWLINE_Consideriamo la rete rappresentata nella figura a lato. Con n = 3, i possibili "ID Nodo" sono 8, dal binario\xc2\xa0000 al 111. In questa rete semplificata ci sono sette nodi rappresentati dai cerchietti in basso: il nodo in esame \xc3\xa8 il sei ed \xc3\xa8 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\xc2\xa0000, 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._NEWLINE_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 entrata valorizzata._NEWLINE_\xc3\x88 statisticamente noto che i nodi che sono collegati alla rete da pi\xc3\xb9 tempo hanno maggiori probabilit\xc3\xa0 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\xc3\xb2 aumenta la conoscenza di nodi validi nel futuro e rende pi\xc3\xb9 stabile la rete._NEWLINE_Quando un k-bucket \xc3\xa8 pieno ed \xc3\xa8 scoperto un nuovo nodo per quel determinato k-bucket, il nodo visto meno recentemente viene PING-ato; se il nodo  \xc3\xa8 ancora vivo, il nuovo nodo \xc3\xa8 messo in una lista di rimpiazzo (cache di rimpiazzo). La lista di rimpiazzo \xc3\xa8 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.\n_START_SECTION_\nLocalizzazione di un Nodo\n_START_PARAGRAPH_\nLa ricerca di un nodo pu\xc3\xb2 procedere in modo asincrono. La quantit\xc3\xa0 di ricerche simultanee \xc3\xa8 denotato da \xce\xb1 ed \xc3\xa8 tipicamente tre. Un nodo inizia una ricerca inviando una richiesta FIND_NODE ai nodi contenuti nel k-bucket pi\xc3\xb9 vicino al "ID Nodo" da trovare. Quando i nodi riceventi ricevono il messaggio, ricercano nei propri k-bucket e restituiscono le k chiavi pi\xc3\xb9 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\xc3\xb9 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\xc3\xb9 vicini al nodo cercato. Poich\xc3\xa9 nel corso della ricerca la conoscenza della rete intorno al valore cercato diventa sempre pi\xc3\xb9 precisa, l\'algoritmo converge velocemente verso i k "ID nodo" pi\xc3\xb9 vicini al valore cercato._NEWLINE_Quando non \xc3\xa8 possibile trovare nodi pi\xc3\xb9 vicini, l\'algoritmo di ricerca termina restituendo i k-valori pi\xc3\xb9 vicini al nodo cercato (incluso eventualmente il nodo stesso, se esiste)._NEWLINE_Le informazioni contenute nel nodo possono essere arricchite con il Round Trip Time o RTT. Questa informazione sar\xc3\xa0 utilizzata per determinare il time-out delle richieste inviate ad uno specifico nodo. Quando una richiesta va in time-out \xc3\xa8 possibile inoltrare un\'ulteriore richiesta evitando cos\xc3\xac di superare il numero \xce\xb1 di richieste contemporanee.\n_START_SECTION_\nLocalizzazione dei Valori\n_START_PARAGRAPH_\nLe 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\xc3\xb9 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._NEWLINE_I valori sono memorizzati (ridondati) in pi\xc3\xb9 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\xc3\xa0 la rete alla ricerca dei k nodi pi\xc3\xb9 vicini alla chiave del valore e vi replicher\xc3\xa0 il valore stesso (per mezzo di un\'istruzione STORE). Questo processo permette di prevenire la scomparsa dei nodi. Questa nuova memorizzazione \xc3\xa8 chiamata cache. I valori pi\xc3\xb9 popolari e ricercati avranno la possibilit\xc3\xa0 di essere distribuiti su pi\xc3\xb9 nodi in prossimit\xc3\xa0 del valore della chiave ricercata, evitando la concentrazione delle richieste su pochi nodi. In certe implementazioni la cache \xc3\xa8 a sua volta replicata da un processo iterativo nei nodi vicini a quello che detiene la cache, contribuendo cos\xc3\xac 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\xc3\xac alla rete di eliminare i valori non pi\xc3\xb9 aggiornati. Poich\xc3\xa9 anche al termine della richiesta anche il richiedente possiede il valore, se ne deriva che le richieste pi\xc3\xb9 popolari sono accelerate dalla disponibilit\xc3\xa0 dell\'informazione presso molti nodi._NEWLINE_Alcune implementazioni (KAD) non dispongono di meccanismi di replica e caching perch\xc3\xa9 \xc3\xa8 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_LOOCKUP e STORE). Quando tutti i nodi che posseggono il file lasciano la rete, l\'informazione non \xc3\xa8 pi\xc3\xb9 replicata e scompare dalla rete.\n_START_SECTION_\nEntrare nella rete\n_START_PARAGRAPH_\nUn 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\xc3\xa0 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\xc3\xa9 non lascia la rete._NEWLINE_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 \xc3\xa8 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\xc3\xb9 lontano del nodo di bootstrap dal nodo entrante.\n_START_SECTION_\nRicerca Accelerata\n_START_PARAGRAPH_\nKademlia calcola le distanze tra nodi utilizzando una metrica XOR. Il calcolo della distanza \xc3\xa8 effettuato eseguendo un\'operazione di XOR (OR esclusivo) tra due ID Nodo oppure tra un ID Nodo e una chiave: il risultato, in binario, \xc3\xa8 assunto come distanza._NEWLINE_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 \xc3\xa8 minore o uguale alla somma delle distanze tra A ed un punto C qualsiasi ed alla distanza tra C e B._NEWLINE_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 \xc3\xa8 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\xc3\xa0 molto minore dato l\'aumento delle prossibilit\xc3\xa0 di trovare un nodo nel proprio k-bucket che condivide molti bit oltre al proprio prefisso.'