Kademlia

Kademlia ist eine Technik für Peer-to-Peer-Netze, die eine verteilte Hashtabelle implementiert, also Informationen in einem verteilten Netzwerk speichert. Kademlia legt nur Art und Aufbau des Netzes fest. Es wurde von Petar Maymounkov und David Mazières entwickelt. Es wird häufig von Filesharing-Tools verwendet, ist aber nicht auf diesen Anwendungsbereich beschränkt.

Einsatz beim Filesharing

Obwohl Kademlia häufig von Filesharing-Programmen verwendet wird, können mit diesem Protokoll keine Dateien übermittelt werden. Vielmehr werden hier die Informationen, die zum Auffinden von gewünschten Dateien nötig sind, in dem verteilten Netz hinterlegt. Die Dateien können dann mit einem anderen Protokoll wie eDonkey2000 oder BitTorrent übertragen werden.

Filesharing-Programme der dritten Generation, zu deren Protokollen auch Kademlia gehört, speichern die Informationen über das Netz in einer verteilten Hashtabelle, jeder Knoten speichert also einen redundanten Teil dieser Informationen. Diese Struktur ersetzt den zentralen Indizierungsserver von Programmen der ersten Generation. Gleichzeitig sinkt der Aufwand, um gewünschte Dateien zu finden, auf O(log n).

Funktionsweise

Meist wird Kademlia über das Internet mit dem verbindungslosen User Datagram Protocol (UDP/IP) benutzt.

Jeder Knoten wird durch eine eindeutige Nummer (genannt „Node-ID“) identifiziert. Diese Nummer dient nicht nur zu seiner Identifizierung, sondern wird von Kademlia gleichzeitig für weitere Zwecke herangezogen. Der eigene Knoten berechnet eine zufällige Node-ID, falls er zuvor noch nie im Netz war.

Ein Knoten, der dem Netz beitreten möchte, muss zuerst einen „Bootstrapping“ genannten Prozess durchlaufen: In dieser Phase erhält der Algorithmus von einem Server oder Benutzer im Netzwerk die IP-Adresse einiger Knoten, die bereits im Kademlia-Netz bekannt sind. Von diesen ersten Knoten erhält er nun auch die IP-Adressen weiterer Knoten, so dass keine Abhängigkeit mehr von einzelnen Knoten besteht.

Da es keine zentrale Instanz gibt, die eine Indizierung der vorhandenen Informationen übernimmt, wird diese Aufgabe auf alle Knoten gleichermaßen aufgeteilt. Ein Knoten, der eine Information besitzt, errechnet zuerst den charakteristischen Hashwert („ID“ genannt) dieser Information. Die verwendete Hash-Funktion in einem Kademlia-Netz muss immer dieselbe sein. Jener Knoten sucht nun im Netz die Knoten, deren ID die kleinste „Distanz“ zum Hash aufweisen, und übermittelt ihnen seine Kontaktdaten.

Sucht ein Knoten genau diese Information, vollzieht er dieselbe Prozedur und gelangt dadurch an die Knoten, die gespeichert haben, wer im Netz diese Information besitzt. Häufig ist dem Suchenden nur der Hashwert der Daten verfügbar. Er kann nun eine direkte Verbindung zu den Quellen eingehen und die Daten 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 nach einer gewissen Zeit aktualisiert.

Zum Auffinden eines Knotens hangelt sich der Algorithmus 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 Knotens 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, sondern logarithmisch.

Ein weiterer Vorteil liegt 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 allzu großen Auswirkungen. Mit der Zeit strickt sich das Netz dann um diese neuen „Löcher“ herum.

„Distanz“ von Knoten

Die oben genannte „Distanz“ hat nichts mit geografischen Gegebenheiten zu tun, sondern bezeichnet die Distanz innerhalb des ID-Bereiches. Es kann also vorkommen, dass z. B. ein Knoten aus Deutschland und einer aus Australien sozusagen „Nachbarn“ sind. Die Distanz zwischen zwei Knoten und Hashwerten wird durch die mathematische XOR-Funktion errechnet und beträgt ID₁ XOR ID₂.

Clients

Clients, die einen Kademlia-Algorithmus implementieren (die eigentlichen Netze für Nutzdaten wie z. B. Dateien sind in der Regel nicht untereinander kompatibel):

• eMule (ab Version 0.42) und aMule (ab Version 2.1.0), Name: Kad
• MLDonkey, Name: Kad & Overnet
• BitTorrent (ab Version 4.1.0, Betaphase)
• µTorrent
• KTorrent
• Vuze
• CSpace (ein Instant Messenger)
• Deluge (über libtorrent implementiert, mit µTorrent kompatibel)
• rTorrent (ab Version 0.8.0)
• eDonkey2000, Name: Overnet (Entwicklung eingestellt)

Weblinks

• Kademlia im Informatik-Wiki der Humboldt Universität Berlin
• Petar Maymounkov und David Mazières: Kademlia – A Peer-to-peer Information System Based on the XOR Metric (PDF, english):
  • Kurzversion (PDF-Datei; 79 kB)
  • Langversion (PDF-Datei; 211 kB)