Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Vereinfachend nehmen wir an, dass alle Peers einen Abstand von nur 2 haben. Rein theoretisch konnten sich maximal n° Peers mit diesem Abstand im Netzwerk befinden. Somit ergibt sich, class ein Peer mit hoher Wahrscheinlichkeit lediglich log n° = c log n unterschiedliche Finger-Zeiger besitzt.

    Damit ist die Chord-Datenstruktur sehr kompakt: Jeder Peer besitzt mit hoher Wahrscheinlichkeit lediglich eine Nachbarschaft logarithmischer GroBe. Somit ist die im Chord-Netzwerk von einem Peer zu verwaltende Nachbarschaftsinformation auch im Fall von sehr vielen Netzwerkteilnehmern noch uberschaubar gering.

    Abb. 5.3. Die Finger-Zeiger eines Peers in Chord.
Routing in Chord
    Wir werden nun sehen, wie mit Hilfe der Finger-Zeiger der fur ein Datum verantwortliche Peer im Netzwerk gefunden werden kann. Das Vorgehen bei der Suche ist denkbar einfach: Ein Peer p, der nach einem Datum x mit Position h'(x) = id auf dem Chord-Ring sucht, uberpruft zunachst, ob er das Datum x selbst verwaltet. Ist dies nicht der Fall, wird die Suchanfrage uber einen der Finger-Zeiger an einen anderen Peer weitergeleitet. Hierbei wird immer der Finger-Zeiger gewahlt, der am nachsten an die Postion h'(x) = id auf dem Chord-Ring zeigt and gleichzeitig noch vor der Position id liegt. Auf these Weise wird die Anfrage an den letzten Peer p' vor Position id des Chord-Rings geleitet. Der Nachfolger von p' ist dann der fur das Datum x verantwortliche Peer. Der gerade beschriebene Algorithmus findet sich als Pseudo-Code in Abbildung 5.4.
    Abbildung 5.5 zeigt den moglichen Verlauf einer Suche im Netzwerk. Wichtig ist wiederum die Frage, wie viele Peers in eine Suchanfrage involviert sind and wieviele Nachrichten benotigt werden. Das folgende Theorem zeigt, dass die Suche in Chord sehr effizient ist.

    Abb. 5.4. Pseudo-Code Algorithmus fur die Suche in Chord. Variablen wie Finger-Zeigern and Funktionsaufrufen ist jeweils der betreffende Peer vorangestellt. So bezeichnet z.B. p.Finger[i] den Peer, auf den der i-te Finger-Zeiger des Peers p zeigt.
    Abb. 5.5. Suche im Chord-Netzwerk mittels des Algorithmus aus Abbildung 5.4. Ausgehend von Peer p6 mit Position h(P6) = 17 auf dem Chord-Ring wird nach einem Datum mit'id = 8 gesucht.

    Theorem 5.4. Die Suche im Chord-Netzwerk benotigt hochstens 0(m) and mit hoher Wahrscheinlichkeit nicht mehr als O(log n) Nachrichten.
    Beweis. Fur die obere Schranke von O(m) Nachrichten mussen wir zeigen, dass die Distanz zwischen Start and Ziel der Suche in jedem Schritt mindestens halbiert wird. Bei Ring-Grode 2m ergeben sich dann log 2m = m Schritte im obigen Algorithmus and somit 0(m) Nachrichten.
    Nehmen wir an, Peer p sucht ein Datum mit Position h(p) - 1 auf dem ChordRing, also ein Datum, fur das sein Vorganger p' verantwortlich ist, sofern p nicht der einzige Peer im Netzwerk ist. Da bei der Suche nur im Uhrzeigersinn auf dem Ring vorangeschritten wird, ist die Distanz zwischen Start and Ziel der Suche hier 2" - 1 and somit maximal.
    Peer p wird die Suchanfrage an denjenigen der ihm bekannten Peers weiterleiten, der sich am ndchsten an Position h(p) - 1 befindet, ohne these Position zu uberschreiten. Dies ware der im m-ten Finger-Zeiger Finger[m] gespeicherte Peer. Wir erinnern uns, dass der i-te Finger-Zeiger eine Distanz von mindestens 2i-1 auf dem Cord-Ring uberbruckt. Somit wird die Suche an einen Peer weitergeleitet, dessen Distanz zum Ziel hochstens noch 2m - 2m-1 betragt. Das bedeutet, dass die Distanz zum Ziel halbiert wird. Dies gilt auch fur alle weiteren Schritte der Suche, so dass die Distanz nach m Schritten Eins ist and wir am Ziel angekommen sind. So sind maximal 0(m) Peers in eine Suche involviert and es werden maximal 0(m) Nachrichten benotigt.

    Nicht weniger wichtig als eine effiziente Suche ist das effiziente Einbinden neuer Peers in das Netzwerk. Das gilt insbesondere im Fall von Peer-to-Peer Netzwerken: Diese unterliegen typischerweise einer andauernden Verdnderung der Netzwerkteilnehmer. So werden wir im Folgenden analysieren, wie ein neuer Peer in ein ChordNetzwerk eingebunden werden kann and wie viele Nachrichten notwendig sind.
    In Abschnitt 5.1 haben wir bereits gesehen, dass beim Einfugen eines neuen Peers p",+1 der Zustandigkeitsbereich des fur die Position h(p",+1) des ChordRings verantwortlichen Peers pi zwischen pi and p",+1 aufgeteilt wird (siehe Abbildung 5.2). Um dies zu initiieren, muss Peer p,"+1 also zunachst Peer pi kontaktieren. Dies geschieht ausgehend von einem beliebigen, Peer p"+i