Chord

Chord ist ein strukturiertes Peer-to-Peer-System, welches im Gegensatz zu den meisten unstrukturierten Systemen eine effiziente Suche nach Inhalten ermöglicht. Wie auch Gnutella ist Chord keine konkrete Implementierung, sondern ein Protokollsystem. Es wird am MIT entwickelt und der Quelltext der aktuellen Version steht unter der MIT-Lizenz zum freien Herunterladen und Benutzen zur Verfügung.

Strukturiertes Overlaynetzwerk

Über der eigentlichen Transportschicht (TCP/IP) bilden Peer-to-Peer-Systeme ein sogenanntes Overlay-Netzwerk. Dieses Overlay-Netzwerk beschreibt die Netzwerktopologie der einzelnen Peers, die über das Peer-to-Peer-System verbunden sind. Die zentrale Frage stellt sich beim Hinzufügen und Entfernen neuer Peers (Netzwerkknoten): Mit wem soll der neue Knoten verbunden werden? Genauso beim Löschen: War der Knoten eventuell eine Verbindung zwischen zwei anderen, sodass das Entfernen des Knotens eine Verschlechterung der Qualität des Overlaynetzwerks darstellt?

Bei Gnutella werden diese Fragen nicht gestellt, neue Knoten verbinden sich wahllos mit den Knoten, die sie durch Flooding des Netzwerkes ermitteln können. Bei Chord hingegen wird ein sogenannter Chord-Ring aufgebaut: Alle Netzwerkknoten werden in einer Ringstruktur angeordnet, wobei jeder Knoten Verbindungen zu seinem Vorgänger, Nachfolger sowie bestimmten anderen Knoten im Netzwerk hat. Diese Ringstruktur ermöglicht (mit Hilfe einer Verteilten Hashtabelle) eine binäre Suche, was im Allgemeinen Suchkosten von ${\mathcal {O}}(log(n))$ bei der Suche nach Inhalten im Netzwerk verursacht. (Im Gegensatz dazu verursacht Gnutella z. B. immense Suchkosten, – etwa 70 % der Netzwerklast in Gnutella-Netzwerken entsteht durch Suchen.) Der Nachteil liegt in der komplexeren Handhabung der Ringstruktur – beim Hinzufügen und Entfernen von Netzwerkknoten ist jeweils immer darauf zu achten, dass die Ringstruktur und die Querverweise erhalten bleiben.

Inhaltsverteilung

Chord-Fingertabelleneinträge auf weiterführende Knoten

Allein mit Hilfe der Ringstruktur ist noch keine binäre Suche möglich: Im naiven Ansatz müsste – zur Suche von Inhalten – der Ring einmal in aufsteigender Reihenfolge der GUIDs durchlaufen werden, um einen „exact match“, d. h. eine präzise Antwort auf eine Suchanfrage zu bekommen. Das ist zwar besser als die Suche in einem unstrukturierten Netz, aber immer noch relativ „teuer“.

Um Daten, also den eigentlichen zu verbreitenden Inhalt des Netzwerkes, korrekt zu identifizieren, wird eine globale Hash-Funktion benötigt. Diese weist jedem Datensatz (z. B. Dateien im Fall von Filesharing) eine eindeutige ID zu, die durch die Verwendung der SHA-1-Hashfunktion zustande kommt (160-Bit-Schlüssel). Jeder Knoten verwaltet nun einen bestimmten Teil der globalen Hashtabelle, der durch ein Intervall des Schlüssels repräsentiert wird. Jeder Knoten weiß jetzt also für einen Teil der Daten, auf welchen anderen Knoten bzw. Intervallen sich diese jeweils befinden.

Bei der Variante "Scalable Key Location" benutzt das Chord-Netzwerk zur Suche und Durchquerung des Ringes Verweise auf entfernte Knoten, eine sogenannte Fingertabelle. Die Einträge werden wie folgt erstellt: Der $i$-te Finger ($1\leq i\leq m$) des Knoten mit der ID $x$ verweist auf den Knoten, der für den Hashwert $(x+2^{(i-1)}){\bmod {2}}^{m}$ zuständig ist, wobei $m$ der Anzahl der Bits entspricht, die einen Knoten darstellen. Das modulo $2^{m}$ sorgt dafür, dass man auf der Ringstruktur bleibt. Dadurch ist gesichert, dass man viel schneller als mit linearer Suche zu dem gesuchten Element gelangen kann.

Weblinks

• The Chord Project
• Erklärung von Chord, HU Berlin