P2P-Systeme - informatik.uni-erlangen.de · Verteilte Algorithmen (VA), WS 2003/04 1 P2P.fm: 03.02.04 14:00 (C) 2003 Hans P. Reiser, Rüdiger Kapitza, Informatik 4, Universität Erlangen-Nürnberg

Verteilte Algorithmen (VA), WS 2003/04 1(C) 2003 Hans P. Reiser, Rüdiger Kapitza, Informatik 4, Universität Erlangen-Nürnberg

P2P

.fm: 0

3.02

.04

14:0

0

P2P-Systeme

■ Überblick

■ Hybride P2P-Systeme

● Napster

■ Unstrukturierte P2P-Systeme

● Gnutella, Freenet

■ Strukturierte P2P-Systeme

● Chord, CAN, Pastry, Kademlia

■ Infrastrukturen für P2P-Systeme

● JXTA


P2P

.fm: 0

3.02

.04

14:0

0

Überblick

■ Grundform des Internet (1969-1995)

InformationsanbieterInformationskonsument


P2P

.fm: 0

3.02

.04

14:0

0

Überblick

■ WWW-dominiertes Internet (1995-1999)



P2P

.fm: 0

3.02

.04

14:0

0

Überblick

■ Peer-to-Peer Internet (ab 1999)



P2P

.fm: 0

3.02

.04

14:0

0

Überblick

■ Nachteile der Client-Server-Architektur

● Verkehrsaufkommen

– Konzentration beim Server, Unterlast in anderen Netzteilen

– Asymmetrischer Verkehr

● Skalierbarkeit

● Ungenutzte Ressourcen in Clients

– Speicherplatz, Rechenleistung, Informationen

● Server oft Single Point of Failure


P2P

.fm: 0

3.02

.04

14:0

0

Überblick

■ Schwache Definition:„Peer-to-Peer computing is a network-based computing model forapplications where computers share resources via direct exchangebetween the participating computers” (David Barkai)


P2P

.fm: 0

3.02

.04

14:0

0

Überblick

■ Ein System kann als Peer-to-Peer bezeichnet werden wenn,

● eine gemeinsame Nutzung von Ressourcen statt findet

– Jedes Teilsystem kann sowohl Informationsanbieter als auchInformationskonsument sein

● jedes Teilsystem einen gewissen Grad an Autonomie besitzt

– Keine zentrale Kontrolle oder Nutzung von zentralen Diensten

● die einzelnen Teilsysteme nicht permanent mit demGesamtsystem verbunden sein müssen

– Selbstorganisation des Systems

● die einzelnen Teilsysteme keine permanenteNetzwerkadresse benötigen

– Von der Netzwerkschicht unabhängige Adressierung


P2P

.fm: 0

3.02

.04

14:0

0

Überblick

■ Bessere Definition (vgl. Tutorial KIVS 2003)

Selbstorganisierendes System gleichberechtigter, autonomerSysteme ohne Nutzung zentraler Dienste auf der Basis einesunzuverlässigen Netzwerks


P2P

.fm: 0

3.02

.04

14:0

0

Überblick

■ Anforderungen an P2P-Systeme

● Skaliert in einem globalen Rahmen

● Einfaches publizieren von Informationen für eine beliebigeAnzahl von Informationskonsumenten

● Schnelles und effizientes Finden von Informationen

● Teilnehmende Peers können zu beliebigen Zeitpunkten demGesamtsystem beitreten und es wieder verlassen


P2P

.fm: 0

3.02

.04

14:0

0

Überblick

■ Was wird alles als P2P-System bezeichnet

● File Sharing

– Napster, Gnutella, FastTrack ....

● Verteilte Dateisysteme

– Freenet, PAST, Oceanstore

● Instant Messaging

– ICQ, AIM (AOL Instant Messenger), Jabber

● Verteiltes Rechnen

– GRID Computing, SETI@home, Popular Power

● Collaboration

– Konferenzanwendungen, Groupware


P2P

.fm: 0

3.02

.04

14:0

0

Überblick

■ Klassifikation

● Client-Server: WWW, Seti@Home

– Klassische Rollenverteilung

– Keine Interaktion zwischen Clients

● Hybride P2P-Systeme: Napster, ICQ, AIM

– Gemeinsame Nutzung von verteilten Ressourcen

– Interaktion zwischen Peers

– Koordination durch zentrale Server

● Reine P2P-Systeme: Gnutella, Freenet, Chord

– Vollständige dezentale Organisation und Nutzung derRessourcen


P2P

.fm: 0

3.02

.04

14:0

0

Überblick

■ Klassifikation von reinen P2P-Systemen

● Unstrukturierte P2P-Systeme

– Es gibt keine vorgegebene Organisationsstruktur

– Beispiele: Gnutella, Freenet

● Strukturierte P2P-Systeme

– Realisieren meist eine verteilte Hash-Tabelle

– Jeder Knoten besitzt einen eindeutigen Identfikator

– Es existiert ein Modell, das die Topologie des Systems bestimmt

– Beispiele: Chord, Can, Past, Kademlia


P2P

.fm: 0

3.02

.04

14:0

0

Überblick

■ Informationen über P2P-Systeme und Applikationen

● Allgemeine Informationen über P2P-Systeme

– http://openp2p.com

● International Workshop on Peer-to-Peer Systems

– http://www.cs.rice.edu/Conferences/IPTPS02

– http://iptps03.cs.berkeley.edu/program.html

