Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Routing-Tabelle.
    Abbildung 6.7 veranschaulicht, warum die Level i-Eintrage des i-ten Peers auf dem Weg von pa nach pz auch fur den neuen Peer p gute Lokalitatseigenschaften aufweisen. Die Kreise zeigen die durchschnittliche Distanz in der Latenzmetrik der Level 0- bis Level2-Eintrage derjeweiligen Peers. Man beachte, dass Peer p zwar innerhalb jedes der Kreise, jedoch jeweils auBerhalb des jeweiligen Zentrums liegt. So wird p durch Ubernahme der Level 1-Eintrage von Pb moglicherweise noch bessere Level0-Eintrage als die von pa finden.
Lokalitat im Routing
    Wir betrachten nun, wie sich die Lokalitatseigenschaft der Routing-Tabellen auf das Routing auswirkt. Bei jedem Schritt des Routings wird jeweils ein zum aktuellen Peer latenznaher Peer ausgewahlt, dessen ID dem gewunschten Prafix entspricht. Da kein Peer eine globale Sicht des Netzwerks hat, muss der Routing-Algorithmus den nachsten Schritt jeweils anhand lokaler Informationen treffen. Das bedeutet, dass beim Routing zwar die Distanz der einzelnen Schritte minimiert wird, allerdings ohne Berucksichtigung der (globalen) Richtung des endgiiltigen Ziels. Dies zeigt, dass beim Routing nicht garantiert der bezuglich der Latenzmetrik kurzeste Weg zwischen Start and Ziel gefunden wird. Jedoch wird das Routing relativ gute Wege wahlen. Dies machen wir uns anhand der beiden folgenden Beobachtungen klar:

    1. Macht eine Nachricht innerhalb des Routings einen Schritt von einem Peer pa zu einem Peer Pb mit Distanz d bezuglich der Latenzmetrik, so wird der nachste vom Routing gewahlte Peer p, eine Distanz grWer als d zu pa haben. Dies folgt direkt aus dem Routing-Algorithmus and der Annahme korrekter Routing Tabellen Eintragen. Ware die Distanz zwischen pa, and pa namlich geringer als d, hatte pa die Nachricht nicht an Pb sondern stattdessen an p, gesendet.

    Abb. 6.7. Beim Routing zuruckgelegte Distanzen in der Latenzmetrik.

    2. Mit jedem Schritt, also mit jedem Level der Routing-Tabelle, steigt die Lange der Schritte bezuglich der Latenzmetrik exponentiell an. Der Grund dafiir ist, dass ein Eintrag fur das Level i der Routing-Tabelle aus einer Menge von n/2bi Peers gewahlt werden kann. Durch die zufallige and uniforme Verteilung der Peer-IDs and unter der Annahme, dass die Peers im euklidischen Raum der Latenzmetrik ebenfalls gleichverteilt sind, bedeutet das, dass die erwartete Distanz des nachsten Peers fur die Eintrage der Routing-Tabellen ebenfalls exponentiell ansteigt.
    Kombiniert implizieren these beiden Beobachtungen, dass die Distanz einer Nachricht zu ihrem Ursprung mit jedem Schritt monoton wachst and die Lange der Schritte jeweils exponentiell zunimmt. Teuer bezuglich der Latenzzeiten sind also insbesondere die letzten Schritte des Routings. Ist eine Nachricht bereits nah an der Ziel-ID, kann jedoch oftmals ein direkter Sprung mit Hilfe der Leaf-Set Eintrage gemacht werden and somit weitere, sehr teure Schritte eingespart werden. Im folgenden Abschnitt werden wir unter anderem experimentelle Resultate uber das Lokalitatsverhalten des Routings betrachten.
6.2.5 Experimentelle Resultate
    Die Autoren des Pastry-Netzwerks haben zahlreiche experimentelle Untersuchungen durchgefuhrt um das Netzwerk zu evaluieren [11]. Einige der Resultate betrachten wir in diesem Abschnitt.
Skalierbarkeit

Verteilung der Hop-Distanz beim Routing
    In Abbildung 6.9 ist die Auswertung der Experimente hinsichtlich der Verteilung der Hop-Distanz dargestellt. Gemessen wurde die Verteilung der Hop-Distanz in einem Netzwerk mit n = 106 Peers. Die Abweichung von der erwarteten HopDistanz (logzb 106) ist extrem gering. Tatsachlich sagt auch die Analyse eine Abweichung mit polynomiell kleiner Wahrscheinlichkeit voraus, so dass auch hier eine gute Ubereinstimmung von formaler and experimenteller Analyse gegeben ist.

    Abb. 6.8. Durchschnittliche Anzahl von Hops beim Routing bei steigender Anzahl der Peers (b = 4, f = 16 und I MI =32)[11].
    Abb. 6.9. Verteilung der Hop-Distanzen beim Routing in einem Pastry-Netzwerk (b = 4, f=16,IMI=32undn=106)[11].

Latenzzeit
    Weiterhin wurden die Latenzzeiten beim Routing in Pastry mit den Latenzzeiten beim Routing in einem fiktiven Netzwerk mit vollstandigen Routing-Tabellen verglichen - also direkten Verbindungen zwischen alien Peers (siehe Abbildung 6.10). Die Ergebnisse wurden anhand der Routing-Zeiten im fiktiven Netzwerk normiert.
    Gemessen wurde in Netzwerken mit n = 1000 bis it = 100.000 Peers. Der Unterschied zwischen den Routing-Zeiten in Pastry and