Peer-to-Peer-Netzwerke: Algorithmen und Methoden

8.8. Baumformige Struktur eines Skip-Graphen.

    Die Name-ID ist eine eindeutige Identifikation des Peers, wobei hier zum Beispiel eine inhaltliche Klassifikation vorgenommen werden kann. Zum Beispiel konnte das

    sein, in Anlehnung an den Hostnamen

    Dieser Name stUnde dann zwischen

    Durch these Art der Darstellung werden Peers, die sich in gleichen lokalen Domains oder Netzwerken befinden, nahe zueinander angeordnet. Durch die Art der Namens- wahl kann man sehr einfach die Lokalitat des Netzwerks steuern. Diese Steuerung ist aber nicht Bestandteil von Skip-Graph and muss von den Betreibern des Netzwerks beigesteuert werden.
    Die Num-ID wird durch den Zufallsprozess des Skip-Graphen erzeugt. Wir erinnern uns, dass fur jeden Knoten eine Folge von Zufallsbits erzeugt wird, bis diese sick unterscheiden. Diese Num-ID dient jetzt als alternative Adresse (zu der IPAdresse and der Name-ID). Im Gegensatz zur Name-ID sind die Peers hier namlich namlich einigermaBen gleichverteilt (im Rahmen des Zufallsprozesses).
8.2.3 Suche im Skip-Graphen
    Skip-Graphen erlauben sowohl die effiziente Suche nach den Name-IDs als auch den Num-IDs.
    Suche nach Peer-Namen (Name-ID). Diese Suche lauft analog zur Suche in einer Skip-Liste ab. Wir starten von einem Peer des Netzwerks and wahlen die hochste Ebene, in der ein Zeiger nicht das Ziel uberspringt. Die Suche wird dann in dem verlinkten Peer fortgesetzt. Wieder wird die hochste Ebene gewahlt, in welcher der gesuchte Peer nicht ubersprungen wird. Das folgende Theorem liefert eine Aussage uber die Anzahl der erforderlichen Schritte.
    Theorem 8.2. Fur die Suche nach einer Name-ID werden mit hoher Wahrscheinlichkeit hochstens O(log n) Schritte benotigt.
    Beweis. Der Beweis dieses Theorems folgt unmittelbar aus der Tatsache, dass in Skip-Listen in logarithmischer Zeit mit hoher Wahrscheinlichkeit gesucht werden kann. ❑
    Suche nach (numerischer) Knoten-ID (Num-ID). Jedem Peer wird eine eindeutige Bitfolge, die Num-ID, zugeordnet. Diese besteht aus einer zufalligen Folge von Bits. Nach dieser numerischen ID kann ebenfalls effizient gesucht werden. Mit Hilfe dieser Suche kann man in Skip-Net auch verteilte Hash-Tabellen (DHT) implemen- tieren.

    Abb. 8.9. Suche nach dem Schlusselwort f (Name-ID) in Skip-Net
    Hierzu startet man die Suche auf dem untersten Ring. Ein Peer sucht in der Ebene i nach einem Peer, der an der (i + 1)-ten Stelle dasselbe Bit wie die gesuchte ID besitzt. Dies geschieht durch lineares Ablaufen des Rings. Ist das gewunschte Bit gefunden, wechselt man zum nachsthoheren Ring. Dort wird die Suche mit einem um Eins erhohten i fortgesetzt. Wurde ein Ring erfolglos umlaufen, endet die Suche and zu mindestens wurden alle Peers mit dem langsten gemeinsamen Prafix von Num-ID gefunden.
    Theorem 8.3. Fur die Suche nach einer Num-ID werden mit hoher Wahrscheinlichkeit hochstens O(log n) Schritte benotigt.
    Beweis. Als erstes beobachten wir, dass es mit hoher Wahrscheinlichkeit hochstens O(log n) Ebenen gibt. In jeder Ebene ist die Wahrscheinlichkeit, dass die Suche schon nach dem nachsten Schritt endet z . Damit beobachten wir O(log n) Bernoulli- Experimente. Aus der Chernoff-Schranke, siehe Seite 268, folgt das Theorem. ❑
    Diese Analysen beruhen auf der zufalligen Wahl der Num-IDs. Wir sehen also, dass die Sortierung der Peers keine Einschrankung bei der Suche ergibt.
8.2.4 Einfiigen von Peers
    Folgender Algorithmus fugt Peers in die Datenstruktur ein. Zuerst wird der korrekte Ort gemaB der Name-ID des Peers gesucht. Dann wird der Peer in den Ring eingef igt. Nun wurfelt der Peer die Num-ID and fugt sich rekursiv in die passenden hoheren Ebenen ein. Um die nachsthohere Ebene zu finden, mussen von dem Peer aus erwartungsgemaB zwei Nachbarpeers abgefragt werden. Wie wir bereits gesehen haben, gibt es mit hoher Wahrscheinlichkeit hochstens 0 (log n) Ebenen. Daher kann man dutch Anwenden der Chernoff-Schranke wieder folgern, dass das Einfugen eines Peers hochstens O(Ion) Operationen benotigt. g

    Theorem 8.4. Das Einfugen eines Peers in Skip-Net benotigt mit hoher Wahrscheinlichkeit O(log n) Nachrichten.
    Der Beweis folgt unmittelbar aus den vorangestellten Uberlegungen.
Bereichsanfragen
    Bereichsanfragen konnen in Skip-Net bezuglich Num-IDs and Name-IDs durchgefuhrt werden. Fur eine Bereichsanfrage sucht man nach alien Peers, die sich in einem gegebenen Intervall befinden.
    Sucht man einen bestimmten Bereich in den Num-IDs, so findet man die Losung in den Blattern der Struktur. Hierzu