● Hauptseminar unseres Lehrstuhls

– http://www4.informatik.uni-erlangen.de/Lehre/SS02/HS_DOOS

– http://www4.informatik.uni-erlangen.de/Lehre/SS04/HS_P2P

● Bücher

– Peer-to- Peer: Harnessing the Benefits of DisruptiveTechnology, O’Reilly & Associates, 2001


P2P

.fm: 0

3.02

.04

14:0

0

Napster

■ Erstes populäres P2P-System (1999-2001)

● Austausch von Musik-Dateien

● Zentraler Verzeichnisserver

– Verwaltet Adressen und Dateilisten der Peers

Napster-Server

PeerPeer

Peer

Peer

Peer

Peer

Dateitransfer

Dateitransfer


P2P

.fm: 0

3.02

.04

14:0

0

Napster

■ Verbindungsaufbau zum Verzeichnisserver

● Peers geben eine Liste der gespeicherten Dateien und ihreIP-Adresse an den Server bekannt

Napster-Server

PeerPeer

Peer

Peer

Peer

Peer

IP-Adresse,Dateiliste


P2P

.fm: 0

3.02

.04

14:0

0

Napster

■ Dateisuche

● Anfrage an den Verzeichnisserver

● Verzeichnisserver sucht im Datenbestand und liefert eineListe von IP-Adressen

Napster-Server

PeerPeer

Peer

Peer

Peer

Peer

Suchanfrage

Ergebnisse


P2P

.fm: 0

3.02

.04

14:0

0

Napster

■ Testen der potentiellen Zielrechner

● Durch Ping-Nachrichten wird die Verbindungsqualität derZielrechner getestet

Napster-Server

PeerPeer

Peer

Peer

Peer

Peer

Ping

Ping

Ping

Pong

Pong


P2P

.fm: 0

3.02

.04

14:0

0

Napster

■ Übertragung der gesuchten Dateien

● Benutzer baut direkte Verbindung zu dem Peer mit derbesten Verbindung auf

Napster-Server

PeerPeer

Peer

Peer

Peer

Peer

Transfer der Datei


P2P

.fm: 0

3.02

.04

14:0

0

Napster

■ Eigenschaften

● Skalierbarkeit ist eingeschränkt durch zentralenVerzeichnisserver

● Verzeichnisserver ist Single Point of Failure

● Hybrides P2P-System

■ Erweiterungen

● Mehrere vernetzte Verzeichnisserver (OpenNap-Netzwerk)

● Unterstützung für beliebige Dateiformate


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Ein Protokoll zur verteilten Suche nach Dateien

■ Ursprünglich von Nullsoft als eine Art freies Napsterentwickelt

■ Literatur:

● The Gnutella Protocol Specification v0.4

Servant

Servant

Servant

ServantServant

Host Cache

Host Cache


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Rahmenbedingungen:

● Zur Teilnahme an einem Gnutella-Netzwerk benötigt einServant mindestens eine IP-Adresse eines bereitsteilnehmenden Knotens

● Nachrichten werden über TCP-Verbindungen als ASCII-Textausgetaucht

● In der Regel verfügt jeder Servant über mehrere ständigeVerbindungen

● Jeder Teilnehmer kann frei entscheiden welche Dateien demNetzwerk zur Verfügung gestellt werden

● Das Protokoll dient zur Suche von Dateien. Der eigentlicheTransfer von Dateien wird über HTTP abgewickelt


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Verbindungsaufbau

● Ermittlung der IP-Adresse eines aktiven Knotens zumBeispiel durch einen Host Cache

● Der eigentliche Verbindungsaufbau erfolgt über eineConnect-Nachricht die durch den kontaktierten Knoten miteiner Ok-Nachricht beantwortet wird

● Im Folgenden werden dann die eigentlichenBasisnachrichten über die permanente Verbindungausgetauscht


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Es gibt verschiedene Arten von Nachrichten die alle eineneinheitlichen Header besitzen

● Message-ID besteht z. B. aus Zeitstempel, Zufallszahl undMAC-Adresse

● Payload Descriptor bestimmt den Nachrichtentyp

● Time to Live (TTL) für die Begrenzung der Suchtiefe

● Hops bestimmt wie oft die Nachricht bereits weitergeleitet wurde

Message ID Payload Descriptor TTL Hops Payload Lenght

Byte offset 0 15 16 17 18 19 22


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Nachrichten zur Erhaltung der Netzwerkstruktur:

● Ping - wird verwendet um neue aktive Peers kennen zulernen. Eine solche Nachricht kann zu einem beliebigenZeitpunkt an andere Peers versendet werden.

● Pong - Anwort auf eine Ping-Nachricht die als PayloadInformationen über einen aktiven Knoten enthält

• IP-Adresse und Port des antwortenden Rechners

• Anzahl der bereitgestellten Dateien

• Größe der bereitgestellten Daten


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Nachrichten für die Suche nach Dateien:

● Query - Eine Suchanfrage nach Dateien

• Gesuchte Zeichenkette

• Mindestanforderungen an die Übertragungsgeschwindigkeit anden bereitstellenden Peer

● QueryHit - Antwort auf eine Suchanfrage falls ein PeerDateien mit passenden Namen bereitstellt

• Port und IP-Adresse des antwortenden Peers

• Übertragungsrate mit der Dateien angeboten werden

• Liste von Dateinamen, sowie einer eindeutigen ID pro Datei undihrer jeweiligen Größe

