Peer2Peer & Computerforum

**Morpheus** · [editiert: 10.12.04, 06:28 von **Morpheus**]

Was ist eigentlich KAD?

Kad oder auch Kademlia ist die Bezeichnung für ein dezentrales P2P-Netzwerk. Der Kademlia-Algorithmus legt die Funktionsweise des jeweiligen Kademlia-Netzes fest. Der Kademlia (Kad) Algorithmus ist lediglich die Grundlage für ein Kad-Netzwerk und legt dessen Arbeitsweise fest. Der Kademlia-Algorithmus sagt jedoch nicht wie genau das Protokoll umgesetzt wird welches den eigentlichen Datenaustausch regelt. Aus eben diesem Grund sind unterschiedliche Kademlia Netze nicht miteinander kompatibel, es kann also kein Datenaustausch zwischen den einzelnen Netzen erfolgen. Bisher sind Kad-Netze unter anderem in den VarVar Client, den
Overnet Client, den mlDonkey und in eMule ab v0.40 integriert.

Kademlia regelt in einem Netz dessen Aufbau und die Kommunikation der einzelnen Clients (Nodes) untereinander. Über ein bestehendes Netzwerk (Internet oder Lan) wird auf Kademlia Grundlage ein virtuelles Netzwerk aufgebaut. Vorteile von Kademlia sind vorallem die dezentrale Netzstruktur die gegen Attacken nahezu immun ist. Jeder Node in diesem Kad-Netzwerk hat eine eindeutige Nummer die seine Identifizierung im Kad-Netzwerk sicherstellt und zugleich Distanzberechnungen im Netzwerk ermöglicht. Auf diese weise können andere Nodes mit minimalem Aufwand gefunden werden und bei einer Teilnehmerverdoppelung muß nur ein weiterer Node befragt werden um trotzdem alle Teilnehmer zu erreichen. Der zusätzliche Abfrageaufwand in einem Kademlia-Netzwerk wächst also linear mit der Teilnehmerzahl.

Ü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.

[Quelle: http://www.informationsarchiv.net/
http://www.emule-anleitung.de/]

____________________