Opracowany przez | Petar Maymounkov i David Mazières |
---|---|
Pierwsza wersja | 2002 |
Środowisko | Niezależny |
Rodzaj | Tabela haszowania |
Kademlia (kad) to rozproszona sieć typu overlay z tablicą skrótów dla sieci peer-to-peer (P2P). Zaprojektowali go Petar Maymounkov i David Mazières w 2002 roku.
Protokół określa strukturę sieci Kademlia, komunikację między węzłami i wymianę informacji. Węzły komunikują się za pomocą UDP (patrz model OSI ).
W ramach istniejącej sieci ( Internet ) Kademlia tworzy nową sieć, w której każdy węzeł jest identyfikowany za pomocą numeru identyfikacyjnego, identyfikatora (160- bitowego numeru binarnego ).
Po fazie zalewania, polegającej na skontaktowaniu się z węzłem sieci, a następnie uzyskaniu identyfikatora, operator matematyczny oblicza „odległość” między dwoma węzłami i odpytuje kilka węzłów na podstawie tej „odległości” w celu znalezienia poszukiwanych informacji. Operator ten, będący wyłącznym OR , zwany także XOR, umożliwia użycie pojęcia odległości między dwoma węzłami, które dają wynik w postaci liczby całkowitej : „odległość”. Ta ostatnia nie ma nic wspólnego z położeniem geograficznym uczestników, ale modeluje odległość w łańcuchu identyfikatorów. Może się więc zdarzyć, że węzeł w Niemczech i węzeł w Australii są „sąsiadami”.
Informacje w Kademlia są przechowywane w „wartościach”, a każda wartość jest przypisana do „klucza”. O Kademlii mówimy, że jest to sieć <wartość, klucz>.
Zestaw kluczy zarządzanych przez węzeł jest powiązany z adresem tego węzła; w ten sposób znając klucz algorytm może określić przybliżoną odległość, jaka dzieli go od węzła mającego wartość skojarzoną z tym kluczem. Aby znaleźć klucz znajdujący się w węźle N, węzeł A będzie szukał sąsiada B z Odległość (B, N) <Odległość (A, N) i zapyta go o informacje; jeśli ten ostatni go nie ma, skontaktuje się z sąsiadem znajdującym się bliżej klucza i tak dalej, aż do uzyskania wartości klucza (lub do momentu, gdy będziemy pewni, że ten klucz nie istnieje). Rozmiar sieci nie wpływa znacząco na liczbę węzłów, z którymi nawiązano kontakt podczas wyszukiwania; jeśli liczba uczestników sieci podwoi się, węzeł użytkownika musi zażądać informacji tylko od jeszcze jednego węzła.
Inne zalety są nieodłącznie związane ze zdecentralizowaną strukturą, na przykład zwiększona odporność na atak typu „odmowa usługi”. Nawet jeśli zanurzony zostanie cały rząd węzłów, będzie to miało ograniczony wpływ na dostępność sieci, która „zszyje” sieć wokół tych dziur.
Protokół Kademlia jest używany przez kilku klientów peer-to-peer (sieci są ze sobą niekompatybilne):
Niektóre programy używają protokołu Kademlia w izolacji: