Peer-to-Peer-Netzwerke: Algorithmen und Methoden

muss der Peer entscheiden, in welchem Teilbaum er eingesetzt wird. Hierzu kann er die Position der Teilbaume, die auf den Peers gespeicherte Datenmenge and deren Zustand verwenden, der anzeigt, ob sie moglicherweise auch gerade einen Teilbaum suchen.
    Eine optimale Entscheidung kann nicht garantiert werden. Die Autoren von PGrid untersuchten fur these Entscheidung verschiedene Heuristiken. Ist die Entscheidung fur einen Teilbaum gefallen, so kennt der Peer mindestens einen Knoten aus diesem Teilbaum aus der vorangegangenen Routing-Tabelle (wenn nicht, muss er annehmen, dass er der erste Knoten in diesem Teilbaum ist).
    Die Entwickler haben sich ausfuhrlich mit dem Fall befasst, wenn viele Peers das Netzwerk simultan betreten. Dann entsteht das Problem, dass sich sehr viele Peers eines Teilbaums gleichzeitig entscheiden mussen. Dadurch kann es sein, dass ein Peer nur andere Peers kennt, die sich nicht entschieden haben. Wartet nun jeder Peer, bis sich der andere entschieden hat, kann sich der Netzwerkaufbau stark verzogern. Daher haben die Autoren fur diesen Fall verschiedene heuristische Strategien untersucht and experimentell verglichen.
8.1.3 Suche
    In der Routing-Tabelle eines Peers steht fur jeden benachbarten Teilbaum die Adresse eines geeigneten Peers. Betrachtet man den identifizierenden Bitstring, so steht jeder Teilbaum fur einen moglichen Prafix. Damit gleicht die Routing-Tabelle der von Pastry and Tapestry. Der entscheidende Unterschied ist, dass Pastry and Tapestry auf verteilten Hash-Tabellen beruhen. Damit ist die Anzahl der Daten in jedem Prafix durch das Vermischen der Hash-Funktion einigermaBen gleichmaBig balanciert.

    Bei P-Grid ist genau das nicht der Fall, da die Daten nicht balanciert werden. Nur die Knoten werden gemaB der Datenanzahl auf die Teilbaume verteilt. Dadurch konnen Teilbaume beliebig tief werden. Hierbei ware nun zu befiirchten, dass die Suche bei solch ungleichmaBig balancierten Suchbaumen ineffizient werden konnte. Tatsachlich hilft die Balancierung der Peers, die Suche zu beschleunigen.
    Die Suche nach einem Datum lauft wie folgt ab: Passend zu dem Datum wahlt man das Prafix aus der Routing-Tabelle. Die Suchanfrage wird an den passenden Peer weitergeleitet. So fuhrt die Suche in dem Suchbaum immer weiter herab, bis das Datum gefunden wurde.
    Theorem 8.1. Die erwartete Anzahl an Hops bei der Suche in P-Grid ist O(log n), wenn n die Anzahl der Peers ist and die Anzahl der Peers in jedem Teilbaum proportional zu der Anzahl der Daten ist.
    Beweis. Der aktuelle Teilbaum der Suche ist der kleinste Teilbaum, der den aktuellen Peer and das gesuchte Datum enthalt. Wir betrachten die Suche nach einem Datum in Phasen. Ein Phasenwechsel tritt dann auf, wenn die Anzahl der Daten im aktuellen Teilbaum halbiert wurde. Ferner gehen wir davon aus, class in der Routing-Tabelle aller Peers jeder Knoten des entsprechenden Teilbaumes gleichwahrscheinlich vor- kommt.
    Zwar konnen die Baume eine Tiefe von bis zu n - 1 erreichen, aber jeder Teilbaum (mit dem Datum), der mehr als die Halfte der Peers besitzt, kann mit nur zwei Schritten erreicht werden. Aus der Markovschen Ungleichung (siehe Anhang Seite 268) folgt, dass die Wahrscheinlichkeit, in einem Schritt in diesem Baum zu gelangen, mindestens a ist. Scheitert dieser Schritt, dann erreicht man diesen Teilbaum im nachsten Schritt wieder mit der Wahrscheinlichkeit z and so weiter. (Das gilt nur unter der Annahme, class jeder Knoten eine unabhangige gleichwahrscheinliche Wahl des Peers aus den Nachbarbaumen trifft.) Die erwartete Anzahl von Schritten ist daher hochstens

    Wir betrachten also den kleinsten Teilbaum, der den Suchbaum enthalt and nicht die GroBe halbiert. Diesen erreichen wir in einer erwarteten Schrittzahl von zwei. Der nachste Teilbaum in der Suche ist damit kleiner als die Halfte der ursprunglichen Datenzahl. Somit tritt erwartungsgemaB nach spatestens drei Schritten ein Phasenwechsel ein.

8.1.4 Weitere Eigenschaften
    Neben der geordneten Sortierung and der effizienten Suche hat P-Grid noch folgende Eigenschaften.
    • Lokale Lastbalancierung
    In P-Grid werden die Peers fortwahrend umbalanciert. Wird ein Peer unterfor- dert, dann ubergibt er die Last einem benachbarten Peer and versucht einen Peer im Baum zu linden, der uberlastet ist. Die Baumstruktur passt sich so standig der Datenlast an. Als Information stehen den Peers hierfur nur die Kontaktpartner wahrend der Suche im Baum zur Verfugung.
    • Dynamische Adressen
    Durch die