1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 07.05.2004 3. Vorlesung

1

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Algorithmen für Peer-to-Peer-Netzwerke

Sommersemester 200407.05.2004

3. Vorlesung

Christian Schindelhauer

Algorithmen für Peer-to-Peer-Netzwerke 2


Algorithmen und KomplexitätChristian Schindelhauer

Kapitel I




Terminänderungen

Vorlesung:– Nächste Vorlesung: Mo. 17.05.2004, 9-11 Uhr F0.530– Dann wieder jeden Freitag 9-11 (c.t.), Raum F0.530

Übung– Anmeldung zum Vorrechnen durch StudInfo{flex}, siehe– http://wwwcs.upb.de/cs/ag-madh/WWW/Teaching/2004SS/AlgoP2P/

– Gruppe A: Mo 10-11 (Christian Schindelhauer), nächste Termine: • Mo. 10.05.2004, 10 Uhr• Fr. 14.05.2004, 9 Uhr (Vertretung durch Mahlmann)

– Gruppe B: Mo 11-12 (Peter Mahlmann), nächste Termine• Mo. 10.05.2004, 11 Uhr• Fr. 14.05.2004, 10 Uhr

– Gruppe C: Mo 16-17 (Peter Mahlmann), nächste Termine• Mo. 10.05.2004, 16 Uhr• Mo. 17.05.2004, 16 Uhr




Kapitel III

Warum manche Netzwerke nicht skalieren




Warum skaliert Napster nicht?

Napster– Client-Server-Struktur entspricht Stern-

Topologie– Grad des Graphen n-1

• n Anzahl der Peers– Der Stern-Graph ist 1-zusammenhängend

Napster skaliert nicht, weil– der Grad des Graphen ist groß

• Flaschenhals in Kommunikation– und der Zusammenhang ist schwach

• keine robuste Konstruktion




Warum skaliert Gnutella nicht?

Gnutella– Graph-Struktur ist zufälliger

Verbindungsgraph– Grad des Graphen klein– Durchmesser gering– Zusammenhang groß

Gnutella skaliert nicht, weil– Gesamtes Netzwerk durchsucht

werden müsste– Keine Struktur in der Datenablage




Warum skalieren Kazaa und Co. nicht?

Hybride Struktur– Durchmesser gering– Zusammenhang kann hoch gewählt

werden• durch Anzahl Super-Nodes per Client

– Grad geringSkaliert

– nicht so schlecht wie Gnutella oder Napster

– nicht gut, da jeder Super-Node jede Anfrage der Clients erhält




Kapitel III

Content Addressable NetworkCAN




Von der Hash-Tabelle zur Distributed Hash-Table (DHT)

Hash-TabellenVorteile

• Suche einfachNachteile

– Ein neuer Peer verursacht neue Wahl der Hash-Funktion

– Lange Wege

Distributed Hash-TablePeers werden an eine Stelle ge“hash“t

und erhalten Bereiche des Wertebereichs der Hashfunktion zugeteilt

Daten werden auch ge“hash“t– Je nach Bereich den Peers

zugeordnet

0 1 2 3 4 5 6

41523 0

Peers

Indexdatenf(23)=1 f(1)=4

Peers

Indexdaten

Hash-Funktion

Hash-Funktion




Einfügen in die Distributed Hash-Table (DHT)

Distributed Hash-Table– Peers werden an eine Stelle ge“hash“t– Dokumente ebenso– Jeder ist für einen Bereich

verantwortlich

Kommt ein neuer Knoten hinzu– müssen die Nachbarn teilen

Verlässt ein Knoten das Netzwerk– übernehmen die Nachbarn sein

Gebiet




Eigenschaften DHT

Vorteile– Jedes Datum kann einem bestimmten

Peer zugewiesen werden– Einfügen und Entfernen von Peers

erzeugt nur Veränderungen in den benachbarten Peers

DHTs werden von vielen P2P-Netzwerken benutzt

Noch zu klären:– Die Verbindungsstruktur

0 1 2 3 4 5 6

41523 0

Peers

Indexdatenf(23)=1 f(1)=4




Content Addressable Network (CAN)

Dateien werden in durch (zweiwertige)-Hash-Funktion in das Quadrat abgebildet




