Kademlia

Kademlia – protokół komunikacyjny umożliwiający wyszukiwanie zawartości w sieciach takich jak P2P bez potrzeby używania centralnego serwera indeksującego zawartość sieci. Protokół ten oparty jest na algorytmie rozproszonej tablicy mieszającej. Z racji braku serwerów łączenie z siecią realizuje się poprzez podanie adresu IP i portu jakiegokolwiek klienta już podłączonego do Kademlii (tzw. bootstrap).

Główną zaletą Kademlii jest jej decentralizacja – sieć sama organizuje się i dostraja, by osiągnąć najlepszą wydajność zależnie od liczby użytkowników i możliwości ich połączeń. Dzięki temu jest bardziej odporna na uszkodzenia w dużej skali.

Protokół Kademlia

Kademlia jest protokołem komunikacji w sieciach peer-to-peer implementującym rozproszone tablice mieszające. Zaprojektowany przez Petara Maymounkova i Davida Mazieresa w celu decentralizacji komputerowych sieci P2P. Struktura sieci w Kademlii jest reprezentowana przez drzewo binarne, w którym każdy węzeł – liść drzewa posiada swój unikatowy identyfikator określający jego pozycję w drzewie. Jest to jedna z wielu wersji systemów DHT.

Terminologia

Sieć Kademlia cechują trzy stałe: alfa, B i k. Pierwsza i ostatnia są standardowymi terminami. Druga jest wprowadzona, ponieważ niektóre implementacje Kademlii stosują różną długość klucza:

• element alfa – mała liczba reprezentująca stopień równoległych połączeń w sieci, zazwyczaj 3;
• element B – rozmiar w bitach (ilość bitów) kluczy identyfikujących węzły oraz przechowywane i otrzymywane dane; w podstawowej wersji Kademlii jest to 160, długość skrótu (hash) funkcji SHA-1;
• element k – maksymalna liczba kontaktów przechowywanych w jednym pojemniku, zazwyczaj 20.

Węzeł

Sieć Kademlia składa się z pewnej liczby współpracujących węzłów, które komunikują się między sobą oraz przechowują o sobie informacje. Każdy węzeł posiada nodeID – pseudoniepowtarzalny numer binarny, który identyfikuje i określa miejsce węzła w sieci. Węzeł to najprościej mówiąc użytkownik sieci, stacja robocza, na której uruchomiona jest aplikacja obsługująca dany protokół sieciowy, w tym przypadku Kademlię. Oprócz adresu IP węzeł posiada klucz, na podstawie którego może zostać rozpoznany i odnaleziony w sieci. W obrębie sieci blok danych (wartość) może być również skojarzony z ciągiem binarnym o ustalonej długości B (klucz wartości). Węzeł, potrzebując wartości, szuka jej na węzłach najbliższych kluczowi. Węzeł, potrzebując zachować wartość, przechowuje ją na węzłach najbliższych kluczowi.

ID węzła (nodeID)

Komputery w sieci są identyfikowane za pomocą adresów IP oraz kluczy określających ich położenie w Kademlii. ID węzła (nodeID) jest liczbą binarną o długości B=160 bitów. W podstawowej wersji Kademlii każdy węzeł wybiera swoje ID według bliżej nieokreślonej pseudolosowej procedury. Ważne jest, aby każdy nodeID był unikatowy i jednakowo rozproszony – projekt sieci właśnie na tym polega.

Klucze

Dane przechowywane w Kademlii są określane jako wartość, przypisane do odpowiedniego klucza. Wynika to z właściwości rozproszonych tablic mieszających. Dane przechowywane lub otrzymywane z sieci muszą posiadać klucz o długości B. Pary <klucz,wartość> tak jak ID węzłów również powinny być jednakowo rozproszone. Istnieje kilka sposobów, które mogą to zagwarantować. Najbardziej popularnym jest utworzenie skrótu, za pomocą bezpiecznej funkcji haszującej SHA-1. Pary <klucz,wartość> są przechowywane na węzłach, których ID jest najbliżej klucza.

