DHT

Überblick

Der Kademlia-Algorithmus wurde 2002 an New York University von Petar Maymounkov and David Mazieres entwickelt. Es handelt sich um die Implementation einer "Distributed Hash Table", sie baut ein selbstorganisierendes, strukturiertes P2P-Netz auf und regelt Kommunikation und Austausch zwischen den Netzwerkknoten.
Dabei wird ein sehr effizientes Vorgehen angewendet, so daß verhältnismäßig wenig Overhead entsteht.

Schlüssel-Wert-Paare

Das besondere Kennzeichen von Kademlia ist der gemeinsame virtuelle Adreßraum für Knoten-IDs und Schlüssel mit 160 Bit Breite. Damit eine Information im Netzwerk gefunden werden kann, wird ihr Hashwert (der Schlüssel) als Schlüssel-Wert-Paar auf mehreren Knoten mit einer zum Schlüssel ähnlichen ID gespeichert. Ein Knoten, der den dort gespeicherten Schlüssel sucht, kann das den Wert des Schlüssel-Wert-Paars enthalten und anhand dessen bestimmen, von welchem Netzwerkknoten er die Information erhalten kann.

XOR-Metrik

Als Abstandsfunktion wird das bitweise XOR verwendet. Da Schlüssel und Knoten-IDs auf dem gleichen Raum definiert sind, kann auch der Abstand eines Schlüssels von einer Knoten-ID ermittelt werden.

  Abstand(Argument_1, Argument_2) = Argument_1 XOR Argument_2

z.B.:

  1011 XOR 1000 = 0011

Das Ergebnis dieser Operation wird als Abstand aufgefaßt.
Die Verwendung der XOR-Funktion bedingt dabei, daß unterschiedliche niederwertige Bits der Operanden sich weit weniger auf den Abstand auswirken als höherwertige Bits - daher werden Knoten mit ähnlichen Knoten-IDs im Netzwerk Nachbarn sein.

Routingtabellen: "k-Buckets"

Bekannte Knoten werden in Kademlia als Listen gehandhabt. Hierzu wird der Adreßraum in Intervalle von je $2^{i}$ bis $2^{i}+1$ mit $0<=i<160$ zerlegt, jeder Knoten führt also 160 solche Listen, um den ganzen Adreßraum erfassen zu können.
In einer solchen Liste ist jeweils Platz für "k" viele Tupel aus (IP-Adresse, UDP-Port und Node-ID), wobei jedes Tupel einen Knoten des Netzwerks beschreibt. Die Liste ist nach dem letzten Kontaktzeitpunkt mit dem jeweiligen Tupel sortiert, die jüngsten Kontakte stehen dazu am Ende der Liste.
"k" ist ein systemweiter Parameter, der so gewählt werden sollte, daß ein Ausfall aller Knoten einer solchen Liste innerhalb von einer Stunde sehr unwahrscheinlich ist, in der Praxis ist $k=20$ ein Richtwert.
Aus diesem Aufbau ergibt sich, daß ein Knoten über ein hohes Wissen über seine Nachbarn verfügt, aber über nur wenige Knoten, die sehr weit von ihm entfernt sind, kennt.

Um diese Listen stets aktuell zu halten, werden aus dem Netzwerk eingehende Nachrichten zur Aktualisierung der "k-Buckets" verwendet.

Rest-Container

Hohe Verbreitung (Overnet, eMule, BitTorrent, …) Eigenschaften gut formal nachweisbar