A Scalable Content Addressable Network (CAN)


DickKarp

Mark Handley

SylviaRatnasamy

Paul Francis

Scott Shenker






Am Anfang ist ein leeres Quadrat mit nur einem Peer als Besitzer







Der Besitzer einer Fläche speichert alle Einträge in der Fläche

Ein Peer wählt einen zufälligen Punkt in der Ebene









– Der Besitzer des entsprechenden Quadrats teilt seine Fläche und

– übergibt die Hälfte dem neuen Peer
































































Wie groß/klein können solche Flächen werden

R(p) : Rechteck eines Peers pA(p) : Fläche des Rechteck eines

Peers pn : Anzahl PeersAnfangsquadrat: Fläche 1

LemmaFür alle Peers p gilt

1.

2. Sei PR,n die Wahrscheinlichkeit, dass keines der n Peers in das Rechteck R hineinfällt. Dann gilt




Wie gleichmäßig werden die Daten verteilt?

Lemma

Mit Wahrscheinlichkeit (log n) n-c wird ein Rechteck der Größe 2c(ln n)/n nicht geteilt.

Wenn m Elemente insgesamt gespeichert werden, – so erhält jeder Peer also im Erwartungswert maximal 2 c (ln n) m/n Elemente,– während der Durchschnitt m/n Elemente speichert

Also speichert jeder Peer mit hoher Wahrscheinlichkeit höchstens 2c (ln n) mal mehr als der Durchschnittspeer.




Lookup in CAN

Lookup– Zuerst wird Ort des Indexes durch

Berechnung der Hash-Funktion bestimmt

– Zwischen den Besitzer benachbarter Rechtecke bestehen Kanten

– Anfrage wird in Richtung des Index weitergeleitet

d Dimension des Quadrats– 1: Linie– 2: Quadrat– 3: Würfel– 4: ...

Erwartete Anzahl Hops in d Dimensionen: n1/d

Durchschnittlicher Grad eines Knotens: O(d)




Einfügen in CAN = Random Tree

Random Tree– Neue Blätter werden zufällig eingefügt– Falls Wurzel interner Knoten, gehe

zufällig in linken oder rechten Teilbaum

– Falls Wurzel ist Blatt, füge zwei Blatt an diese Wurzel an

Tiefe:– im Erwartungswert 2 log n + O(1)– Tiefe O(log n) mit hoher

Wahrscheinlichkeit, d.h. 1-n-c

Beobachtung– CAN fügt neue Peers ein wie neue

Blätter beim Random Tree eingefügt werden




Entfernen von Peers in CAN

Verschwindet ein Peer,–meldet er das nicht vorher an

• Daher Nachbarn testen regelmäßig Anwesenheit

–übernimmt der erste Nachbar der das merkt das Gebiet des verschwundenen Peers

Peers können mehrere Gebiete verwalten

Häufiges Einfügen und Entfernen führt zur Kleinstaaterei (Fragmentierung)




Defragmentierung - der einfache Fall

Um die Fragmentierung zu beseitigen, wird von Zeit zu Zeit eine Zonenneuzuweisung durchgeführt

Für jeden Peer, der mindestens zwei Zonen hat,

Lösche kleinste Zone des Peers und finde Ersatzpeer für dieses Gebiet

1. Fall: Nachbarzone im Baum ist ungeteilt

Dann sind beide Peers Blätter im CAN-Baum

Übertrage Zone dem Nachbarknoten




Defragmentierung - der schwierige Fall

Für jeden Peer, der mindestens zwei Zonen hat,

Lösche kleinste Zone des Peers und finde Ersatzpeer für dieses Gebiet

2. Fall: Nachbarzone im Baum ist weiter unterteilt

Führe Tiefensuche in Nachbarbaum durch, bis zwei benachbarte Blätter gefunden worden sind

Übertrage einem Blatt (Peer) die Zonen beider Blätter und

wähle das andere Blatt (Peer) als Ersatzpeer




Bewertung CAN

Vorteile– Einfaches robustes Verfahren– Balanciert die Datenmenge– Kleiner Grad– Netzwerk ist stark

