DHT

Überblick

Der Kademlia-Algorithmus wurde 2002 an New York University von Petar Maymounkov and David Mazieres entwickelt. Es handelt sich um die Implementation einer "Distributed Hash Table", sie baut ein selbstorganisierendes, strukturiertes P2P-Netz auf und regelt Kommunikation und Austausch zwischen den Netzwerkknoten.
Dabei wird ein sehr effizientes Vorgehen angewendet, so daß verhältnismäßig wenig Overhead entsteht.

Schlüssel-Wert-Paare

Das besondere Kennzeichen von Kademlia ist der gemeinsame virtuelle Adreßraum für Knoten-IDs und Schlüssel mit 160 Bit Breite. Damit eine Information im Netzwerk gefunden werden kann, wird ihr Hashwert (der Schlüssel) als Schlüssel-Wert-Paar auf mehreren Knoten mit einer zum Schlüssel ähnlichen ID gespeichert. Ein Knoten, der den dort gespeicherten Schlüssel sucht, kann das den Wert des Schlüssel-Wert-Paars enthalten und anhand dessen bestimmen, von welchem Netzwerkknoten er die Information erhalten kann.

XOR-Metrik

Als Abstandsfunktion wird das bitweise XOR verwendet. Da Schlüssel und Knoten-IDs auf dem gleichen Raum definiert sind, kann auch der Abstand eines Schlüssels von einer Knoten-ID ermittelt werden.

  Abstand(Argument_1, Argument_2) = Argument_1 XOR Argument_2

z.B.:

  1011 XOR 1000 = 0011

Das Ergebnis dieser Operation wird als Abstand aufgefaßt.
Die Verwendung der XOR-Funktion bedingt dabei, daß unterschiedliche niederwertige Bits der Operanden sich weit weniger auf den Abstand auswirken als höherwertige Bits - daher werden Knoten mit ähnlichen Knoten-IDs im Netzwerk Nachbarn sein.

Routingtabellen: "k-Buckets"

Bekannte Knoten werden in Kademlia als Listen gehandhabt, dabei wird der Adreßraum in Intervalle von je $2^{i}$ bis $2^{i}+1$ mit $0lei<160$ zerlegt

Rest-Container

Hohe Verbreitung (Overnet, eMule, BitTorrent, …) Eigenschaften gut formal nachweisbar