Peer-to-Peer-Netzwerke: Algorithmen und Methoden

b E N interpretiert. In der Praxis wird typischerweise der Parameter b = 4 and somit die Basis 16 verwendet. Bezeichne fortan B = {0, 1, ... , 2b - 1} die Menge der moglichen Ziffern fiir Peer- bzw. Daten-IDs.
    In Pastry wird ein Datum jeweils von demjenigen Peer verwaltet, dessen ID der ID des Datums numerisch am nachsten ist. Beim naheren Hinsehen unterscheidet sich dieses Verfahren zur Zuweisung von Daten zu Peers nicht sehr von demjenigen im Chord-Netzwerk, schlieBlich wird in beiden Netzwerken ein eindimensionaler Raum fur these Zuweisung verwendet.
6.2.1 Netzwerkstruktur
    Die Netzwerkstruktur von Pastry ist eng angelehnt an die primaren Nachbarschaftslisten des Plaxton-Routings [13]. Die den primaren Nachbarschaftslisten entsprechenden Verbindungen eines Peers werden in Pastry als Routing-Tabelle R bezeichnet. Zusatzlich zur Routing-Tabelle unterhalt jeder Peer noch zwei weitere Mengen von Netzwerkverbindungen, welche als Leaf-Set L and Nachbarschaftsmenge M bezeichnet werden. Wir werden den Aufbau dieser drei Mengen von Netzwerkverbindungen im Folgenden naher betrachten.
Die Routing-Tabelle R
    Wie bereits erwahnt, wird die ID eines Peers als Zahl zur Basis IB I = 2b interpretiert. Ein Peer p kennt fur jedes Prafix z der eigenen ID and fur jede Ziffer j E B einen anderen Peer, dessen ID mit z o j beginnt (siehe Abbildung 6.1), es sei denn z o j ist ein Prafix der ID von p. Hier stellt o die Konkatenation zweier Ziffernfolgen dar. Ein Beispiel fur eine Routing-Tabelle fur den Fall b = 2 and 16-Bit IDs ist fur einen Peer p mit ID 2310 in Abbildung 6.1 dargestellt. Die oberste Zeile der Routing-Tabelle enthalt Peers, deren ID kein gemeinsames Prafix mit p teilen, die nachste Zeile enthalt Peers, deren ID, ebenso wie diejenige von p, mit 2 beginnt, usw. Grau hinterlegt sind die Eintrage der Routing-Tabelle, die einem Prafix der ID 2310 entsprechen and somit leer sind. Wir bezeichnen die Eintrage der Routing-Tabelle im Folgenden auch als Level i-Nachbarn, wobei i die Lange des gemeinsamen Prafixes bezeichnet, also die Zeile in der Routing-Tabelle.

    Abb. 6.1. Routing-Tabelle R eines Peers in Pastry.
    Existiert im Netzwerk fur ein Prafix z and ein j e B kein Peer, dessen ID mit z o j beginnt, so bleibt der entsprechende Eintrag der Routing-Tabelle leer. Existieren hingegen mehrere Peers, deren IDs dieser Bedingung genugen, wird aus diesen der nachste Peer bezuglich der Latenzzeit (RTT - Round Trip Time) im UnderlayNetzwerk gewahlt.
    Die Routing-Tabelle eines Peers ist also nicht notwendigerweise vollstandig besetzt. Durch die zufallige Wahl der Peer-IDs Lassen sich folgende Aussagen uber die Anzahl der Eintrage in der Routing-Tabelle treffen.

    Beweis. Die Wahrscheinlichkeit, dass ein Peer ein bestimmtes m-stelliges Prafix erhalt, ist 2-bm. Damit ist die Wahrscheinlichkeit, dass ein m-stelliges Prafix im Netzwerk an einen Peer vergeben wird, hochstens
    7L2-bm

Das Leaf-Set L
    Das Leaf-Set L, ILI = £, eines Peers p besteht aus den £/2 Peers mit der nachst hoheren and ?/2 Peers mit der nachst niedrigeren ID zu p. Als triviale Beobachtung halten wir test, dass durch das Leaf-Set unter anderem eine Ringstruktur entsteht, durch die bereits ein grundlegendes Routing realisiert werden kann. Im Fall £ = 2 entspricht these gerade dem Chord-Ring (siehe auch Kapitel 5). In Abbildung 6.2 wird beispielhaft fur den Fall f = 4 das Leaf-Set eines Peers mit ID 2310 dargestellt.
    Abb. 6.2. Leaf-Set L eines Peers in Pastry.
Die Nachbarschaftsmenge M
    Die Nachbarschaftsmenge M besteht typischerweise aus IMF = 2b Verbindungen zu den Peers des Netzwerks, die gemaB der Latenzzeit am nachsten sind. Die IDs der Peers in M ist hierbei beliebig. Hierbei ist anzumerken, dass die Nachbarschaftsmenge M normalerweise nicht fur das Routing verwendet wird, sondern z.B. falls beim Routing Probleme durch ausgefallene Peers oder ahnlich auftreten.
    Insgesamt verfUgt ein Peer in Pastry also Uber die drei in Abbildung 6.3 dar- gestellten Klassen von Nachbarn. Abbildung 6.4 veranschaulicht die Nachbarschaft eines Peers am Netzwerkgraph. (Aus GrUnden der Ubersichtlichkeit wurde dabei auf die Darstellung der latenznahen Peers der Menge M verzichtet.)
6.2.2 Routing
    Nachdem wir im letzten Abschnitt die Netzwerkstruktur von Pastry vorgestellt haben, werden wir nun untersuchen wie in dieser Struktur effizientes Routing von Nachrichten geschehen kann. Wie eingangs erwahnt wird in Pastry ein Datumjeweils von demjenigen Peer verwaltet, dessen ID der ID des