Kademlia

Kademlia er en peer-to-peer nettverksprotokoll designet av Petar Maymounkov og David Mazières fra New York University for et desentralisert datanettverk.

Den spesifiserer strukturen til nettverket, regulerer kommunikasjonen mellom nodene og måten utvekslingen av informasjon skal utføres på. Kademlia-noder kommuniserer med hverandre ved hjelp av UDP -transportprotokollen .

Bruk i fildelingsnettverk

Kademlia brukes av mange fildelingsprogrammer fordi det er basert på tabeller distribuert på nettverksnoder uten sentrale servere . Nøkkelordsøk kan utføres på Kademlia for å finne den søkte filen og oppgaven med å lagre indeksen til eksisterende filer er delt likt mellom alle klienter . Noden som eier en fil som den ønsker å dele, analyserer den og beregner et hashnummer som vil identifisere den filen på fildelingsnettverket. Hashes og ID-er må være like lange.

Noden søker i alle andre noder etter den som har IDen med kortest avstand fra filhashen, og lagrer IP-adressen på den noden. Klienten som starter søket vil bruke Kademlia til å søke etter klient-ID-en som har minimumsavstanden fra hashen til filen den leter etter, deretter vil den hente listen over kontakter (dvs. IP-er) som er lagret i den noden. Kontaktene som er lagret på nettverket endres hele tiden ettersom noder kobles til og fra. Takket være en iboende redundans av informasjon om Kademlia blir disse kontaktene replikert i forskjellige noder.

Funksjoner

Kademlia er basert på Distributed Hash Table (DHT) teknologi. På et eksisterende LAN / WAN (som Internett ) opprettes et nytt virtuelt nettverk der hver node identifiseres med et nummer ("node-ID"). Dette nummeret brukes ikke bare for å gjenkjenne en node, men Kademlia-algoritmen bruker det til å finne verdier (for eksempel hash-koden til filnavnet eller et nøkkelord / nøkkelord) da node-IDen lar deg kartlegge verdiene som må lagres.

Nettverket definerer et avstandsbegrep som gjør det mulig å etablere nærheten mellom to noder slik at gitt en node "A" er det alltid mulig å bestemme om en node "B" er nærmere enn en node "C". Hver node har en kunnskap om Kademlia-nettverket som avtar når avstanden fra selve noden øker, og har derfor en svært detaljert kunnskap om nettverket i omgivelsene, en god kjennskap til mellomdistansenettverket og kun spredt kunnskap. av selve nodene, langt unna.

Kademlias formål er å lagre og hente verdier som kan være av hvilken som helst type, men som vanligvis er pekepinner til filer. Verdiene er indeksert med "nøkler". Node ID og Keys har samme format, så det er mulig å beregne avstanden nøyaktig som mellom to noder. Det følger at hver node er i stand til å beregne avstanden mellom seg selv og to nøkler "K1" og "K2", og forstå hvilken av de to som er nærmest. På samme måte er node "A" i stand til å bestemme hvilken av de to nøklene "K1" og "K2" som er nærmest en node "B". "A" og "B" stemmer alltid overens i denne beregningen.

For å lagre en verdi, anmodende node:

Når man leter etter en nøkkel, skanner algoritmen nettverket i påfølgende trinn og for hvert trinn kommer man nærmere og nærmere nøkkelen det søkes etter inntil noden som kontaktes returnerer verdien eller det ikke er flere noder å spørre etter. Antallet noder som kontaktes under søket avhenger bare marginalt av størrelsen på nettverket: Hvis antall deltakere i nettverket dobles, må en brukers node bare spørre en node til for hvert søk, ikke doble antallet den kontaktet. Før.

Ytterligere fordeler finnes spesielt i den desentraliserte strukturen som klart øker motstanden mot tjenestenektangrep . Selv om et helt sett med noder er målrettet vil det ha svært begrensede effekter på nettverket, som automatisk vil overvinne problemet ved å isolere nettverket rundt disse problematiske nodene.

Operasjonsdetaljer

