Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Netzwerk, ohne dass dieses lokal wahrgenommen wird. So ist prazises Zahlen in einem groBen Peer-to-Peer-Netzwerk nicht moglich, da dadurch bei jeder Anderung der Teilnehmerzahl Kommunikation zwischen allen n Peers erforderlich wird.
    Die Autoren von Viceroy schlagen die Berechnung des Naherungswertes n' anhand des erwarteten Abstands zweier auf dem Ring benachbarter Peers im [0, 1) Intervall vor. Da wir annehmen, dass die Peer-IDs uniform im [0, 1) Intervall verteilt sind, ist der erwartete Abstand zwischen zwei benachbarten Peers auf dem Ring gerade 1/n. Bezeichnet nun dist(pa, pb) den Abstand in positiver Zahlrichtung zwischen zwei benachbarten Peers pa and Pb im [0, 1) Intervall, dann kann der Naherungswert n' durch

    bestimmt werden. Der so bestimmte Naherungswert n' ist eine relativ grobe Schatzung, wie das folgende Lemma zeigt.
    Lemma 7.3. In einem Netzwerk mit n Peers wird durch das oben beschriebenen Verfahren jeder Peer die geschatzte Anzahl der erforderlichen Ebenen [log n'] so bestimmen, dass Konstanten c and c' existieren, so dass

    mit hoher Wahrscheinlichkeit gilt.

    Ein positiver Effekt dieses Verfahrens zur Schatzung ist, dass die Schatzung n' eines Peers p lediglich von seinem Nachfolger auf dem Ring abhangt and sich die Schatzung somit auch lediglich andert, wenn sich der Nachfolger auf dem Ring andert. Falls sich durch den neuen Schatzwert n' auch der Wert [log n'] andert, wurde Peer p eine neue Ebene wahlen. Tatsachlich wird p die Ebene jedoch nur wechseln, falls die zuvor gewahlte Ebene nicht linger existiert oder die neu gewahlte Ebene zuvor nicht existiert hat (andernfalls ist die zuvor getroffene zufallige Wahl ausreichend).

    Wird eine genauere Schatzung von it benotigt, so kann man anstelle des Abstands zum nachsten Peer auf dem Ring, den Abstand d zum k-nachsten Peer des Rings im [0, 1) Intervall fur eine ausreichend groB gewahlte Konstante k betrachten. Die Anzahl n der Peers kann dann durch
    / n k = d
    abgeschatzt werden. Wir werden dieses Verfahren zur Schatung von nun an als er- weitertes Schatzverfahren bezeichnen.
    Fur den Erwartungswert E[d] des Abstands gilt E[d] = kin. Auch hier kann gezeigt werden, dass die Abweichung von diesem Erwartungswert mit hoher Wahrscheinlichkeit durch einen logarithmischen Faktor nach oben and durch einen po- lynomiellen Faktor nach unten beschrankt ist. Fur die Schatzung der erfoderlichen Anzahl an Ebenen gelten beim erweiterten Schatzverfahren insbesondere die im folgenden Lemma angegebenen Schranken, welche die Grundlage fur unsere weitere Analyse des Viceroy-Netzwerks darstellen.
    Lemma 7.4. Fur jedes c' > 1 and c > 0 kann in einem Viceroy-Netzwerk mit is Peers durch das erweiterte Schdtzverfahren mit geeignet gewdhlten Parameter k E 0(1) jeder Peer die geschatzte Anzahl der erforderlichen Ebenen [log n'] so bestimmen, dass

    mit holier Wahrscheinlichkeit gilt.
    Der Beweis ergibt sich durch die Betrachtung des Nachbarintervalls eines messenden Peers and Anwendung der Chernoff-Schranken. Wir werden wie im Originalartikel im Folgenden annehmen, dass eine Abschatzung von

    mit holier Wahrscheinlichkeit vorliegt (obgleich eine genauere Schatzung moglich ist).
7.1.5 Routing
    Wie schon die Netzwerkstruktur, ist auch Viceroys Routing-Algorithmus komplizier- ter als diejenigen vergleichbarer Netzwerke. Das Routing geschieht in drei Phasen, fur die wir bier eine textuelle Beschreibung anstelle einer Pseudo-Code Beschreibung geben werden, um das Verstandnis nicht unnotig zu erschweren. Im Folgenden beschreibt p jeweils den gerade aktiven Peer des Routings sowie dessen ID im [0, 1) Intervall. Mit p.ebene bezeichnen wir die Ebene des Peers p and mit id E [0, 1) das Ziel des Routings. Die drei Phasen gestalten sich dann wie folgt.
    Phase 1: Routing zu Ebene 1. Route entlang der Aufwartskanten bis zu einem Peer der Ebene 1. Sobald ein Peer der Ebene 1 erreicht wurde, fahre mit Phase 2 fort. Falls eine Aufwartskante nicht existiert, ubergebe die Anfrage an den Nachfolger auf dem Ring and fahre mit Phase 1 fort.

    Phase 2: Baum traversieren. Falls dist(p, id) < 1/2P-ebene route entlang der linken Abwartskante and fahre mit Phase 2 fort. Falls dist(p, id) > 1/2P.ebene route entlang der rechten Abwartskante and fahre mit Phase 2 fort. Sollte die gewahlte Abwartskante nicht existieren oder auf ein Peer p' mit p' > id zeigen, fahre mit Phase 3 fort.
    Phase 3: Ring traversieren. Falls p der Nachfolger der Position id auf deco Ring ist, wurde das Ziel erreicht.