• Eine eindeutige ID die den bereitstellenden Peer indentifiziert.Diese wird durch eine Funktion über die IP-Adresse gebildet.


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Optionale zusätzliche Nachricht Push:

● Diese Nachricht ermöglicht das Laden von Dateien falls derbereitstellende Peer hinter einer Firewall liegt und nur aktivVerbindungen aufbauen kann. Sollte sowohl das suchendePeer als auch das bereitstellende Peer hinter einer Firewallliegen können keine Dateien ausgetauscht werden.

● Zusammensetzung des Payload der Nachricht:

• ID des Zielpeers

• ID der zu übertragenden Datei

• Port und IP Adresse des anfragenden Peers


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Transfer von Dateien

● Das eigentliche Laden von Dateien erfolgt nicht über dasGnutella-Netzwerk sondern über HTTP. Hierbei wird derDateiname und die ID der zu übertragenden Datei über eineHTTP Get-Nachricht an den bereitstellenden Peer übermitteltwelcher als Antwort die Datei liefert


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Routing der Nachrichten zur Erhaltung der Netzwerkstruktur:

● Empfängt ein Peer eine Ping Nachricht, wird diese an alleverbundenen Peers weitergeleitet (vgl. Wahlalgorithmen)

● Jeder Peer der eine Ping Nachricht erhält kann mit einerPong-Nachricht antworten. Diese wird dann zurück an denInitiator geroutet.

● Erhält ein Peer eine bereits beantwortete Ping Nachricht wirdsie verworfen. Dies wird durch einen Message-Cacheermöglicht der die Nachrichten kurzzeitig zwischenspeichert.

Ping (1)Ping (2)

Ping (2

)Ping (2)

Pong (2)


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Routing der Nachrichten zur Erhaltung der Netzwerkstruktur:

● Jede Nachricht verfügt über die Felder Hops und TTL. EinPeer der eine Nachricht weiterleitet inkrementiert das FeldHops und dekrementiert das Feld TTL. Sinkt das Feld TTLauf den Wert 0 wird die Nachricht nicht mehr weitergeleitet.

Ping (TTL:5, Hops:0)Ping (TTL:4 Hops:1)


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Routing der Nachrichten zur Suche nach Dateien:

● Empfängt ein Peer eine Query-Nachricht wird diese wie einePing-Nachricht an alle verbundenen Peers weitergeleitet

● Jeder Peer der eine Query-Nachricht erhält kann mit einerQuery-Hit Nachricht antworten. Diese wird dann zurück anden Initiator geroutet.

● Erhält ein Peer eine bereits beantwortete Query-Nachrichtwird sie verworfen. Jeder Peer der eine Nachricht weiterleitetinkrementiert das Feld Hops und dekrementiert das Feld TTL.

Query (1)Query (2)

Query

(2)

Query (2)

Hit (4)

Hit (3)


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Sonderfall die Push-Nachricht

● Kann eine gefundene Datei nicht geladen werden, da derbereitstellende Peer hinter einer Firewall liegt, wird einePush-Nachricht versendet

● Diese wird über den Pfad der Query-Hit Nachricht an denbereitstellenden Peer zugestellt

Hit (4)

Hit (3)

Push (5)

Push

(6)

Push File


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Problem der Push-Nachricht: Ausnutzung für DDos-Angriffe

● Fälschen der Quelladresse in Push-Nachrichten mit derAdresse des Angriffsziels

● Versenden vieler solcher Nachrichten an mehrere Peers

● Benachrichtigte Peers versuchen nun eine Datenverbindungzum Angriffsziel aufzubauen

● Die Ermittlung des Angreifers gestaltet sich durch dasGnutella-Protokoll sehr schwierig

Hit (4)

Hit (3)

Push (5)

Push

(6)

Push File


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Evolution des Gnutella-Protokolls

■ 1.Gnutella-Generation

● Alle Knoten besitzen die gleiche Anzahl an Verbindungen

● Folge: Knoten die nur über eine schmalbandige Verbindungverfügen werden überlastet. ( Bei einer Modemverbindung istdies meist bereits bei einer Netzwerkgrösse von 1000 Knotender Fall. )

● Konsequenz: Kollaps und Fragmentierung des Netzwerks


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella


● Anzahl der Verbindungen werden entsprechend der zurVerfügung stehenden Bandbreite variiert

● Verbindungen zu überlasteten Knoten werden abgebrochen

● Skalierungsproblem bleibt bestehen


● Einführung von Hierarchien

● Sogenannte Super-Peers übernehmen Netzlast fürschmalbandig angebundene Peers

● Hybrides P2P

● Architektur ähnlich der von FastTrack


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ FastTrack als Erweiterung von Gnutella

■ Super Peers

● Einfache Peers haben nur Verbindungen zu einigen wenigenSuper Peers

● Einfache Peers teilen einem Super Peer ihre IP-Adresse undDateiliste mit

● Super Peers agieren als Proxy für einfache Peers

• Anfragen an einfache Peers können von Super Peersbeantwortet werden

• Entlastung der einfachen Peers

● Super Peers werden je nach verfügbarer Bandbreite undCPU-Leistung bestimmt


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Netzwerktopologie

● Durch die via Broadcast weitergegebenen Nachrichtenentsteht ein hoher Kommunikationsaufwand. Vor allemKnoten mit einer schwachen Netzwerkanbindung werden oftso stark belastet, dass sie nicht mehr reagieren oder ihreVerbindungen abbrechen.

