Peer-to-Peer-Netzwerke: Algorithmen und Methoden

bereits bekannten, Peer mit Hilfe des Such-Algorithmus and benotigt mit hoher Wahrscheinlichkeit lediglich O(log n) Nachrichten.
    Wurde der Bereich des Chord-Rings aufgeteilt and pn,+1 in die Ringstruktur eingebunden, gilt es noch die Finger-Zeiger anzupassen. Hier mussen einerseits die ausgehenden Finger-Zeiger von Pn+l aufgebaut werden and andererseits FingerZeiger von Peers aktualisiert werden, die in den Bereich zwischen Pn+1 and seinem Vorganger auf dem Chord-Ring zeigen. Betrachten wir zunachst die Finger-Zeiger von p.+1• Wir haben bereits gesehen, class ein Peer mit hoher Wahrscheinlichkeit nur O(log n) verschiedene Finger-Zeiger besitzt, so dass das Anpassen der FingerZeiger von Pn+1 mit hoher Wahrscheinlichkeit mit 0 (logy n) Nachrichten geschehen kann.

    Die Frage, wie viele Nachrichten fur das Anpassen der auf p,,,+1 zeigenden Peers notwendig sind, ist schwieriger zu beantworten. Wir uberlegen uns zunachst, wie viele Peers auf p,,+1 zeigen werden. Das folgende Lemma liefert eine obere Schranke fur diesen Wert.
    Lemma 5.5. Die Anzahl der Peers, die einen Finger-Zeiger auf einen Peer p besitzen, ist im Erwartungswert O(log n) and mit hoher Wahrscheinlichkeit beschrankt durch 0 (loge n).
    Beweis. Die Aussage uber den Erwartungswert ergibt sich daraus, dass die Anzahl der eingehenden Kanten gleich der Anzahl der ausgehenden Kamen ist. Damit ist fur einen Peer der erwartete Eingrad gleich dem erwarteten Ausgrad.
    Um zu zeigen, dass der Eingrad mit hoher Wahrscheinlichkeit durch 0 (loge n) beschrankt ist, betrachten wir ein Peer Pk mit Vorganger pj auf dem Chord-Ring. Aus Lemma 5.1 folgt, dass es mit hoher Wahrscheinlichkeit nur 0(log n) Bereiche gibt, aus denen Peers auf Pk zeigen.

    and somit befinden sich mit hoher Wahrscheinlichkeit nicht mehr als O(log n) Peers in einem Intervall der GroBe 1.
    Fassen wir unsere Uberlegungen zusammen, ergibt sich, dass Peers aus 0(log n) Bereichen auf den Peer Pk zeigen and sich in jedem dieser Bereiche mit hoher Wahrscheinlichkeit nicht mehr als ((log n) Peers befinden. Somit ist der Eingrad von Pk mit hoher Wahrscheinlichkeit durch 0 (loge n) beschrankt. ❑
    Wenden wir uns wieder der Anzahl benotigter Nachrichten zum EinfUgen eines neuen Peers Pn+1 zu. Wir wissenjetzt, class mit hoher Wahrscheinlichkeit nicht mehr als 0 (loge n) Peers auf pn+1 zeigen werden. Diese Peers gilt es nun effizient Uber den neuen Netzwerkteilnehmer pn+1 zu benachrichtigen.
    Wir nutzen aus, dass die 0 (log2 n) Peers in 0 (log n) zusammenhangenden Bereichen liegen and betrachten zunachst nur einen dieser Bereiche. Um einen Peer in diesem Bereich zu benachrichtigen, konnen wir den Suchalgorithmus verwenden. Um dann die weiteren O(log n) Peers dieses Bereichs zu informieren, sind nur O(log n) weitere Nachrichten erforderlich, wenn die Nachricht entlang des ChordRings weitergeleitet wird. Des Weiteren ist der Aufwand zur Anpassung des jeweiligen Finger-Zeigers konstant. Somit benotigen wir 0 (log n) Nachrichten fur die Anpassung der Finger-Zeiger aller Peers eines dieser Bereiche.

    Da es insgesamt O(log n) dieser Bereiche gibt, werden mit hoher Wahrscheinlichkeit 0 109,2 n) benotigt, um alle auf p,,+, zeigenden Finger-Zeiger anzupassen. Durch unsere Uberlegungen ergibt sich folgendes Theorem:
    Theorem 5.6. Um einen neuen Peer in Chord einzufiigen, geniigen mit polynomiell hoher Wahrscheinlichkeit 0 (logz n) Nachrichten.
    Abb. 5.6. Eingrad eines Peers Pk in Chord. Es zeigen Peers aus log n Bereichen des ChordRings auf einen Peer pk.

5.3 Latenzoptimiertes Routing
    Wir haben bereits im Fall von CAN gesehen, dass es Moglichkeiten gibt, die Latenzzeiten beim Routing zu verringern oder die Zuverlassigkeit eines Netzwerks zu erhohen. Auf den ersten Blick ist dies fur Chord nicht ohne Weiteres moglich. Tatsachlich kann man aber mit Hilfe neuer Techniken auch in Chord die Latenzzeiten verringern. Wir werden hier die von Dabek, Li, Robertson and Kaashoek in [39] vorgestellten Ergebnisse erlautern.
    Wir gehen dabei von der im letzten Abschnitt beschriebenen Chord-Struktur mit Chord-Ring and Finger-Zeigern aus. Unser Ziel ist es, Routing-Zeiten im Netzwerk zu reduzieren. Um dies zu erreichen, werden wir zum einen den Such-Algorithmus etwas abwandeln and zum anderen versuchen, die Chord-Verbindungsstruktur dahingehend zu optimieren, dass die Finger-Zeiger der Peers zu moglichst latenznahen Peers ffihren - also Peers, die im Underlay-Netzwerk, dem Internet, nicht weit entfernt sind.
    Der im letzten Abschnitt