Peer-to-Peer-Netzwerke: Algorithmen und Methoden

dem vollstandigen Netzwerk ist erstaunlich gering: Das Routing in Pastry benotigt durchweg hochstens 30%-40% mehr Zeit als das Routing im vollstandigen Netzwerk, also als die bestmogliche Verbindung. Des Weiteren scheint die Latenzzeit beim Routing mit steigender Knoten- zahl nicht zuzunehmen.

    Mit der Parameterwahl b = 4, £ = 16 and J11II = 32 wird die Anzahl der Verbindungen je Peer relativ groB. Damit kann der Faktor 2b/b 4 das Ergebnis erheblich beeinflussen. Wenn sich zum Beispiel n = 106 Peers im Netzwerk befinden, dann unterhalt jeder Peer bereits (2b - 1) 101-2b n > 60 Verbindungen in seiner Routing-Tabelle. Hinzu kommen noch 16 Verbindungen im Leaf-Set L and 32 in der Menge Al latenznaher Peers. Dadurch ist der Grad des Netzwerks verglichen mit den vollstandigen Netzwerk zwar noch gering, im Verhaltnis zu anderen Peer-toPeer-Netzwerken wie Chord allerdings sehr groB.

Knotenausfalle
    Zuletzt seien hier noch die experimentellen Ergebnisse fur die Zuverlassigkeit des Reparaturmechanismus aufgefuhrt (Abbildung 6.11). Ausgehend von einem Netzwerk mit n = 5000 Peers, b = 4, f = 16 and IMF = 32 werden 10% der Peers aus dem Netzwerk entfernt. Nach diesen simulierten Peer-Ausfallen werden eine ID and zwei Peers zufallig gewahlt. Dann wird von diesen beiden Peers eine Suche nach der zufalligen ID durchgefuhrt. Dieser Vorgang wurde 100.000 mal wiederholt. Abbildung 6.11 zeigt den Zustand der Routing-Tabellen vor and nach diesem Experiment, sowie mit and ohne Reparaturmechanismus.
    Abb. 6.11. Gute der Routing-Tabelle von Pastry vor and nach dem Ausfall von 500 von 5.000 Peers and nach Abschluss der Reparatur-Routine [11].

6.3 Tapestry
    Das Peer-to-Peer-Netzwerk Tapestry [ 12] wurde in seiner ursprunglichen Version von Ben Y. Zhao, John D. Kubiatowicz and Anthony Joseph an der University of California, Berkeley, entwickelt. Wie auch bei Pastry, ist die Netzwerkstruktur an diejenige des Plaxton-Routings angelehnt. Als Besonderheit ist im Vergleich zu einigen anderen Peer-to-Peer-Netzwerken hervorzuheben, dass Tapestry wie auch Pastry beim Aufbau der Netzwerkstruktur die Netzwerklokalitat berucksichtigt, um die beim Routing entstehenden Latenzzeiten gering zu halten. Wir werden zunachst einige grundlegende Begriffe kennenlernen and uns dann mit der Netzwerkstruktur, dem Routing, der Verwaltung von Daten and dem Einfugen neuer Peers beschaftigen.
Grundlegende Terminologie
    Wie auch in den Netzwerken Chord and Pastry beruht die Zuordnung von Daten zu Peers in Tapestry auf verteilten Hash-Tabellen uber einem eindimensionalen Raum. Das bedeutet, dass Daten bzw. Peers im Tapestry-Netzwerk durch eindeutige DatenIDs bzw. Peer-IDs identifiziert werden. Peer-IDs konnen wie zuvor zufallig vergeben oder durch Hash-Funktionen bestimmt werden. Daten-IDs werden, wie schon bei CAN, Chord and Pastry, durch kryptographische Hash-Funktionen berechnet.
    Wie beim Verfahren von Plaxton et al. and Pastry werden die IDs als Zahlen zu einer Basis 2b, b E N interpretiert. Sei von nun an B = {0, ... , 2b-1 I die Menge der moglichen Ziffern fur Peer- sowie Daten-IDs and bezeichne Ian fur eine Zahl a zur Basis 2b die Lange dieser Zahl in Ziffern aus B. Des Weiteren stellt die Schreibweise a o /3 fur zwei Zahlen a and /3 fortan die Konkatenation eben dieser dar.
6.3.1 Netzwerkstruktur
    Die Nachbarschaft eines Peers in Tapestry ist eng angelehnt an die Verbindungsstruktur beim Verfahren von Plaxton et al. and ahnelt somit auch der Routing-Tabelle eines Pastry-Peers (siehe Seite 100). Im Gegensatz zu Pastry beschranken sich die Nachbarschaftsinformationen eines Peers in Tapestry jedoch auf eine einzige Menge, die wir fortan als Routing-Tabelle bezeichnen. Wir werden im Folgenden den Aufbau der Routing-Tabelle beschreiben. Die Beschreibung ist dabei etwas formaler als zuvor im Fall von Pastry, da wir die formale Notation fur die spateren Analysen benotigen.
    In seiner Routing-Tabelle unterhalt ein Peer p Verbindungen zu ausgewahlten anderen Peers, die ein Prafix z seiner ID mit ihm teilen. Wieder ist die RoutingTabelle in so genannte Level unterteilt, wobei der Level die Lange des gemeinsamen Prafix zwischen Peer-ID and den Eintragen der Routing-Tabelle angibt.
    Grundsatzlich kann ein Peer p mit einem Peer p' im Level f benachbart sein, falls es eine Zahl z der Lange IzI = £ gibt, so dass p = z o b and p' = z o b' fur zwei geeignete Zahlen S, b', die sich in ihrer ersten Ziffer unterscheiden. Also bezeichnet £ = IzI den Level der Nachbarschaft.