Upload
ilma-andreae
View
106
Download
0
Embed Size (px)
Citation preview
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und Komplexität
Algorithmen desInternets
Sommersemester 200527.06.2005
11. Vorlesung
Christian [email protected]
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
2
Heute
Überblick
•Das Internet: Einführung und Überblick
•Mathematische Grundlagen
•IP: Routing im Internet
•TCP: Das Transport-Protokoll des Internets
•Die Struktur des World Wide Web und des Internets
•Suche im Web
•Web-Caching im Internet
•Peer-to-peer-Netzwerke
– Geschichte und Bedeutung
– 1. Generation: Napster
– 2. Generation: Gnutella
– 3. Generation: CAN und CHORD
•Angriffe auf das Internet
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Peer-to-Peer Netzwerke 2005
•Popularität
– 50% des Internetverkehrs werden durch Peer-to-Peer-Netzwerke verursacht
– 30 Mio. Europäer haben schon ein Peer-to-Peer-Netzwerk benutzt
•Peer-to-Peer-Netzwerke leben in einer feindlichen Umgebung
– Legale Situation
– Egoistische Benutzer
– Netzwerke:
• Internet Service Provider (ISP) filtern Peer-to-Peer Networking Verkehr
• Benutzer kommen und gehen unangemeldet
• Peer-to-Peer-Netzwerke werden attackiert
• Lokale Systemadministratoren bekämpfen Peer-to-peer Netzwerke
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Peer-to-peer Netzwerke
•Peer-to-peer Netzwerke sind verteilte Systeme
– ohne zentrale Kontrolle oder hierarchische Strukturen
– mit gleicher Software
– mit großer Dynamik, d.h. Knoten erscheinen und verschwinden
– mit vielen Knoten
– mit geringer Netzwerkinformation
Internet
Knotenerscheint
Knoten verschwindet
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
5
A Short History of Peer-to-Peer-Networks
•1. Generation
– Shawn “Napster” Fanning (1999)
– Zentralisierte Client-Server-Datenbank
– Peer-to-peer: download (zumeist mp3-Musik/Video)
•2. Generation
– Dezentral, unkontrolliert
• Gnutella
• eDonkey
• FastTrack
•3. Generation
– Effiziente Datenstruktur (DHT)
• CAN, Chord, Pastry, Tapestriy, ...
– Anonymität
• Freenet, I2P, GNUnet, Entropy
Zur Anzeige wird der QuickTime™ Dekompressor „TIFF (LZW)“
benötigt.
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Definition
•„Ein Peer-to-Peer-Netzwerk ist ein Kommunikationsnetzwerk zwischen Rechnern, in dem jeder Teilnehmer sowohl Client als auch Server-Aufgaben durchführt.“
•Beobachtung
– Das Internet ist (eigentlich auch) ein Peer-to-Peer-Netzwerk
•Andere Definition
– von Peer-to-Peer-Working-Group
– „In einem Peer-to-Peer-Netzwerk werden verteilte Rechenresourcen durch direkte Kommunikation gemeinsam genutzt.“
•Was ist ein Peer-to-Peer-Netzwerk nicht?
– Ein Peer-to-Peer-Netzwerk ist kein Client-Server-Netzwerk!
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
7
Napster-Geschichte
•Shawn (Napster) Fanning
– brachte Juni 1999 eine Beta-Version seines mittlerweile legendären Napster-Peer-to-peer-Netzwerks heraus
– Ziel: File-sharing-System
– Tatsächlich: Musik-Tauschbörse
– Herbst 1999 war Napster Download des Jahres
•Urheberrechtsklage der Musik-Industrie im Juni 2000
•Gegen Ende 2000 Kooperationsvertrag
– zwischen Fanning mit Bertelsmann Ecommerce
•Seitdem ist Napster eine kommerzielle File-Sharing-Plattform
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
8
Wie funktioniert Napster?
•Client-Server-Struktur
•Server unterhält
– Index mit Meta-Daten
• Dateiname, Datum, etc
– Tabelle der Verbindungen der teilnehmenden Clients
– Tabelle aller Dateien der teilnehmenden Clients
•Query
– Client fragt nach Dateinamen
– Server sucht nach passenden Teilnehmern
– Server antwortet, wer die Datei besitzt
– Anfrage-Client lädt Datei von datei-besitzenden Client herunter
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
9
Wie gut ist Napster?
•Vorteile
– Napster ist einfach
– Dateien werden schnell und effizient gefunden
•Nachteile
– Zentrale Struktur erleichtert Zensur, feindliche Eingriffe und technisches Pannen
• wie z.B. Denial-of-Service-Angriff
– Napster skaliert nicht
• d.h. mit zunehmender Teilnehmerzahl verschlechtert sich die Performanz
• Speicher auf dem Server endlich
•Resumee
– Napster keine akzeptable Peer-to-Peer-Netzwerklösung
– Bis auf den Download-Aspekt ist Napster im eigentlichen Sinne kein P2P-Netzwerk
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
10
Gnutella - Geschichte
•Gnutella
– wurde im März 2000 herausgegeben von Justin Frankel und Tom Pepper von Nullsoft
– Nullsoft ist seit 1999 eine Tochter von AOL
•File-Sharing-System
– Ziel wie Napster
– Arbeitet aber völlig ohne zentrale Strukturen
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Gnutella - Originalversion - Anbindung
•Nachbarschaftslisten
– Gnutella verbindet direkt mit anderen Clients
– Beim Download wird ein Liste von Clients mitgeliefert
– Diese werden ausprobiert bis ein Aktiver sich meldet
– Ein aktiver Client gibt dann seine Nachbarschaftsliste weiter
– Nachbarschaftslisten werden immer weiter verlängert und gespeichert
– Die Anzahl aktiver Nachbarn ist beschränkt (typisch auf fünf)
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Gnutella - Originalversion - Anbindung
•Protokoll
– Ping
• Teilnehmeranfrage
• werden weiter gereicht gemäß TTL-Feld (time to live)
– Pong
• Reaktion auf Ping
• Werden auf dem Anfragepfad zurückgereicht
• IP und Port des angefragten Teilnehmers
• Anzahl und Größe zur Verfügung gestellter Dateien
•Graphstruktur
– entsteht durch zufälligen Prozess
– unterliegt Pareto-Verteilung
– entsteht unkontrolliert
Gnutella Schnappschuss im Jahr 2000
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Gnutella - Originalversion - Anfrage
•Dateianfrage
– wird an alle Nachbarn geschickt
– diese senden sie an ihre Nachbarn
– bis zu einer vorgegebenen Anzahl von Hops
• TTL-Feld (time to live)
•Protokoll
– Query
• Anfrage nach Datei wird bis zu TTL-hops weitergereicht
– Query-hits
• Antwort auf umgekehrten Pfad
•Wenn Datei gefunden wurde, direkter Download
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Gnutella - Diskussion
•Vorteile
– verteilte Netzwerkstruktur
– Netzwerk skalierbar
•Nachteil
– Durch TTL findet für Abfragen eine implizite Netzwerkpartitionierung statt
– Dadurch Anfrageerfolg gering
– Durch lange Wege, große Latenzzeiten
•Verbesserungsvorschläge
– Random Walks statt Broadcasting
– Passive Replikation von Information entlang des Pfads
• Häufigkeit der Replikate nimmt im Quadrat des Abstands ab
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Kazaa, Gnutella (II), Morpheus
•Hybride Struktur
– Knoten mit großer Bandbreite werden zu P2P-Server ausgewählt
– Diese unterhalten P2P-Netzwerk im Stil von Gnutella
– Normale Knoten werden als Clients an diese Super-Knoten angebunden
•Eingesetzt in
– Kazaa
– Morpheus
– Gnutella (neuere Ausgabe)
•Vorteile
– Verbesserte Skalierbarkeit
– Geringere Latenzzeiten
•Nachteile
– Immer noch unzuverlässig und langsam
– Clients können sich der Super-Node-Aufgabe verweigern
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
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
•Ein Graph ist k-zusammenhängend,
– wenn es k Knoten gibt, nach deren Entfernung der Graph unzusammenhängend ist
– wenn nach Entfernen von k-1 beliebigen Knoten der Graph noch zusammenhängend ist.
•Napster skaliert nicht, weil
– der Grad des Graphen ist groß
• Flaschenhals in Kommunikation
– und der Zusammenhang ist schwach
• keine robuste Konstruktion
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Warum skaliert Gnutella nicht?
•Gnutella
– Graph-Struktur ist zufälliger Verbindungsgraph
– Grad des Graphen klein
– Durchmesser gering
– Zusammenhang groß
•Suche aber aufwändig
– Um ein Datum sicher zu finden, muss das gesamte Netzwerk durchsucht werden
•Gnutella skaliert nicht, weil
– Keine Struktur in der Datenablage
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Warum skalieren Kazaa und Co. nicht?
•Hybride Struktur
– Durchmesser gering
– Zusammenhang kann hoch gewählt werden
• durch Anzahl Super-Nodes per Client
– Grad gering
•Skaliert
– nicht so schlecht wie Gnutella oder Napster
– nicht gut, da jeder Super-Node jede Anfrage der Clients erhält
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Von der Hash-Tabelle zur Distributed Hash-Table (DHT)
•Hash-Tabellen
•Vorteile
• Suche einfach
•Nachteile
– Ein neuer Peer verursacht neue Wahl der Hash-Funktion
– Lange Wege
•Distributed Hash-Table
•Peers 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
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
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
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
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
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Content Addressable Network (CAN)
•Dateien werden in durch (zweiwertige)-Hash-Funktion in das Quadrat abgebildet
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
A Scalable Content Addressable Network (CAN)
•Dateien werden in durch (zweiwertige)-Hash-Funktion in das Quadrat abgebildet
DickKarp
Mark Handley
SylviaRatnasamy
Paul Francis
Scott Shenker
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Content Addressable Network (CAN)
•Dateien werden in durch (zweiwertige)-Hash-Funktion in das Quadrat abgebildet
•Am Anfang ist ein leeres Quadrat mit nur einem Peer als Besitzer
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Content Addressable Network (CAN)
•Dateien werden in durch (zweiwertige)-Hash-Funktion in das Quadrat abgebildet
•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
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Content Addressable Network (CAN)
•Dateien werden in durch (zweiwertige)-Hash-Funktion in das Quadrat abgebildet
•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
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Content Addressable Network (CAN)
•Dateien werden in durch (zweiwertige)-Hash-Funktion in das Quadrat abgebildet
•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
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Content Addressable Network (CAN)
•Dateien werden in durch (zweiwertige)-Hash-Funktion in das Quadrat abgebildet
•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
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Content Addressable Network (CAN)
•Dateien werden in durch (zweiwertige)-Hash-Funktion in das Quadrat abgebildet
•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
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Content Addressable Network (CAN)
•Dateien werden in durch (zweiwertige)-Hash-Funktion in das Quadrat abgebildet
•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
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Content Addressable Network (CAN)
•Dateien werden in durch (zweiwertige)-Hash-Funktion in das Quadrat abgebildet
•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
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Content Addressable Network (CAN)
•Dateien werden in durch (zweiwertige)-Hash-Funktion in das Quadrat abgebildet
•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
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Wie groß/klein können solche Flächen werden
•R(p) : Rechteck eines Peers p
•A(p) : Fläche des Rechteck eines Peers p
•n : Anzahl Peers
•Anfangsquadrat: Fläche 1
•Lemma
– Für alle Peers p gilt
•Sei PR,n die Wahrscheinlichkeit, dass keines der n Peers in das Rechteck R hineinfällt. Dann gilt
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Die erwartete Fläche eines Peers in CAN
Beweis von 1.
Seien {1,..,n} die Peers.
Dann gilt:
Ferner gilt wegen Symmetrie
Damit gilt:
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Ein nichtgetroffenes Rechteck
Beweis von 2.
Betrachte ein Rechteck R der Fläche x=Vol(R)
Die Wahrscheinlichkeit, dass ein Peer nicht in diese Fläche fällt, ist
Die Wahrscheinlichkeit, dass n Peers nicht in R hineinfallen ist
Damit ist die Wahrscheinlichkeit dafür höchstens
weil für alle
R
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Wie groß kann ein nicht getroffenes Rechteck sein?
Aus 2.
folgt für ein Rechteck Ri Fläche 2-i
Es genügen also Peers um Ri
mit Wahrscheinlichkeit 1- n-c
zu teilen. Diese kommen jetzt hintereinander. Sei nun
Damit wird ein Rechteck der Fläche mit W‘keit nicht geteilt
R1
R2
R3
R4
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
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 maximal 2 c (ln n) m/n Elemente,
– während der Durchschnitt m/n Elemente speichert
•Also speichert jeder Peer höchstens 2c (ln n) mal mehr als der Durchschnittspeer mit hoher Wahrscheinlichkeit.
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Lookup in CAN
•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)
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
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
•Nachteil
– Durchmesser bei konstanten Dimensionen des Raums polynomiell groß
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Wie gleichmäßig werden die Daten verteilt?
•Lemm
– 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.
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
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
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
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)
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
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
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
44
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
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
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
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Chord
•von Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek und Hari Balakrishnan (2001)
•DHT mit Hash-Bildbereich {0,..,2m-1}
– für genügend großes m
•Ring-Verknüpfung der Peers
•Abkürzungen im Ring durch exponentiell gestaffelte Zeiger auf Nachfolger
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Chord als DHT
•n: Knotenanzahl, Knotenmenge V
•k: Anzahl Schlüssel, Schlüsselmenge K
•m: Hashwertlänge: m >> log max{K,N}
•Zwei Hash-Funktionen bilden auf {0,..,2m-1} ab
– rV(b): bildet Peer b zufällig auf {0,..,2m-
1} ab
– rK(i): bildet Index i zufällig auf {0,..,2m-1}
ab
•Abbildung von i auf einen Peer b = fv(i)
– fV(i) := arg minb∈V (rB(b)-rK(i))
Index0
123
4
5
6
7
2
3
5
2 0
6
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Die Datenstruktur von Chord
•Für jeden Knoten b:
– successor: Nachfolger
– predecessor: Vorgänger
– Für i {0,..m-1}∈• Finger[i] := Der Knoten der
dem Wert rV(b+2i) folgt
•Für kleine i werden die Finger-Einträge immer gleich
– Nur unterschiedliche Fingereinträge werden gespeichert
•Lemma
– Die Anzahl unterschiedlicher Finger-Einträge für Knoten b ist mit hoher Wahrscheinlichkeit O(log n)
•Hohe Wahrscheinlichkeit = 1 - n-c
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Balance in Chord
•n: Anzahl der Knoten im P2P-Netzwerk
•k: Anzahl der Schlüssel ≥ 1
•Theorem
– Die Datenstruktur von Chord hat folgende Eigenschaften
• Balance&Load: Mit pol. W‘keit (1-n-c) werden in jedem Knoten höchstens O(k/n log n) Schlüssel gespeichert
• Dynamik: Tritt ein neuer Knoten hinzu oder verlässt ein Knoten das Netzwerk müssen mit pol. W‘keit höchstens O(k/n log n) Schlüssel bewegt werden.
•Beweis
– …
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Eigenschaften der Datenstruktur
•Lemma
– Der Abstand |rV(b.succ) - rV(b)| ist
• im Erwartungswert 2m/n,
• mit hoher Wahrscheinlichkeit höchstens O((2m/n) log n) und
• mit hoher Wahrscheinlichkeit mindestens (2m/n)/ nc für eine Konstante c>0
• In einem Intervall der Länge w 2m/n sind mit hoher Wahrscheinlichkeit
Θ(w) Knoten, falls w=Ω(log n)
höchstens O(w log n) Knoten, falls w=O(log n)
•Lemma
– Die Anzahl der Knoten, die einen Fingerzeiger auf Knoten b besitzen ist
• im Erwartungswert O(log n)
• mit pol. Wahrscheinlichkeit höchstens O(log n)
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Suchen in Chord
•Theorem
– Die Suche braucht mit hoher W’keit O(log n) Sprünge
•Suchalgorithmus für Element s:
Abbruch(b,s):
Knoten b,b’=b.succ gefunden, mit rK(s) [r∈ V(b),rV(b‘)|
Hauptroutine: Starte mit irgendeinem Knoten b
while not Abbruch(b,s) do
for i=m downto 0 do
if rK(s) [r∈ V(b.finger[i]),rV(finger[i+1])] then
b ← b.finger[i]
fi
od
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
b
s
b.finger[m]
b.finger[m-1]c
x y
Suchen in Chord
•Theorem
– Die Suche braucht mit hoher W’keit O(log n) Sprünge
•Beweis:
– Mit jedem Sprung wird die Entfernung zum Ziel mindestens halbiert
– Zu Beginn ist der Abstand höchstens 2m
– Der Mindestabstand zweier benachbarter Peers ist 2m/nc mit hoher W’keit
– Damit ist die Laufzeit beschränkt durch c log n
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Lemma
– Der Ausgrad im CHORD-Netzwerk ist O(log n) mit hoher W‘keit
– Der Eingrad im CHORD-Netzwerk ist O(log2 n) mit hoher W‘keit
Beweis
• Der minimale Abstand zweier Peers ist 2m/nc (mit hoher W‘keit)
– Damit ist der Ausgrad beschränkt durch c log n (mit hoher W‘keit)
• Der maximale Abstand zweier Peers ist O(log n 2m/n)
– Jeder Peer, der mit einem seiner Finger auf diese Linie zeigt, erhöht den Eingrad des nachstehenden Peers.
– Die Gesamtlänge der Streckenabschnitte, wo solche Peers liegen ist O(log2n 2m/n)
– Damit ist w=O(log2n)
Fingeranzahl
b
b.finger[m]
a.finger[m-1]
x ya
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
54
Einfügen von Peers
•Theorem
– O(log2 n) Nachrichten genügen mit hoher W’keit, um Peers in CHORD aufzunehmen
Algorithmen des Internets 2005-11
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
55
Einfügen von Peers
•Zuerst wird Zielgebiet in O(log n) Schritten gesucht
•Die ausgehenden Zeiger werden vom Vorgänger und Nachfolger übernommen und angepasst
– Die Zeiger müssen jeweils um bis zu O(log n) Schritte entlang des Rings angepasst werden
•Der Eingrad des neuen ist mit hoher W’keit O(log2 n)
– Zu suchen kostet jeweils O(log n)
– Diese sind jeweils in Gruppen von maximal O(log n) benachbart.
– Damit fallen nur O(log n) Suchen á Kosten O(log n) an
– Die Aktualisierung hat jeweils konstante Kosten
56
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und Komplexität
Vielen Dank!
Ende der 11. VorlesungNächste Übung: Mo. 04.07.2005Nächste Vorlesung: Mo. 04.07.2005
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