Kademlia

Kademlia

Kademlia ist eine Technik für Peer-to-Peer-Netze, die eine verteilte Hashtabelle implementiert, also Informationen in einem verteilten Netzwerk speichert. Kademlia legt nur Art und Aufbau des Netzes fest. 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

Einsatz beim Filesharing

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

Filesharing-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).

Funktionsweise

Meist wird Kademlia über das Internet mit dem verbindungslosen User Datagram Protocol (UDP/IP) benutzt.

Jeder Knoten wird durch eine eindeutige Nummer (genannt „Node-ID“) identifiziert. Diese Nummer dient nicht nur zu seiner Identifizierung, sondern wird von Kademlia 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 von einem Server oder Benutzer im Netzwerk die IP-Adresse einiger Knoten, die bereits im Kademlia-Netz bekannt sind. Von diesen ersten Knoten erhält er nun auch die IP-Adressen weiterer Knoten, so dass keine Abhängigkeit mehr von einzelnen Knoten besteht.

Da es keine zentrale Instanz gibt, die eine Indizierung der vorhandenen Informationen übernimmt, wird diese Aufgabe auf alle Knoten gleichermaßen aufgeteilt. Ein Knoten, der eine Information besitzt, errechnet zuerst den charakteristischen Hashwert („ID“ genannt) dieser Information. Die verwendete Hash-Funktion in einem Kademlia-Netz muss immer dieselbe sein. Jener Knoten sucht nun im Netz die Knoten, deren ID 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. Häufig ist dem Suchenden nur der Hashwert der Daten verfügbar. Er kann nun eine direkte Verbindung zu den Quellen eingehen und die Daten 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 nach einer gewissen Zeit aktualisiert.

Zum Auffinden eines Knotens hangelt sich der Algorithmus 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.

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.

„Distanz“ von Knoten

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 zwei Knoten und Hashwerten wird durch die mathematische XOR-Funktion errechnet und beträgt ID1 XOR ID2.

Clients

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

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Kademlia — is a distributed hash table for decentralized peer to peer computer networks designed by Petar Maymounkov and David Mazières [* [http://pdos.csail.mit.edu/ petar/papers/maymounkov kademlia lncs.pdf Kademlia: A Peer to peer information system… …   Wikipedia

  • Kademlia — (kad) est un réseau de recouvrement créé pour décentraliser les autres réseaux d échange de fichiers pair à pair (Peer to Peer ou P2P en anglais). Il a été conçu par Petar Maymounkov et David Mazières en 2002[1]. Le protocole précise la structure …   Wikipédia en Français

  • Kademlia — es un protocolo de la capa de aplicación diseñado para redes P2P descentralizadas. Especifica la estructura de la red, regula la comunicación entre nodos y el intercambio de información. Los nodos se comunican entre sí usando el protocolo sin… …   Wikipedia Español

  • Kademlia — это реализация распределённой хеш таблицы для одноранговых компьютерных сетей, разработанная Петром Маймунковым и David Mazières. Протокол Kademlia определяет структуру сети, регулирующей связь между узлами, и способ обмена информацией в ней.… …   Википедия

  • Kademlia — Protocolo de la capa de aplicación diseñado para redes P2P descentralizadas. Especifica la estructura de la red, regula la comunicación entre nodos y el intercambio de información. Los nodos se comunican entre sí usando el protocolo sin conexión… …   Enciclopedia Universal

  • Kadmelia — Kademlia Kademlia est un réseau de recouvrement créé pour décentraliser les autres réseaux d échange de fichiers pair à pair (Peer to Peer ou P2P en anglais). Le protocole précise la structure du réseau Kademlia, les communications entre les… …   Wikipédia en Français

  • E-Mule — eMule Downloadübersicht bei eMule 0.48a Basisdaten Entwickler …   Deutsch Wikipedia

  • EMule — Downloadübersicht bei eMule 0.48a Basisdaten Entwickler …   Deutsch Wikipedia

  • Emule — Downloadübersicht bei eMule 0.48a Basisdaten Entwickler …   Deutsch Wikipedia

  • File-Sharing — Mit Filesharing (deutsch Dateifreigabe oder gemeinsamer Dateizugriff, wörtlich Dateien teilen) bezeichnet man das direkte Weitergeben von Dateien zwischen Benutzern des Internets unter Verwendung eines Peer to Peer Netzwerks. Dabei befinden sich… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”