Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Andernfalls route in Abhangigkeit des geringeren Abstands zur Ziel-ID zum Nachfolger oder Vorganger von p auf dem Ring and fahre mit Phase 3 fort.
    In den Phasen I and 2 besteht die Moglichkeit, dass entsprechende Aufwarts- bzw. Abwarts-Kanten nicht existieren and dann entlang des Rings geroutet werden muss. Der Grund hierfUr ist, dass die Ebenen zufallig gewahlt werden and somit nicht auszuschlieBen ist, dass bestimmte Ebenen von keinem der n Peers gewahlt wurden. Dies wird wegen Lemma 7.3 eher auf groBe Ebenen zutreffen. Aufgrund der zufalligen Wahl der IDs, des im vorigen Abschnitt beschriebenen Verfahrens zur Bestimmung der erforderlichen Ebenen sowie des Verfahrens zur Auswahl der Ebene erfullt das Viceroy-Netzwerk jedoch die folgenden Eigenschaften:

    Wir werden these Eigenschaften hier nicht beweisen, sie jedoch in den folgenden Lemmata and Theoremen verwenden. Wir werden nun den Routing-Algorithmus Rix Viceroy analysieren. Das folgende Lemma trifft zunachst eine Aussage uber die ersten beiden Phasen des Algorithmus.
    Lemma 7.5. In einem Viceroy Netzwerk mit n Peers benotigen die Phasen I and 2 des Routing-Algorithmus mit hoher Wahrscheinlichkeit O(log n) Schritte.

    Phase 2 benotigt ebenfalls mit hoher Wahrscheinlichkeit maximal O(log n) Schritte, da die Anzahl der Ebenen nach Lemma 7.3 durch O(log n) beschrankt ist and in jedem Schritt in die nachst Where Ebene gewechselt wird. ❑
    Die dritte Phase des Algorithmus benotigt unter Umstanden mehr als logarithmisch viele Schritte, wie das folgende Lemma zeigt.
    Lemma 7.6. In einem Viceroy Netzwerk mit n Peers benotigt die Phase 3 des Routing-Algorithmus im Erwartungswert O(log n) and mit hoher Wahrscheinlichkeit hochstens O(log2 n) Schritte.

    Es ist jedoch auch moglich, dass dist(p, id) > 1/2p.ebene gilt, die rechte Abwartskante jedoch hinter das Ziel zeigt and somit in Phase 3 ubergegangen wird. In diesern Fall wird das Ziel im Erwartungswert um O(log n) and mit hoher Wahrscheinlichkeit hochstens um O(log2 n) Peers auf deco Ring uberschritten (dies folgt aus Eigenschaft 2).
    Somit benotigt Phase 3 im Erwartungswert O(log n) and mit hoher Wahrscheinlichkeit hochstens O(log2 n) Schritte auf dem Ring. ❑
    Da sich die Gesamtzahl der benotigten Schritte des Routing-Algorithmus aus der Summe der Schritte der drei Phasen ergibt, erhalten wir aus Lemma 7.5 and Lemma 7.6 folgendes Korollar:
    Korollar 7.7. In einem Viceroy Netzwerk mit it Peers benotigt der Routing-Algorithmus im Erwartungswert O(log n) and mit hoher Wahrscheinlichkeit hochstens O(log2 n) Schritte.
    Der beschriebene Routing-Algorithmus benotigt also mehr Schritte als das Routing in den zuvor beschriebenen Netzwerken Chord, Pastry and Tapestry. Allerdings haben wir bislang auch nicht die Ebenen-Ringe fur das Routing verwendet. Tatsachlich lasst sich mit ihrer Hilfe die Anzahl der Routing-Schritte mit hoher Wahrscheinlichkeit auf O(log n) beschranken, was das Routing ahnlich effizient wie in den zuvor genannten Netzwerken macht.
    Die Laufzeit des Routing-Algorithmus wird bislang von der Laufzeit der dritten Phase dominiert, die mit hoher Wahrscheinlichkeit hochstens O(log2 n) Schritte benotigt. Urn die Gesamtlaufzeit zu verringern, mussen wir also einen Weg linden um in der dritten Phase Schritte einzusparen. Dies ist moglich, wenn wir Phase 3 wie folgt abandern. In der Beschreibung bezeichnen wir mit p.ebene_nach bzw. p.ebene_vor den Nachfolger bzw. Vorganger eines Peers p auf deco von p gewahltem Ebenen-Ring.

    Phase 3: Ring traversieren. Falls p der Nachfolger der Position id auf dem Ring ist, wurde das Ziel erreicht. Andernfalls route zum Peer p.ebene_nach falls gilt p.ebene_nach E [p, id] oder zum Peer p.ebene_vor falls gilt p.ebene_vor E [p, id] and fahre mit Phase 3 fort. Zeigt keine der Ebenen-Kanten in das Intervall [p, id], dann route in Abhangigkeit des geringeren Abstands zur Ziel-ID zum Nachfolger oder Vorganger von p auf dem Ring and fahre mit Phase 3 fort.
    Die Phasen I and 2 bleiben von den Anderungen unberuhrt, and wir werden den Algorithmus mit modifizierter dritten Phase fortan als erweiterten RoutingAlgorithmus bezeichnen.
    Das folgende Lemma zeigt, dass die modifizierte dritte Phase die Anzahl der benotigten Schritte tatsachlich um einen logarithmischen Faktor reduziert.
    Lemma 7.8. Die dritte Phase des erweiterten Routing-Algorithmus benotgt mit hoher Wahrscheinlichkeit O(log n) Schritte.
    Beweis. Im Beweis zu Lemma 7.6 haben wir bereits festgestellt, dass wir zu Beginn der dritten