Peer-to-Peer-Netzwerke · 2007. 7. 16. · Peer-to-Peer-Netzwerke Peer-to-Peer-Netzwerke Rolf Wanka Sommersemester 2007 11. Vorlesung 05.07.2007 [email protected] basiert auf einer

Peer-to-Peer-Netzwerke

PeerPeer--toto--PeerPeer--NetzwerkeNetzwerkeRolf WankaRolf Wanka

Sommersemester 2007Sommersemester 200711. Vorlesung11. Vorlesung

[email protected]@cs.fau.de

basiert auf einer Vorlesung vonbasiert auf einer Vorlesung vonChristian SchindelhauerChristian Schindelhauer

an der Uni Freiburgan der Uni Freiburg


2

InhalteInhalte

• Kurze Geschichte der Peer-to-Peer-Netzwerke

• Das Internet: Unter dem Overlay• Die ersten Peer-to-Peer-Netzwerke

– Napster– Gnutella

• CAN• Chord• Pastry• Gradoptimierte Netzwerke

– Viceroy– Distance-Halving

• Netzwerke mit Suchbäumen– Skipnet und Skip-Graphs– P-Grid

• Selbstorganisation– Pareto-Netzwerke– Zufallsnetzwerke

• Sicherheit in Peer-to-Peer-Netzwerken

• Anonymität• Datenzugriff: Der schnellere

Download • Peer-to-Peer-Netzwerke in der

Praxis– eDonkey– FastTrack– Bittorrent

• Peer-to-Peer-Verkehr• Juristische Situation


3

PastryPastry: Einfügen eines Peers: Einfügen eines Peers• Neuer Knoten X sendet Nachricht an

Knoten Z mit längstem gemeinsamen Präfix p

• X erhält – Routingtabelle von Z– Nachbarschaftsmenge von Z

• Z aktualisiert Nachbarschaftsmenge• X informiert ℓ-Nachbarschaft• X informiert Peers in Routing-Tabelle

– mit gleichem Präfix p außerhalb der ℓ-Nachbarschaft (falls ℓ/2 < 2b)

Aufwand für Einfüge-Operation:– ℓ Nachrichten an Nachbarschaft– Erwartet (2b - ℓ/2) Nachrichten an

Knoten mit gemeinsamen Präfix – Eine Nachricht an Knoten Z mit

Antwort


4

PastryPastry: Wenn das Einfügen versagt: Wenn das Einfügen versagt

• Die Übernahme der Nachbarschaftsmenge vom nächstgelegenen Peer reicht im allgemeinen nicht

• Beispiel:– Falls kein Peer mit 1* vorhanden

ist, müssen alle anderen Peers auf den neuen Knoten zeigen

– Einfügen von 11:– 03 kennt aus Routing-Tabelle

• 22,33• 00,01,02

– 02 kennt aus Leaf-Set• 01,02,20,21

• 11 kann nicht alle notwendigen Links veranlassen


5

Fehlender Eintrag in RoutingFehlender Eintrag in Routing--TableTable

Annahme:• Tabelleneintrag Ri

ℓ fehlt in Peer D– ℓ-te Zeile und i-te Spalte der

Routing-Table• Wird festgestellt, sobald eine

Nachricht von einem Peer mit diesem Präfix ankommt

• Kommt auch vor, falls ein Peer das Netzwerk verlässt

• Kontaktiere Peers in derselben Zeile• Falls Peer bekannt ist, wird Adresse

kopiert

• Falls dies scheitert, führe Routing zu dieser Adresse durch


6

Lokalisierung der Lokalisierung der nächstennächsten KnotenKnoten

• Direkte Nachbarn bzgl. Node-ID im Peer-to-Peer-Netzwerk sind nicht Knoten in der Nähe– z.B. Link von Neuseeland nach Mittelfranken– von Indien nach Kalifornien

• Das TCP-Protokoll des Internets misst Latenzzeiten– Damit kann eine Metrik definiert werden– Diese ist die Grundlage zur Suche nach den nächsten Peers