● Messungen haben gezeigt das Gnutella-Netzwerke einPower-Law-Netz (Potenzgesetz-Verteilung) bilden


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Netzwerktopologie

● Potenzgesetz-Verteilung

• Allgemeine Form:

• t ist eine Domänen spezifische Konstante

• x ist der Verknüpfungsgrad eines Knotens

• P(x) ist die Wahrscheinlichkeit das ein Knoten den Grad x hat

● Knoten mit vielen Verbindungen werden stark belastet

● Neuere Gnutella-Netzwerke bewegen sich weg von Power-Law-Netzen

P x( ) xt–∼


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ November 2000


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Mai 2001


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Eigenschaften von Small-World Netzwerken

● Small-World Netzwerke können durch die Potenzgesetz-Verteilung charakterisiert werden

● Viele Knoten eines solchen Netzwerks verfügen nur übereine geringe Anzahl von Verbindungen

● Eine kleine Anzahl von Knoten sind sehr gut in das Netzwerkintegriert und verfügen über viele Verbindungen zu anderenKnoten

● Ein solches Netzwerk verkraftet den zufälligen Ausfall voneiner grossen Anzahl von Knoten ohne zu zerfallen

● Der minimale Abstand der beiden am weitesten entferntenEcken ist sehr klein


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Eigenschaften von Small-World Netzwerken (Fortsetzung)

● Die charakteristische Pfadlänge wächst logarithmisch mit derGröße des Netzes

■ Beispiele für Small-World Netze

● Natürliche neuronale Netze

• Nervensystem von Caenorhabditis elegans

● Soziale Netze

• Einwohner der USA (Six Degree of Separation)

• AT&T call graph


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Wie bilden sich Small-World-Netze?

● Small-World-Netze sind oft einem ständigem Wachstumunterworfen

● Neue Knoten binden sich bevorzugt an Knoten mit hoherKonnektivität

■ Entstehung der Small-World-Topologie bei Gnutella

● Knoten mit vielen Verbindungen antworten auf viele Ping-Nachrichten und werden deshalb für neue Verbindungenbevorzugt

● Host-Caches liefern oft gut vermaschte Knoten alsEinstiegspunkte


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Reduktion des Nachrichtenaufkommens durch effizienteSuchverfahren basierend auf der Small-World-Topologie

■ Random Walk

● Tiefensuche statt Broadcast

● Suchnachrichten werden immer nur an einen Nachbarnweitergeleitet

● Nachrichten werden höchstens einmal an einen Knotenweitergeleitet. Der Anfragepfad wird dafür in der Nachrichtvermerkt.

● Jeder Knoten hat Kenntnis über seine Nachbarn ersten undzweiten Grades und kennt alle Dateien die sie bereit stellen


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ High-degree seeking (DS)

● Vorgehensweise entspricht der von Random Walk

● Zusätzlich kennt jeder Knoten die Konnektivität seinerNachbarn

● Gerichtete Weiterleitung zu unbesuchten Nachbarn mithöchstem Verbindungsgrad


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Beispiel für DS: Simulation mit t=2.1

● Bei 10.000 Knoten werden 10 Schritte benötigt, um 50% desGraphen abzusuchen

● Mittlere Anzahl Schritte, um beliebige Knoten zu finden ist

217


P2P

.fm: 0

3.02

.04

14:0

0

Gnutella

■ Nötige Veränderungen zur Realisierung von DS

● Jeder Knoten muss Informationen über Nachbarn speichern

● Anfragen müssen mit dieser Liste verglichen werden

● Periodisches Abgleichen der Liste

● Anhängen der Knotenliste an Anfragen

■ Nachteile

● Knoten mit hoher Konnektivität werden stark belastet

● Suchanfragen dauern länger

● Das System wird anfälliger gegen Angriffe


P2P

.fm: 0

3.02

.04

14:0

0

Gia

■ Ein verbessertes Gnutella-System durch die Berück-sichtigung der Kapazität der einzelnen Knoten

■ Zielsetzung: Jeder Knoten wird so in das Netzwerk integriert,dass er entsprechend seiner Kapazität Anfragen erhält.

■ Literatur:

● Yatin Chawathe, Sylvia Ratnasamy, Lee Breslau, NickLanham, Scott Shenker: “Making Gnutella-like P2P SystemsScalable”, SIGCOMM 2003


P2P

.fm: 0

3.02

.04

14:0

0

Gia

■ Die unterschiedliche Kapazität der Knoten hängthauptsächlich von folgenden Faktoren ab

● Prozessor

● Festplattenzugriffszeiten

● Anbindung zum Netz

■ Kapazität kann im Kontext von Gnutella als bearbeiteteAnfragen pro Zeiteinheit betrachtet werden


P2P

.fm: 0

3.02

.04

14:0

0

Gia

■ Maßnahmen zur Berücksichtigung der Heterogenität

● Dynamische Anpassung der Topologie

● Aktive Flusskontrolle

● Aktive Replikation von Metadaten

● Bessere Suche basierend auf Random Walk


P2P

.fm: 0

3.02

.04

14:0

0

Gia

■ Dynamische Anpassung der Topologie

■ Zielsetzung

● Knoten mit hoher Kapazität sollen viele Verbindungenbesitzen, Knoten mit geringer Kapazität wenigeVerbindungen

■ Rahmenbedingungen

