Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Baumstruktur erhalt jeder Peer dynamische Adressen, die auch auBerhalb der Suche fur andere Zwecke verwendet werden konnen.
    • Dezentrales Trust-Management
    Ein weiterer Bestandteil von P-Grid ist ein Vertrauensmanagementsystem (TrustManagement). Dieses wird notwendig, wenn Angreifer versuchen, die Struktur von Peer-to-Peer-Netzwerken zu zerstoren. Die Autoren von P-Grid haben sich schon sehr fruh mit diesem Problem beschaftigt, das, wie wir noch in Kapitel 10 sehen werden, sehr schwierig ist.
    • Epidemische Informationsverbreitung
    Bestimmte Informationen, wie die lokale Baumstruktur oder das Fehlen von Teilbaumen, mussen in P-Grid an alle Knoten verteilt werden. Hierfur wird epidemische Informationsverbreitung [49] genutzt, auch bekannt unter dem Namen Rumor Spreading. Dabei werden die Daten von informierten (infizierten) Knoten fur eine bestimmte Zeit an Kontaktpartner weitergegeben. Ahnlich wie eine ansteckende Krankheit breitet sich so die Information im gesamten betroffenen Teilbaum aus. Der Vorteil solcher Verfahren besteht darin, class keine eigenen Datenstrukturen fur these Informationsverbreitung aufgebaut werden mUssen and dass dennoch alle Knoten von der Information angesteckt werden konnen. So wird eine konsistente Sicht auf den Baum erzeugt.
8.1.5 Zusammenfassung
    P-Grid ist ein Peer-to-Peer-Netzwerk, das die Autoren mehrfach in Hinsicht auf seine praktische Einsatzfahigkeit optimiert haben. Es ist das erste Peer-to-Peer-Netzwerk, das Daten geordnet speichert and zugleich effizient arbeitet. Mit P-Grid kann man effizient Bereichsanfragen durchfuhren. Hierzu sucht man den ersten Peer and kann dann durch eine Baumtraversierung die Daten aus dem Baum auslesen.
    P-Grid bietet die Moglichkeit der dynamischen Lastanpassung and verteilt die Daten aktiv auf die Peers. In dieser Hinsicht ist P-Grid sicher Skip-Net uberlegen, welches wir gleich besprechen werden.
    Auf der negativen Seite hat P-Grid Schwierigkeiten, den Verlust von Peers and damit von Informationen in Teilbaumen zu kompensieren. Dieses Risiko wurde inso- fern abgemildert, da P-Grid es erlaubt, mehrere Peers auf Teilbaume zuzuweisen. Die Mechanismen zur (Wieder-)Vereinigung von Teilbaumen sind aber (noch) nicht spe- zifiziert. In P-Grid wurde sehr viel Energie auf die Frage verwendet, wie man einen Massenansturm auf das Peer-to-Peer-Netzwerk handhaben kann. Ob dies wirklich ein nennenswertes Problem ist, erscheint fraglich. SchlieBlich ist ein solcher Massenansturm nur mit einer zentralen Kontrolle moglich. Es muss aber erwahnt werden, dass P-Grid ohne die erwahnten Heuristiken mit diesem Ansturm nicht fertig werden wurde. Somit ist es durchaus legitim, P-Grid gegen diesen (wenn auch un- realistischen) Fall zu wappnen.

8.2 Skip-Net
    Von James Aspnes and Gauri Shah wurde im Jahr 2003 Skip-Graph [50] als effizientes Peer-to-Peer-Netzwerk eingefuhrt. Gleichzeitig and unabhangig haben Harvey, Jones, Saroiu, Theimer and Wolman das weitgehend aquivalente Peer-to-PeerNetzwerk Skip-Net [51] entwickelt. Die Begriffe Skip-Net and Skip-Graph werden zumeist synonym verwendet. Hier werden these Begriffe verwendet, um das Peer-to-Peer-Netzwerk (Skip-Net) von der zugrunde liegenden Verbindungsstruktur (Skip-Graph) zu unterscheiden. Da von Anfang an die Rechner-Netzwerk-Struktur im Vordergrund stand, verwenden wir bier den Begriff Skip-Net fur das Peer-toPeer-Netzwerk and den Begriff Skip-Graph, wenn wir uns auf die Graphstruktur des Netzwerks beziehen.
    Ziel von Skip-Net ist die sortierte Verwaltung von Daten and Peers, so dass neben der einfachen Suche auch kompliziertere Anfragen wie zum Beispiel Bereichsanfragen moglich werden. Der Name (oder der Schlussel) eines Peers legt fest, welche Daten dieser verwalten wird. Wurde der fur ein Datum zustandige Peer gefunden, so wird der Rest der Anfrage durch eine konventionelle Datenstruktur (wie zum Beispiel durch balancierte Suchbaume) lokal auf dem Peer gelost.
8.2.1 Skip-Listen
    Um die Struktur eines Skip-Graphen zu verstehen, hilft es Skip-Listen zu kennen. Diese stellen eine Moglichkeit dar, Suchbaume effizient zu implementieren. Zur Veranschaulichung startet man mit einer sortierten and einfach verketteten linearen Liste, siehe Abbildung 8.4. In solch einer Liste ist die Suchzeit im schlimmsten Fall n - 1, wenn n Daten vorhanden sind.
    Abb. 8.4. Eine einfach verkettete Liste.

    Nun werden abkurzende Zeiger hinzugefugt, indent jeder Knoten per Munzwurf ausgewahlt wird. Die ausgewahlten Knoten werden wieder