zusammenhängend, dadurch robust– Kennt verschiedene Wege zum Ziel

und kann dadurch Routen optimieren Nachteile

– Lange Wege (polynomiell lang)– Stabilität durch geringe Nachbarzahl

gefährdet




Systemverbesserungen für CAN

1. Mehrdimensionale Räume2. Verschiedene Realitäten3. Abstandsmetrik für Routing4. Überladen der Zonen5. Mehrfaches Hashing6. Topologie-angepasste Netzwerkkonstruktion7. Gleichmäßigere Partitionierung8. Caching, Replikation und Hot-Spot-Management




Mehrdimensionale Räume

D-dimensionaler Raum (statt 2-D)– 1: Linie– 2: Quadrat– 3: Würfel– ...

Die erwartete Pfadlänge bei d Dimensionen ist O(n1/d)

Erwartete Anzahl von Nachbarn O(2d)




Mehrere Realitäten

Simultan werden r CAN-Netzwerke aufgebaut

Jedes CAN-Netzwerk wird Realität genannt

Auf der Suche nach einem Feld– springt man zwischen den Realitäten – wählt man die Realität, in welcher der

Abstand zum Ziel am geringsten istVorteile

– Hohe Robustheit




Mehrere Realitäten

Vorteile– Hohe Robustheit– Kürzere Wege




Realitäten versus Dimensionen

Dimensionen verkürzen die Wege besser

Realitäten erzeugen robustere Netzwerke




Überladen von Zonen

In jede Zone werden bis zu MAXPEERS (z.B. 10) Peers abgelegt

–Jeder Peer kennt alle Peers seiner Zone

–und jeweils einen der Nachbarzone–Dadurch werden Routen nicht verlängert

Wege verkürzen sich um O(MAXPEERS)Latenzzeit kann verkürzt werden

–indem jeder Peer den nächsten Peer der Nachbarzone wählt

Verbesserte Fehlertoleranz




Abstandsmetriken für Routing

Durch Messung der RTT (round trip time) wird Abstandsmessung vorgenommen

Bevorzuge kürzesten Nachbarn gemäß dieser Metrik

Vorteil:– Verringerung der Latenzzeit um konstanten Faktor

Bessere Zeitersparnis Topologie-angepasste Netzwerkkonstruktion

Siehe auch Übungsaufgabe




Mehrfaches Hashing

Daten werden nicht nur an einmal, sondern mehrfach abgespeichert,– indem man den Schlüssen mit Zahl k aus {1,2,..,COPIES} kombiniert

Dadurch erhöhte Robustheit Geringere Entfernungen

– Lookup nur zu nächster Kopie– Anzahl Hops indirekt proportional zu Anzahl Kopien




Topologie-angepasste Netzwerkkonstruktion

Die gemessenen Latenzzeiten zu m ausgezeichneten Peers, genannt Landmarken, dienen als Positionsinformation

Die Zeiten werden sortiert Die sortierte Liste der Landmarken dient als Schlüssel Dieser Schlüssel wird jetzt als Basis für die Abbildung auf Bildbereich

gewählt– Dabei wird keine „echte“ Hashfunktion gewählt– Sondern eine die ähnliche Permutation in nahe Bereiche abbildet

Dadurch– Nahe Knoten kommen in den gleichen Bereich– Enorme Verkürzung der Latenzzeiten

Aber– Wahl der Landmarken schwierig– Gefahr der ungleichen Aufgabenverteilung

40


Algorithmen und Komplexität

Heinz Nixdorf Institut& Institut für InformatikUniversität PaderbornFürstenallee 1133102 Paderborn

Tel.: 0 52 51/60 66 92Fax: 0 52 51/62 64 82E-Mail: [email protected]://www.upb.de/cs/schindel.html

Vielen DankEnde der 3. VorlesungACHTUNG TERMINÄNDERUNGNächste Vorlesung: Mo. 17.05.2004 9-11 UhrNächste Übung: 3. Übung Mo. 10.05.2004 10,12,16 Uhr (A,B,C)

4. Übung Fr. 14.05.2004 9,10 Uhr (A/B)4. Übung Mo. 17.05.2004 11 Uhr (C)

Documents

1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 07.05.2004 3. Vorlesung