● Adressen andere Knoten werden wie bei Gnutella durch HostCaches und Ping/Pong Nachrichten ermittelt. Es wirdzusätzlich die Kapazität der Knoten mitgeteilt.

● Jeder Knoten besitzt einen ‘Level of Satisfaction’ bezüglichseiner Verbindungen. Dieser liegt zwischen 0(unbefriedigend) und 1 (zufriedenstellend)


P2P

.fm: 0

3.02

.04

14:0

0

Gia

■ Algorithmus

(1)Start: Knoten Y öffnet die Verbindung zu X

(2)Wenn X noch nicht die maximale Anzahl von Verbindugengeöffnet hat, nimmt X die Anfrage an

(3)Sollte schon die maximale Anzahl erreicht sein, werden aus derMenge bestehenden Verbindungen die Knoten ermittlet derenKapazität geringer ist als die von Y. Aus dieser Menge wird derKnoten Z mit dem höchsten Verbindungsgrad ermittlelt.


P2P

.fm: 0

3.02

.04

14:0

0

Gia

■ Algorithmus (Fortsetzung)

(4)Sollte es keinen solchen Knoten geben wird die Verbindunggeschlossen.

Sollte Y eine höhere Kapazität als alle Nachbarn von X habenoder der Verbindungsgrad von Z höher sein als der von Y, wirddie Verbindung zu Y akzeptiert und die Verbindung zu Zabgebrochen.

In allen anderen Fällen wird der Verbindungsaufbau von Y nichtakzeptiert.

■ Der Algorithmus beachtet also zuerst die Kapazität und dannden Verbindungsgrad


P2P

.fm: 0

3.02

.04

14:0

0

Gia

■ Aktive Flusskontrolle

● Jeder Knoten schickt an seine Nachbarn periodisch einErlaubnis-Token für eine Anfrage

● Anfragen werden nur bearbeitet wenn der anfragendeKnoten auch ein Token besitzt

● Kann ein Knoten nicht alle Anfragen bewältigen, weil seineKapazität nicht ausreicht oder weil er kein Token besitzt,kann er die Rate der verteilten Token reduzieren

● Token werden nicht gleichmäßig an alle Nachbarn verteilt,sondern entsprechend ihrer Kapazität (Start Time FairQueuing).

● Oft können Token an Basisnachrichten angehängt werden


P2P

.fm: 0

3.02

.04

14:0

0

Gia

■ Aktive Replikation von Metadaten

● Jeder Knoten verwaltet den Datei-Index aller seinerNachbarn

● Index wird bei jedem neuen Verbindungsaufbauausgetauscht

● Aktualisierung erfolgt periodisch


P2P

.fm: 0

3.02

.04

14:0

0

Gia

■ Bessere Suche basierend auf Random Walk

● Anfragen werden an den Nachbarn mit der größten Kapazitätvon dem ein Token vorliegt weitergeleitet

● Jeder Nachricht enthält einen Globally Unique Identifier(GUID) mit deren Hilfe Knoten erkennen können, ob sie dieNachricht schon erhalten haben und an welche Nachbarn siebereits zugestellt wurde

● Wie bei Gnutella gibt es in jeder Nachricht das Feld TTLwelches die Ausbreitung einer Nachricht begrenzt

● Zusätzlich besitzt jede Anfrage das Feld MAX_RESPONSESwelches bei jedem Treffer der Suchanfrage dekrementiertwird. Sobald MAX_RESPONSES=0 wir die Nachricht nichtmehr weiter geleite


P2P

.fm: 0

3.02

.04

14:0

0

Gia

■ Simulation - Vier Systeme

● FLOOD - Fluten begrenzt durch TTL auf einer zufälligenTopologie (Gnutella)

● RWRT - Random Walk auf einer zufälligen Topologie

● SUPER - Hierarchische Struktur unter Verwendung vonSupernodes

● GIA - Initial zufällige Topologie


P2P

.fm: 0

3.02

.04

14:0

0

Gia

■ System Model

● Knoten

• Kapazität Ci verteilt gemäß einer realen Messung des Gnutella-Netzwerkes

• Anfragerate Qi

• Warteschlange

● Zufällige Replikation

● Anfrage - Suche nach einem Schlüsselwort

● GIA

• Initial zufällige Topologie

• Min_nbrs = 3; Max_nbrs = min(max_nbrs,[C/min_alloc])min_alloc=4, max_nbrs=128


P2P

.fm: 0

3.02

.04

14:0

0

Gia

■ Metrik

● Wieviele Anfragen kann das System verkraften bevor eskollabiert ?

● Collapse point: Weniger als 90% Anfragen sind erfolgreich

0.00001

0.001

0.1

10

1000

0.01 0.1 1Replication Rate (percentage)

Co

llap

seP

oin

t(q

ps/

no

de) GIA: N=10,000

SUPER: N=10,000

RWRT: N=10,000

FLOOD: N=10,000


P2P

.fm: 0

3.02

.04

14:0

0

Gia

■ Welche der verwendeten Techniken verbessert dasVerhalten von Gia ?

Algorithmus Collapse point

GIA 7

GIA - Index-Replikation 0.004

GIA - Bessere Suche 6

GIA - Anpassung der Topologie 0.2

GIA - Adap. Flusskontrolle 2


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Freenet ist ein zensurresistentes, sicheres, verteiltesInformationssystem

■ Literatur:

