Peer-to-Peer-Netzwerke: Algorithmen und Methoden

wird folgender Reparaturmechanismus verwendet: Zuerst werden andere, p bekannte Nachbarn aus demselben Level j der Routing-Tabelle kontaktiert. Fehlt also beispielsweise dem Peer 021 ein Link zum Prafix 01*, dann fragt er seine Nachbarn mit Prafix 00*, 02* and 03* nach einem Peer fur den fehlenden Eintrag. Falls einer dieser Peers einen passenden Eintrag fur dieses Prafix hat, wird er von p ubernommen. Scheitert dies, wird der gleiche Vorgang far die Level j + 1, j + 2, .. . der Routing-Tabelle wiederholt.
6.2.4 Lokalitat
    Eine wichtige Eigenschaft von Pastry ist, dass beim Aufbau der Nachbarschaft eines Peers and beim Routing versucht wird, Routingzeiten durch Nutzung latenznaher Verbindungen zu verringern. Wir bezeichnen these Eigenschaft von Pastry auch als Netzwerklokalitat.
    Bevor wir auf die Details bezuglich Pastry and Lokalitat naher eingehen, halten wir ein paar grundlegende Dinge diesbezuglich test. Eine wichtige Beobachtung zur Latenzzeit ist, dass die Nahe eines Peers bezuglich der Ringmetrik (Raum Uber den durch Hashing zugewiesenen IDs E {0, 1}128)1 and der Latenzmetrik (gemessen in der Zeit, die eine Nachricht durchschnittlich zwischen zwei Peers benotigt) vollig unabhangig voneinander sind. Das heiBt insbesondere, dass direkte Nachbarn im Peer-to-Peer-Netzwerk typischerweise nicht nah bezuglich der Latenzmetrik sind.
    Wir haben in Abschnitt 2.3.2 (Seite 35) gesehen, dass das TCP-Protokoll des Internets sowieso Latenzzeiten durch die Round Trip Time RTT misst. In Pastry wird davon ausgegangen, dass die so gewonnenen Latenzzeiten eine euklidische Metrik definieren - die Latenzmetrik. Diese Latenzmetrik ist die Grundlage fur die Suche eines nahen Peers fur die Eintrage in der Routing-Tabelle.
    Die Verfahren in Pastry beruhen auf heuristischen Uberlegungen, and ein mathematischer Nachweis der Gute der Verfahren ist bisher nicht erbracht worden. Insbesondere gilt dies auch fur die Annahme, dass die Latenzmetrik euklidisch ist (d.h., es existiert eine Einbettung der Punkte in einem Raum, so dass die Latenzmetrik durch den euklidischen Abstand dieser Punkte entsteht).

Lokalitat in der Routing-Tabelle
    Wir werden nun untersuchen, ob ein dem Netzwerk beitretender Peer p durch die Einfuge Operation tatsachlich eine an Latenzmetrik angepasste Routing-Tabelle erhalt. Hierfur halten wir uns zunachst noch einmal das Verfahren zum Aufbau der Routing-Tabelle vor Augen: Der neue Peer p kontaktiert einen latenznahen Peer pa, von dem aus zum Peer pz mit langstem gemeinsamen Prafix zu p geroutet wird. Peer p ubernimmt von pa die Level0-Eintrage der Routing-Tabelle, vom zweiten Peer auf dem Weg zu pz die Level 1-Eintrage usw.
    Wir nehmen im Folgenden an, dass alle anderen Peers im Netzwerk ihre RoutingTabelle bereits bezuglich der Latenzmetrik optimiert haben. Da die Level O-Eintrage der Routing-Tabelle von pa nur Peers enthalten, die nah zu pa Sind, pa nah zu p ist and weil die Dreiecksungleichung gilt, folgt, dass die Eintrage ebenfalls relativ nah zu p sind.
    Betrachten wir nun die Level 1-Eintrage der Routing-Tabelle des Peers p. Diese werden vom ersten Peer Pb auf dem Weg von pa nach pz ubernommen. Hier befinden sich die eingetragenen Peers wiederum in der Nahe von Pb, jedoch nicht mehr notwendigerweise in der Nahe von p. Tatsachlich sind these Eintrage jedoch noch in einer so geringen Entfernung zu p, dass die Ubernahme der Eintrage in die RoutingTabelle sinnvoll ist. Um dies zu verdeutlichen, erinnern wir uns, dass die Eintrage der Routing-Tabellen mit jedem weiteren Level aus einer exponentiell schrumpfen- den Menge gewahlt werden. Dies gilt, da mit jedem weiterem Level eine weitere Ziffer des Prafixes festgelegt wird. Daher ist der erwartete Abstand zwischen Pb and den Peers in den Level 1-Eintragen von pt's Routing-Tabelle bereits weitaus groBer als der erwartete Abstand zwischen pa and Pb. So macht es durchaus noch Sinn, die Level 1-Eintrage von pt's Routing-Tabelle fur p zu ubernehmen. Die gleiche Argumentation gilt fur die weiteren Zeilen der Routing-Tabelle.
    Nachdem p seine Routing-Tabelle auf diese Weise initialisiert hat, approximiert diese also bereits die gewunschte Lokalitatseigenschaft. Jedoch werden die Eintrage weiter optimiert, indem p jeden Peer aus seiner Routing-Tabelle and der Menge M latenznaher Peers kontaktiert and deren Routing-Tabellen anfordert. Peer p vergleicht dann seine eigenen Eintrage mit denen aus den erhaltenen Routing-Tabellen and ersetzt ggf. Eintrage in der eigenen