Den første generasjonen av peer-to-peer-nettverk for utveksling av filer, som for eksempel Napster , var avhengig av en sentralisert database for å koordinere søke- og lagringsaktiviteter i nettverket. Den andre generasjonen, for eksempel Gnutella, utfører et massivt søk etter informasjon ved å spørre etter alle kjente noder i nettverket. Den tredje generasjonen bruker Distributed Hash Tables (DHT) for å søke etter filer på nettverket. DHT-er lagrer verdier (dvs. adressene til ressursene som skal deles) og gjør dem tilgjengelige for hele nettverket. Hovedmålet med disse protokollene er hastigheten i søket etter informasjon.

Kademlias algoritme er basert på beregning av avstanden mellom to noder. Avstanden beregnes som en XOR mellom to "Node IDer" og tar den resulterende verdien som et heltall. "Node ID" og "Keys" har samme format og lengde, slik at avstander mellom noder og mellom dem og nøkler kan beregnes på nøyaktig samme måte.

Avstanden som er beregnet på denne måten har ingenting med den geografiske avstanden å gjøre og to noder som er nær algoritmen kan lokaliseres i to forskjellige kontinenter.

Algoritmen fortsetter iterativt i søket etter nøkler gjennom nettverket, og nærmer seg resultatet med en bit for hvert trinn som tas. Det følger at et Kademlia-nettverk med noder vil kreve maksimalt n trinn for å finne noden som søkes.

Rutingtabell

Kademlia-adressetabellen består av en liste for hver bit av "Node ID" (dvs. hvis "Node ID" er 128 biter lang , vil noden beholde 128 av disse listene). Hver liste har mange oppføringer. Hver oppføring i listen inneholder informasjonen som er nødvendig for å finne en node; hoveddataene er IP-adressen, porten og "Node ID" til en annen node på nettverket. Hver liste tilsvarer en bestemt avstand fra noden. Nodene som havner i den n'te listen må ha minst den n'te biten forskjellig fra noden: de første n-1 bitene må være lik de til noden som vurderes. Dette betyr at det er mulig å nominere halvparten av nodene lengst fra noden som undersøkes for å fylle den første listen. Den neste listen kan bruke 1/4 av nodene i nettverket som er nærmere enn litt, og så videre.

Med en "Node ID" på 128 biter, kan hver node klassifiseres i en av 128 mulige avstander, en for hver bit av forskjell.

Når noder påtreffes i Kademlia-nettverket, legges de til adressetabelllistene. Dette skjer under søke- og lagringsoperasjonene og også under søkehjelpeaktivitetene på vegne av en annen node. Hver node som påtreffes vil være en kandidat for inkludering i listene. Det følger at kunnskapen om nettverket er veldig dynamisk, det gjør det mulig å holde oppdatert informasjon og gir motstand mot anomalier og angrep.

I Kademlia-litteraturen kalles listen k-bøtte , der k er en konstant verdi for hele nettverket (vanligvis k = 20). Hver k-bøtte er derfor en liste som inneholder opptil k oppføringer (i vårt tilfelle 20) som refererer til k noder k biter unna den betraktede noden.

Siden antallet mulige noder for en gitt k-bøtte avtar raskt med avtagende avstand, beskriver k-bøttene med laveste bit fullstendig nettverket som omgir noden. Siden antallet mulige node-ID-er er mye større enn noen mulig populasjon av noder som tilhører nettverket, vil noen k-bøtter tilsvarende korte avstander fra noden forbli tomme.

La oss vurdere nettverket som er representert i figuren på siden. Med n = 3 er den mulige "Node ID" 8, fra binær 000 til 111. I dette forenklede nettverket er det syv noder representert av sirklene nedenfor: noden under vurdering er seks og er representert av den svarte sirkelen ("ID node "= 110). Knuten med det sorte pannebåndet (og de andre også) har 3 k-bøtter. Nodene null, en og to (dvs. 000, 001 og 010) er kandidater som skal inkluderes i den første k-bøtten; node fire og fem (100 og 101) er kandidater som skal inkluderes i den andre k-bøtten; den tredje k-bøtten inneholder kun node syv. K-bøttene er omsluttet i grå sirkler. Hvis størrelsen på k-bøtten var 2 (k = 2), ville den første 2-bøtten inneholde bare to av de mulige nodene, den andre begge, mens den tredje ville ha bare én oppføring verdsatt.

