Kademlia

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

Kademlia ist ein Protokoll für Peer-to-Peer-Netze. Es legt Art und Aufbau des Netzes fest, reglementiert die Kommunikation zwischen den Knoten und den Austausch von Informationen.

Inhaltsverzeichnis

1 Abgrenzung
2 Funktionsweise
3 Clients
4 Siehe auch
5 Weblinks

[Bearbeiten] Abgrenzung

Kademlia dient vor allem dem Zweck des Filesharing. Filesharing-Tools unterscheiden sich primär im Mechanismus zum Auffinden der bereitgestellten Dateien zum Download.

Tools der ersten Generation, wie Napster, besitzen einen zentralen Server, der alle im System vorhandenen Dateien und ihren Besitzer kennt. Bei Anfragen wird der zentrale Server kontaktiert und dann die entsprechende Datei von einem der dort verzeichneten Besitzer heruntergeladen. Dieser Ansatz besitzt zwei Nachteile: Zum Einen sind solche Systeme anfällig gegenüber Denial-of-Service-Angriffen gegen den zentralen Indexierungsserver. Zum Anderen ist dieser Ansatz aus rechtlichen Gründen für Filesharing ungeeignet: Dem Betreiber des Indexierungsservers ist es unmöglich alle bereitgestellten Dateien auf Urheberrechtsverletzungen zu untersuchen, er ist aber für von Teilnehmern illegal bereitgestellte Inhalte mitverantwortlich.

Tools der zweiten Generation, wie Gnutella, verzichten auf den zentralen Indexierungsserver. Hier werden Anfragen an einen Teil der Knoten im System weitergegeben. Auf diesen wird dann überprüft, ob der Teilnehmer eine passende Datei zum Download besitzt. Besitzt der Teilnehmer eine Datei wird dies an den Anfrager zurückgegeben. Mit diesem Ansatz werden teilweise nicht alle Knoten des Netzwerkes abgefragt, so dass nicht alle passenden Dateien gefunden werden.

Tools der dritten Generation, zu denen auch Kademlia gehört, beheben dieses Problem: Über dem bestehenden LAN/WAN (z. B. Internet) wird eine zweite, virtuelle Netzstruktur (eine sog. Verteilte Hashtabelle) aufgebaut. Diese Struktur ersetzt den zentralen Indexierungsserver von Tools der ersten Generation. So ist es möglich alle gesuchten Dateien im Netz zu finden, ohne einen zentralen Indexierungsserver zu benötigen. Außerdem behebt es auch den Nachteil von Tools der zweiten Generation, denn sind Dateien vorhanden, dann werden sie auch gefunden und dies mit einem Aufwand von O(log n).

[Bearbeiten] Funktionsweise

Grundlage von Kademlia ist das Internet Protocol und das darauf aufbauende verbindungslose UDP.

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.

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 eigene Knoten noch nie zuvor im Netz, berechnet er eine zufällige Node-ID.

Da es keine zentrale Instanz gibt, die eine Indizierung der vorhandenen Dateien übernehmen kann, 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 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 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).

Beim Auffinden eines Knotens 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 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.
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 neuen „Löcher“ herum 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..