Kademlia ist ein Algorithmus zum Aufbau eines dezentralen
Peer-to-Peer-Netzwerkes. 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 Netzwerk 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.
siehe Bootstrap
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
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 log2(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. |