● Ian Clarke, Oskar Sandberg, Brandon Wiley, and TheodoreW. Hong, "Freenet: A Distributed Anonymous InformationStorage and Retrieval System" in Designing PrivacyEnhancing Technologies: International Workshop on DesignIssues in Anonymity and Unobservability, LNCS 2009, 2001

● Ian Clarke, Oskar Sandberg, Brandon Wiley, and TheodoreW. Hong,“Protecting Freedom of Information Online withFreenet”, IEEE Internet Computing

● Projektseite: http://www.freenetproject.org


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Designziele

● Effiziente dynamische Verteilung von Informationen

● Anonymität für Informationsproduzenten und Konsumenten

● Sicherheit für Informationsanbieter

● Resistent gegenüber von Zensur


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Struktur des Free Network Protocol (FNP)

● Transportschicht

• Verbindungsorientiert, zuverlässige Datenübertragung (TCP)

● Verschlüsselungsschicht

• Dient zum Aufbau von verschlüsselten Verbindungen zwischenKnoten

• Bei einem Verbindungsaufbau wird durch den Public-KeyAlgorithmus nach ELGamal ein gemeinsamer Schlüsselausgehandelt. Dieser dient im Folgenden dazu, dieübertragenen Daten mit AES (Rijndael) zu verschlüsseln.

● Anwendungsschicht

• Definiert das eigentliche Freenet-Protokoll zum Austausch undzur Suche von Informationen


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Es können grundsätzlich drei Operation in Freenetdurchgeführt werden:

● Integration eines neuen Knotens in das Netzwerk

● Einfügen von Daten

● Anfordern von Daten


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Rahmenbedingungen des Systems

● Jegliche Informationen in Freenet werden durch Hash-Schlüssel referenziert

● Informationen werden auf Grund von lexikografischer Nähevon Schlüsseln abgelegt und gefunden

● Jeder Knoten verfügt dafür eine Routing-Tabelle die sich ausHash-Schlüsseln und Knoten-Adressen zusammensetzt. Dereinem Hash-Schlüssel zugeordnete Knoten verwaltetentweder die durch den Schlüssel referenzierten Daten oderkennt einen Knoten der die Daten verwaltet.

● Jeder Knoten verfügt über einen sogenannten Data Store.Dieser verwaltet die von einem Knoten zur Verfügunggestellten Daten.


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Rahmenbedingungen des Systems (Fortsetzung)

● Alle Nachrichten werden über verschlüsselte Verbindungenübertragen

● Wichtige Felder der meisten Nachricht:

• UniqueId: Eindeutiger ID

• Source: Absender der Nachricht

• TTL: Time to Live Zähler


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Daten anfordern:

● Anfrage an den Data Store ob Daten unter dem gesuchtenHash-Schlüssel abgelegt sind. Ist dies der Fall werden dieDaten zurückgeliefert.

● Ansonsten wird aus der Routing-Tabelle der Knoten gewählt,der am ehesten den gesuchten Schlüssel in seinem DataStore verwaltet. An diesen Knoten wird dann eine DataRequest-Nachricht versendet.

= Data Reply

= Data Request

= Request Faild

KEY DATA ADDRESS

dfsee qe4d3 tcp/5.34.27.4:66434


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Daten anfordern (Fortsetzung):

● Beim Empfang einer Nachricht wird das Feld TTLdekrementiert und die Nachricht verarbeitet. Werden dieDaten nicht durch den lokalen Data Store verwaltet wird dieData Request-Nachricht an den nächsten geeigneten Knotenweitergeleitet.

● Kennt der Knoten keinen weiteren Knoten so antwortet er anden anfragenden Knoten mit einer Request Failed-Nachricht.Der anfragende Knoten kann dann die Request-Nachricht aneinen anderen Knoten weiterleiten.

= Data Reply

= Data Request

= Request Faild

Data RequestUniqueID=C24.....Source=131.188.34.159:84523TTL=10SearchKey=8e0...


P2P

.fm: 0

3.02

.04

14:0

0

Freenet


● Sinkt das Feld TTL auf den Wert 0 und sind keine Datenauffindbar wird eine Data Not Found-Nachricht an denanfragenden Knoten versendet

= Data Reply

= Data Request

= Data Not Found


P2P

.fm: 0

3.02

.04

14:0

0

Freenet


● Verwaltet ein Knoten den gesuchten Schlüssel so versendeter eine Data Reply-Nachricht an den anfragenden Knoten

● Empfängt ein Knoten eine Data Reply-Nachricht so speicherter den Hash-Schlüssel und die Daten im Data Store. Ist derKnoten Initiator der Anfrage, werden die Daten an denAnwender zurückgeliefert, sonst wird dieNachricht an den Vorgänger in der Anfrageketteweitergeleitet.

= Data Reply

= Data Request

= Request FailedData ReplyUniqueID=C24300FB7BEA06E3DataLength=122Data...


P2P

.fm: 0

3.02

.04

14:0

0

Freenet


● Hat der letzte Knoten in der Anfragekette die Datenerfolgreich übertragen, versendet er eine Store Data-Nachricht. Diese wird entlang der Anfragekette an denInitiator propagiert

= Data Reply

= Data Request

= Store DataStore DataUniqueID=C24300FB7BEA06E3DataSoure= 131....159:84523


P2P

.fm: 0

3.02

.04

14:0

0

Freenet


