Peer-to-Peer-Netzwerke: Algorithmen und Methoden

x3 < ... ist Zipf-verteilt mit Exponenten a, wenn

    gilt and die Wahrscheinlichkeit fur andere Werte 0 ist. Somit stellen Zipf-Verteilungen eine Verallgemeinerung der Pareto-Verteilungen dar.
    Ein Beispiel fur eine Zipf-Verteilung ist die Verteilung der GrOBe von Stadten [60, 61]. Hierfur liegen ausfuhrliche Untersuchungen vor, in denen man mittels des Zipf-Exponenten den Grad der Verstddterung einer Region erkennen kann.
    Im Internet konnen Zipf- and Pareto-Verteilungen nicht nur bei Gnutella be- obachtet werden. So untersuchte man in [62] den Verbindungsgrad von InternetRoutern, siehe Abbildung 9.2. In [63, 64] wurde der Ein- and Ausgrad von WebSeiten im WWW untersucht, siehe Abbildung 9.3. Der Ausgrad einer Webseite ist hierbei einfach die Anzahl ihrer Links, der Eingrad ist die Anzahl anderer WebSeiten, die auf diese zeigen.
    Abb. 9.2. Anzahl der Verbindungen von Internet-Routern (vertikale Achse), sortiert nach dem Rang (horizontale Achse) im Dezember 1998 [62].

    Abb. 9.3. Anzahl and Haufigkeit eingehender and ausgehender Links auf Web-Seiten im Mai 1999 [65].
    Abbildung 9.3 zeigt, wie gut eine Pareto-Verteilung these Hdufigkeitsverteilung annahert. Betrachtet man die Anzahl der Web-Seiten einer Web-Site, die Anzahl der Benutzer, die Anzahl der Links auf eine Web-Site and von einer Web-Site, so findet man wieder eine Pareto-Verteilung [66]. Auch die Anzahl der Zugriffe auf eine WebSeite unterliegt einer Zipf-Verteilung [67]. Interessanterweise ist auch die GroBe einer Web-Seite (die Anzahl der Bytes) Pareto-verteilt [67]. Diese Beobachtung kannte man schon aus der GroBenverteilung von Unix-System-Dateien.
9.1.1 Der Durchmesser des Gnutella-Netzwerks
    In der schon zitierten Arbeit von Jovanovic [54] wird neben der Gradverteilung auch der Durchmesser von Gnutella untersucht. Gerade dieser Parameter ist wichtig fur eine erfolgreiche Suche in einem unstrukturierten Peer-to-Peer-Netzwerk. Die Untersuchung geschah anhand von funf Messungen im Jahr 2000 im Gnutella-Netzwerk. Dabei zeigte sich, dass der Durchmesser eines Gnutella-Netzwerks mit rund 1000 Teilnehmern im Bereich von acht bis zwolf liegt (siehe Tabelle 9.1). Der durchschnittliche Grad der Peers lag zwischen 1,7 and 4.

    Der Durchmesser des Gnutella-Netzwerks ist somit erstaunlich klein. Zum Vergleich: Ein zweidimensionales Gitter mit Grad vier hat bei 1000 Teilnehmern einen Durchmesser von rund 62. Ein ebensolcher Torus hat einen Durchmesser von 31. Einen so geringen Durchmesser wie beim Gnutella-Netzwerk erreicht man sonst nur durch Strukturen wie einem vollstandigen Baum, der bei einem Grad von drei einen Durchmesser von 20 besitzt. Diese Beobachtung wirft die Frage auf, wie sich der geringe Durchmesser des Gnutella-Netzwerks erklaren lasst. Bevor wir eine mathematische Erklarung liefern, mochten wir andere soziale Netzwerke vorstellen, die solch einen geringen Durchmesser besitzen.
9.1.2 Small-World-Netzwerke
    In den Sechzigern hat der Psychologe Stanley Milgram das folgende Experiment durchgefuhrt [68]: Er handigte 60 zufallig ausgewahlten Teilnehmern in Omaha, Nebraska, jeweils einen Brief aus, den diese einer Adresse in Sharon, Massachusetts, zukommen lassen sollten. Sic durften den Brief aber nur Personen zusenden, die sie personlich kannten (und nicht etwa direkt an die Ziel-Adresse). AuBerdem sollten die Personen, die nun als Zwischenstationen ausgewahlt warden, sich wieder an diese Bedingungen halten. Tatsachlich kam die Mehrzahl der Briefe am Bestimmungsort an und die Teilnehmer hielten sich an die Anforderungen. Die meisten Briefe kamen mit nur sechs Zwischenstationen zum Ziel, was Milgram zu der Vermutung brachte, dass jeder Mensch jeden anderen fiber maximal sechs Zwischenstationen kennt (six degrees of separation) [68].
    Dieses Phanomen wird als Small-World-Phanomen bezeichnet and soziale Netzwerke mit einem so geringen Durchmesser bezeichnet man als Small-World-Netzwerke (Small-World-Network). Bis heute ist auBer dem geringen Durchmesser noch keine genauere Beschreibung oder Charakterisierung dieser Netzwerke erfolgt. Wie entstehen Small-World-Netzwerke? Wir werden im Folgenden drei Ansatze fur die Modellierung von Small-World-Netzwerken vorstellen.
Das Modell von Watts und Strogatz
    Watts und Strogatz [69] gehen von der Beobachtung aus, dass in sozialen Netzwerken Cliquen (das sind vollstandige Teilgraphen: eine Menge von Knoten, in derjeder Knoten mit jedem anderen verbunden ist) weitaus haufiger vorkommen als zum Beispiel in