Det er statistisk kjent at noder som har vært koblet til nettverket i lengst tid har større sannsynlighet for å forbli tilkoblet i lengre tid i fremtiden. På grunn av denne statistiske fordelingen velger Kademlia de lengste tilkoblede nodene som skal lagres i en k-bøtte. Dette øker kunnskapen om gyldige noder i fremtiden og gjør nettverket mer stabilt.

Når en k-bøtte er full og en ny node blir oppdaget for den aktuelle k-bøtten, er den minst nylig sett noden PING-to; hvis noden fortsatt er i live, settes den nye noden i en erstatningsliste (erstatningsbuffer). Erstatningslisten brukes bare hvis en node i en k-bøtte slutter å svare. Med andre ord, de nye nodene brukes bare når de gamle nodene slutter å svare.

Kademlia har fire meldinger:

  • PING - brukes til å bekrefte at en node er i live;
  • STORE - for å lagre et par (nøkkel, verdi) i en node;
  • FIND_NODE - for å søke etter noder; noden som mottar meldingen tilveiebringer de k nodene som er inneholdt i dens k-bøtte nærmest den "node ID" som søkes;
  • FIND_VALUE - som FIND_NODE, men hvis mottakeren har den nødvendige nøkkelen, leverer den verdien som tilsvarer nøkkelen i stedet for de k nodene.

Hver RPC-melding inkluderer en tilfeldig verdi generert av forespørselsinitiatoren. Denne verdien brukes for å sikre at svaret er relatert til spørsmålet som stilles.

Finne en node

Søket etter en node kan fortsette asynkront. Mengden av samtidige søk er angitt med α og er vanligvis tre. En node starter et søk ved å sende en FIND_NODE-forespørsel til nodene i k-bøtten som er nærmest "Node ID" som skal finnes. Når mottaksnodene mottar meldingen, søker de i k-bøttene sine og returnerer k-nøklene nærmest den ønskede noden. På grunnlag av de mottatte svarene oppdaterer søkeren sin svarliste, og lagrer kun de beste k svarene (dvs. k "Node ID" nærmest noden det søkes etter). På dette tidspunktet gjentar forespørselen forespørselen mot de nye resulterende nodene så lenge det ikke er ytterligere noder nærmere den søkte noden. Ettersom kunnskapen om nettverket rundt den søkte verdien i løpet av søket blir mer og mer presis, konvergerer algoritmen raskt mot "node-IDen" nærmest den søkte verdien.

Når ingen nærmere noder kan bli funnet, avsluttes søkealgoritmen ved å returnere k-verdiene nærmest den søkte noden (muligens inkludert selve noden, hvis den eksisterer).

Informasjonen i noden kan berikes med Round Trip Time eller RTT. Denne informasjonen vil bli brukt til å bestemme tidsavbruddet for forespørsler sendt til en bestemt node. Når en forespørsel blir tidsavbrutt, er det mulig å videresende en ytterligere forespørsel og dermed unngå å overskride antallet α av samtidige forespørsler.

Lokalisering av verdier

Informasjonen lokaliseres ved tilordning til en nøkkel. Denne kartleggingen foregår med en algoritme som beregner hashen til verdien og bruker den som en nøkkel. Lagringsnoden oppnådde verdien ved hjelp av en tidligere STORE-melding. Lokaliseringen av verdien gjøres ved å søke etter noden med "node ID" nærmest nøkkelen til verdien, med unntak av at søket avsluttes når en node er funnet som inneholder nøkkelen til den søkte verdien: i dette tilfellet den aktuelle noden returnerer verdien som tilsvarer nøkkelen.

