Peer-to-Peer-Netzwerke: Algorithmen und Methoden

verringert die Anzahl der Zwischenstationen fur die Suche and damit die Latenzzeit, da fur die Suche immer die nachstgelegene Kopie gewahlt werden kann. Die Anzahl der Hops zu der nachsten Kopie nimmt hierbei mit der Anzahl der Kopien ab.
4.6 Zusammenfassung
    Verglichen mit Gnutella and Napster ist CAN ein groBer Fortschritt. Zum ersten Mal kann man garantieren, dass ein Datum gefunden wird, wenn es im Netzwerk vorhanden ist. Hierzu wird die Anfrage nur gemaB einer Richtung zum Ziel weitergeleitet. Nur ein kleiner Bruchteil der Peers ist involviert and der Weg vom anfragenden Peer zu demjenigen Peer, der das Datum bereitstellt, ist relativ kurz. In einem zweidimensionalen CAN sind nur 0(n1/2) Peers an einer Suche beteiligt. Dies ist ein erheblicher Fortschritt im Vergleich zu Gnutella, das nicht garantieren kann, dass die Suche uberhaupt erfolgreich ist.
    CAN ist auch das erste Netzwerk, das das Konzept der verteilten Hash-Tabellen (DHT) verwendet. Das ist mittlerweile eine Standardmethode im Bereich der Peer to-Peer-Netzwerke. Trotz allem hat sich CAN nicht durchgesetzt, denn die Peer-toPeer-Netzwerke, die wir in den folgenden Kapiteln vorstellen, sind hinsichtlich Grad and Routing-Zeit noch effizienter.

5

Chord
    A chord is by no means an agglomeration of intervals.
    Paul Hindemith
    Beim von Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek and Hari Balakrishnan entwickelten Chord-Netzwerk [10] handelt es sich um eins der bekanntesten Peer-to-Peer-Netzwerke wissenschaftlicher Herkunft. Dies liegt zum einen sicherlich daran, dass Chord eins der ersten Peer-to-Peer Netzwerke wissenschaftlichen Ursprungs ist. Nicht weniger ausschlaggebend dUrftejedoch die Tatsache sein, dass es mit Chord gelungen ist, eine vergleichsweise einfache Netzwerkstruktur auf- zubauen, die zugleich sehr effizient ist.
5.1 Verteilte Hash-Tabellen in Chord
    Wie schon bei CAN im vorigen Kapitel, werden in Chord verteilte Hash-Tabellen fur die Zuordnung zwischen Daten and Peers eingesetzt. Das Prinzip der verteilten Hash-Tabellen wird in beiden Netzwerken jedoch unterschiedlich umgesetzt. Wir erinnern uns, dass im Fall von CAN ein zweidimensionaler Raum unter den Peers aufgeteilt wurde. Um die Effizienz zu steigern, wurde dann zum Beispiel die Anzahl der Dimensionen weiter erhoht. Chord wahlt gerade den anderen Weg and beschrankt sich auf einen eindimensionalen Raum.
    Bezeichne im Folgenden P = {pl,... , pn,} die Menge der Peers and X = {x1, ... , xk} die Menge der Daten im Netzwerk. Bei Chord werden Peers sowie Daten mittels kryptographischer Hash-Funktionen h : P - Z2m and h' : X ~ Z2- auf die Zahlen in 7Z2m = {0, ... , 2"1} abgebildet. Dass hier auf ganze Zahlen anstelle eines kontinuierlichen Intervalls abgebildet wird, ist ein unwesentliches Detail. Die Zahl m muss genugend groB gewahlt werden, um die Wahrscheinlichkeit von Kollisionen beim Hashing vernachlassigbar klein zu halten. Ein typischer Wert fur 7n ist 128.
    Fur die Zuordnung der Daten zu den Peers wird der Zahlenraum Z2m als Ring betrachtet. Deshaib and wegen der Verbindungsstruktur, die wir im nachsten Abschnitt betrachten werden, wird auch vom so genannten Chord-Ring gesprochen. Auf dem Chord-Ring wird jedes Datum demjenigen Peer zugeordnet, der der Position (also dem Hash-Wert) des Datums in aufsteigender Zahlrichtung folgt. Somit ist ein Peer fur den Bereich hinter seinem Vorganger bis zu seiner eigenen Position auf dem Chord-Ring zustandig. Abbildung 5.1 veranschaulicht die Zuordnung von Daten zu Peers an einem Chord-Ring der GroBe 23 mit 3 Peers and 3 Dateien.

    Abb. 5.1. Zuordnung von Daten zu Peers in Chord.
    Wenn dem Netzwerk nun ein neuer Peer pn+1 beitritt, so wird diesem durch Hashing die Position h(p,z+1) auf dem Chord-Ring zugewiesen. Sei Peer pi zustandig far den Bereich h(pj) + 1 his h(pi) des Chord-Rings. Liegt h(pn,+1) nun in diesem Bereich, so wird Peer pn,+1 Peer pi kontaktieren, and die Zustandigkeiten werden wie folgt verandert: Der Zustandigkeitsbereich von pi wird auf den Bereich von h(pn+i) + 1 his h(pi) verkleinert, and der neue Peer Pn+1 ist von nun an verantwortlich fur den Bereich h(pj) + 1 bis h(pn+l) (siehe Abbildung 5.2).
    Meldet sich ein Peer pj vom Netzwerk ab oder fallt dieser Peer aus technischen Grunden aus, so muss der bislang durch pj verwaltete Bereich des Chord-Rings von einem anderen Peer ubernommen werden. Der dafur zustandige Peer ist nach dem oben beschriebenen Schema der Nachfolger pi von pj auf dem Chord-Ring. Falls ein