Peer-to-Peer-Netzwerke: Algorithmen und Methoden

sucht man nach entsprechenden Peers am Intervallanfang and Intervallende. Dann kann man sich in der Ringstruktur von dort durch das Intervall bewegen. Die Ziel-Peers befinden sich in einer zusammenhangenden Menge von Teilbaumen.
    Man kann aber auch eine Bereichsanfrage bezuglich der Name-IDs stellen. Genau wie zuvor sucht man zuerst den Intervallanfang and das Intervallende. Die gesuchte Menge von Peers befindet sich nun auf einem Kreisausschnitt auf dem untersten Ring (Root Ring). Auch hier kann man mit Hilfe der oberen Ringe im gewunschten Bereich effizient suchen.

    Abb. 8.10. Suche nach der Num-ID 111 in Skip-Net.

    Beide Bereichsanfragen konnen die Intervallgrenzen mit hoher Wahrscheinlichkeit in Zeit O(log n) bestimmen. Das sukzessive Durchwandern der Peers dauert bei der Num-ID-Bereichssuche pro Num-ID hochstens O(log n) Schritte, im Erwartungswert aber nur konstant viele Schritte. Da bei der Name-ID-Bereichssuche ein Abschnitt auf dem untersten Ring alle gesuchten Peers beinhaltet, ist dort das Durchwandern aller Peers in jeweils einem Schritt moglich.
Lokalitat in Skip-Net
    Wahlt man die Name-IDs so, dass sie die Lokalitat der Peers widerspiegeln, so kann man das effizient ausnutzen. Beipielsweise kann die Name-ID die DNS-Adresse eines Rechners, z.B. john.microsoft.com, jack.microsoft.com, in eine Form umsetzen, welche Rechner in einem lokalen Netzwerk benachbart belasst, also z.B. com. microsoft . john and com. microsoft . jack. Damit verbleibt die Suche nach einem Schlusselwort (Name-ID) im lokalen Netzwerk, da dieses lokale Netzwerk einen Bereich im untersten Ring and entsprechende Teilbereiche in den oberen Ringen einnimmt.
    Ublicherweise werden von den Enwicklern von Peer-to-Peer-Netzwerken nur singulare Ausfalle betrachtet. Es kommt aber durchaus vor, dass ganze Teilnetzwer- ke ausfallen, weil entscheidende Netzwerkverbindungen verloren gehen. Verwendet man verteilte Hash-Tabellen, so sind die Ausfalle gleichmaBig fiber das ganze Netzwerk verteilt and konnen verkraftet werden, solange das ausfallende Teilnetzwerk nicht zu groB ist.
    In Skip-Net kann man das Netzwerk sehr schnell nach einem solchen Ausfall reparieren. Hierzu mUssen die Kamen benachbarter Peers in den Ringen jeweils mit gegenlaufigen Zeigern belegt werden. Um den verlorenen Ringausschnitt zu reparieren, werden die Abkurzungen in den hoheren Schichten betrachtet. Von diesen ausgehend, kann man die Zeiger in den unteren Schichten rekonstruieren. Dieser Reparaturvorgang dauert nur O(log n) Schritte.
8.2.5 Deterministisches Skip-Net
    Die zufallige Wahl der Num-ID kann lokal zu Effizienzverlusten fuhren. So kommt es immer wieder vor, dass in einem Ring benachbarte Peers die gleichen Munzwurfe erhalten and so in denselben Unterring kommen. Dies sorgt speziell bei der Suche zu Effizienzverlusten, da man nun im Ring linger suchen muss. Man kann sich uberlegen, dass im unteren Ring mit Wahrscheinlichkeit von 1 - o(1) solche Ketten bis zur Lange (1 - o(1)) log n vorkommen konnen.
    In [53] wird ein deterministischer Rebalancierungsmechanismus vorgestellt, der diesen Fall lost. Hierzu wird in einer zu langen Kette von funf benachbarten Peers, die alle in den gleichen Ring fallen, der mittlere herausgegriffen and in den anderen Ring umbalanciert. Diese Operation nennt man Rotation. Sie ist in Abbildung 8.11 dargestellt. Dort wird der Peer dann rekursiv weiter einsortiert. Fur solch ein deterministisches Skip-Net gelten die hier gezeigten Schranken nicht nur mit hoher Wahrscheinlichkeit, sondern absolut.

    Hierzu uberlegt man sich, dass der linke hochstens viermal so groB ist wie der rechte Teilbaum (und umgekehrt). Damit ist die Tiefe des deterministischen SkipGraphen hochstens IOU 4n. n. Verwendet man these Operation auch zum Netzwerkauf- 3 bau, so erhalt man ein Skip-Net ganz ohne Zufall and ohne entsprechende randomi- sierte Analysen.
    Abb. 8.11. Rotationsoperation fur eine deterministische Version von Skip-Net.
8.2.6 Zusammenfassung
    Skip-Net stellt eine effiziente and einfache Datenstruktur zur sortierten Speicherung von Daten oder Indizes zur Verfugung. Die Voraussetzung hierbei ist, dass jeder Peer einen zusammenhangenden disjunkten Datenbereich verwaltet. Die Zuordnung dieser Daten and eine mogliche Rebalancierung sind nicht Gegenstand der Betrachtung innerhalb von Skip-Net.
    Skip-Net ist skalierbar and besitzt logarithmischen Grad, Durchmesser and eine effiziente Suchzeit fur Bereichsanfragen. Ausfalle von Teilnetzwerken konnen in