Kademlia

aus Wikipedia, der freien Enzyklopädie

Kademlia (häufig KAD abgekürzt) ist ein Protokoll für Peer-to-Peer-Netze, welches eine verteilte Hashtabelle implementiert, also Informationen in einem verteilten Netzwerk speichert. Kademlia legt Art und Aufbau des Netzes fest, reglementiert die Kommunikation zwischen den Knoten und den Austausch von Informationen. 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.

Inhaltsverzeichnis 1 Einsatz beim Filesharing 2 Funktionsweise 3 Clients 4 Weblinks

[Bearbeiten] Einsatz beim Filesharing

Obwohl Kademlia häufig von Filesharing-Tools 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.

Die Funktionsweisen der Filesharing-Tools zum Auffinden der gewünschten Dateien lassen sich in drei Generationen unterteilen:

• Programme der ersten Generation, etwa Napster, besitzen einen zentralen Server, der alle im Netzwerk vorhandenen Dateien samt ihrer Besitzer kennt. Bei Suchanfragen wird der zentrale Server kontaktiert und dann die entsprechende Datei von einem der dort verzeichneten Besitzer heruntergeladen. Dieser Ansatz besitzt zwei Merkmale: Zum einen sind solche Netzwerke anfällig gegenüber Denial-of-Service-Angriffen gegen den zentralen Indizierungsserver. Zum anderen kann sich der Betreiber eines solchen Servers rechtlich leicht angreifbar machen, falls über solche Server widerrechtlich urheberrechtlich geschützte Dateien getauscht werden.
• Programme der zweiten Generation wie Gnutella verzichten auf den zentralen Indizierungsserver. Hier werden Anfragen an einen Teil der Knoten im System weitergegeben. Auf diesen wird dann überprüft, ob derjenige Teilnehmer eine passende Datei zum Download besitzt. Besitzt dieser Teilnehmer eine solche Datei wird dies an den Anfrager zurück gegeben. Mit diesem Ansatz werden meist nicht alle Knoten des Netzwerkes abgefragt, so dass nicht alle passenden Dateien gefunden werden. Außerdem ist der Aufwand zum Auffinden der Dateien vergleichsweise groß und der Suchvorgang langsam.
• 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).

[Bearbeiten] Funktionsweise

Grundlage von Kademlia ist das Internet Protocol und das darauf aufbauende, verbindungslose UDP („User Datagram Protocol“). Jeder Knoten wird durch eine eindeutige Nummer („Node-ID“) identifiziert. Diese Nummer dient nicht nur zu seiner Identifizierung, sondern wird vom Kademlia-Algorithmus 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 vom Benutzer (oder aus einer gespeicherten Liste) die IP-Adresse eines Knotens, der bereits im Kademlia-Netz bekannt ist. Von diesem ersten Knoten erhält er nun auch die IP-Adressen der übrigen Knoten, so dass keine Abhängigkeit mehr von einzelnen Knoten besteht.

Da es keine zentrale Instanz gibt, die eine Indizierung der vorhandenen Informationen übernehmen kann, wird diese Aufgabe auf alle Knoten 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 sein. Er sucht nun im Netz die Knoten, deren ID (in Bits gerechnet) 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. 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.

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 den Knoten im Kademlia-ID-Space wird durch die mathematische XOR-Funktion errechnet und beträgt immer log₂(ID₁ XOR ID₂).

Zum Auffinden eines Knotens hangelt sich der Algorithmus intelligent immer näher an diesen heran, bis er gefunden wird oder ein Fehler zurück kommt. 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. Durch Optimierung lässt sich die für das Protokoll benötigte Bandbreite auf relativ kleine Werte senken; der Quellentausch von eMule ist hierfür ein gutes Beispiel.

[Bearbeiten] Clients

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

• µTorrent
• VarVar [1] (erster Client mit Kademlia, eigenes Netzwerk)
• MLDonkey
• eMule (ab Version 0.42) und aMule (ab Version 2.1.0), Name: Kad
• eDonkey2000, Name: Overnet
• Azureus (ab Version 2.3)
• BitTorrent (ab Version 4.1.0, Betaphase)
• eXeem (eingestellt)
• ANts P2P
• CSpace [2] (ein Instant Messenger)
• lPhant

[Bearbeiten] Weblinks

• Kademlia: A Peer-to-peer Information System Based on the XOR Metric (PDF, english):
  • Kurzversion
  • Langversion