Kademlia

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

Über ein bestehendes LAN/WAN (also z. B. auch das Internet) wird ein neues, virtuelles Netz aufgebaut, in dem jeder Knoten 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 Knoten, der dem Netz beitreten möchte, muss zuerst einen „Bootstrapping“ genannten Prozess durchlaufen: In dieser Phase erhält der Algorithmus vom Benutzer (oder aus einer gespeicherten Liste) die IP-Adresse eines Knotens, der bereits im Kademlia-Netz bekannt ist. War der Knoten noch nie zuvor im Netz, berechnet er eine zufällige ID, 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 Netz 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 Knoten, der eine Information besitzt, errechnet zuerst eine eindeutige und immer gleich lange Bitsequenz, die diese Information charakterisiert (Hash-Wert). Die Länge der im Netz verwendeten Hashes und der Node-IDs muss gleich lang sein. Er sucht nun im Netz die Knoten, deren ID (in Bits gerechnet) die kleinste „Distanz“ zum Hash aufweisen, und übermittelt ihnen ihre Kontaktdaten.

Sucht ein Host genau diese Information, vollzieht er dieselbe Prozedur und gelangt dadurch an die Knoten, 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 Knoten 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 Knoten aus Deutschland und einer aus Australien sozusagen „Nachbarn“ sind. Die Distanz zwischen den Knoten im Kademlia-ID-Space wird durch die mathematische XOR-Funktion errechnet und beträgt immer log₂(ID1 XOR ID2). Diese Vorgehensweise hat große Vorteile sowohl gegenüber serverbasierten Netzen, als auch gegenüber dem total dezentralen Gnutella-Verfahren:

• Beim Auffinden eines Knoten 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 Knoten entspricht der Distanz dieses Knoten zu einem selbst. Sollte sich die Anzahl der Teilnehmer im Netz verdoppeln, so muss man nicht doppelt so viele Knoten befragen – sondern pro Verdoppelung nur einen Knoten 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-Attacken deutlich steigert. Selbst wenn eine ganze Reihe von Knoten angegriffen wird, hat das für das Netz selbst keine allzugroß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.

Weblinks

Öffentlich verfügbare Clients, die den Kademlia-Algorithmus implementieren (Netze sind untereinander inkompatibel):

• VarVar (erster Client mit Kademlia, eigenes Netz)
• Overnet, eDonkeyHybrid und mlDonkey (Overnet)
• eMule (ab v0.40, Netz noch unbenannt)
• Azureus (ab Version 2.3)
• BitTorrent (ab Version 4.1.0, Betaphase)

Weiterführende Informationen (englisch):

• Kademlia: A of Peer to peer information system Based on the XOR Metric (PDF)