Dystans: metryka XOR

Działanie Kademlii oparte jest w dużym stopniu na użyciu operacji XOR (eXclusive OR) jako metryki. Dystans pomiędzy kluczami lub ID węzłów np. x i y jest definiowany następująco: dystans(x,y) = x ^ y, gdzie ^ reprezentuje operator XOR. Rezultat jest otrzymywany z wykonanej operacji XOR na każdym bicie argumentów. Jest to najważniejsza operacja protokołu Kademlia odpowiedzialna za poprawne określanie bliskości między węzłami oraz kluczami a węzłem.

Tablica prawdy XOR

a	b	a XOR B
0	0	0
0	1	1
1	0	1
1	1	0

k-pojemnik (k-buckets)

Węzły w Kademlii organizują swoje kontakty, o których wiedzą inne węzły, w pojemniki, które przetrzymują maksymalnie k kontaktów. Są to tak zwane k-pojemniki. Pojemniki są organizowane na podstawie dystansu pomiędzy węzłem a kontaktami w pojemniku. Dla każdego pojemnika i, 0 ≤ i < B, gdzie (B=160) węzeł przechowuje listę trójek <adresIP,portUDP,IDwęzła>. W każdym z tych pojemników węzeł przechowuje kontakty o dystansie znajdującym się w zakresie 2i ≤ dystans(węzeł,kontakt) < 2i+1 od siebie samego. Daje to bardzo dużą przestrzeń adresową. Generalnie dla małych wartości i pojemniki będą puste, gdyż węzeł o odpowiednio małym dystansie nie będzie istniał. Dla dużych wartości i pojemnik może przechowywać do k kontaktów.

Wewnątrz pojemników, kontakty są sortowane według czasu ostatniej komunikacji. Kontakty, które najczęściej komunikują się z naszym węzłem, są zapisane na końcu listy odpowiedniego pojemnika, a te które najrzadziej się komunikują, przechowywane są na początku takiej listy w pojemniku.

Rozmiar pojemnika

W Kademlii stała k jest ustawiona na wartość 20, przy której jest wielce nieprawdopodobna, że w dużych sieciach kontakty w każdym pojedynczym pojemniku mogą zniknąć w przeciągu godziny. Próbując obliczyć takie prawdopodobieństwo, powinno się wziąć pod uwagę politykę, która prowadzi do tego, że kontakty o długiej żywotności przechowywane w tablicy, są preferowane jako bardziej aktualne kontakty. k jest systemową wartością protokołu sieciowego Kademlia.

Kontakty

Kontakty w Kademlii są przechowywane w postaci trójki następujących elementów:

• ID węzła – nodeID
• adres IP
• port UDP

Projektanci Kademlii nie wzięli pod uwagę użycia adresów IPv6 czy protokołu TCP/IP zamiast UDP oraz możliwości, że węzeł może posiadać wiele adresów IP. W Kademlii jest ważne w miarę szybkie przesyłanych komunikatów między węzłami. W tym celu używany jest bezpołączeniowy protokół komunikacji UDP. Jest to protokół bezpołączeniowy, więc nie ma narzutu na nawiązywanie połączenia i śledzenie sesji (w przeciwieństwie do TCP). Nie ma też mechanizmów kontroli przepływu i retransmisji danych. Korzyścią płynącą z takiego uproszczenia budowy jest większa szybkość transmisji informacji i brak dodatkowych zadań, którymi musi zajmować się użytkownik posługujący się tym protokołem.

Protokół

