Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Zugriffszeit auf ein Objekt: Diese ergibt sich aus der Summe der nachfolgenden Kopiervorgange des Objekts A gemaB der Metrik c and der ObjektgroBe f(A), d.h. der Summe von c(u, v) • f (f (A)) fur alle Kopiervorgange von einem Knoten u zu einem Knoten v, die durch den Zugriff notwendig werden.
    • Lokaler Speicherbedarf Die Menge der lokal zu speichernden Kopien, wobei fur alle Knoten die gleiche Speichermenge q angestrebt wird.
    • Anzahl der zit aktualisierenden Knoten: Die Anzahl der Knoten, deren Informationen aktualisiert werden mussen, wenn ein Knoten dem System beitritt oder es verlasst.
    • Aktualisierungszeit fiir Datendnderung: Die erwarteten (Zeit-)Kosten fur das Aufnehmen oder Andern eines Objekts.
6.1.2 Netzwerkstruktur
    Knoten and Objekte erhalten numerische IDs zur Basis B = 2b, b e N. Fur die Zuweisung von Objekten zu Knoten gilt, dass ein Objekt mit ID A auf demjenigen Knoten gespeichert wird, dessen ID das langste gemeinsame Prafix hat. Gibt es mehrere solcher Knoten, so wird derjenige Knoten gewahlt, dessen Suffix die groBte bitweise Ubereinstimmung mit A aufweist. Dieser eindeutige Knoten wird dann Wurzelknoten (Root) von A genannt. Ziel dieser Zuordnung ist eine gleichmaBige Verteilung der Daten auf die Knoten.
    Fur das Routing unterhalt jeder Knoten v e V zwei Tabellen: Eine Nachbarschaftsliste and eine Zeigerliste. Die Eintrage der Zeigerliste eines Knotens u sind Tripel (A, v, k). Ein solches Tripel gibt an, dass Objekt A sich auf Knoten v E V befindet and dass c(u, v) < k gilt. Die Zeigerliste enthalt eine Auswahl aller Objekte im Netzwerk and wird dutch alle drei Operationen aktualisiert.
    In der nun folgenden Beschreibung der Nachbarschaftsliste bezieht sich der Parameter i auf die Lange eines Prafixes einer Knoten- bzw. Objekt-ID, and der Parameter j bezeichnet ein Zeichen aus der Basis {0, 1, . . . , B -1}. Die Nachbarschaftsliste eines Knotens v enthalt Eintrage der folgende Mengen von Eintragen:
    Primdre (i, j)-Nachbarn. Hier wird der Knoten u E Vgewahlt, dessen ID mit v den Prafix der Lange i - 1 teilt and dessen i-tes Zeichen der ID j entspricht. Falls nun mehrere Knoten existieren, die diesen Eigenschaften genugen, so wird derjenige gewahlt, der c(u, v) minimiert. Existiert hingegen kein Knoten mit diesen Eigenschaften, so wird der mit dem langsten gemeinsamen Prafix zu v gewahlt. Trifft dies wiederum auf mehrere Knoten zu, so wird aus diesen derjenige gewahlt, der das langste Suffix mit v teilt. Ist these Wahl immer noch nicht eindeutig, wird aus dieser Menge der Knoten mit der groBten ID gewahlt.
    Sekundare (i, j)-Nachbarn. Sei u der primare (i, j)-Nachbar von v and sei das i-te Zeichen der ID von u gerade j. Als sekundare (i, j) -Nachbarn von v wird dann die konstante Anzahl d von Knoten v'gewahlt, deren Prafix bis zur (i - 1)-ten Stelle mit der ID von v ubereinstimmt, als nachstes Zeichen den Buchstaben j enthalten and zugleich die Abstandsbedingung c(v, v') < d•c(v, u) erfUllen. Besteht these Menge aus weniger als d Elementen, so wird die Menge mit Knoten v" erweitert, fur die der Wert c(v, v") moglichst gering ist.

    Primare (i, j )-Ruckwartsnachbarn. Em n Knoten a ist ein primarer (i, j)-Ruckwarts- nachbar von v, wenn u ein primarer (i, j)-Nachbar von v ist.
    Man beachte, dass die Anzahl der sekundaren Nachbarn sehr groB werden kann, wenn nichts uber die Struktur der Kostenmetrik c bekannt ist. Deshalb ist die oben formalisierte gleichmaBige Verteilung der Knoten wichtig. Die komplexe Struktur der primaren Adresse dient hauptsachlich zur Vermeidung von hohen Eingraden, die bei der Definition der Ruckwartsnachbarn zu hohen Ausgraden fuhren wurde.
6.1.3 Operationen
    Das Verfahren stellt drei einfache Operationen zur Verfagung: Read, Insert and Delete. Diese werden wir im Folgenden kurz erlauten.
Read
    Die Read-Operation eines Objektes besteht zum einen naturlich aus dem Routing vom anfragenden Knoten zu dem Knoten, der das Objekt bereitstellt, beschrankt sich jedoch nicht hierauf. Die Read-Operation beinhaltet auch die automatische Erstellung von Kopien des Objektes, um die Kommunikationskosten fur zukUnftige Anfragen zu senken.
    Das Routing selbst geschieht durch das einfache Abfolgen der primaren Nachbarschaftszeiger, indem der Prafix nach and nach erganzt wird mit der Adressinfor- mation des gesuchten Objektes A. Auf dem Weg dieser Suchanfrage muss also ein guter Weg gefunden werden, um das Objekt zum Anfrager zu schicken. Dabei ist nicht klar, dass ein direkter