Peer-to-Peer-Netzwerke: Algorithmen und Methoden

anderer Peer Pk, k j den Ausfall von pj als erster bemerkt, so wird pi von Pk uber den Ausfall informiert und pi anschlieBend seinen Zustandigkeitsbereich anpassen.

    Wie schon im Fall von CAN, andert sich auch bei Chord beim Einfugen bzw. Entfernen eines Peers lediglich der Zustandigkeitsbereich genau eines anderen Peers. Somit ist auch hier die fur dynamische Netzwerke wichtige Konsistenzeigenschaft gegeben.

    Naturlich wird es Peers geben, die einen Bereich des Chord-Rings verwalten mussen, der mehr oder weniger vom Erwartungswert abweicht. Das folgende Lemma zeigt, welche Schranken hierbei mit hoher Wahrscheinlichkeit gelten.

    Abb. 5.2. Veranderung der Zustandigkeiten auf dem Chord-Ring beim Einfrigen eines Peers.

    Mit Hilfe von Lemma 5.1 konnen wir nun genauer abschatzen, fur wie viele Daten ein Peer hochstens verantwortlich sein wird.

    Die Erfolgswahrscheinlichkeit Pr[Xj = 1], d.h., ein Datum wird p zugeordnet, ist damit gegeben durch

    Wir kOnnen jetzt mit Hilfe der Chernoff Schranke (siehe Seite 268) abschatzen, wie viele Daten p, mit hoher Wahrscheinlichkeit hochstens zugewiesen werden. Die Chernoff-Schranke besagt, class fur jedes 6 > 0

    Pr [X > (1 + b)E[X]] < -3 min{b,s2}E[X] (5.1)
    gilt. In der folgenden Analyse werden wir die beiden Falle k E 0(n) and k e ,f2(n) unterscheiden.

    Des Weiteren gilt b < 62 and wir erhalten durch einsetzen in Ungleichung 5.1

    was die erste Aussage beweist.

    fur die linke Seite von Ungleichung 5.1. Wiederum gilt b < SZ and durch einsetzen erhalten wir

    Dies beweist die zweite Aussage and damit das Theorem. ❑
5.2 Netzwerkstruktur and Routing
    Um die im vorigen Abschnitt beschriebene verteilte Hash-Tabelle in einem Netzwerk zu realisieren, genugt ein Minimum an Routing-Information: Jeder Peer muss lediglich seinen Vorganger and Nachfolger auf dem Chord-Ring kennen. Die Suche nach einem Datum kann dann einfach entlang der Ringstruktur geschehen, in dem die Suchanfrage solange weitergeleitet wird, his der erste Peer erreicht wird, dessen Hash-Wert groBer als der des gesuchten Datums ist. Abgesehen davon, dass these Art der Suche recht viel Zeit, namlich linear in der Anzahl der Peers, benotigt, ist ein solches Ringnetzwerk auch nicht sehr fehlertolerant. Schon beim Ausfall zweier Peers zerfallt ein Ring in zwei Zusammenhangskomponenten.

    Um these beiden Probleme zu beheben, besitzt jeder Peer des Chord-Netzwerks neben Zeigern auf seinen Vorganger and Nachfolger auf dem Chord-Ring noch so genannte Finger-Zeiger. Sei der Zahienraum des Chord-Rings wieder Z2m, dann unterhalt jeder Peer p hochstens m solcher Finger-Zeiger in einer so genannten FingerTabelle. Der i-te Eintrag (1 < i < m) der Finger-Tabelle besteht dabei jeweils aus der Adresse des Peers pj, der der Position (h(p) + 2i-1) mod 2m auf dem ChordRing zugeordnet ist. Ist these Postion des Chord-Rings unbesetzt, d.h., es existiert kein Peer pj mit h(pj) = (h(p) + 2'-') mod 2', so wird derjenige Peer gewahlt, der dieser Position in aufsteigender Zahlrichtung folgt. Der Einfachheit halber werden wir diesen Zeiger eines Peers auch als i-ten Finger oder als Finger[i] referen- zieren. Der i-te Fingerzeiger eines Peers uberbruckt also eine Distanz von 2j-1 auf dem Chord-Ring. Des Weiteren ist zu beachten, dass die Finger-Zeiger im Fall i = 1 gerade den Nachfolgerzeigern des Chord-Rings entsprechen.
    Abbildung 5.3 veranschaulicht die Finger-Zeiger. Dargestellt werden die FingerZeiger des Peers p4 mit h(p4) = 0. Die duchgezogenen Pfeile zeigen auf die Zielpo- sitionen (h(p) + 2i-1) mod 2''n der Finger-Zeiger von p4 auf dem Chord-Ring. Einige Positionen sind jedoch nicht mit Peers besetzt. Dann unterhalt p4 Finger-Zeiger zu den jeweils nachfolgenden Peers, gekennzeichnet mit gestrichelten Pfeilen. In diesem Fall sind das gerade Peer pl an Position 2, p5 an Position 6, p3 an Position 12 and P6 an Position 17.
    Die ersten Finger-Zeiger, die nur kleine Distanzen uberbrucken, zeigen zumeist nur auf den selben Peer, da die Anzahl n der Peers im Netzwerk typischerweise wesentlich geringer als die GroBe 2r" des Chord-Rings ist. So wird die Anzahl unterschiedlicher Finger-Zeiger zumeist deutlich niedriger als das theoretische Maximum in sein. Das folgende Lemma liefert eine genauere Aussage.
    Lemma 5.3. Ein Peer im Chord-Netzwerk besitzt mit hoher Wahrscheinlichkeit lediglich 0(logn) unterschiedliche Finger-Zeiger.
    Beweis. Diese Aussage folgt aus der unteren Schranke des Zustandigkeitsbereichs eines Peers (siehe Lemma 5.1).