Verdiene er lagret (redundante) i flere noder for å la hver enkelt node gå inn og ut av nettverket uten å påvirke driften. Med jevne mellomrom vil en node som lagrer en verdi skanne nettverket for de k nodene som er nærmest nøkkelen til verdien og vil replikere verdien til dem (ved hjelp av en STORE-instruksjon). Denne prosessen bidrar til å forhindre at nodene forsvinner. Denne nye lagringen kalles cachen. De mest populære og ettertraktede verdiene vil ha muligheten til å bli fordelt over flere noder i nærheten av verdien av nøkkelen som søkes, og unngå konsentrasjon av forespørsler på noen få noder. I noen implementeringer blir cachen i sin tur replikert av en iterativ prosess i nodene nær den som holder cachen, og hjelper dermed til å distribuere verdiene over nettverket. Informasjonen i hurtigbufferen slettes etter en viss tidsperiode avhengig av avstanden fra nøkkelen, slik at nettverket kan slette verdiene som ikke lenger er oppdatert. Siden rekvirenten også har verdien på slutten av forespørselen, følger det at de mest populære forespørslene akselereres av tilgjengeligheten av informasjon på mange noder.

Noen implementeringer (KAD-er) har ikke replikerings- og hurtigbuffermekanismer fordi det er viktig å slette utdatert informasjon umiddelbart. Bare noden som ønsker å dele filen sørger for periodisk oppdatering av informasjonen i nettverket (gjennom en NODE_LOOKUP og STORE operasjon). Når alle nodene som eier filen forlater nettverket, replikeres ikke informasjonen lenger og forsvinner fra nettverket.

Gå inn i nettverket

En node som ønsker å bli med i nettverket må først starte en prosess kalt bootstrap . I denne fasen må noden vite IP-adressen til en annen node (hentet fra brukeren eller fra en lagret liste) som allerede deltar i Kademlia-nettverket. Hvis noden som skal bootstrap aldri har deltatt i nettverket, beregner den et tilfeldig identifikasjonsnummer som ennå ikke er tildelt en annen node. Bruk denne ID-en til den forlater nettverket.

Den innkommende noden setter inn startnoden i en av k-bøttene, og fortsetter deretter til selvsøk. På denne måten lagres ID-en til den innkommende noden i k-bøttene til nodene som deltar i søket, mens svarene vil fylle ut k-bøttene med ID-ene til nodene inkludert i banen mellom bootstrap-noden og den innkommende. node. På dette tidspunktet fullføres prosessen med et søk etter en tilfeldig verdi lenger enn bootstrap-noden fra den innkommende noden.

Akselerert søk

Kademlia beregner avstandene mellom noder ved hjelp av en XOR-metrikk . Avstanden beregnes ved å utføre en XOR-operasjon (eksklusiv ELLER) mellom to node-IDer eller mellom en node-ID og en nøkkel: resultatet, i binært format, antas som en avstand.

For hver bit returnerer XOR-funksjonen 0 hvis de to bitene er like eller 1 hvis de to bitene er forskjellige. I XOR-metrikken forblir følgende trekantulikhet gyldig i klassisk geometri: avstanden mellom to punkter A og B er mindre enn eller lik summen av avstandene mellom A og et hvilket som helst punkt C og avstanden mellom C og B.

XOR-metrikken lar Kademlia utvide adresseringstabellene utover grensen for individuelle biter. Gruppe av biter kan grupperes i K-bøtter. For et gitt prefiks av m-bits vil det være 2m-1 k-bøtter. Den manglende k-bøtten er den videre utvidelsen av adressetreet som inneholder node-ID. Et m-bits prefiks reduserer antallet maksimale adressetabelloppslag fra log2 n til log2b n. Gjennomsnittlig antall søk vil være mye mindre gitt de økte sjansene for å finne en node i k-bøtten din som deler mange biter i tillegg til prefikset.

Programvare som bruker Kademlia

Den er for tiden implementert, på ulike nivåer og for ulike formål, i peer-to-peer-klienter:

Eksterne lenker