Chord
aus Wikipedia, der freien Enzyklopädie
Chord ist ein strukturiertes Peer-to-Peer-System, welches im Gegensatz zu den meisten unstrukturierten Systemen effiziente Suche nach Inhalten ermöglicht. Wie auch Gnutella ist Chord keine konkrete Implementierung sondern ein Protokollsystem.
[Bearbeiten] 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 evtl. 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 des verteilten Hashings) eine binäre Suche, was im Allgemeinen Suchkosten von O(log(n)) bei der Suche nach Inhalten im Netzwerk verursacht. (Im Gegensatz dazu verursacht Gnutella z.B. immense Suchkosten, - ca. 70% der Netzwerklast in Gnutella-Netzwerken werden durch Suche belegt.) Der Nachteil liegt natürlich 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.
[Bearbeiten] Inhaltsverteilung
Nur mit Hilfe der Ringstruktur ist natürlich keine binäre Suche möglich: Im naiven Ansatz müsste - zur Suche von Inhalten - der Ring einmal nach links und einmal nach rechts durchlaufen werden, um einen "exact Match", eine präzise Antwort auf eine Suchanfrage zu bekommen. Das ist zwar besser als die Suche in einem unstrukturierten Netz, aber immmr 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 (z.B. einen 128-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. (für eine detailliertere mathematisch unterlegte Darstellung sei hier auf die Vorlesung der Universität Freiburg von Prof. Dr. Christian Schindelhauer hingewiesen, siehe Weblinks)
