Peer-to-Peer-Netzwerke: Algorithmen und Methoden

verschiedenen Realitaten hin and her gesprungen. Ist man in einer Realitat schon ziemlich nah am Ziel, sinkt jedoch die Wahrscheinlichkeit, dass das Ziel in einer anderen Realitat naher ist.

    Abbildung 4.11 zeigt, wie sick der Durchmesser eines CANs verandert, wenn mehrere Realitaten verwendet werden. Vergleicht man die resultierende Anzahl von Suchschritten mit den Gewinnen aus einer VergroBerung der Dimension, so schneidet die Dimensionserhohung besser ab, wenn man den Grad der Knoten jeweils gleich groB wahlt.
Uberladen von Rechtecken and latenzoptimiertes Routing
    Bislang war jeweils ein Peer fur ein Rechteck im CAN verantwortlich. Werden jedem Rechteck mehrere Peers zugeordnet, so nennt man es „ Uberladen" eines Rechtecks. Hierzu wird eine Obergrenze gewahlt, die wir mit Maxpeers bezeichnen. Die Netzwerkstruktur wird dahingehend erweitert, dass ein Peer Verbindungen zu alien anderen Peers unterhalt, die fur das gleiche Rechteck verantwortlich sind. Fur die Verbindung zu benachbarten Rechtecken kann ein Peer jeweils einen beliebigen Peer aus den bis zu Maxpeers Peers wahlen. Dadurch erhoht sich der Grad des Netzwerks nur um den additiven Term Maxpeers -1. Damit die maximal Maxpeers Peers eines Rechtecks sich vollstandig ersetzen konnen, unterhalten alle Peers eines Rechtecks Kopien der Daten in diesem Rechteck. Ein solches uberladenes CAN ist in Abbildung 4.12 dargestellt.

    Abb. 4.9. Verringerung des Durchmessers durch Erhdhen der Dimension in CAN [8].

    Ein Vorteil dieser Methode ist, dass ein Peer fur seine Netzwerkverbindungen jeweils einen beliebigen der bis zu Maxpeers Peers eines Rechtecks wahlen kann. So kann zum Beispiel immer ein latenznaher Peer gewahlt werden, um das Routing im Netzwerk zu beschleunigen. Man muss sich verdeutlichen, dass die Nachbarschaft in CAN nichts uber die Laufzeit der Nachrichten aussagt. So konnen sich im Netzwerk benachbarte Rechner auf unterschiedlichen Kontinenten oder im selben Raum befinden. Die latenznahen Nachbarn konnen durch Messung der RTT (Round Trip Time) von Testnachrichten gefunden werden. Wenn man unter den Nachbarn den reaktionsschnellsten wahlen kann, ergibt sich eine wesentliche Verbesserung der Suchgeschwindigkeit. Wir werden spater sehen, dass these Idee auch von anderen Peer-to-Peer-Netzwerken aufgegriffen worden ist.
    Ein weiterer Effekt des Uberladens ist die Verringerung des Netzwerkdurchmes- sers. Der Grund hierfur ist, dass ein unfragmentiertes Netzwerk mit n Peers nun nicht mehr auf n Rechtecke aufgeteilt wird, da fur jedes Rechteck mehrere Peers erforderlich sind. Die weitere Unterteilung eines Rechtecks A findet immer nur dann statt, wenn die Anzahl der Peers in A bereits Maxpeers betragt and ein neuer Peer mittels der Hash-Funktion in das Rechteck A platziert wird. So besteht ein CAN mit n Peers moglicherweise nur noch aus [n/Maxpeers] Rechtecken.
    Abb. 4.10. Zwei Realitaten eines (zweidimensionalen) CANs.

    Abb. 4.11. Verringern des Durchmessers eines zweidimensionalen CANs durch Verwendung mehrerer Realitaten [8].
    Ein weiterer nicht zu vernachlassigender Effekt ist, dass das Nezwerk durch den hoheren Grad and die Redundanz robuster wird. Diese Robustheit kann in einem Peer-to-Peer Netzwerk von groBer Bedeutung sein.
    Latenzoptimiertes Routing kann nattirlich auch ohne das Uberladen von Rechtecken verwendet werden. Soll zum Beispiel vom Punkt (0, 0) zum Punkt (0.5, 0.5) geroutet werden and die Netzwerkstruktur besteht aus Tauter gleich groBen Rechtecken der GroBe 2-16 x 2-16 so mussen acht Schritte in x- and acht in y-Richtung in beliebiger Reihenfolge gegangen werden. Hierbei kann dann mindestens achtmal die Richtung gewahlt werden, in der der bezuglich Latenzzeit nahere Peer liegt. Dies ist jedoch nicht so effektiv wie im Fall von uberladenen Rechtecken, wo bei jedem der 16 Schritte einer von Maxpeers Peers gewahlt werden kann. Eine noch bessere Zeitersparnis kann sich durch eine der Topologie angepasste Netzwerkkonstruktion ergeben, die das CAN von Anfang an gemaB der Latenzzeiten aufbaut. Dieser Ansatz setzt aber Struktur- and Ortsinformationen im Internet voraus, die nicht einfach herauszufinden sind.

    Abb. 4.12. Ein CAN mit uberladenen Rechtecken.
Datenkopien
    Genauso wie Peers an verschiedenen Stellen des Quadrats helfen konnen die Struktur zu verbessern, konnen auch Daten mehrfach platziert werden. Dafur wird einfach der Schlussel fur ein Datum mit einer Zahl k aus {1, 2, .., Copies} kombiniert. Das erhoht ebenfalls die Robustheit and