DIPARTIMENTODIINGEGNERIADELL'INFORMAZIONE
CORSO DILAUREATRIENNALE ININGEGNERIADELL'INFORMAZIONE
TESI DI LAUREA
PARIKAD: KAD ROUTING TABLE
RELATORE: Ch.mo Prof. Eno h Peseri o Ste hini Negri De Salvi
CORRELATORE: Ing. Paolo Bertasi
LAUREANDO: Christian Pi olo
Anno A ademi o 2009-2010
per le matite e i olori.
Kad è indubbiamente una delle po he DHT he si è estesa su una osì ampia
s ala, an he grazie alla sua integrazione in programmi di le sharing di grande
su esso quali eMule/aMule eMLDonkey: ogni giorno Kad hapiù di1,5 milioni
diutenti onnessi simultaneamente.
L'obiettivodiquestatesièquellodides rivereindettaglioilfunzionamentodella
struttura dati he sta alla base della rete Kad; si farà in parti olare riferimento
alprogetto PariKad, ilquale implementainJava una rete Kad sviluppata peril
progetto PariMulo diPariPari[1℄. La strutturadati allabase diPariKad sibasa
fedelmente sull'implementazionediKad in eMule 0.49 [2℄.
Sommario v
1 Introduzione: il progetto PariPari 1
2 Ar hitettura Kad 3
2.1 Network Proto ol . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Spazioa 128-bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Routing Table 8 3.1 Int128 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 KadConta t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2.1 GeoLo ator . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3 RoutingBin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.4 RoutingZone. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.4.1 Struttura della RoutingTable . . . . . . . . . . . . . . . . 15
3.5 Taskdi Mantenimento . . . . . . . . . . . . . . . . . . . . . . . . 19
3.5.1 OnSmallTimer . . . . . . . . . . . . . . . . . . . . . . . . 20
3.5.2 OnBigTimer . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.5.3 Consolidate . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4 PariKad 22 4.1 Thread prin ipale . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.2 Sviluppi futuri. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2.1 Vulnerabilità della rete Kad . . . . . . . . . . . . . . . . . 23
5 Con lusioni 25
A Relazione PariKad - eMule 26
Bibliogra a 27
Elen o delle gure 28
Elen o delle tabelle 29
Introduzione: il progetto PariPari
PariPari è un progetto ambizioso, portato avanti dagli studenti dell'Università
di Padova, il quale ha ome obiettivo la reazione di un software libero s ritto
in Java, he raggruppi al suo interno appli azioni di le-sharing, messaggisti a,
video onferenza e permettaall'utentedi usufruire di interessanti servizi tra ui
quellidi WebServer, DBMS 1
eDHT 2
.
L'idea innovativadiquesto progetto èquelladifar gestiredaun'appli azione
uni a molti programmi he utilizzano Internet e he, no adora, hanno sempre
lavoratoinmodoindipendentel'unodall'altro. Il neèquellodiutilizzarelarete
nelmodo più e iente: l'utente nale potrà, adesempio, parlare uidamente in
video onferenza,s ari aremolti ledallareteeDonkeye hattare onsuoiami i,
senzadovere perforzainterrompereunadiqueste treattività, omespessoinve e
a ade on le appli azioni attuali.
PariPari è suddiviso in diversi plugin ognuno dei quali ri opre un ompito
pre iso e permette il funzionamento di altri plugin o estende nuove funzionalità
al programma. Il plugin PariMulo, in parti olare, si o upa di riprodurre un
lient eMule permettendo di eseguire ri er he nella rete eDonkey per s ari are e
ondividere le.
In questo ontesto siinseris eil nostrolavoro; PariMulo,infatti,non suppor-
tava no adora l'utilizzo della rete Kad per la ri er a e la pubbli azionedi le.
Ladierenzasostanzialetralarete eDonkeyelarete Kadstanelfatto he, men-
tre la primaè una rete entralizzata, la se onda èuna rete de entralizzata. Kad
1
DatabaseManagementSystem
2
DistribuitedHashTable
sfrutta la potenza di tutti gli utenti onnessi a questa rete per ondividere le e
funzionareininterrottamente, senza doverdipendere daun uni o server entrale.
L'integrazione della rete Kad nel plugin di PariMulo ha portato alla nas ita
di PariKad. PariKad si può sostanzialmente dividere in due grossi blo hi:
una prima parte legata allo s ambio di messaggi tra utenti, ne essario per il
funzionamento globale di Kad, e una se onda parte he si o upa di gestire la
struttura dati, tenendo organizzati i ontatti della rete. Questa tesi si pre gge
ome obiettivoquellodi des rivere inmodoesauriente quest'ultimo punto.
Ar hitettura Kad
L'obiettivodiquesto apitoloèquellodispiegarei on etti hestannoallabasedi
ogniDHT(DistributedHash Table)tra uiKad, unaDHTusataperretipeer-to-
peer eideatadaPetar Maymounkov eDavidMazièresdellaNew YorkUniversity
[4℄. É ne essario introdurre al unitermini fondamentali:
• peer: un punto di onnessionenella rete Kad.
• lient: un'appli azione (peresempio ome eMule/aMule) in gradodi on- nettersialla rete Kad; il omputer su uiviene eseguitaquest'appli azione
risulteràessere un peer.
• hash ID:si intende un valore a128 bit(16 byte) he identi a inmaniera
quasi univo a qualsiasi oggetto nella rete Kad, siaesso un oggettopassivo
(keyword, le, et .) o un peer. Per i peer, l'hash ID è reato in maniera
pseudorandom all'avvio del lient, mentre per gli oggetti passivi si ottiene
attraverso il al olodel MD4 suparti olari aratteristi he dell'oggetto.
• nodo: si intendeuna parti olare zona nellarete Kad in ui tuttigliogget- ti/peerpresentihanno lostessohash ID; inogninodo ipossono esserepiù
peer e oggettipassivi he possiedono lostesso hash ID.
• onta t: un peer onos iuto he viene tenuto in memoriaegestito per usi
futuri.
Quindi un utente, he avvia il proprio lient eMule, fa sì he il suo omputer
diventi un peer della rete Kad. Appena questo peer si mette in ontatto on
altripeer della rete e viene a ettato, i suoi dati vengonoimmagazzinati ed esso
diventa un onta t per l'utente he ne hasalvato i dati.
Figura 2.1: rete entralizzata Figura2.2: rete de entralizzata
Ipuntidiforzadiuna DHTsonolade entralizzazione, ioèlapossibilitàdi
permetterelos ambioinformazionitravariutentisenzal'usodiunserver entrale
di oordinamento( gura2.1e 2.2), las alabilità,la qualepermetteallarete di
funzionare e ientemente on entinaia o milioni di nodi, e lastabilità, poi hé
la ontinua onnessione di nuovi peer, la loro dis onnessione dalla rete e i loro
problemidi omuni azionenon in ianoil funzionamentoglobale dellaDHT. Ne
onsegue he unabuonaDHTdevefornireunottimometodoperfare omuni are
ivari lienttradiloroeun'e ientestruttura dati he permettadimemorizzare
i ontattied eseguire velo emente azioni ome lari er adi le, keyword, et .
Questatesi nonhalos opodispiegareilme anismodi omuni azioneusato
tra i vari peer nella rete Kad, tuttavia si è s elto di riportare, per ompletezza,
una breve e sempli espiegazione ariguardo.
2.1 Network Proto ol
Kad usa il proto ollo UDP per gestire le omuni azioni tra i vari peer. Il pro-
to ollo UDP permette di s ambiare messaggi in maniera molto velo e, on un
minimo overhead e senza la ne essità di eseguire un handshake prima dell'inizio
della omuni azione. Se un lient A vuole inviare un messaggio ad un suo on-
tatto B, è su iente he A invii il pa hetto all'indirizzo IP di B alla porta in
ui B è in as olto per i pa hetti UDP. Se B è attivo, allora legge il messaggio
e se opportuno risponde, altrimenti A, non ottenendo repli he, può de idere di
mandare il suo messaggio adaltri lient, he forse sono in grado disoddisfare la
sua ri hiesta.
Risulta evidente he uno dei primi problemi he Kad deve gestire è ome
permettere ai vari lient di rendersi onto he un loro ontatto si è dis onnesso
dalla rete. La soluzione sempli e ed e a e è quella di usare un timer, il quale
va a veri are dopo ogni intervallo di tempo prestabilito se il ontatto è an ora
attivoattraverso uno s ambiodi pa hetti UDP ditipoPING/PONG(se arriva
unpa hettoPINGbisognarispondere onunpa hettoPONG).Sedopoal une
volte hesiè er atodi omuni are on il ontattoesso ontinuaanonrispondere
sipro ede allasua eliminazionedallanostra RoutingTable, lastruttura dati he
sio upadi gestire inostri ontatti.
Ogni pa hetto UDP inviato nella rete Kad è ontraddistinto dal primo by-
te hiamato ID. eMule/aMule osì ome PariKad utilizzano il byte 0xE4 per
pa hetti standard e 0xE5 per pa hetti ompressi. Il byte su essivo de nis e
inve e la funzione he ha quel pa hetto, ioè se è un pa hetto per ri hiedere
le, per omuni arequal osa, o altro. I byte he seguono dipendonoovviamente
dapa hetto apa hetto.
Per ompletezza è importante ri ordare he negli ultimi anni eMule ha svi-
luppatouna te ni a hiamataProto ol Obfus ation he ha l'obiettivodi riptare
ipa hettiinus ita (ede riptarequelliinentrata) osi hé gliISP 1
nonsiano in
grado di blo are i pa hetti della rete Kad 2
. Di onseguenza, ilpa hetto rip-
tato non inizia più on i byte 0xE4 o 0xE5, ma sembra una sequenza asuale di
byte. Tuttaviaquestopa hetto,unavoltade riptato,tornaadaverelastruttura
lassi asopra des ritta.
Un lient della rete Kad è quindi aratterizzato da due porte utilizzate per
funzioni diverse. Una porta UDP he è utilizzata per s ambiare messaggi re-
lativi a operazioni standard (ri er a, pubbli azione le, ...) e di mantenimento
(ping/pong, pa hetti dihello, ...) e una porta per pa hetti TCP utilizzataper
1
InternetServi eProvider.
2
Il tra o generato da programmi peer-to-peer viene infatti spesso blo ato per evitare
rallentamentisullareteInternetglobale.
s ari are e ondividere i propri les on si urezza. eMule usa ome standard la
porta UDP 4672e TCP 4662, maquesto valore può essere ambiato dall'utente.
2.2 Spazio a 128-bit
Ogni hash ID in Kad è di 128 bit, per questo si aerma he il proto ollo Kad
è aratterizzato da uno spazio a 128 bit, infatti iò omporta he è possibile
ollo are in maniera univo a no a 2128 ≃ 3.40 ∗ 1038 oggetti dierenti (è un
numeromolto grandesesitienepresente he l'universoosservabile ontiene ir a
7 ∗ 1022 stelle). Ogni utente he vuoleparte ipare allarete deve rearsiun valore random a 128 bit he in seguito rappresenterà il suo lient ID; an he ogni le
o keyword presente in Kad deve ottenere un ID a 128 bit, in modo he possa
ollo arsi in un punto pre iso della rete. In aggiunta a iò, tutti gli oggetti
passivi devono an he trovare un hostpeer nelle vi inanze he sio upidigestirli.
Éimportante omprendere n dasubito he lientvi inigeogra amentepos-
sono non esserlo nella rete Kad evi eversa. Dal momento he il lient IDsi può
interpretare omel'indirizzo he un lients egliediavere nella propriareteKad,
può a adere he due lient diversi generino due valori random a 128 bit molto
vi ini tra loro e he, quindi, la loro distanza possa risultare molto pi ola. In
metafora possiamo dire he questi due lient si ritroveranno ad essere vi ini di
asa nel mondo virtuale diKad.
A questo punto è ne essario spiegare in he modo al oliamola distanza tra
peere/ooggetti,omeglio, ome al oliamoladistanzatradueIDa128bit,siano
essi asso iati a un peer o adun oggetto passivo. Per far iò Kad si avvale della
metri aXOR(simbolo⊕). Siriporta latabelladiveritàdella metri aXOReun
esempiopermeglio omprenderne il funzionamento.
A B A ⊕ B
0 0 0
0 1 1
1 0 1
1 1 0
Tabella 2.1: tabella diverità XOR
110100110 HASHID A
010101001 HASHID B
100001111 A⊕B
Tabella 2.2: distanza al olata tra due hash
ID se ondolametri a XOR
Come verranno gestiti i ontatti on i loro ID è oggetto di dis ussione nel
prossimo apitolo, il qualespiegherà indettaglio le aratteristi he della Routing
Table diKad.
Routing Table
LaRoutingTablerappresentail uoredellareteKadpoi héessatieneinmemoria
tutte leinformazioniriguardantii ontatti epermettedieseguire rapideri er he
sudiessi,trovandoquelli he piùadattisu uieseguiredeterminati ompiti,quali
lari er a diun le, di una keyword o dialtri ontatti.
Perdes rivere ilfunzionamentodellaRoutingTablesiutilizzeràun appro io
buttom-up; verranno ioè introdotte per prime le lassi più sempli i he stan-
no alla base e si andrà via via ostruendo la struttura dati on lassi sempre
più omplesse. Le spiegazioni faranno spesso riferimentoalle lassi, ai metodi e
alle variabili Java usate in PariKad, ma iò non limiteràin al un modola om-
prensione del funzionamento della Routing Table an he a hi non padroneggia
Java.
Le informazioni he verranno di seguito spiegate sono state ri avate in gran
parte dalla lettura del odi e sorgente di eMule 0.49 , he rappresenta l'uni a
fonte seria e a dabile per poter omprendere appieno il funzionamento della
rete Kad ed inparti olare della sua struttura dati. I numerosido umenti he si
trovano in Internet sono inve e risultati spesso approssimativi o impre isi.
3.1 Int128
La lasseInt128.java, lapiùsempli eefondamentale dituttalastrutturadati,
è usata per rappresentare gli hash ID 1
dei peer, dei le e delle keyword. Questa
1
Nelseguitodellaspiegazionesi utilizzerannoin manierainter ambiabileleparole hashID
oInt128.
lasse he rappresentaun valore a128bit(16 byte)viene usataperrappresentare
moltevariabilied èquindi ne essario he sia e ientenel onsumo dimemoria.
Per implementare questa lasse si è sfruttata la lasse BitSet di Java, he
fornis elapossibilitàdi reareunarraydibitbooleani(trueofalse)didimensioni
apia ere ed è provvista diun metodoperfare loXORtra due BitSet.
tipo nome variabile des rizione
BitSet bitSet lasseJavausataperrappresentareunInt128
Tabella 3.1: variabili diInt128
La lasse Int128.java è stata quindi provvista di metodi he mappassero i
valori booleani true e false nei orrispettivi 1 e 0 2
(vedi tabella 3.2), oltre ad
al uni metodi he permettessero la sua rappresentazione in stringa binaria ed
esade imale,lo shiftdi un Int128 ealtre funzioni he tornavano utili.
indi e 0M SB 1 2 3 4 · · · 124 125 126 127LSB
Int128 1 0 0 1 1 · · · 1 0 1 0
BitSet true false false true true · · · true false true false
Tabella 3.2: relazione Int128 eBitSet
3.2 KadConta t
Ognipeerhaunalistadipeer onos iuti hiamati ontatti,iqualivengonoinseriti
nella RoutingTable.
La lasse KadConta t.java si o upa di gestire tutte le informazioni di un
ontatto. Essa è ompostaprin ipalmentedametodisetter/getter he permetto-
nodisettareoottenere ilvaloredelle sue variabili. Siriporta intabella3.3tutte
levariabilidi questa lasse on una lorobreve des rizione.
IlnostroInt128,usatoperottenerelavariabile onta tDistan e,viene reato
randomduranteil primo avvio di PariKad e salvato in un le, all'us ita dell'ap-
pli azione. Al su essivo avvio, si riutilizza il valore dell'Int128 re uperato dal
2
Adierenzadialtrilinguaggidi programmazionequaliC/C++,Javanonpermetteil ast
impli itodiunbyte/intinunbooleanonéilvi eversa
tipo nomevariabile des rizione
Int128 id hashID heidenti ail ontatto
Int128 distan e distanza tra il nostro Int128 e quello del
ontatto(distan e=nostroIDXORsuoID)
InetAddress ip indirizzoIP
byte type identi alabontàdel ontatto: range[0,4℄
byte kadVersion versionedelproto olloKad
int TCPPort portaTCP
int UDPPort portaUDP
long reationTime_millis quandoèstato reatoil ontatto
long expirationTime_millis indi a noaquandosipuò onsiderarevalido
ilvaloretypeimpostato
long lastTypeSetTime_millis quandoèstatoaggiornatoperl'ultimavoltail
typedel ontatto
KadUDPKey kadUDPKey hiaveutilizzataperinviarepa hettious ati
al ontatto
boolean IPVerified indi a sel'IPdel ontatto èstato ontrollato
erisultavalido
boolean re eivedHelloPa ket true se è giunto un pa hetto di HELLO da
questo ontatto,falsealtrimenti
boolean he kKad2 segnala se è già stato fatto un ontrollo per
veri areseil ontattosupportaipa hettidi
tipoKad2
Tabella 3.3: variabili diKadConta t
le;questo omportamento oerente onquellodieMuledovrebbeportareaduna
maggiorstabilità allarete Kad.
Delle variabili sopra riportate desidero spiegare in dettaglio la funzione di
kadVersion e type.
Il byte kadVersion identi a quale versione del proto ollo Kad utilizza il
ontatto. Il valore 0 signi a he il KadConta t utilizza la versione 1 di Kad,
mentreognialtrovaloremaggioredi0impli a heil ontattoutilizzalaversione2
diKad. Questadierenzaèmoltoimportantepoi hé laversionediKadutilizzata
determina quale tipo di pa hetti possono essere spediti, quali aratteristi he il
ontatto supporta, et .
Ilbytetype,inve e, permettedivalutarel'a dabilitàdiun ontatto. Appena
un ontatto è aggiunto gli viene assegnato il valore type=3. Periodi amente il
lient ontrollasequesto ontattoèan oraattivoelopromuoveodegradase ondo
laregola in tabella3.4.
type des rizione
4 il ontattodeveessere an ellato(ingenerepoi hénonèraggiungibile)
3 questoèilvaloreassegnatodidefaultai ontatti hesonoappenastatiaggiunti
allaRoutingTable
2 ontatti onos iutidamenodi1ora,ma hehannodimostratodiessereattivi
1 ontatti onos iutidamenodi2oremadapiùdi1orae hehannodimostrato
diessereattivi
0 ontatti onos iutidapiùdi2oree hehannodimostratodiessereattivi
Tabella 3.4: des rizionevariabile typediKadConta t
Il typedi un ontatto viene memorizzatoinun lealla hiusura dell'appli a-
zione, a n hé al su essivo avvio il nostro lient sappia n dasubito quali sono
i ontatti migliori he stanno onnessi allarete Kad dapiù tempo.
3.2.1 GeoLo ator
IlGeoLo atorèunafunzionalità heèstataaggiuntoalla lasseKadConta t.java
perpermetterle diri onos erea he nazioneappartengono isuoi ontatti. Cisiè
appoggiatiallalibreria javaInetAddressLo ator [8℄.
tipo nomevariabile
des rizione
HashMap<String,Integer> onta tsGeoLo ation
asso ia ad ogniNazione X il
numerodi ontatti heèinX
Tabella 3.5: variabile stati a diKadConta t
In teoria, eseguendoil GeoLo ator sumolti ontatti, sidovrebbe trovare una
distribuzione molto simile a quellapresente nell'arti olo [6℄. Si riporta in gura
3.1l'istogrammapresenteinquellapubbli azione, he èstatoottenuto attraverso
un'analisidiquasi tutti i ontatti presenti nella rete Kad il 30/08/2006.
0 0.05 0.1 0.15 0.2 0.25
GB PT AR KR TW US BR IL PL DE IT FR ES CN
DF
countries zone 0x91
zone 0xf4 full crawl
Figura 3.1: distribuzione geogra a deipeersdell'intero spazio Kadal30/08/2006
3.3 RoutingBin
I KadConta t vengono a lorovoltainseriti indelle liste dimassimo 10KadCon-
ta t ias una (perquesto vengonode nite spesso 10-Bu ket), gestite dalla lasse
RoutingBin.java, la quale si o upa di tenerli ordinati se ondo un riterio di
tempo.
tipo nomevariabile des rizione
List<KadConta t> m_listEntries ontienealmassimo10KadConta t
Tabella 3.6: variabile diRoutingBin
Appena un ontattosidimostraattivo(harispostoaunadellenostreri hieste
o iha hiestoqual osa),vienespintoinfondoallalista. Inquestomodoi ontatti
più ve hi, in relazione alla nostra ultima omuni azione on loro, vengono a
trovarsi in ima alla lista, mentre quelli più nuovi in fondo (si veda a proposito
la tabella 3.7). Questo modo di gestire i ontatti permette di ottenere una rete
Kad più stabile, poi hé i KadConta t in ima alla listavengono periodi amente
ontattati per vedere se sono an ora attivi e dopo un determinato numero di
fallimenti vengono rimossi dalla nostra Routing Table (questo omportamento
verrà des ritto bene nella sezionerelativaai taskdi mantenimento 3.5).
