Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Authentifizierung von Daten. Es gibt Hash-Funktionen (z.B. SHA-2), bei denen man fur einen gegebenen Hash-Wert nicht einen einzigen Schlussel rekonstruieren kann, wenn man den Hash-Wert nicht selbst erzeugt hat. Hash-Funktionen mit dieser Eigenschaft bezeichnen wir als kryptographisch sicher. So konnen Hash-Funktionen als kompak- ter Fingerabdruck verwendet werden. AuBerdem werden Hash-Funktionen in der Fehlerkorrektur bei der DatenUbertragung verwendet oder bei der Suche in Texten (z.B. Rabin-Karp Text-Suche). Fur Peer-to-Peer-Netzwerke wahlt man typischerweise kryptographisch sichere Hash-Funktion, wie um Beispiel MD-5 (Message-Digest Version 5)[36], SHA-1 (Secure Hash Algorithm 1)[37] oder SHA-2 (Secure Hash Algorithm 2)[38], von denen mittlerweile aber nur noch SHA-2 als sicher erachtet wird.

    Um das Funktionsprinzip einer Hash-Funktion zu erlautern, betrachten wir die einfache Modulo-Funktion. Diese ist im Allgemeinen ungeeignet and dient hier nur der Veranschaulichung. Wir wahlen einen eindimensionalen Bildbereich der GroBe B = 5 and mochten diesem Bildbereich Schlussel in Form von Dateinamen zu- weisen. Dafiir interpretieren wir den Schlussel als game Zahl. Wenn der Schlussel beispielsweise music. mp3 ist, so entspricht dies folgender ASCII-Zeichenkette in Hexadezimal-Darstellung: 6 d 7 5 7 3 6 9 6 3 2 e 6 d 7 0 3 3. Als Dezimalzahl ist dies 870.920.545.682.538.843.149. Da unser Bildbereich die GroBe 5 hat, wahlen wir als Hash-Funktion h(x) = x mod 5. Damit ergibt sich in unserem Beispiel als Hash-Wert: h(music.mp3) =4.
    Man verwendet Hash-Funktionen zumeist zum Speichern and Suchen von Daten. Hierzu platziert man ein Element mit SchlUssel K an der Position h(K), d.h. an der Speicheradresse des Hash-Werts von K in der Hash-Tabelle. In unserem Beispiel wird also das Datum in der Hash-Tabelle an der Position 4 abgelegt.
    Diese Technik lasst sich fur das Speichern von Daten auf Peers nicht direkt anwenden. Das hat folgende Grunde: Die Peers sind nicht durchgehend nummeriert wie die Speicheradressen. Zudem wechselt die Anzahl der Peers in einem Netzwerk standig: Neue Peers kommen fortwahrend hinzu, wahrend andere das Netzwerk verlassen. Daher musste eine eventuelle Nummerierung standig angepasst werden. Wdrde man sich sklavisch an die Datenstruktur der Hash-Tabelle halten, musste mit jedem neuen (oder verlorenen) Peer eine neue Hash-Funktion gewahlt werden, so dass die GroBe des Bildbereichs der Anzahl der gerade anwesenden Peers entspricht. Dies hatte zur Folge, dass sich die Zuordnung der Daten and Peers fast vollstandig andert. Solch eine vollstandige Neuverteilung der Daten bei einer margi- nalen Anderung der Netzwerkteilnehmer ist ineffizient and inakzeptabel.
    Dieses Problem wurde in [9] elegant gelost. Ziel dieser Arbeit war die Verteilung von Web-Seiten auf Web-Servern. Die dort entwickelte Technik ist allgemein unter dem Namen verteilte Hash-Tabelle (DHT.- Distributed Hash Table) bekannt and stellt eine Standardmethode im Bereich der Peer-to-Peer-Netzwerke dar.
    In CAN werden verteilte Hash-Tabellen wie folgt umgesetzt: Wir betrachten das Quadrat Q als zweidimensionalen Bildbereich (x, y) E [0, 1) x [0, 1). Jedem Daten- element wird durch zwei verschiedene Hash-Funktionen eine x- and y-Koordinate zugewiesen. Das Quadrat ist, wie bereits erwahnt, in Rechtecke partitioniert. Jedem Rechteck ist ein Peer zugeordnet. Jeder Peer ist fur alle seinem Rechteck zugewiesenen Daten verantwortlich. Damit ist eindeutig bestimmt, welcher Peer welches Datum speichert.
    Meldet sich nun ein neuer Peer im CAN an, so wird eines der Rechtecke in der Mitte halbiert, and der bisher Verantwortliche and der neue Peer erhalten je eine Halfte. Somit bleibt die Zuordnung von Daten anderer Peers von dieser Einfugeope ration unberuhrt. Diese Eigenschaft wird Konsistenz genannt. Daher verwendet man fur verteilte Hash-Tabellen mitunter auch den Begriff Consistent Hashing.

    Wenn die Hash-Funktion die Daten gleichma6ig auf das Quadrat verteilt, muss nur noch gewahrleistet werden, dass den Peers gleich groBe Bereiche zugewiesen werden, um die Daten gleichmaBig auf die Peers zu verteilen.
    Abb. 4.2. Zuordnung von Daten zu Peers im CAN.
4.2 Einfiigen von Peers
    Zu Beginn besteht ein CAN aus nur einem Peer, der das gesamte Quadrat Q verwaltet. Wir beschranken uns zunachst auf den Fall, dass nur neue Peers hinzukommen and keine Peers das Netzwerk verlassen.
    Jeder neue Peer wahlt zuerst einen zufalligen Punkt im Quadrat Q. Dann kontaktiert