Kademlia

Kademlia ist ein Algorithmus zum Aufbau eines dezentralen Peer-to-Peer-Netzwerkes. Es legt Art und Aufbau des Netzes fest, reglementiert die Kommunikation zwischen den Nodes und wie der Austausch von Informationen stattzufinden hat. Grundlage von Kademlia sind das Internet Protocol und das darauf aufbauende, verbindungslose UDP Protocol.

Über einem bestehenden LAN/WAN (also z.B. auch dem Internet) wird ein neues, virtuelles Netzwerk aufgebaut, in dem jeder Node durch eine eindeutige Nummer ("Node-ID") identifiziert wird. Diese Nummer dient nicht nur zu seiner Identifizierung, sondern wird vom Kademlia-Algorithmus gleichzeitig für weitere Zwecke herangezogen.

Ein Node, der dem Netz beitreten möchte, muss zuerst einen "Bootstrapping" genannnten Prozes durchlaufen: In dieser Phase erhält der Algorithmus vom Benutzer (oder aus einer gespeicherten Liste) die IP eines Nodes, der bereits im Kademlia Netz bekannt ist. War der Node noch nie uvor im Netz, berechnet er so lange zufällige IDs bis er eine findet die noch nicht vergeben wurde. Diese verwendet er bis zum Verlassen des Netzes.

Kademlia dient vor allem dem Zweck des Filesharings, sprich des auffindens von Informationen im Netzwerk zum Download. Da es keine zentrale Instanz gibt, die eine Indexierung der vorhandenen Dateien übernehmen kann (wie z.B. bei eDonkey), wird diese Aufgabe auf alle Clients gleichermaßen aufgeteilt: Ein Node, der eine Information besitzt, errechnet zuerst eine eindeutige und immer gleich lange Bitsequenz, die diese Information charakterisiert (im folgenden "Hash" genannt). Die Länge der im Netz verwendeten Hashes und der Node-IDs muss gleich lang sein. Er sucht nun im Netz die Nodes, deren ID (in Bits gerechnet) die kleinste "Distanz" zum Hash aufweisen, und übermittelt ihnen seine Kontaktdaten.

Sucht ein Host genau diese Information, vollzieht er dieselbe Prozedur und gelangt dadurch an die Nodes, die gespeichert haben, wer im Netz diese Information besitzt. Der Suchende kann nun eine direkte Verbindung zur Quelle eingehen und die Information empfangen. Es ist also sichergestellt, dass der Suchende die Kontaktdaten der Quelle genau an der Stelle findet, wo diese sie hinterlassen hat. Da das Netz üblicherweise in ständigem Wandel begriffen ist, werden die Kontaktdaten auf mehrere Nodes verteilt und von der Quelle alle paar Stunden aktualisiert. (HINWEIS: Bei Filesharing-Tools ist eine "Information" im Regelfall eine Datei.)

Die oben genannte "Distanz" hat nichts mit geographischen Gegebenheiten zu tun, sondern bezeichnet die Distanz innerhalb des ID-Bereiches. Es kann (und wird) also vorkommen, dass z.B. ein Node aus Deutschland und einer aus Australien sozusagen "Nachbarn" sind. Die Distanz zwischen den Nodes im Kademlia-ID-Space wird durch die mathematische XOR-Funktion errechnet und beträgt immer log2(ID1 XOR ID2). Diese Vorgehensweise hat große Vorteile:

Beim Auffinden eines Nodes hangelt sich der Algorithmus intelligent immer näher an diesen heran, bis er gefunden wird oder ein Fehler zurückkommt. Die Anzahl der während dieser Suche maximal zu befragenden Nodes entspricht der Distanz dieses Nodes zu einem selbst. Sollte sich die Anzahl der Teilnehmer im Netz verdoppeln, so muss man nicht doppelt so viele Nodes befragen - sondern pro Verdoppelung nur einen Node mehr. Die benötigte Bandbreite skaliert also nicht linear mit der Größe des Netzes.

Weitere Vorteile liegen vor allem in der dezentralen Struktur, die die Resistenz gegen DDoS-Attackten deutlich steigert. Selbst wenn eine ganze Reihe von Nodes gefloodet wird hat das für das Netz selbst keine allzu großen Auswirkungen, mit der Zeit strickt sich das Netz dann um diese "Löcher" herum neu und das Problem ist gelöst.

Durch Optimierung lässt sich die für das Protokoll benötigte Bandbreite auf relativ kleine Werte senken, der Quellentausch von eMule ist hier ein gutes Beispiel.

Öffentlich verfügbare Clients mit Kademlia-Algorithmus (Netze sind inkompatibel):

- VarVar (erster Client mit Kademlia, eigenes Netz) - Overnet, eDonkeyHybrid und mlDonkey (Overnet-Netzwerk) - eMule (ab v0.40, Netz noch unbenannt)

Weitere Informationen:

"Kademlia: The optimized Peer network", http://kademlia.scs.cs.nyu.edu/ "Kademlia: A Peer-to-peer Information System Based on the XOR Metric"