Oryginalna dokumentacja Kademlii mówi, że protokół posiada cztery zdalne procedury połączeniowe (RPCs – Remote Procedure Calls) PING, STORE, FIND_NODE, FIND_VALUE, ale także specyfikuje inne procedury, które muszą nastąpić podczas ich wywołania, jako pewien inny protokół. Dobrze jest dodać te procedury i inne protokoły do tego co nazywamy protokołem Kademlia. Podczas komunikacji w sieci, każdy węzeł wysyłając komunikat RPC lub dowolny inny, dostarcza informacje o sobie jego odbiorcy w postaci adresu IP, portu UDP oraz ID węzła.

PING

Ta procedura RPC pociąga za sobą to, że jeden węzeł wysyła komunikat PING do innego węzła, który przypuszczalnie odpowie komunikatem PONG, jeżeli jest aktywny. Procedura ma dwuskładniowy efekt: odbiorca wiadomości PING musi zaktualizować pojemnik odpowiadający nadawcy i jeżeli jest odpowiedź, nadawca musi zaktualizować właściwy pojemnik dla odbiorcy. Wszystkie pakiety procedur RPC wymagają tego, aby zawierały identyfikator węzła przypisany przez nadawce. Jest to pseudolosowa liczba o długości B (160-bitów). Musi również istnieć możliwość odpowiedzi zwrotnej na komunikat PING za pomocą procedury RPC, aby wymusić albo zezwolić inicjatorowi – nadawcy procedury RPC – dostarczenie dodatkowych informacji do jego odbiorcy. Może to być inny adres IP lub zestaw adresów IP albo preferowany protokół do dalszej komunikacji. Komunikat jest wykorzystywany podczas dodawania kontaktów do pojemnika oraz przy połączeniu startowym – Bootstrap.

STORE

Nadawca komunikatu RPC STORE dostarcza klucz i blok danych (para <klucz,wartość>) oraz wymaga, aby odbiorca przechował dane i uczynił je dostępnymi dla późniejszych wyszukiwań według klucza. Jest to podstawowa operacja udostępniania danych w sieci Kademlia, nieiteracyjna.

FIND_NODE

Procedura FIND_NODE jako parametr przyjmuje 160-bitowy klucz – ID szukanego węzła. Odbiorca komunikatu zwraca do k kontaktów w postaci trójek <adres IP, port, nodeID>, o których wie, że są one najbliższe kluczowi. Odbiorca musi zwrócić k trójek, jeśli jest to możliwe. Może zwrócić mniej niż k kontaktów, jeżeli tylko zwraca wszystkie kontakty, o których wie. Jest to podstawowa operacja wyszukiwania węzłów, a co za tym idzie zasobów w sieci Kademlia, nieiteracyjna.

FIND_VALUE

Procedura FIND_VALUE jako parametr przyjmuje 160-bitowy klucz szukanej wartości. Jeżeli odpowiadająca kluczowi wartość jest obecna u odbiorcy, to skojarzone z nią dane są zwracane do inicjatora procedury. W przeciwnym razie procedura jest równoznaczna do FIND_NODE i zwracany jest zestaw k najbliższych kontaktów szukanemu kluczowi. Jest to podstawowa operacja wyszukiwania zasobów w sieci Kademlia, nieiteracyjna.

Oprogramowanie P2P wykorzystujące Kademlię

• VarVar – pierwszy klient obsługujący Kademlię
• Sieć overnet: overnet (obecnie zintegrowany jako eDonkey2000), eDonkeyHybrid, mlDonkey
• Sieć Kad: eMule (od wersji 0.42), mlDonkey (od wersji 2.5-28), aMule (od wersji 2.1.0)
• RevConnect – klient Direct Connect poszerzony m.in. o Kademlię

Poszczególne sieci nie są ze sobą kompatybilne.

Bibliografia

• Petar Maymounkov, David Mazieres: Kademlia: A Peer-to-peer Information System Based on the XOR Metric.
• Kademlia: A Design Specification.

Linki zewnętrzne

• Opis działania algorytmu Kademlia. cs.rice.edu. [zarchiwizowane z tego adresu (2005-12-11)]. (ang.)