● Beim Empfang einer Store Data Nachricht wird in dieRouting-Tabelle ein neuer Eintrag mit der Adresse derNachricht und dem Hash-Schlüssel der Nachrichtaufgenommen

● Bevor ein Knoten die Data Store Nachricht weiterversendet,ersetzt er mit der Wahrscheinlichkeit p das Feld Data Sourcedurch seine eigene Adresse sonst bleibt die Adresse erhalten

● Nach Verarbeitung der Data Store-Nachricht gilt die Anfrageals erfolgreich verarbeitet und der Knoten kann jeglicheStatusinformation zur Anfrage löschen


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Einfügen von Daten:

● Sollen Informationen in das System eingefügt werden, musszuerst ein Schlüssel für die einzufügenden Daten generiertwerden

● Anschließend wird eine Insert Request-Nachricht mit diesemHash-Schlüssel dem lokalen Knoten übergeben


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Einfügen von Daten (Fortsetzung):

● Dieser kontrolliert ob der Schlüssel bereits durch den lokalenData Store verwaltet wird. Ist dies der Fall wird eineFehlermeldung generiert und der Vorgang ist beendet,anderenfalls wird die Insert Request-Nachricht an dengeeignetesten Knoten weitergeleitet.

= Data Insert

= Data Reply

= Insert Reply

= Insert Request


P2P

.fm: 0

3.02

.04

14:0

0

Freenet


● Verwaltet einer der befragten Knoten den gesuchten Hash-Schlüssel generiert er eine Data Reply Nachricht. Dieseenthält die unter dem Schlüssel abgelegten Daten und wirdentlang der Anfragekette an den Initiator übertragen. Diebereits im System abgelegten Daten werden also repliziert.

= Data Insert

= Data Reply

= Insert Reply

= Insert Request


P2P

.fm: 0

3.02

.04

14:0

0

Freenet


● Verwaltet keiner der befragten Knoten den Hash-Schlüssel,wird durch den letzten Knoten in der Anfragekette eine InsertReply-Nachricht erzeugt. Diese signalisiert dass noch keineDaten mit diesem Hash-Schlüssel im System vorhanden sindund wird an den Initiator der Anfrage zurückgeleitet.

● Der Initiator kann nun die Daten mit einer Data Insert-Nachricht im Netzwerk verbreiten

= Data Insert

= Data Reply

= Insert Reply

= Insert Request


P2P

.fm: 0

3.02

.04

14:0

0

Freenet


● Hat der letzte Knoten in der Anfragekette die Daten erhalten,generiert er eine Store Data-Nachricht, die zurück an denInitiator übermittelt wird

= Data Insert

= Data Reply

= Insert Reply

= Insert Request


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Integration eines neuen Knotens in das Netzwerk geschiehtüber ein Announcement-Protokoll

■ Ziel dieses Protokolls ist es einen neuen Knoten möglichstschnell in das Netzwerk zu integrieren. Zusätzlich werdenverschiedene Anforderungen gestellt:

● Eine Anzahl von Knoten soll gleichberechtigt in die Zuteilungdes Schlüsselbereichs, für den der neue Knotenverantwortlich ist, beteiligt sein

● Der zugeteilte Schlüsselbereich muss völlig zufällig sein

● Der neue Knoten muss nach dem Announcementausreichend Kenntnis über seinen Schlüsselbereichbesitzen, d.h. er kann Anfragen effizient beantworten


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Anforderung an das Protokoll zur Intergration neuer Knoten

● Alle am Announcement beteiligten Konten besitzen nach derIntegration des neuen Knoten Kenntnis über seinen Adresseund dem ihm zugeordneten Schlüsselraum


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Ablauf der Integration eines neuen Knotens

● Node Announcement - Knoten macht sich einer Reihe vonKnoten bekannt. Jeder der Knoten wählt einen Zufallswertden er nur in Form eines kumulativen Hashwertes weiter gibt.

● Announcement Reply - Alle Zufallswerte werden entlang desAnfragepfades via XOR vermengt

● Announcement Exceute - Erzeugter Schlüssel wird an allebeteiligten Knoten vermittelt. Diese überprüfen die korrekteErzeugung.

● Announcement Completed - Alle beteiligten Knotenübermitteln die zum erzeugten Schlüssel lexikografischnaheliegenden Schlüssel.


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Allgemein wird jede in Freenet abgelegte Information durcheinen Hash-Schlüssel referenziert, der mit Hilfe des SecureHash Algorithmus erzeugt wurde

■ Es wird zwischen zwei verschiedene Schlüssel-Artenunterschieden:

● Ein Content Hash Keys (CHK) wird durch die Hashsummeüber eine Datei erzeugt und bildet einen Basismechanismusum Dateien global eindeutig zu referenzieren

● Signed Subspace Keys (SSK) bilden einen Mechanismus umeinen privaten Namensraum zu erzeugen, der von jedemBenutzer gelesen, aber nur durch den Besitzer desNamensraums geschrieben werden kann


P2P

.fm: 0

3.02

.04

14:0

0

Freenetenet

■ Erzeugung eines Signed Subspace Keys (SSK)

Public-Key-Algorithmus

Datei-Schlüssel = hash( hash(öffenlicher Schlüssel) XOR hash(Name))

Freeenet-Datei = Datei + sign(Datei)

Beispiel: SSK@9G4s~jLQJB7ALQg-v2q5xKAJy9YPAgM/mp3/Laid-Back-Bakerman.mp3

