Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Suche benotigt, ist ein Datum in Chord bereits nach O(log n) Schritten lokalisiert. Diese nicht unwesentliche Verbesserung der RoutingZeit wird erkauft durch die groBeren Routing-Tabellen in Chord, wo jeder Peer mit O(log n) anderen Peers verbunden ist. Zudem erlauben sowohl CAN als auch Chord, das Routing an das Underlay-Netzwerk (das Internet) anzupassen, um Latenzzeiten zu reduzieren.

6

Pastry and Tapestry
    You like potato and I like potahto You like tomato and I like tomahto Potato, potahto, Tomato, tomahto. Let's call the whole thing off.
    Ira Gershwin
    Pastry and Tapestry sind zwei unabhangig voneinander entstandene Peer-toPeer-Netzwerke, die auf derselben Idee aufbauen, namlich der Verwendung eines Routing-Verfahrens von Plaxton, Rajarman and Richa [13]. Hierbei handelt es sich um ein effizientes verteiltes Verfahren zum Zugriff auf Datenkopien in einem verteilten statischen Netzwerk.
    Auf dieser Basis wurden Pastry and Tapestry entwickelt, die das Verfahren unter anderem um Mechanismen zurn EinfUgen and Loschen von Peers and Daten er- weitern. Wegen der gemeinsamen Vorarbeit unterscheiden sich Pastry and Tapestry daher nicht sehr and werden hier wegen ihrer Ahnlichkeit in einem Kapitel beschrieben. Wie wir sehen werden, existieren jedoch auch Unterschiede, sowohl in der Phi- losophie als auch in der Umsetzung der Netzwerke.
6.1 Verfahren von Plaxton, Rajamaran and Richa
    Das Verfahren von Plaxton, Rajamaran and Richa [13] wurde schon 1997 konzipiert. Ziel was nicht ein Peer-to-Peer-Netzwerk oder ein geeignetes Routing dafur zu finden, schlieBlich waren Peer-to-Peer-Netzwerke 1997 noch unbekannt. Vielmehr ging es darum, in einem verteilten Netzwerk Kopien der bereitgestellten Daten (hier als Objekte bezeichnet) so zu platzieren, dass die Teilnehmer moglichst schnell darauf zugreifen konnen. Dieses klassische Problem [41] im Bereich der verteilten Netzwerke wurde zuvor bereits von anderen Autoren untersucht [42, 9, 43]. In der Arbeit von Plaxton, Rajamaran and Richa wurde jedoch erstmals der Aufwand fur den Zugriff and Speicherbedarf unter einem allgemeineren Kostenmodell untersucht. Das Verfahren selbst ist komplex and insbesondere komplexer als die darauf aufbauen- den Peer-to-Peer-Netzwerke Pastry and Tapestry. Daher werden wir hier nur eine vereinfachte Beschreibung geben and uns auf die fur uns wesentlichen Aspekte konzentrieren.

6.1.1 Das Modell
    Das verteilte Netzwerk wird durch einen vollstandigen Graph G = (V, V2) model- liert, d.h. ein Knoten v E V des Netzwerks hat die Moglichkeit, beliebige Knoten u E V in seine Routing-Tabelle aufzunehmen. Die Kommunikationskosten zwischen zwei Knoten des Netzwerks werden durch eine Funktion c : V2 ~ 118 beschrieben, die zu einer Metrik gehort. Also gelten fur beliebige u, v, w E V die folgenden Eigenschaften einer Metrik:
    • Identitat: c(v, w) = 0 genau dann, wenn v = w,
    • Symmetrie: c(v, w) = c(w, v),
    • Dreiecksungleichung: c(u, w) < c(u, v) + c(v, w).
    Die Kosten zur Ubertragung von n Bits von a nach v werden durch den Term c(u, v) . f (n) modelliert, wobei f : N -f IR+ eine beliebige, monoton steigende Funktion mit f (1) = 1 darstellt.
    Es wird angenommen, dass die Knoten des Netzwerks einigermaBen gleichmaBig in der Metrik c verteilt sind. Urn dies zu formalisieren, definieren wir fur einen Knoten u E V and ein r E JR die Menge

    M(u, r) enthalt also alle Knoten im Umkreis r von u. Fur die Verteilung der Knoten im Raum nehmen wir an, dass reelle Konstanten b > 8 and A existieren, so dass fur alle r > 1 gilt:

    Nur unter dieser Annahme ist das Verfahren nachweisbar effizient. Hierbei ist anzu- merken, dass nicht klar ist, ob das Internet als verteiltes Netzwerk dieser Annahme tatsachlich genugt.
Objekte als Kopien
    Jedes der m Objekte hat eine eindeutige Identifikation aus log m Bits. Die Datenmenge in Bits eines Objekts A wird mit £(A) beschrieben. Genauso sei fur jeden der V1 = n Knoten eine eindeutige Adresse als Bitstring der Lange log n vorhanden.
    Ziel ist es, Anfragen nach Objekten so schnell wie moglich zu beantworten. Um die Zugriffszeit zu minimieren, werden Kopien der Objekte auf geeigneten Knoten gespeichert. Zugleich soil der Unterhalt der Datenstruktur einfach sein, d.h., es sollen nur wenige Knoten aktualisiert werden mussen, wenn sich die Netzwerkteilnehmer andern. Fur these Eigenschaft wird in [13] der Begriff der Anpassungsfahigkeit (Adaptability) eingefuhrt.
    Die Gute des Verfahrens wird anhand der folgenden MaBe bewertet:

    •