Peer-to-Peer-Netzwerke: Algorithmen und Methoden

vorgestellte Such-Algorithmus (siehe Abbildung 5.4) benotigt doppelt so viele Nachrichten, wie Peers besucht werden. Mitjedem weiteren Schritt der Suche werden zwei weitere Nachrichten benotigt: eine zum nachsten Peer p der Suche and die entsprechende Antwortnachricht des Peers p. Verlauft die Suche also uber Peers pi, ... , pj, werden zunachst Nachrichten von pl nach p2 usw. his pj gesendet and anschlieBend in umgekehrter Reihenfolge zuruckgesendet.
    Hier konnen j -1 Nachrichten and somit ein nicht unerheblicher Anteil der Suchzeit eingespart werden, wenn mit der Suche gesendet wird, welcher Peer die Suche initiiert hat. Anstatt die Antwort dann vom Ziel-Peer fiber alle anderen j - 1 Peers zuruckzuleiten, kann die Antwort dann direkt an den Start-Peer gesendet werden. Als Nachteil dieser modifizierten Suche ist die eingeschrankte Fehlerkontrolle anzusehen. Geht eine der Nachrichten verloren, z.B. falls ein kontaktierter Peer das kurz zuvor Netzwerk verlassen hat, so erhalt der suchende Peer keinerlei Rfickmeldung an welcher Stelle and weshalb die Suche gescheitert ist. In diesem eher seltenen Fall kann jedoch jedoch auf den Such-Algorithmus aus Abbildung 5.4 zuruckgegriffen werden, der eine solche Rfickmeldung ermoglicht. Wir werden bei unseren weiteren Uberlegungen von dem Suchalgorithmus mit reduzierter Nachrichtenanzahl ausge- hen.
    Eine grundsatzliche Technik fur die Minimierung von Latenzzeiten beim Routing wird von Gummadi et al. in [40] vorgestellt: Proximity Neighbor Selection (PNS). Bei PNS werden beim Aufbau der Routing-Tabellen latenznahe Peers bevorzugt. Wir widmen uns nun der Frage, wie sich dies in Chord realisieren lasst.
    Im urspriinglichen Chord-Netzwerk zeigt der i-te Finger-Zeiger eines Peers p auf einen Peer im Bereich (h(p) +2') mod 2m bis (h(p) + 2'+1) mod 2'des ChordRings, wenn wir annehmen dass der i-te Finger-Zeiger ungleich dem (i + 1)-ten and (i - 1)-ten Finger-Zeiger ist. Der PNS-Algorithmus betrachtet anstelle des ersten Peers, der der Position (h(p) + 2') mod 2" auf dem Chord-Ring folgt, die ersten k Peers, die dieser Position folgen (moglicherweise auch weniger als k, falls sich nicht genugend Peers in diesem Intervall befinden). Ffir den Finger-Zeiger wird derjenige dieser k Peers gewahlt, dessen Latenz zu Peer p am geringsten ist.

    Das Routing in Chord bleibt bei Verwendung von Proximity-Neighbor-Selection unverandert: In jedem Schritt wird derjenige Peer ausgewahlt, der dem Ziel nachsten liegt, ohne dieses zu uberschreiten. Experimente in [39] zeigen, dass es in der Praxis genUgt, jeweils den latenznahesten aus k = 16 Peers zu wahlen, anstatt alle in Frage kommenden Peers zu betrachten.
    Interessanterweise nimmt die Latenzzeit einer Suche mit der NetzwerkgroBe kaum zu. Wie lasst sich dies erklaren? Eine Intuition liefert die folgende Uberlegung: Wir nehmen vereinfachend an, dass die Latenzzeiten gleichmaBig (uniform) verteilt sind. Sei des Weiteren b die durchschnittliche Latenzzeit. Wir betrachten nun eine Suche im Netzwerk. Diese besteht aus O(log n) Hops vom Start zum Ziel and einem letzten Hop vom Ziel zuruck zum Startpunkt der Suche. Fur den letzten Hop der Suche gibt es keine Wahlmoglichkeiten zwischen verschiedenen Peers, denn er muss vom vorletzten zum Ziel-Peer fUhren and benotigt somit Latenzzeit b. Beim vorletzten Schritt kann aus zwei moglichen Peers der nahere gewahlt werden, so dass sich hier eine erwartete Latenzzeit von 612 ergibt. In jedem weiteren Schritt davor verdoppelt sick jeweils die Anzahl moglicher Peers. Summieren wir these Latenzzeiten auf and fugen noch einmal Latenzzeit b fur den Hop vom Ziel zuruck zum Start hinzu, ergibt sich eine gesamte Latenzzeit von

    Dieses Verhalten wird durch Simulationen bestatigt. Die Latenzzeit beim Routing mit PNS kann also durch eine unendliche geometrische Reihe approximiert werden, die schnell konvergiert. Dies ist der Grund dafur, class die Gesamtlatenz einer Suche, fast unabhangig von der Anzahl der Netzwerkteilnehmer n, immer nahe dem Wert 36 liegt, auch wenn die Anzahl der Hops fur die Suche mit O(log n) deutlich schwacher wachst als n.
5.4 Zusammenfassung and Vergleich
    Vergleicht man das im vorigen Kapitel vorgestellte CAN mit Chord, so bieten beide Netzwerke die gleiche Funktionalitat: Sowohl CAN als auch Chord stellen Suchfunktionen bereit, die ein Datum garantiert finden, falls es sich im Netzwerk befindet. Unterschiede bestehen in der Effizienz. Wahrend die grundlegende CAN- Struktur O(n1/2) Schritte fur die