Erzeuge eine zufällige Zeichenkette für den

Name: mp3/Laid-Back-Bakerman.mp3

Datei Namensbereich ’mp3/’

SSK@ öffentlicher Schlüssel + Name der Datei


P2P

.fm: 0

3.02

.04

14:0

0

Freenetreenet

■ Wie schnell bzw. in welcher Entfernung können Datenaufgefunden werden?

■ Ausgangspunkt der Simulation

● 1000 Knoten angeordnet in einer Ringstruktur

● Jeder Knoten kennt initial nur seine unmittelbaren zweiVorgänger und Nachfolger im Ring

● Jeder Knoten verfügt über einen Data Store der maximal 50Einträge fassen kann und eine Routing-Tabelle mit maximal200 Einträgen


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Ablauf der Simulation

● Es werden in zufälliger Reihenfolge Anfrage- und Einfüge-Operationen mit einer TTL von 20 durchgeführt

● Nach 100 Operationen wird das Netzwerk betrachtet und 300Suchanfragen mit einer TTL von 500 die durchschnittlichePfadlänge bestimmt


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Durchschnittliche Pfadlänge von Anfragen


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Verknüpfungsgrad der Knoten => Small World Netzwerk


P2P

.fm: 0

3.02

.04

14:0

0

Freenetreenet

■ Wie skaliert Freenet?

■ Ausgangspunkt der Simulation

● 20 Knoten angeordnet in einer Ringstruktur

● Sonst gleiche Bedingungen wie in der ersten Simulation

■ Ablauf der Simulation

● Einfüge- und Anfrage-Operationen wie in der erstenSimulation

● Nach jeder fünften Operation wird ein neuer Knoten demNetzwerk hinzugefügt


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Durchschnittliche Pfadlänge von Anfragen


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Wie fehlertolerant ist Freenet?


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Weitere Entwicklung: Next generation routing mechanism

■ Probleme des aktuellen Systems

● Keine Unterscheidung zwischen Knoten mitunterschiedlicher Anbindung und deshalb oft langeAntwortzeiten

● Schwierigkeiten das System zu verbessern, da sichSimulationen nur bedingt als aussagekräftig erwiesen haben

● Lange Entwicklungszyklen, da Evaluierung von Änderungennur im realen System möglich sind


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Idee des next generation routing mechanism

● Intelligenteres Routing basierend auf statistischenInformationen wie

• Zeitdauer zum Aufbau von Verbindungen

• Antwortzeiten

• Anteil der erfolgreichen Anfrage

■ Abschätzung von Antwortzeiten bei Data Reply

● Ziele

• Gute Abschätzungen auch für unbekannte Schlüssel

• Schätzung passt sich dynamisch an

• Lokal berechenbar


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Algorithmus zur Abschätzung von Antwortzeiten

● Es gibt ca. 10 Referenzpunkt die sich über den gesamtenSchlüsselraum verteilen

● Nach jeder erfolgreichen Anfrage werden dienächstliegenden Referenzpunkt verschoben

● Anfragezeiten für unbekannte Schlüssel können abgeschätztwerden

Schlüsselraum

Antwortzeit


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Algorithmus (Fortsetzung)

● Die Antwortzeit einer erfogreichen Anfrage setzt sich aus derZeit zur Lokalisierung des gesuchten Schlüssels und derTransferzeit der Daten zusammen.

● Die Normalisierung der Anfragezeit kann auf der mittlerenDateigröße des lokalen Data Stores erreicht werden


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Berücksichtigung nicht erfolgreicher Anfragen

● Problem: Wie können legetime ‘Data Not Found’ (DNF)Anfragen von fehlerhaften unterschieden werden?

● Annahme: Man kann bei einer DNF-Anfrage feststellen ob siefalsch ist

• Die Dauer einer fehlerhaften Anfrage kann dann aus dermittleren Zeit von DFN-Anfragen des befragten Knotens und derdurchschnittlichen Dauer einer erfolgreichen Anfrage an einenanderen Knoten berechnet werden.

● Die Anzahl der legitimen DNF-Anfragen kannnäherungsweise durch den Knoten mit den niedrigsten DNF-Anfragen Rate bestimmt werden. Knoten mit einer höherenDNF-Anfrage Rate haben ein Routing-Problem.


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Berücksichtigung abgebrochener Verbindungen

● Sollte ein Knoten überlastet sein nimmt er temporär keineVerbindungen an

● Man kann die durchschnittliche Anzahl der fehlgeschlagenenVerbindungsversuche und ihre Dauer bertachten. Diesewerden der geschätzten Routing-Dauer hinzugerechnet


P2P

.fm: 0

3.02

.04

14:0

0

Freenet

■ Fazit

● Durch die Abschätzung der Dauer von Anfragen können inZukunft Routingentscheidungen nicht nur auf Grund vonlexikografischer Nähe gefällt werden, sondern zusätzlichbasierend auf der Kapazität und der geographischen Näheder zur Auswahl stehenden Knoten

● Die Erfassung von statistischen Daten und die daraufbasierende Abschätzung von Routingzeiten erlaubt einebessere Evaluierung von Veränderungen des Routings

Documents

P2P-Systeme - informatik.uni-erlangen.de · Verteilte Algorithmen (VA), WS 2003/04 1 P2P.fm: 03.02.04 14:00 (C) 2003 Hans P. Reiser, Rüdiger Kapitza, Informatik 4, Universität Erlangen-Nürnberg