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:
- ist der Absenderknoten bereits in den "k-Buckets" vorhanden, wird er in seiner Liste an das Ende der Liste sortiert
- ist der Absenderknoten noch nicht in den "k-Buckets" vorhanden und ist das entsprechende Bucket noch nicht voll, wird der Knoten am Ende der Liste eingefügt
- ist der Absenderknoten noch nicht in den "k-Buckets" vorhanden und ist das entsprechende Bucket voll, wird der am Kopf der Liste stehende Knoten angepingt. Reagiert dieser nicht, wird der neue Knoten am Ende der Liste eingefügt - andernfalls wird der neue Knoten verworfen.

Dieses Verfahren bietet einen gewissen Schutz gegen "einfache" Denial-Of-Service-Angriffe, da dem Knoten bekannte Knoten bei Flutung mit Nachrichten nicht verworfen werden, bis diese tatsächlich das Netzwerk verlassen.

Operationen

Kademlia kommt mit vier Operationen aus:

  PING

-> Dient lediglich der Ermittlung, ob ein Knoten online ist

  FIND_NODE

-> Ermitteln der "k" nächsten Knoten zu einer Knotenadresse

  FIND_VALUE

-> Suche und Abfragen des Wertes aus dem Schlüssel-Wert-Paares zu einem Schlüssel

  STORE

-> Abspeichern eines Schlüssel-Wert-Paares auf einem Knoten

Knotensuche mit FIND_NODE

FIND_NODE ermittelt die "k" nächsten Knoten zu der übergebenen Knoten-ID. Dazu werden aus dem passenden "k-Bucket" die "i" nächsten Knoten parallel angefragt. Diese liefern ihre zur gesuchten Knoten-ID "k" nächsten Tupel aus ihren "k-Buckets" an den Anfrager zurück, wobei diese bereits näher an der gesuchten Knoten-ID als sie selbst liegen.
Der Anfragende wiederholt dieses Verfahren, bis in einem Durchlauf keine weitere Annähernung an den gesuchten Knoten mehr erreicht werden kann und schickt an diesem Punkt noch abschließend "k" Anfragen an die nächsten Knoten, die er noch nicht angefragt hat.
"i" ist für dieses Verfahren ein systemweiter Paramter, der in der Praxis mit $i=3$ angegeben ist.

Rest-Container

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