• Damit können die Einträge in der Routing-Table optimiert werden

• Sämtliche Verfahren in Pastry beruhen hier auf Heuristiken– D.h. es gibt keinen mathematischen Nachweis der Güte der Verfahren

• Annahme: Metrik ist Euklidisch


7

Lokalität in der Lokalität in der RoutingRouting--TabelleTabelle• Annahme:

– Beim Einfügen eines Peers A in Pastry kontaktiert der Knoten zuerst einen nahen Knoten P

– Alle Knoten haben schon ihre Routing-Table optimiert

• Aber:– Der zuerst kontaktierte Peer P ist

bezüglich der Node-ID nicht nah• 1. Schritt

– Kopiere Einträge der ersten Zeile der Routing-Table von P

• wegen der Dreiecksungleichung sind diese Einträge recht gut

• 2. Schritt– Kontaktiere passenden Peer P´ von P

mit gleichen ersten Buchstaben– Wiederum sind diese Einträge relativ

nah• Wiederhole diese Schritte bis alle

Tabelleneinträge gefüllt sind


8

Lokalität im RoutingLokalität im Routing

• Für jeden Eintrag in der Routing-Tabelle wird der nächste Knoten gemäß der Latenzzeit gewählt

– Routing wählt nicht unbedingt den kürzesten Weg (bezüglich der Latenzmetrik)

– Dennoch Hoffnung auf kurze Wege

• Warum?– Mit der Länge des gemeinsamen

Präfix steigt die erwartete Latenzmetrik exponentiell

– Damit sind die letzten Sprünge am teuersten

– Hier greift aber die Menge M


9

Experimentelle ResultateExperimentelle ResultateSkalierungSkalierung

• Parameter b = 4, ℓ = 16, M = 32• In diesem Experiment steigt die durchschnittlich Hop-Distanz

logarithmisch mit der Knotenanzahl an• Analyse sagt hier 4 log n voraus• Gute Übereinstimmung


10

Experimentelle ResultateExperimentelle ResultateVerteilung der Verteilung der RoutingRouting--HopsHops

• Parameter b = 4, ℓ = 16, M = 32, n = 100 000• Ergebnis:

– Die Abweichung von der erwarteten Hop-Distanz ist extrem gering• Analyse sagt Abweichung mit extrem kleiner Wahrscheinlichkeit voraus

– Gute Übereinstimmung


11

Experimentelle ResultateExperimentelle ResultateLatenzzeitLatenzzeit

• Parameter b = 4, ℓ =16, M = 3• Im Vergleich zum kürzesten Weg erstaunlich gering

– scheint zu stagnieren


12

Kritische Betrachtung der ExperimenteKritische Betrachtung der Experimente

• Experimente geschahen in einer (gutartigen) Simulationsumgebung

• Mit b = 4, ℓ = 16 wird die Anzahl der Links pro Knoten relativ groß – Damit kann der Faktor 2b/b = 4 das Ergebnis erheblich beeinflussen– Beispiel n = 100 000

• 2b/b log n = 4 log n > 60 Links in Routing-Tabelle• Hinzu kommen noch 16 Links in Leaf-Set und 32 in M

• Dadurch ist der Grad im Verhältnis zu anderen Protokollen wie CHORD enorm groß

• Annahme Euklidischer Latenzzeiten aus der Luft gegriffen


13

Experimentelle UntersuchungenExperimentelle UntersuchungenKnotenausfälleKnotenausfälle

• Parameter b = 4, ℓ = 16, M = 32, n = 5000

• No fail: vor Ausfall• No repair: 500 von 5000 Peers fallen aus• Repair: Nach Reparatur der Routing-Tabellen


14

ZusammenfassungZusammenfassung

• Beruht auf dem Routing-Prinzip von– Plaxton, Rajamaran und Richa– Verallgemeinerung vom Routing auf dem Hypercube

• Pastry– Heuristiken für die Metrik– Experimentelle Verifikation ersetzt analytische Untersuchungen– Praktisch umsetzbar– Durch Leaf-Sets sehr robust


