Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Albert ergibt. Mit dem Modell von Watts-Strogatz sowie dem Zufallsgraph mit n Knoten and Kanten- wahrscheinlichkeit p kann eine gewisse Nahe festgestellt werden. Die schlechteste Beschreibung des Gnutella-Netzwerks liefert das zweidimensionale Gitter aus Kleinbergs Ansatz.'

    Dieses Ergebnis ist nicht sehr uberraschend, wenn man bedenkt, wie ahnlich das EinfUgen von Knoten im Modell von Barabasi and Albert and der Netzwerkaufbau von Gnutella funktionieren. Man kann also schlussfolgern, dass obwohl in Gnutella die Netzwerkstruktur ungeplant aufgebaut wird, sich durch das Prinzip der Selbstorganisation ein Pareto-verteiltes Small-World-Netzwerk (ahnlich dem des Modells von Barabasi and Albert) mit geringem Durchmesser ergibt.
9.2 Selbstorganisierende Zufalls-Netzwerke
    Wie wir gesehen haben, besitzen Pareto-Netzwerke sehr gute strukturelle Eigenschaften. Wenn sie jedoch als Verbindungsstruktur eines Peer-to-Peer-Netzwerks dienen sollen, in dem die Peers typischerweise vollkommen gleichwertig behandelt werden sollen, so ist die ungleichmaBige Verteilung der Grade nicht akzeptabel. Es ist dann vielmehr erstrebenswert, ein Netzwerk mit gleichem Grad, kleinem Durchmesser and starkem Zusammenhang zu haben. Daruber hinaus sollen sich diese Netzwerke noch selbst organisieren konnen wie Pareto-Netzwerke.

    Eine Alternative sind Zufalls-Netzwerke. Wie der Name schon sagt, sind dies Netzwerke mit zufalliger Verbindungsstruktur. Zufalls-Netzwerke haben viele Eigenschaften, die sie fur den Einsatz im Bereich der Peer-to-Peer-Netzwerke inter- essant machen. So besitzen sie z.B. mit hoher Wahrscheinlichkeit einen logarithmischen Durchmesser, bleiben auch beim Ausfall vieler Netzwerkteilnehmer mit hoher Wahrscheinlichkeit zusammenhangend, lassen sich beim Ausfall einiger Netzwerkteilnehmer leicht reparieren, da lediglich ein neuer zufalliger (d.h., beliebiger) Nachbar gewahlt werden muss, etc.
    Es stellt sich die Frage, wie wir Zufalls-Netzwerke erzeugen and unterhalten konnen and welche Typen von Zufalls-Netzwerken es gibt. Hierfur werden wir im Folgenden zunachst mathematische Modelle fur Zufallsgraphen vorstellen. Dann werden wir untersuchen, wie wir Zufalls-Netzwerke, die diesen Klassen entsprechen, verteilt als Verbindungsstruktur eines Peer-to-Peer-Netzwerks unterhalten konnen.
9.2.1 Standardmodelle fur Zufallsgraphen

    Es gibt eine einfache Operation, die zufallige Graphen aus yn.p gleichwahrscheinlich erzeugt. Hierzu wahlt man wiederholt ein zufalliges Knotenpaar aus den n Knoten and fugt eine Kante zwischen diesen mit Wahrscheinlichkeit p ein and entfernt these mit Wahrscheinlichkeit 1 - p. Dabei spielt es keine Rolle, ob die Kante bereits existiert hat, oder ob das zufallige Knotenpaar schon einmal zuvor gewahlt wurde. Der resultierende Graph ist ein echt zufalliger Graph der Masse gn,p, sobald jedes der moglichen Knotenpaare mindestens einmal gewahlt wurde.
    Leider ist es schwierig, die beschriebene Operation in einem Peer-to-Peer-Netzwerk umzusetzen. Ein Problem ist die zufallige Wahl eines Knotenpaares. Hierzu musste ein Peer alle anderen im Netzwerk existierenden Peers kennen (z.B. durch Fluten mit Nachrichten). Eine weitere Moglichkeit ware es, einen sehr langen Random Walk im Netzwerk durchzufuhren. Bei einem Random Walk wandert man durch das Netzwerk, in dem man an jedem Knoten bzw. Peer eine zufallige Kante wahlt and dieser folgt. Ist ein solcher Random Walk sehr lang, wird irgendwann jeder andere Knoten mit gleicher Wahrscheinlichkeit erreicht. Allerdings ist die Lange des hierfur benotigten Random Walks abhangig von der (unbekannten) Struktur des Netzwerks and mitunter viel zu lang, um praktisch umgesetzt zu werden.

    Ein weiteres Problem ist, dass das Netzwerk durch these Operationen auseinanderfallen kann. Und ist das Peer-to-Peer-Netzwerk erst in zwei Komponenten zerfallen, kann es nicht wieder zusammengefugt werden - zumindest nicht ohne zusatzliche Informationen, die in einem Peer-to-Peer-Netzwerk nicht vorhanden sind.
    In einem Zufallsgraph des yn,p-Modells haben die Knoten zudem unterschiedliche Grade; wir batten jedoch eingangs festgehalten, dass die Knoten moglichst den gleichen Grad haben sollten. Nun existiert jedoch mit cn,d auch ein weit ver- breitetes Modell fur solche reguldren Zufallsgraphen. Hier bezeichnet n wieder die Anzahl der Knoten and d den Grad ebendieser. Der Wechsel zu d-reguldren Graphen hilft zugleich, das Problem des mangelnden Zusammenhangs abzuschwachen. Denn f u r d > 3 ist ein