Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Kopiervorgang dies leistet. Es konnte sein, dass ein anderer Weg als der uber die primaren Nachbarn Ersparnisse bringt. Deshalb werden die sekund iren Nachbarn beauftragt zu uberprufen, ob es nicht wesentlich bessere Wege gibt. Diese speichern die Zwischenergebnisse in ihrer Zeigerliste. Finden sich Uber these keine kurzeren Wege, so wird der primare Nachbarschaftszeiger verwendet and die Kopie direkt versendet. Ansonsten wird eine Kopie an dem sekundaren Zeiger abgespeichert, der einen kurzeren Weg anbieten konnte.
    Dieser Prozess erzeugt unter Umstanden eine groBe Anzahl von Nachrichten im verteilten Netzwerk durch die Abfrage bei den sekundaren Zeigern. Der Aufwand dieser Nachrichten wird bei der Analyse vernachlassigt. Die Autoren beschreiben nur den Aufwand fur die eigentlichen Kopieraktionen des Objekts.
Insert
    Beim Einfugen eines Objekts wird Uber die primaren Ruckwartsnachbarn die Zeigerliste aller Knoten aktualisiert, die auf dem Weg vom bereitstellenden Knoten eines Objekts zum Adressknoten des Objekts liegen. Hierfur werden die aufsummierten Kosten gespeichert.

Delete
    Das Loschen eines Objekts A macht es notwendig, dass in alien Zeigerlisten der zu A vorhandene Eintrag geloscht werden muss. Wir haben gesehen, dass these Eintrage bei Insert- and Read-Operationen erganzt werden. Um also einen Eintrag zu Loschen, muss im ganzen Netzwerk nach solchen Eintragen gesucht werden. Diese Suche lasst sich dadurch beschleunigen, dass die Eintrage durch die primaren Ruckwartsnachbarn gefunden werden konnen.
6.1.4 Ergebnisse
    Unter den getroffenen Annahmen erweist sich das Zugriffsverfahren als auBerst effizient. Es gelten folgende Aussagen, auf deren Beweis wir hier verzichten.
    Theorem 6.1. [13]
    1. Die erwarteten Kosten fur Read-Operationen sind asymptotisch optimal, d.h. beschranktdurch O(f (f(A))c(v, u)), falls das Datum A von v nachgefragt wird and u der nachste Knoten ist, der das Objekt A speichert.
    2. Die erwarteten Kosten fir eine Insert-Operation sind 0(C); fir eine DeleteOperation O(C log n), wobei C = max{c(u, v) : it, v E V}.
    3. Falls q die gewunschte Speichergr5f3e in jedem Knoten ist, so wird mit hoher Wahrscheinlichkeit in jedem Knoten hochstens O(glog2 n) Speicher verwendet.
    4. Die Anzahl der Knoten, die beim Einfugen oder Loschen eines Objekts eine Aktualisierung vornehmen miissen, ist erwartungsgemafj ((lob n) and mit hoher Wahrscheinlichkeit 0(lob2 n)
    Fur den sehr umfangreichen Beweis and die genaue Beschreibung der Operationen sei auf den Originalartikel [13] verwiesen.
    Dieser Artikel war offensichtlich seiner Zeit voraus. Jedoch beruht er auf ein paar Annahmen, die far Peer-to-Peer-Netzwerke im Internet wohl nicht zutreffen. Zum einen ist die angenommene Metrik wahrscheinlich nicht angemessen far Peers im Internet. Ist these Metrik jedoch nicht vorhanden, so nimmt die Anzahl der sekundaren Nachbarn uberhand. AuBerdem konnen weder die Knoten noch die Daten per Bijektion auf einen kleinen Raum aus log n oder log m Bits abgebildet werden. Ferner ist man in Peer-to-Peer-Netzwerken oft nicht bereit, fur andere Peers Kopien von Daten anzulegen, nur um deren Zugriffszeit zu verkurzen.
    Diese Probleme lassen sich jedoch durch einfache Modifikationen beheben. So kann die Bijektion durch eine Hash-Funktion auf etwas langere Bitstrings ersetzt werden. Auf die Erstellung von Kopien (die ursprungliche Motivation des Verfahrens) kann verzichtet werden, and das Problem der Metrik wird verdrangt. Daher verzichtet man auf die sekundaren Nachbarn and setzt eine starker eingeschrankte Metrik voraus.
    Die folgenden Kapitel 6.2 and 6.3 beschreiben die ein paar Jahre spacer erschie- nenen and auf dem Plaxton-Routing basierenden Peer-to-Peer-Netzwerke Pastry and Tapestry.

6.2 Pastry
    Peter Druschel and Antony Rowstron entwickelten in Cambridge bei Microsoft Research das Peer-to-Peer-Netzwerk Pastry [11]. Zielsetzung von Pastry ist ein vollstandig dezentralisiertes, fehlertolerantes, skalierbares Peer-to-Peer-Netzwerk, das zur Optimierung der Latenzzeiten an das Underlay-Netzwerk angepasst ist.
Uberblick
    Genau wie Chord basiert Pastry auf verteilten Hash-Tabellen uber einem eindimensionalen Raum der GrWe 2128. D.h. jedem Peer and jedem Datum im PastryNetzwerk wird eine eindeutige 128-Bit ID durch Hashing zugewiesen. Im Falle der Daten geschieht dies wiederum durch eine kryptographische Hash-Funktion, die Peer-IDs konnen wahlweise auch zufallig gewahlt werden. Diese IDs werden in Pastry als Zahlen zur Basis 2b,