15

InhalteInhalte

• Kurze Geschichte der Peer-to-Peer-Netzwerke

• Das Internet: Unter dem Overlay• Die ersten Peer-to-Peer-Netzwerke

– Napster– Gnutella

• CAN• Chord• Pastry• Gradoptimierte Netzwerke

– Viceroy– Distance-Halving

• Netzwerke mit Suchbäumen– Skipnet und Skip-Graphs– P-Grid

• Selbstorganisation– Pareto-Netzwerke– Zufallsnetzwerke

• Sicherheit in Peer-to-Peer-Netzwerken

• Anonymität• Datenzugriff: Der schnellere

Download • Peer-to-Peer-Netzwerke in der Praxis

– eDonkey– FastTrack– Bittorrent

• Peer-to-Peer-Verkehr• Juristische Situation


16

Gradoptimierte NetzwerkeGradoptimierte Netzwerke

ViceroyA Scalable and Dynamic Emulation of the

Butterfly

Dahlia Malkhi, Moni Naor, David Ratajczak2001


17

Erreichbarer DurchmesserErreichbarer Durchmesser

• CHORD, Pastry:– Durchmesser O(log n) – Grad O(log n)

• Gesucht:– Netzwerk mit kleinem Ausgangsgrad– D.h. Eingangsgrad, Ausgangsgrad konstant, O(1)– Durchmesser O(log n)

• Lösung:– Viceroy– Distance-Halving-Netzwerk


18

Definition ButterflyDefinition Butterfly--Graph (mit Graph (mit wrapwrap--aroundaround--KantenKanten))

• Knoten: (i, S)– i ist aus {0,..,k-1}– S ist k-stelliger Binärstring

• Interpretation– m = 2k Knoten pro Ebene– k Ebenen– In der Regel werden die Knoten

der k-ten Ebene zweimal gezeichnet

• Kanten: Von (i, (b0,..,bi, ..., bk-1)) nach((i+1) mod k, (b0,..,bi, ..., bk-1)) und ((i+1) mod k, (b0,..,1-bi, ..., bk-1))


19

Eigenschaften ButterflyEigenschaften Butterfly--GraphGraph

• Kleiner Grad– Eingangsgrad + Ausgangsgrad = 4

• Kleiner Durchmesser– mit log m = log n + log log n optimal

• Gute Simluationseigenschaften– Andere Netzwerke können sehr effizient in einen Butterfly-Graphen

eingebettet werden– D.h. Eine Kante eines anderen Netzwerks wird durch sehr kurze Pfade im

Butterfly-Graph ersetzt• Einfache Routing-Algorithmen

– Routing-Entscheidung in konstanter Zeit möglich• Kaum Flaschhälse

– Mit hoher W‘keit: Kein Knoten wird beim Routing mit Nachrichten überlastet• Hohe Fehlertoleranz

– Ausfall von Knoten kann gut toleriert werden


20

Übersicht Übersicht ViceroyViceroy

• Zielsetzung– Skalierbarkeit– Bewältigung von Dynamik– Verteilung des Traffic

• Congestion– Maximale Anzahl Nachrichten, die ein Peer zu bewältigen hat

• Kosten für Peer-Aufnahme/Entfernen– Minimierung Anzahl Nachrichten/Zeit

• Dilation, Länge des Suchpfads• Viceroy war das erste P2P-Netzwerk mit optimaler

Grad/Durchmesser-Beziehung– Techniken lassen sich auf andere Netzwerke übertragen


Ende der 11. VorlesungEnde der 11. Vorlesung

PeerPeer--toto--PeerPeer--NetzwerkeNetzwerke

Documents

Peer-to-Peer-Netzwerke · 2007. 7. 16. · Peer-to-Peer-Netzwerke Peer-to-Peer-Netzwerke Rolf Wanka Sommersemester 2007 11. Vorlesung 05.07.2007 [email protected] basiert auf einer