Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Zufallsgraphen. Ihr Ziel war es, eine Netzwerkbeschreibung zu liefern, die durch Wahl eines Parameters p E [0, 1] variabel und kontinuierlich aus einem struk- turierten Netzwerk ein vollkommen zufalliges entstehen lasst. Hierzu betrachteten sie einen Ring aus n Knoten, in dem jeder der Knoten mit den k/2 nachsten Knoten zur linken und zur rechten verbunden ist (also ahnlich wie bei Pastry, nur ohne die Menge Al lokaler Nachbarn und ohne die Routing-Tabelle). Ein solches RingNetzwerk ist in Abbildung 9.4(a) dargestellt.
    Ausgehend von diesem Ring-Netzwerk wird nun jede der ursprunglichen Kanten mit Wahrscheinlichkeitp durch eine Kante zu einem zufalligen Nachbarn ersetzt. Die dabei entstehenden Netzwerke sind fur verschiedene Parameter p in Abbildungen 9.4 dargestellt. So bleibt das Ring-Netzwerk fur p = 0 unverandert and wird fur p = 1 zu einem Zufalls-Netzwerk. Fur p = 0.1 zum Beispiel bleiben jedoch relativ viele Cliquen des ursprunglichen Ring-Netzwerks bestehen and durch die zufalligen Kanten wird der Durchmesser des Netzwerks stark verringert.

Das Modell von Kleinberg
    Die Small-World-Netzwerk-Modellierung von Watts and Strogatz wurde von Kleinberg in [70] aufgegriffen. Kleinberg zeigte, dass Milgrams Beweis sogar konstruktiv war. Jeder der Teilnehmer hatte also eine Intuition, wem man das Paket zu geben hat, damit dieses moglichst schnell ankommt. In Kleinbergs Modell [70] sind die Teil nehmer in einem euklidischen Gitternetzwerk angeordnet. Die Verbindungen dieser Gitter-Struktur werden als Lokal-Verbindungen bezeichnet (siehe Abbildung 9.5). Mit Hilfe der Gitterstruktur kann bereits Routing durchgeffihrt werden, wenn die Koordinaten des Ziels im Gitter bekannt sind (siehe CAN, Kapitel 4).

    Abb. 9.4. Small-World-Netzwerke nach dem Modell von Watts and Strogatz. Dargestellt werden Netzwerke mit k = 4 sowie Parameter p = 0 (a), 0 < p < 1 (b) and p = 1 (c) [69].

    Abb. 9.5. Die Lokal-Verbindungen in Kleinbergs Modell [70].
    Zusatzlich zu den Lokal-Verbindungen erhalt jeder Knoten noch einige Kanten zu weiter entfernten Knoten, die dann als Abkurzungen beim Routing dienen (siehe Abbildung 9.6). Diese Verbindungen werden als Fern-Verbindungen bezeichnet. Durch eine vorsichtige Wahl dieser Fern-Verbindungen mittels einer fiber dem Abstand gewichteten Wahrscheinlichkeitsverteilung konnte Kleinberg zeigen, dass in diesen Graphenjedes Paket mit O(log2 n) Schritten zum Ziel gesendet werden kann. Das Modell von Kleinberg ist insbesondere in der Auswahl der Fernverbindungen komplexer and flexibler als das Modell von Watts and Strogatz. Wir verzichten hier jedoch auf die detaillierte Beschreibung der Wahrscheinlichkeitsverteilung zur Auswahl ebendieser. Die Details hierzu linden sich in [70].
Das Modell von Barabasi end Albert
    Einen vollig anderen Weg zum Aufbau eines Small-World-Netzwerks gehen Barabasi and Albert in [63]. Ausgehend von einem kleinen Startgraphen werden sukzessive Knoten mit jeweils m Kanten eingefugt. Nun wird Paretos Beobachtung verwendet: „rich gets richet". So wahlt ein neuer Knoten seine Nachbarn mit einer Wahrscheinlichkeit, die proportional zum Grad dieser Knoten ist. Somit erhalten Knoten, die bereits einen hohen Grad haben, mehr neue Kanten (und damit einen noch hoheren Grad) als Knoten mit geringem Grad (siehe Abbildung 9.7). Es zeigt sich, dass das entstehende Netzwerk einen logarithmischen Durchmesser besitzt and dass die Gradverteilung einer Pareto-Verteilung mit Exponent 2, 9 ± 0, 1 genugt. Auch hier verzichten wir auf weitere Details des Modells.

    Abb. 9.6. Die Lokal- and Fernverbindungen eines Knotens v in Kleinbergs Modell [70].
    Abb. 9.7. Einf igen eines Knotens im Small-World-Netzwerk Modell von Barabasi and Albert [63] (m = 2).

9.1.3 Vergleich von Gnutella and Small-World-Netzwerken
    Wir werden nun die drei vorgestellten Modelle fur Small-World-Netzwerke mit dem Gnutella-Netzwerk anhand ihrer charakteristischen Pfadlange vergleichen. Die charakteristische Pfadlange ist der durchschnittliche Abstand zweier Knoten bzw. Peers in einem Netzwerk. Tabelle 9.2 zeigt die charakteristische Pfadlange des GnutellaNetzwerks (hier handelt es sich wiederum um funf Messungen aus dem Jahr 2000 [54]) verglichen mit derjenigen, der eben vorgestellten Small-World-Netzwerke and der eines Zufallsgraphen. Die Parameter der einzelnen Modelle wurden hierbei (soweit moglich) der GroBe and dem Grad von Gnutella angepasst. Es zeigt sich, dass sich die beste Ubereinstimmung mit dem Modell von Barabasi and