Kademlia ist ein Algorithmus
(Verfahrens- oder Verarbeitungsvorschrift;
zum Beispiel für einen Rechenvorgang, der
wiederholt nach einem bestimmten,
gleichbleibenden Schema abläuft) zum Aufbau
eines dezentralen Peer-to-Peer-Netzwerkes.
Es legt Art und Aufbau des Netzes fest,
reglementiert die Kommunikation zwischen den
Nodes und wie der Austausch von
Informationen stattzufinden hat. Grundlage
von Kademlia sind das Internet Protocol und
das darauf aufbauende, verbindungslose UDP
Protocol.
Über einem bestehenden LAN/WAN (also z.B.
auch dem Internet) wird ein neues,
virtuelles Netzwerk aufgebaut, in dem jeder
Node 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 Node, der dem Netz beitreten möchte,
muss zuerst einen "Bootstrapping" genannnten
Prozes durchlaufen: In dieser Phase erhält
der Algorithmus vom Benutzer (oder aus einer
gespeicherten Liste) die IP eines Nodes, der
bereits im Kademlia Netz bekannt ist. War
der Node noch nie uvor im Netz, berechnet er
so lange zufällige IDs bis er eine findet
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 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 Node, der eine Information
besitzt, errechnet zuerst eine eindeutige
und immer gleich lange Bitsequenz, die diese
Information charakterisiert (im folgenden
"Hash" genannt). Die Länge der im Netz
verwendeten Hashes und der Node-IDs muss
gleich lang sein. Er sucht nun im Netz die
Nodes, 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 Nodes, 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 Nodes 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 Node aus
Deutschland und einer aus Australien
sozusagen "Nachbarn" sind. Die Distanz
zwischen den Nodes 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:
Beim Auffinden eines Nodes 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 Nodes
entspricht der Distanz dieses Nodes zu einem
selbst. Sollte sich die Anzahl der
Teilnehmer im Netz verdoppeln, so muss man
nicht doppelt so viele Nodes befragen -
sondern pro Verdoppelung nur einen Node
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-Attackten deutlich steigert.
Selbst wenn eine ganze Reihe von Nodes
gefloodet wird hat das für das Netz selbst
keine allzu groß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.
|
Menu