PPT - Institut für Informatik

 Documents

 90 views
of 28
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 17.05.2004 4. Vorlesung…
Share
Transcript
HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 17.05.2004 4. Vorlesung Christian Schindelhauer 1 HEINZ NIXDORF INSTITUT Kapitel I Universität Paderborn Algorithmen und Komplexität Christian Schindelhauer Algorithmen für Peer-to-Peer- Netzwerke 2 HEINZ NIXDORF INSTITUT Terminänderungen Universität Paderborn Algorithmen und Komplexität Christian Schindelhauer  Vorlesung: – Nächste Vorlesung: Fr. 21.05.2004, 9-11 Uhr F0.530  Übung – Übungsblätter erscheinen seit letzter Woche immer montags Nächste Übungen: – Gruppe A: Mo 10-11 (Christian Schindelhauer), nächste Termine: • Mo. 24.05.2004, 10 Uhr – Gruppe B: Mo 11-12 (Peter Mahlmann), nächste Termine • Mo. 24.05.2004, 11 Uhr – Gruppe C: Mo 16-17 (Peter Mahlmann), nächste Termine • Mo. 24.05.2004, 16 Uhr Algorithmen für Peer-to-Peer- Netzwerke 3 HEINZ NIXDORF INSTITUT Kapitel III Universität Paderborn Algorithmen und Komplexität Christian Schindelhauer CHORD Algorithmen für Peer-to-Peer- Netzwerke 4 HEINZ NIXDORF INSTITUT Von der Hash-Tabelle zur Distributed Hash- Universität Paderborn Table (DHT) Algorithmen und Komplexität Christian Schindelhauer Hash-Tabellen  Vorteile Peers • Suche einfach 0 1 2 3 4 5 6  Nachteile 23 0 5 1 4 – Ein neuer Peer verursacht neue Wahl f(23)=1 f(1)=4 der Hash-Funktion Indexdaten – Lange Wege Indexdaten Distributed Hash-Table Hash-Funktion  Peers werden an eine Stelle ge“hash“t und erhalten Bereiche des Wertebereichs der Hashfunktion zugeteilt Hash-Funktion  Daten werden auch ge“hash“t – Je nach Bereich den Peers zugeordnet Peers Algorithmen für Peer-to-Peer- Netzwerke 5 HEINZ NIXDORF INSTITUT Einfügen in die Distributed Hash-Table (DHT) Universität Paderborn Algorithmen und Komplexität Christian Schindelhauer  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 für Peer-to-Peer- Netzwerke 6 HEINZ NIXDORF INSTITUT Eigenschaften DHT Universität Paderborn Algorithmen und Komplexität Christian Schindelhauer  Vorteile – Jedes Datum kann einem bestimmten Peers Peer zugewiesen werden 0 1 2 3 4 5 6 – Einfügen und Entfernen von Peers 23 0 5 1 4 erzeugt nur Veränderungen in den benachbarten Peers f(23)=1 Indexdaten f(1)=4  DHTs werden von vielen P2P- Netzwerken benutzt  Noch zu klären: – Die Verbindungsstruktur Algorithmen für Peer-to-Peer- Netzwerke 7 HEINZ NIXDORF INSTITUT Peer-to-peer Netzwerke Universität Paderborn Algorithmen und Komplexität Christian Schindelhauer  Peer-to-peer Netzwerke sind verteilte Systeme – ohne zentrale Kontrolle oder Knoten hierarchische Strukturen erscheint – mit gleicher Software – mit großer Dynamik, d.h. Knoten erscheinen und verschwinden – mit vielen Knoten Internet – mit geringer Netzwerkinformation Knoten verschwindet Algorithmen für Peer-to-Peer- Netzwerke 8 HEINZ NIXDORF INSTITUT Chord Universität Paderborn Algorithmen und Komplexität Christian Schindelhauer  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 für Peer-to-Peer- Netzwerke 9 HEINZ NIXDORF INSTITUT Chord als DHT Universität Paderborn Algorithmen und Komplexität Christian Schindelhauer rV(b) = b+1 mod 8  n: Knotenanzahl, Knotenmenge V  k: Anzahl Schlüssel, Schlüsselmenge 5 K 6  m: Hashwertlänge: m >> log max{K,N} 5 7  Zwei Hash-Funktionen bilden auf 3 {0,..,2m-1} ab rK(i) = 3i-2 mod 8 – rV(b): bildet Peer b zufällig auf 0 {0,..,2m-1} ab 4 2 Index 6 – rK(i): bildet Index i zufällig auf {0,..,2m-1} ab 1  Abbildung von i auf einen Peer b = fv(i) 3 2 2 0 – fV(i) := arg minbV (rB(b)-rK(i)) Algorithmen für Peer-to-Peer- Netzwerke 10 HEINZ NIXDORF INSTITUT Die Datenstruktur von Chord Universität Paderborn Algorithmen und Komplexität Christian Schindelhauer  Für jeden Knoten b: successor predecessor 5 – successor: Nachfolger – predecessor: Vorgänger 6 finger[0] – Für i  {0,..m-1} • Finger[i] := Der Knoten der 5 7 dem Wert rV(b+2i) folgt  Für kleine i werden die Finger- finger[1] Einträge immer gleich 0 – Nur unterschiedliche Fingereinträge finger[2] werden gespeichert 4 Lemma Die Anzahl unterschiedlicher Finger- Einträge für Knoten b ist mit hoher Wahrscheinlichkeit O(log n) 1 3 2 Hohe Wahrscheinlichkeit = 1 - n-c 2 0 Algorithmen für Peer-to-Peer- Netzwerke 11 HEINZ NIXDORF INSTITUT Suchen in Chord Universität Paderborn Algorithmen und Komplexität Christian Schindelhauer Theorem Die Schlüsselsuche braucht mit hoher Wahrscheinlichkeit O(log n) Sprünge, d.h. insbesondere nur O(log n) Nachrichten für Schlüsseleinfügen/löschen mit hoher Wahrscheinlichkeit Suchalgorithmus für Schlüssel s: – Abbruch(b,s): • Knoten b,b’=b.succ gefunden, mit rK(s)  [rV(b),rV(b‘)| – Hauptroutine: Starte mit irgendeinem Knoten b while not Abbruch(b,s) do for i=m downto 0 do if rK(s)  [rV(b.finger[i]),rV(finger[i+1])] then b ← b.finger[i] fi b.finger[m] od b.finger[m-1] b c x sy Algorithmen für Peer-to-Peer- Netzwerke 12 HEINZ NIXDORF INSTITUT Balance in Chord Universität Paderborn Algorithmen und Komplexität Christian Schindelhauer – n: Anzahl der Knoten im P2P-Netzwerk – k: Anzahl der Schlüssel  1 Theorem Die Datenstruktur von Chord hat folgende Eigenschaften 1. Balance&Load: Mit pol. W‘keit (1-n-c) werden in jedem Knoten höchstens O(k/n log n) Schlüssel gespeichert 2. 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 für Peer-to-Peer- Netzwerke 13 HEINZ NIXDORF INSTITUT Eigenschaften der Datenstruktur Universität Paderborn Algorithmen und Komplexität Christian Schindelhauer Lemma Der Abstand |rV(b.succ) - rV(b)| ist 1. im Erwartungswert 2m/n, 2. mit hoher Wahrscheinlichkeit höchstens O((2m/n) log n) und 3. mit hoher Wahrscheinlichkeit mindestens (2m/n)/ nc für eine Konstante c>0 4. In einem Intervall der Länge w 2m/n sind mit hoher Wahrscheinlichkeit a) (w) Knoten, falls w=Ω(log n) b) 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 1. im Erwartungswert O(log n) 2. mit pol. Wahrscheinlichkeit höchstens O(log n) Algorithmen für Peer-to-Peer- Netzwerke 14 HEINZ NIXDORF INSTITUT Beweise? Universität Paderborn Algorithmen und Komplexität Christian Schindelhauer Wie beweist man diese Eigenschaften Abstrakte Formulierung durch Bälle und Körbe Anwenden der Chernoff-Schranke Algorithmen für Peer-to-Peer- Netzwerke 15 HEINZ NIXDORF INSTITUT Bälle und Körbe Universität Paderborn Algorithmen und Komplexität Christian Schindelhauer Lemma Werden m Bälle zufällig in n Körbe geworfen. Dann gilt: 1. Die erwartete Zahl von Bällen pro Korb ist m/n. 2. Die Wahrscheinlichkeit, dass k Bälle auf einen bestimmten Korb fallen ist, Lemma Werden m=n Bälle zufällig in n Körbe geworfen. Dann gilt: 1. Die Wahrscheinlichkeit, dass ein (bestimmter) Korb leer bleibt, ist konstant (konvergiert gegen 1/e). Die erwartete Anzahl leerer Körbe konvergiert gegen n/e 2. Die Wahrscheinlichkeit, dass mehr als k ln n Bälle auf einen bestimmten Korb fallen, ist höchstens O(n-c) für konstante k und c. Beweis: 1. aus Übung 2. durch Chernoff-Schranke Algorithmen für Peer-to-Peer- Netzwerke 16 HEINZ NIXDORF INSTITUT Bälle und Körbe Universität Paderborn Algorithmen und Komplexität Christian Schindelhauer Lemma Werden m= k n log n Bälle zufällig in n Körbe geworfen (für jedes k>0), gilt Folgendes: 1. Für alle c>k ist die Wahrscheinlichkeit, dass mehr als c log n Bälle auf einen Korb fallen ist höchstens O(n-c‘) für ein c‘>0. 2. Für alle c0. Beweis: durch Chernoff-Schranke Algorithmen für Peer-to-Peer- Netzwerke 17 HEINZ NIXDORF INSTITUT Exkurs Wahrscheinlichkeitstheorie Universität Paderborn 1. Der Weg nach Markov Algorithmen und Komplexität Christian Schindelhauer Erwartungswert einer diskreten Zufallsvariable Daraus folgt sofort Algorithmen für Peer-to-Peer- Netzwerke 18 HEINZ NIXDORF INSTITUT Markovs Ungleichung Universität Paderborn Algorithmen und Komplexität Christian Schindelhauer Daraus folgt Stärkere Abschätzung: Chebyshev wenn die Varianz bekannt ist: Algorithmen für Peer-to-Peer- Netzwerke 19 HEINZ NIXDORF INSTITUT Chernoff-Schranke Universität Paderborn Algorithmen und Komplexität Christian Schindelhauer Bernoulli-Experiment – Entweder 0 mit Wahrscheinlichkeit 1-p – Oder 1 mit Wahrscheindlichkeit p Algorithmen für Peer-to-Peer- Netzwerke 20 HEINZ NIXDORF INSTITUT Beweis der Chernoff-Schranke: 1. Teil Universität Paderborn Algorithmen und Komplexität Christian Schindelhauer Für t>0: Wir wählen t und k wie folgt: Algorithmen für Peer-to-Peer- Netzwerke 21 HEINZ NIXDORF INSTITUT Beweis der Chernoff-Schranke 1. Teil Universität Paderborn Einfach einsetzen... Algorithmen und Komplexität Christian Schindelhauer Nun ist Daraus folgt Algorithmen für Peer-to-Peer- Netzwerke 22 HEINZ NIXDORF INSTITUT Beweis der Chernoff-Schranke 1. Teil Universität Paderborn Was ist (1+c) ln (1+c) - Nachtrag Algorithmen und Komplexität Christian Schindelhauer Nun ist Daraus folgt Nun erhält man für (1+c) ln(1+c) Nun setzt man für ein (1+c) ln(1+c) und erhält for c(0,1): Algorithmen für Peer-to-Peer- Netzwerke 23 HEINZ NIXDORF INSTITUT Chernoff-Schranke 2.Teil Universität Paderborn Algorithmen und Komplexität Christian Schindelhauer Algorithmen für Peer-to-Peer- Netzwerke 24 HEINZ NIXDORF INSTITUT Beweis der Chernoff-Schranke: 2. Teil Universität Paderborn Algorithmen und Komplexität Christian Schindelhauer Für t<0: Wir wählen t und k wie folgt: Algorithmen für Peer-to-Peer- Netzwerke 25 HEINZ NIXDORF INSTITUT Beweis der Chernoff-Schranke 2. Teil Universität Paderborn Einfach einsetzen... Algorithmen und Komplexität Christian Schindelhauer Nun ist Daraus folgt Algorithmen für Peer-to-Peer- Netzwerke 26 HEINZ NIXDORF INSTITUT Beweis der Chernoff-Schranke 2. Teil Universität Paderborn Was ist (1-c) ln (1-c) - Nachtrag Algorithmen und Komplexität Christian Schindelhauer Warum ist ? Für c=0 sind beide Seiten gleich. Die Ableitung der linken Seite ist ln(1-c); die der rechten ist -c Nun ist Daraus folgt und insbesonder die gewünschte Ungleichung. Algorithmen für Peer-to-Peer- Netzwerke 27 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Vielen Dank Ende der 4. Vorlesung Nächste Vorlesung: Fr. 21.05.2004 9-11 Uhr Nächste Übung: 5. Übung Mo. 24.05.2004 10,12,16 Uhr (A,B,C) Heinz Nixdorf Institut & Institut für Informatik Universität Paderborn Fürstenallee 11 33102 Paderborn Tel.: 0 52 51/60 66 92 Fax: 0 52 51/62 64 82 E-Mail: schindell@upb.de http://www.upb.de/cs/schindel.html 28
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks