imported>Rmcharb: Änderungen von 2A00:79C0:7E2:E000:F0A3:CBA5:AD44:C2AF (Diskussion) auf die letzte Version von Uncopy zurückgesetzt

2020-04-23T07:45:21Z

Änderungen von 2A00:79C0:7E2:E000:F0A3:CBA5:AD44:C2AF (Diskussion) auf die letzte Version von Uncopy zurückgesetzt

Neue Seite

{{Begriffsklärungshinweis}}

'''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 [[Massachusetts Institute of Technology|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 [[Verteilte Hashtabelle|Verteilten Hashtabelle]]) eine binäre Suche, was im Allgemeinen Suchkosten von <math>\mathcal{O}(log(n))</math> 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 ==
[[Datei:Chord fingers full.svg|thumb|250px|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 [[Secure Hash Algorithm#SHA-1|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 <math>i</math>-te Finger (<math>1 \leq i \leq m</math>) des Knoten mit der ID <math>x</math> verweist auf den Knoten, der für den Hashwert <math>(x+2^{(i-1)}) \bmod 2^m</math> zuständig ist, wobei <math>m</math> der Anzahl der Bits entspricht, die einen Knoten darstellen. Das modulo <math>2^m</math> 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 ==
* [http://pdos.csail.mit.edu/chord/ The Chord Project]
* [http://sarwiki.informatik.hu-berlin.de/Chord Erklärung von Chord, HU Berlin]

[[Kategorie:Peer-to-Peer]]

Chord - Versionsgeschichte

imported>Rmcharb: Änderungen von 2A00:79C0:7E2:E000:F0A3:CBA5:AD44:C2AF (Diskussion) auf die letzte Version von Uncopy zurückgesetzt