Peer-to-Peer-Netzwerke: Algorithmen und Methoden

gesuchte Datei befindet, muss zwangsweise eine genugend groBe Teilmenge aller Peers be- fragt werden, um zumindest einen GroBteil der Dateien im Netzwerk auffindbar zu machen.
    Es gibt eine Reihe von Verbesserungvorschlagen, um das Nachrichtenaufkommen zu verringern. Eine Moglichkeit besteht zum Beispiel darin, Random Walks anstelle von Broadcasts fur die Suche zu verwenden [34]. Bei einem Random-Walk wird eine Nachricht nicht an alle Nachbarn, sondern nur an einen zufalligen weitergereicht. Auf these Weise wird die Suche weiter in das Netzwerk hineingereicht, ohne das Nachrichtenaufkommen stark zu erhohen.
    Ein weiterer Vorschlag ist die passive Replikation [35] von Information entlang eines Pfads. Hierbei werden Ergebnislisten gespeichert, and neue Anfragen nach demselben Dokument konnen dann sofort ohne weitere Suchnachrichten beantwortet werden.
3.3 Zusammenfassung
    Wir haben in diesem Kapitel die Fruhphase der Peer-to-Peer-Netzwerke kurz ge- streift. Das klassische Peer-to-Peer-Netzwerk ist sicherlich Gnutella, wahrend Napster, obgleich seiner Client-Server-nahen Struktur, durch seine Publizitat die Auf- merksamkeit and Fantasie einer groBeren Offentlichkeit erregt hat. Das GnutellaNetzwerk in seiner ursprunglichen als auch in einer weiterentwickelten Form (Gnutella-2, Seite 244) hat bis heute uberlebt. Das kann man als deutlichen Beweis der Tragf ihigkeit des Peer-to-Peer-Netzwerk-Ansatzes werten.

4

CAN: Ein Netzwerk mit adressierbaren Inhalten
    It's hip to be square.
    Huey Lewis And The News.
    Im Jahr 2000 verOffentlichten Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp and Scott Shenker ein,,Skalierendes Netzwerk mit adressierbaren Inhalten" (Scalable Content Addressable Network) [8], abgekurzt als CAN.
    Im Wesentlichen ist CAN eine verteilte Datenstruktur, durch die Daten bestimmten Peers zugewiesen werden. Die Peers sind dabei durch eine Gitterstruktur verbunden, siehe Abbildung 4.1. Diese Gitterstruktur kann durch einfache lokale Operationen aufgebaut and aufrechterhalten werden. CAN war das erste Peer-to-PeerNetzwerk, das effiziente Datenstrukturen mit einem verteilten Overlay-Netzwerk kombinierte.
    Wir konzentrieren uns im Folgenden bei der Beschreibung von CAN auf die verteilte Datenstruktur and gehen nicht naher auf Details des Verbindungsaufbaus oder des Kommunikationsprotokolls ein.
4.1 Verteilte Hash-Tabellen
    CAN versucht die Daten gerecht auf die Peers zu verteilen. Fur die Zuordnung wird eine quadratische Flache Q = [0, 1) x [0, 1) verwendet. Diese Flache wird partitio- niert in Rechtecke and Quadrate, die jeweils einem Peer zugewiesen werden. Des Weiteren wird jedem Datum ein Punkt des Quadrates Q zugeordnet. Jeder Peer verwaltet dann die Daten, die seinem Quadrat oder Rechteck zugewiesen wurden.
    Idealerweise sollten die Daten gleichmaBig uber das game Quadrat verteilt werden and die Flachen der Peers gleich groB sein, so dass die Daten gleichmaBig auf die Peers verteilt werden. Die Verteilung der Daten geschieht Uber eine so genannte Hash-Funktion f : K Q, die jedem Datum eine scheinbar zufallige Position zu- weist. Hierbei bezeichnet IC die Menge aller moglichen Datenschlussel. Dies konnen z.B. Dateinamen sein.

    Abb. 4.1. Ein CAN mit idealer Struktur.
    Das englische Wort Hash bedeutet soviel wie ,zerhacken". Eine Hash-Funktion bildet die Eingabe, hier den Schlussel, auf eine Ausgabe bestimmter Lange ab, den Hash-Wert . Im Idealfall erhalt jede Eingabe einen eindeutigen Hash-Wert. Da der Schlusselraum jedoch typischerweise wesentlich groBer ist als der Bildraum, lasst es sich nicht vermeiden, dass einige Eingaben dem gleichen Hash-Wert zugeordnet werden. Hierbei spricht man von so genannten Kollisionen. Tatsachlich treten Kollisionen in der Praxis jedoch kaum auf, wenn der Wertebereich der Hash-Funktion groB genug gewahlt wird, d.h. der Wertebereich wesentlich groBer als die Anzahl der tatsachlich verwendeten Schlussel ist. Dies wird z.B. durch 128-Bit-Hash-Werte erreicht, wodurch sich bereits 2128 > 3, 4 • 1038 mogliche Hash-Werte ergeben. Gute Hash-Funktionen zu finden, ist eine Wissenschaft fur sich. Typischerweise bilden Hash-Funktionen ahnliche Eingaben auf Behr unterschiedliche Hash-Werte ab. Im Idealfall verhalt sich eine Hash-Funktion so, als ob jedem SchlUssel ein zufalliger Hash-Wert zugeordnet wUrde. Fur die Analyse von auf Hash-Funktionen beruhen- den Datenstrukturen wird genau das angenommen.
    Hash-Funktionen spielen in der Kryptographie eine groBe Rolle bei der