Effizientes Routing in Peer-to-Peer Netzwerkenfile/Diplom_Schade.pdf · Netzwerk getrennt werden, lassen sich in der Regel keine verl¨asslichen Aussagen uber¨ die Verfugbarkeit

Universitat des SaarlandesNaturwissenschaftlich-Technische Fakultat IFachbereich Informatik

Diplomarbeit

Effizientes Routing in Peer-to-Peer

Netzwerken

vorgelegt von

Dennis Schade

Angefertigt unter der Leitung von

Prof. Dr. Gerhard Weikum

Max-Planck-Institut fur Informatik

AG5 Databases and Information Systems Group

Saarbrucken, 28. Marz 2005

Hiermit erklare ich an Eides statt, dass ich diese Arbeit selbstandig verfasst und keineanderen als die im Literaturverzeichnis angegebenen Quellen benutzt habe.

Dennis SchadeSaarbrucken, 28. Marz 2005

Inhaltsverzeichnis

Abbildungsverzeichnis iv

Tabellenverzeichnis vi

1 Einleitung 1

2 Einfuhrung in Peer-to-Peer-Systeme 3

2.1 Was ist Peer-to-Peer? . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.2 Vor- und Nachteile von Peer-to-Peer-Systemen . . . . . . . . . . . . . 4

2.3 Verschiedene Losungsansatze . . . . . . . . . . . . . . . . . . . . . . . 5

2.3.1 Hybride P2P-Systeme . . . . . . . . . . . . . . . . . . . . . . . 5

2.3.2 Echte P2P-Systeme . . . . . . . . . . . . . . . . . . . . . . . . 6

2.4 Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3 Der Chord-Algorithmus 15

3.1 Das Chord-Systemmodell . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.2 Das Auffinden von Schlusseln im Chord-Ring . . . . . . . . . . . . . . 16

3.2.1 Einfache Suche . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.2.2 Skalierbare Suche mit Fingertabellen . . . . . . . . . . . . . . . 18

3.3 Der Chord-Peer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.3.1 Die Chord-Stabilisierungsalgorithmen . . . . . . . . . . . . . . 21

3.3.2 Erzeugen eines Chord-Rings und Integration von Peers . . . . . 21

3.3.3 Die Nachfolgerliste . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.3.4 Verlassen und Reparatur des Chord-Rings . . . . . . . . . . . . 27

3.3.5 Aktualisierung der Fingertabelle . . . . . . . . . . . . . . . . . 28

3.4 Lastbalancierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.5 Sicherheit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.6 Verwandte Arbeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

i

4 Implementierung 32

4.1 Klassendesign . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.1.1 Die Klasse DHTNode . . . . . . . . . . . . . . . . . . . . . . . 324.1.2 Die Klasse Location . . . . . . . . . . . . . . . . . . . . . . . . 344.1.3 Die Klasse LookupKeyThread und LookupFingerThread . . . . 354.1.4 Die Klasse FingerTableStabilizer . . . . . . . . . . . . . . . . . 364.1.5 Die Klasse Stabilizer . . . . . . . . . . . . . . . . . . . . . . . . 374.1.6 Die Klassen DHTServer, PeerConnectionServer und -Client . . 384.1.7 Die Klasse RemoteMessage . . . . . . . . . . . . . . . . . . . . 404.1.8 Die Klasse Mediator . . . . . . . . . . . . . . . . . . . . . . . . 40

4.2 Kommunikation und Interaktion . . . . . . . . . . . . . . . . . . . . . 424.2.1 Betreten und Verlassen des Chord-Rings . . . . . . . . . . . . . 424.2.2 Durchfuhrung von Lookups . . . . . . . . . . . . . . . . . . . . 434.2.3 Aktualisierung der Fingertabelle . . . . . . . . . . . . . . . . . 484.2.4 Ausfuhrung des Stabilisierungsprotokolls . . . . . . . . . . . . . 49

4.3 Datenvolumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514.3.1 Datenvolumen je Lookup . . . . . . . . . . . . . . . . . . . . . 524.3.2 Datenvolumen je Stabilisierung . . . . . . . . . . . . . . . . . . 53

5 Experimentelle Analyse 55

5.1 Der statische Chord-Ring . . . . . . . . . . . . . . . . . . . . . . . . . 555.1.1 Lookups im statischen Chord-Ring . . . . . . . . . . . . . . . 555.1.2 Nachrichtenaufkommen durch Lookups . . . . . . . . . . . . . . 59

5.2 Der dynamische Chord-Ring . . . . . . . . . . . . . . . . . . . . . . . . 615.2.1 Lookups im dynamischen Chord-Ring . . . . . . . . . . . . . . 615.2.2 Systemstabilitat . . . . . . . . . . . . . . . . . . . . . . . . . . 68

5.3 Bandbreitenverbrauch . . . . . . . . . . . . . . . . . . . . . . . . . . . 775.3.1 Bandbreitenverbrauch durch Lookups . . . . . . . . . . . . . . 775.3.2 Bandbreitenverbrauch durch Stabilisierung . . . . . . . . . . . 805.3.3 Mindestbandbreitenverbrauch . . . . . . . . . . . . . . . . . . . 82

6 Zusammenfassung und Ausblick 83

A UML-Darstellungen vii

B Auswertung der Experimente ix

C Nachrichten und Nachrichtengroßen xiii

ii

D Die Konfigurationsdatei xvi

Literaturverzeichnis xvii

iii

Abbildungsverzeichnis

2.1 Arbeitsweise von Napster . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.2 Suchen mit Gnutella . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.3 Aufbau von Super-Peer-Netzwerken . . . . . . . . . . . . . . . . . . . . 10

2.4 2-dimensionales CAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.1 Chord-Ring, 10 Peers und 6 Keys . . . . . . . . . . . . . . . . . . . . . 16

3.2 Einfache Suche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.3 Fingertabelle von Peer 14 . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.4 Suche mit Hilfe der Fingertabelle . . . . . . . . . . . . . . . . . . . . . 20

3.5 Integration eines neuen Peers . . . . . . . . . . . . . . . . . . . . . . . 24

3.6 Zyklus beim Weiterleiten einer Suche . . . . . . . . . . . . . . . . . . . 27

4.1 UML-Klassendiagramm: DHTNnode . . . . . . . . . . . . . . . . . . . 33

4.2 UML-Klassendiagramm: Location . . . . . . . . . . . . . . . . . . . . . 34

4.3 UML-Klassendiagramm: LookupThreads . . . . . . . . . . . . . . . . . 36

4.4 UML-Klassendiagramm: PeerConnectionClient und -Server . . . . . . 39

4.5 UML-Klassendiagramm: Mediator . . . . . . . . . . . . . . . . . . . . 41

4.6 UML-Sequenzdiagramm: Durchfuhrung von Lookups . . . . . . . . . . 46

4.7 UML-Sequenzdiagramm: Antwort auf Lookups . . . . . . . . . . . . . 48

4.8 UML-Sequenzdiagramm: Aktualisierung eines Fingers . . . . . . . . . 49

4.9 Vererbung der Nachfolgerliste . . . . . . . . . . . . . . . . . . . . . . . 50

5.1 Durchschnittlich Suchdauer im statischen Chord-Ring . . . . . . . . . 56

5.2 Pfadlange: Suche im statischen Chord-Ring (absolut) . . . . . . . . . . 57

5.3 Pfadlange: Suche im statischen Chord-Ring (prozentual) . . . . . . . . 58

5.4 Nachrichtenanzahl (KEY LOOKUP) . . . . . . . . . . . . . . . . . . . 60

5.5 Anteil fehlgeschlagener Suchen im dynamischen Chord-Ring . . . . . . 63

5.6 Durchschnittliche Suchzeit fur dynamische Chord-Ringe . . . . . . . . 65

iv

5.7 Pfadlange fur 16 Peers in dynamischen Chord-Ringen mit verschiede-nen Join-Leave-Zeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

5.8 Pfadlange fur 64 Peers in dynamischen Chord-Ringen mit verschiede-nen Join-Leave-Zeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

5.9 Durchschnittliche Pfadlange in dynamischen Chord-Ringen . . . . . . 675.10 Stabilitat im Join-Leave-Fall, tstab = 1.5s . . . . . . . . . . . . . . . . 705.11 Vom Ring getrennte Peers im Join-Leave-Fall, tstab = 1.5s . . . . . . . 715.12 Stabilitat im Join-Fail-Fall, tstab = 1.5s . . . . . . . . . . . . . . . . . . 735.13 Vom Ring getrennte Peers im Join-Fail-Fall, tstab = 1.5s . . . . . . . . 735.14 Stabilitat im Join-Fail-Fall, tstab = 3s . . . . . . . . . . . . . . . . . . . 755.15 Vom Ring getrennte Peers im Join-Fail-Fall, tstab = 3s . . . . . . . . . 755.16 Bandbreite pro Lookup . . . . . . . . . . . . . . . . . . . . . . . . . . 795.17 Bandbreite in KB/s fur Lookups pro Sekunde . . . . . . . . . . . . . . 805.18 Bandbreite Stabilisierung . . . . . . . . . . . . . . . . . . . . . . . . . 81

A.1 UML-Klassendiagramme (1) . . . . . . . . . . . . . . . . . . . . . . . . viiA.2 UML-Klassendiagramme (2) . . . . . . . . . . . . . . . . . . . . . . . . viii

B.1 Pfadlange fur 8 Peers in dynamischen Chord-Ringen mit verschiedenenJoin-Leave-Zeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x

B.2 Pfadlange fur 32 Peers in dynamischen Chord-Ringen mit verschiede-nen Join-Leave-Zeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . x

B.3 Pfadlange fur 48 Peers in dynamischen Chord-Ringen mit verschiede-nen Join-Leave-Zeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . xi

v

Tabellenverzeichnis

2.1 Das Gnutella Protokoll . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

4.1 Beispiele fur RemoteMessages . . . . . . . . . . . . . . . . . . . . . . . 40

B.1 Pfadlange: Suche im statischen Chord-Ring (absolut) . . . . . . . . . . ixB.2 Pfadlange: Suche im statischen Chord-Ring (prozentual) . . . . . . . . ixB.3 Durch Lookups belegte Bandbreite . . . . . . . . . . . . . . . . . . . . xiiB.4 Durch Stabilisierung belegte Bandbreite . . . . . . . . . . . . . . . . . xii

C.1 Nachrichtenaufbau und -große . . . . . . . . . . . . . . . . . . . . . . . xv

D.1 Parameter der Konfigurationsdatei . . . . . . . . . . . . . . . . . . . . xvi

vi

1 Einleitung

Viele im Internet verfugbare Dienste, wie z. B. das World Wide Web (WWW) oderdas Domain Name System (DNS) [30], sind durch das Client-Server-Prinzip und ei-ne hierarchische Organisationsstruktur gepragt. In den letzten Jahren kommt jedochzunehmend eine andere Organisationsform zur Anwendung: Peer-to-Peer-Systeme(P2P-Systeme).

P2P-Systeme schließen ihre Teilnehmer (Peers) zu einem virtuellen Netzwerk inner-halb des Internets zusammen, in dem jeder Peer als Client teilnimmt und gleichzeitigaber auch als Server agiert, indem er einen Teil seiner Ressourcen zur Verfugungstellt. Durch dieses Prinzip werden die ”Kosten“ fur die Speicherung und Vertei-lung von im P2P-System gespeicherten Daten auf die einzelnen Peers verteilt, wasP2P-Systeme besonders fur die Speicherung und Verteilung von große Datenmengeninteressant macht. So erfreuen sich P2P-Systeme einer derart großen Beliebtheit, dasssie mittlerweile den großten Teil des Datenaufkommens im Internet verursachen [20].

Die anfanglich verwendeten P2P-Systeme hatten jedoch noch Designschwachen, wiemangelnde Skalierbarkeit und hohen Bandbreitenverbrauch. Um diesem Problem zubegegnen, hat sich ein neuer Ansatz herausgebildet, der auf verteilten Hashtabellenberuht. Die meisten P2P-Systeme, die verteilte Hashtabellen verwenden, benutzenrecht komplizierte und nicht immer intuitiv nachvollziehbare Such- bzw. Routingal-gorithmen.

Die Chord-Architektur [43] ist hier jedoch eine positive Ausnahme. Aus diesem Grundsoll Chord im Rahmen dieser Arbeit genauer untersucht werden. Kapitel 2 beschreibtzunachst kurz die grundlegenden Eigenschaften von P2P-Systemen und gibt einenUberblick uber die verschiedenen P2P-Ansatze. Im Anschluss daran beschreibt Ka-pitel 3 das Chord-Systemmodell und erklart die verwendeten Algorithmen. Eine Be-schreibung der im Rahmen dieser Arbeit entstandenen Implementierung von Chordsowie der wichtigsten Klassen erfolgt in Kapitel 4. Kapitel 5 beschaftigt sich mit derexperimentellen Analyse des Chord-Algorithmus. Zum Abschluss fasst Kapitel 6 die

1

1 Einleitung

Ergebnisse dieser Arbeit kurz zusammen und zeigt weitere Arbeitsfelder auf.

2

2 Einfuhrung in Peer-to-Peer-Systeme

2.1 Was ist Peer-to-Peer?

Die Idee von Peer-to-Peer-Netzwerken (P2P) ist es, Ressourcen wie Rechenleistungoder Speicherplatz miteinander zu teilen. Die teilnehmenden Hosts (Peers) konnenauf die Ressourcen anderer Peers zugreifen und ”bezahlen“ dafur, indem sie einenTeil ihrer Ressourcen im P2P-Netzwerk zur Verfugung stellen.

Der Unterschied zum klassischen Client-Server-Design besteht darin, dass ein Peersowohl Client als auch Server sein kann. Ein Peer agiert dabei als Client, wenn er aufRessourcen anderer Peers zugreift, und er agiert als Server, wenn er Ressourcen imNetzwerk bereitstellt.

Die klassischen Client-Server-Architekturen wie das DNS [31, 30] sind durch einenhierarchischen Aufbau mit zentralen Servern gekennzeichnet. P2P-Architekturen ver-zichten darauf und organisieren die Peers dezentral. Das P2P-Netzwerk entsteht da-durch, dass die Peers ”in irgendeiner Weise“ innerhalb des Internet zu einem virtuellenNetzwerk verbunden werden, in dem jeder Peer potenziell alle Aufgaben ubernehmenkann.

Daruber hinaus sind P2P-Systeme darauf ausgelegt, dass insbesondere auch Heiman-wender mit ihren privaten PC’s daran teilnehmen konnen. Da viele Heimanwenderjedoch nicht standig mit dem Internet verbunden sind, nehmen diese nicht permanentam P2P-Netzwerk teil, sondern nur dann, wenn sie auch mit dem Internet verbundensind. Schaltet der Heimanwender seinen PC ab, oder trennt er die Internetverbin-dung, so fallt der entsprechende Peer im P2P-Netzwerk aus. Daher verandert sich dieTopologie des P2P-Netzwerks fortwahrend.

3

2.2 Vor- und Nachteile von Peer-to-Peer-Systemen

2.2 Vor- und Nachteile von Peer-to-Peer-Systemen

Einer der Vorteile von P2P ist, dass zentrale Server durch die Dezentralisierung entfal-len. Dies ist insoweit ein Vorteil, da in Client-Server-Architekturen das Funktionierendes gesamten Systems hauptsachlich vom Betrieb des Servers abhangt. Kommt es andieser Stelle, dem so genannten single-point-of-failure, zu einem Fehler, so ist dasgesamte System nicht mehr verfugbar.

Eine weiterer entscheidender Vorteil von P2P-Systemen ist, dass durch zentrale Ser-ver bedingte Performanzprobleme entfallen. Den Flaschenhals (bottle neck) fur dieLeistung eines Client-Server-Systems stellt meistens der Server dar. Ist der Serveruberlastet, so ist meist das gesamte System nicht mehr verfugbar. Eine Uberlastungdes Servers kann z. B. dadurch entstehen, dass zu viele Clients gleichzeitig auf dievon ihm angebotenen Dienste zugreifen mochten. In P2P-Systemen wird einer sol-chen Uberlastung entgegengewirkt, da hier hier die Systemlast auf mehreren Peersverteilt werden kann.

Der großte Vorteil von P2P-Architekturen ist aber, dass sie, da sie ohne zentrale Ser-ver auskommen, besser skalierbar sind als herkommliche Client-Server-Architekturen,wodurch potenziell die Anzahl der Peers fast beliebig erhoht werden kann.

Ein Nachteil von P2P-Architekturen liegt darin, dass sich die Topologie des Netzwerksstandig verandert. Wird ein Peer vom P2P-Netzwerk getrennt, so sind damit dieRessourcen des ausgefallenen Peers nicht mehr ansprechbar. Da standig Peers vomNetzwerk getrennt werden, lassen sich in der Regel keine verlasslichen Aussagen uberdie Verfugbarkeit einer bestimmten Ressource treffen.

Hinzu kommt, dass die einzelnen Peers wegen der dezentralen Organisation und dersich standig verandernden Topologie des P2P-Netzwerks, in der Regel nicht alle an-deren Peers im Netzwerk kennen. Insbesondere liegt, bedingt durch die Dynamik,zu keinem Zeitpunkt ein vollstandiges Abbild des aktuellen Netzwerkzustandes vor.Wurde jeder Peer ein vollstandiges Abbild besitzen, so musste auch jeder Peer in-formiert werden, wenn sich der Netzwerkzustand andert. Das wiederum wurde abereinen sehr hohen Ressourcenverbrauch hervorrufen. Aus diesem Grund kennt jederPeer nur einen begrenzten Teil des Netzwerks, wodurch sich das Auffinden von Res-sourcen komplexer darstellt als in herkommlichen Client-Server-Architekturen.

Auf Grund dieser Problematik haben sich mit der Zeit unterschiedliche Losungs-ansatze zur Organisation der Peers sowie der Lokalisierung von Ressourcen heraus-gebildet. Im folgenden wird ein kurzer Uberblick uber diese gegeben. Einen solchen

4

2.3 Verschiedene Losungsansatze

Uberblick geben auch [4] und [7].


Das gemeinsame Problem aller P2P-Systeme ist die Lokalisierung von Ressourcen,das so genannte Lookup Problem. Dieses wird in [7] so formuliert: Gegeben sei einDatenelement X, das von einer dynamischen Teilmenge von Peers im System gespei-chert wird. Finde X.1

Im Laufe der Zeit entstanden unterschiedliche Ansatze zur Losung des Lookup Pro-blems. Neben hybriden P2P-Systemen, einer Mischform aus Client-Server und P2P,bei der die Peers bei der Ressourcensuche von einem zentralen Server abhangig sind,gibt es die echten P2P-Systeme. Charakteristisch fur echte P2P-Systeme ist, dasssie, zumindest auf physikalischer Ebene ohne zentrale Verzeichnisse arbeiten und einverteiltes Suchprotokoll implementieren.

2.3.1 Hybride P2P-Systeme

Hybride P2P-Systeme wie Napster [46] verzichten nicht vollstandig auf die Client-Server-Struktur. Sie fuhren die Suche nach Ressourcen mit Hilfe von zentralen Ver-zeichnissen durch, welche auf einem Server hinterlegt sind. Jeder Peer registriert dievon ihm bereitgestellten Ressourcen in diesem zentralen Verzeichnis. Sucht ein Peernun nach einer bestimmten Ressource, so erhalt er aus dem zentralen Verzeichnis dieInformation, welcher Peer diese zur Verfugung stellt. Der eigentliche Zugriff auf dieRessource erfolgt dann uber den fur P2P-Systeme charakteristischen, direkten Kon-takt zum entsprechenden Peer. Abbildung 2.1 stellt die Arbeitsweise von Napstergrafisch dar.

Diese Arbeitsweise birgt den Vorteil, dass sie die sonst in P2P-Systemen vorhandenenProbleme wie das Auffinden von Ressourcen und Routing von Suchen umgeht. Auchlasst sich zumindest eine verlassliche obere Schranke fur die Dauer einer Abfrageangeben, da man hinreichend Informationen uber das Netzwerk und den Ablauf derSuche besitzt.Der Nachteil dieser hybriden Architektur besteht darin, dass sie nicht so gut skalierbarist wie echte P2P-Systeme. Alle Peers greifen bei der Suche nach und der Registrie-rung von Ressourcen auf einen zentralen Server zu, wobei die maximale Peeranzahl

1Given a data item X stored at some dynamic set of nodes in the system, find it.

5


Napster Server

Peer BPeer A

benutze X

registriere X suche X

X wird von Aangeboten

Abbildung 2.1: Arbeitsweise von Napster

von der Leistungsfahigkeit des Servers abhangt. Wenn der Server uberlastet ist, dannkonnen keine Ressourcen mehr gefunden werden. Ein weiterer Nachteil ist, dass auchein zentrales Verzeichnis immer einen single-point-of-failure darstellt, wodurch dasSystem anfalliger fur Angriffe wie DoS-Attacken wird.2

2.3.2 Echte P2P-Systeme

Bei den echten P2P-Systemen existieren wiederum zwei unterschiedliche Losungs-ansatze, die unstrukturierten und die strukturierten. Sie unterscheiden sich dadurch,dass unstrukturierte Ansatze auf physikalischer wie auf konzeptioneller Ebene aufzentrale Verzeichnisse verzichten und die Peers einfach in ”irgendeiner Weise“ mit-einander verbunden sind, wobei strukturierte Ansatze auf konzeptioneller Ebene sehr-wohl mit zentralen Verzeichnissen arbeiten und die Peers in einer ”bestimmten Weise“miteinander verbinden.

Eine Sonderstellung unter den echten P2P-Netzwerken nehmen so genannte Super-Peer-Netzwerke [47] ein. Diese sind eine Mischform aus unstrukturierten und hybriden

2Als DoS-Angriff (Denial of Service) bezeichnet man einen Angriff auf einen Server, mit dem Ziel

einen oder mehrere seiner Dienste arbeitsunfahig zu machen. In der Regel geschieht das durch

Uberlastung, indem eine großere Anzahl Anfragen gestellt wird, als der Server gleichzeitig bear-

beiten kann, woraufhin ein Dienst eingestellt wird oder regulare Anfragen so langsam beantwortet

werden, dass diese abgebrochen werden.

6


P2P-Systemen. Sie sind der Versuch, die Nachteile von unstrukturierten Ansatzenabzumildern.

Unstrukturierte Ansatze

Unstrukturierte P2P-Ansatze wie Gnutella [15] oder Freenet [10] verwenden keinebestimmte Ordnung fur die Peers. Bei dieser Art der Organisation kennt jeder Peereine gewisse Anzahl von anderen Peers (Nachbarn). Insbesondere ist es so, dass keinPeer alle Peers im Netzwerk kennt, da das Auffinden sowie das Aktualisieren allerPeers das Netzwerk mit hoher Wahrscheinlichkeit auslasten wurde.Betrachtet man nun das P2P-Netzwerk als Graphen, so ergeben sich zwei Moglichkei-ten Ressourcen und andere Peers in einem P2P-Netzwerk aufzufinden: Tiefensucheund Breitensuche. Bei der Tiefensuche wird ein Pfad im Graphen bis zur maximalenPfadlange abgesucht. Hierzu wird die Suche von Peer zu Peer weitergeleitet. Bei jederWeiterleitung wahlt der Peer, der gerade die Nachricht erhalten hat, einen Peer unterden mit ihm verbundenen Peers aus, und leitet ihm die erhaltene Nachricht weiter.Hierdurch werden bei einer Suchtiefe r genau r Peers erreicht. Bei der Breitensu-che leiten die Peers eine erhaltene Nachricht jeweils an alle mit ihnen verbundenenPeers weiter. Hierdurch werden bei einer Suchtiefe r alle Peers erreicht, die vom Aus-gangspunkt der Suche innerhalb des Radius r liegen, d. h. die Peers, die maximal rWeiterleitungen entfernt sind. Bei beiden Arten der Suche wird jede fur die Sucheversandte Nachricht wird mit einer time-to-live (TTL) versehen. Diese gibt an, wieoft eine Nachricht weitergeleitet werden darf und bestimmt somit die Suchtiefe bzw.den Radius der Suche. Bei jeder Weiterleitung wird diese um eins verringert. GiltTTL = 0, so wird die Nachricht nicht mehr weitergeleitet.

Gnutella verfolgt den Ansatz der Breitensuche. Mit ihr ist es moglich, mit einer Sucheeine große Anzahl anderer Peers zu erreichen. Wenn ein Peer z. B. mit durchschnittlichC = 5 Peers verbunden ist, eine eingehende Nachricht also an 4 Peers weitergeleitetwird, so werden innerhalb einer TTL = 7 maximal 109225 verschiedene Peers erreicht.

TTL∑i=0

C ∗ (C − 1)i = 109225

Ein Gnutella Peer unterscheidet bei der Breitensuche zwischen dem Auffinden ande-rer bzw. neuer Peers sowie der Suche nach Ressourcen. Dementsprechend sieht dasGnutella Protokoll auch zwei unterschiedliche Nachrichten Ping und Query vor. Ta-belle 2.1 gibt einen Uberblick uber die Nachrichten des Gnutella Protokolls.

7


Das Auffinden neuer Peers durch einen Peer x erfolgt durch Versenden der mit einerTTL versehenen Nachricht Ping an alle Peers, die x bereits bekannt sind. Erhalt nunPeer y eine Ping-Nachricht von x, so sendet er an Peer x die Antwort Pong. DieseNachricht wird dabei uber den Weg, uber den sie gekommen ist, zuruckgeroutet.Sofern die TTL der erhaltenen Ping-Nachricht großer als Null ist, verringert y dieseum Eins und leitet dann die Ping-Nachricht wiederum an alle ihm bekannten Peersweiter.

Da es bei diesem Vorgehen zu Zyklen kommen kann, erhalt jede Nachricht zusatzlicheinen Identifier. Anhand dieses Identifiers konnen Peers schon einmal erhaltene undweitergeleitete Nachrichten erkennen. Somit konnen Zyklen vermieden werden, dabekannte Nachrichten nicht mehr weitergeleitet werden.

Nachricht Beschreibung

Ping Suche nach anderen Peers

Pong Antwort auf Ping

Query Suche nach einer Ressource

QueryHit Antwort auf Query

Push Download von Peers hinter einer Firewall

Tabelle 2.1: Das Gnutella Protokoll

Bei der Suche nach einer bestimmten Ressource, wird eine dem Auffinden neuerNachbarn analoge Verfahrensweise angewandt. Der suchende Peer sendet die Nach-richt Query an alle ihm bekannten Peers. Diese leiten die Suchanfrage dann wiederuman alle ihnen bekannten Peers weiter, bis die TTL der Suchanfrage abgelaufen ist.

Wird dabei innerhalb des Radius TTL kein Peer erreicht, der die gesuchte Ressourcezur Verfugung stellt, so ist die Suche erfolglos. Existiert jedoch ein Peer, der dieRessource bereitstellt, innerhalb des durch TTL festgelegten Radius, so sendet dieserdie Nachricht QueryHit an den Initiator der Suche zuruck. Die Antwort wird dabeiuber die gleichen Peers geroutet, uber die auch die Query-Nachricht gesendet wurde.

Abbildung 2.2 zeigt den Ablauf einer Suche bei der Peer A nach Ressource X sucht.Im ersten Schritt sendet A die Nachricht Query an die Peers B und E. Diese wie-derum leiten die Suche im zweiten Schritt an die Peers C, B, E und F weiter. DaB und E die Suche schon einmal weitergeleitet haben, wird diese dort nicht nocheinmal weitergeleitet. In nachsten Schritt leitet Peer F die Suche an Peer D und C

8


A B

C

D

E

F

Query X

X

X

G

GET X

1 Hop

2 Hops

3 Hops

G‘s QueryHit

D‘s QueryHit

Abbildung 2.2: Suchen mit Gnutella

weiter, wahrend C die Suche an F und G weiterleitet. Da G und D die Ressource Xanbieten, senden sie jeweils die Nachricht QueryHit zuruck.

Ein typischer Wert fur die von den meisten Gnutella Clients verwendete time-to-liveist TTL = 7. Diese wurde gewahlt, da Gnutella Netzwerke die Eigenschaften vonsmall-world Graphen besitzen, weshalb eine Suche mit hoher Wahrscheinlichkeit in-nerhalb dieses Radius erfolgreich verlauft [29, 22].

Der Vorteil von unstrukturierten P2P-Architekturen wie Gnutella ist, dass sie bes-ser skalieren als hybride Systeme und keinen single-point-of-failure mehr besitzen.Nachteile bestehen jedoch u. a. darin, dass durch die bei Gnutella verwendete Brei-tensuche viele bzw. auch unnotige Nachrichten versendet werden, was große MengenNetzwerkbandbreite belegt [40]. Im Beispiel von Abbildung 2.2 leitet z. B. Peer Bdie Suche nach Ressource X in dem Moment an Peer E weiter, in dem E die gleicheSuche umgekehrt an B weiterleitet. Neben dem hohen Bandbreitenverbrauch bestehtein weiterer Nachteil darin, dass durch die willkurliche Anordnung der Peers keineeffiziente Lastbalancierung (load-balancing) zwischen den Peers erfolgt.

Super-Peer-Netzwerke

Super-Peer-Netzwerke [47] sind eine Mischform zwischen unstrukturierten und hy-briden P2P-Systemen. Das Ziel von Super-Peer-Architekturen ist es, den sehr hohen

9


Bandbreitenverbrauch, der z. B. durch die von Gnutella verwendete Breitensuche ent-steht, zu senken. Dies wird durch die Unterteilung des Netzwerks in Cluster erreicht.

In einem Cluster ist die Arbeitsweise ahnlich der von Napster. So gibt es innerhalb ei-nes Clusters zwei unterschiedliche Arten von Peers: Super-Peers und Clients. Wie beiNapster agieren die Super-Peers innerhalb eines Clusters fur die Clients als zentraleServer. Sie besitzen Informationen uber alle im Cluster bereitgestellten Ressourcen.Die Clients registrieren die von ihnen bereitgestellten Ressourcen bei den Super-Peers. Untereinander sind die Cluster durch ihre jeweiligen Super-Peers miteinanderverbunden. Die Anzahl der Peers im Cluster, inklusive der Super-Peers, wird mit clus-ter size bezeichnet.3 Abbildung 2.3 zeigt den Aufbau eines Super-Peer-Netzwerks aus4 Clustern mit ihren Super-Peers SP1 bis SP4.

SP1

SP2

SP4

SP3

Abbildung 2.3: Aufbau von Super-Peer-Netzwerken

Sucht ein Client eine Ressource, so stellt er seine Anfrage an den Super-Peer des eige-nen Clusters. Dieser uberpruft zunachst, ob innerhalb des Clusters ein Peer existiert,der die Ressource bereitstellt. Ist dies der Fall, so sendet er eine entsprechende Ant-wort an den suchenden Peer. Erst wenn kein solcher Peer existiert, leitet der Super-Peer die Suche an die mit ihm verbundenen Super-Peers weiter. Diese uberprufendann wiederum, ob in ihrem Cluster ein Peer existiert, der die gesuchte Ressource

3Das P2P-Netzwerk Gnutella stellt ein”degeneriertes“ Super-Peer-Netzwerk mit cluster size = 1

dar.

10


bereitstellt. Wird die gesuchte Ressource nun gefunden, so wird eine entsprechen-de Antwort an den fragenden Super-Peer gesendet, der dann den suchenden Peerin seinem Cluster verstandigt. Kann die Ressource wiederum nicht gefunden wer-den, so leiten die Super-Peers die Suche erneut an andere Super-Peers in anderenClustern weiter. Ein Beispiel fur ein auf einer Super-Peer-Architektur beruhendesP2P-Netzwerk ist KaZaA [32].

Super-Peer-Netzwerke sind durch die Verwendung von Client-Server innerhalb derCluster jedoch keine echten P2P-Netzwerke im eigentlichen Sinne. Nicht zuletzt er-geben sich innerhalb der Cluster wieder die fur Client-Server-Architekturen typischenProbleme bezuglich Skalierbarbeit und Ausfallsicherheit.4

Strukturierte Ansatze

Im Gegensatz zu unstrukturierten und Super-Peer-Architekturen versuchen die struk-turierten Ansatze, die Anzahl der Nachrichten und damit die belegte Bandbreite da-durch zu verringern, dass sie versuchen Ressourcen ”effizient“ zu lokalisieren. Umeffizient bzw. strukturiert suchen zu konnen, werden die Ressourcen zunachst in ent-sprechenden Index-Strukturen erfasst. Hierzu bedienen sich die einzelnen Ansatzeunterschiedlicher Indexing-Mechanismen.

Eine Moglichkeit der Indizierung sind Skip-Listen bzw. Skip-Graphen [5], wie sie vonP-Grid [2] oder SkipNet [16] verwendet werden. Kern dieser Ansatze ist eine uber diePeers verteilte sortierte Liste, in der alle bereitgestellten Ressourcen erfasst sind. Furjede Ressource wird in dieser Liste ein String hinterlegt, der die Ressource beschreibt.Die so angelegte Liste wird mittels eines Suchbaumes indiziert, in dem sich das Prafixder indizierten Strings mit zunehmender Suchtiefe verlangert.

Ein anderer verbreiteter Ansatz zur Indizierung sind verteilte Hashtabellen (distribu-ted hashtables - DHTs), die von etlichen Projekten [12, 38, 23, 49] verwendet werden.In einer Hashtabelle werden, wie in einem Array, Werte gespeichert. Der Unterschiedzum Array besteht darin, dass die Werte nicht uber einen Index referenziert werden,sondern durch einen Schlussel, der mit Hilfe einer Hashfunktion aus dem Wert selbstberechnet wird. Als Werte selbst kann, je nach Implementierung des P2P-Systems,wiederum die Ressource selbst, oder eine Beschreibung, wie auf die Ressource zuge-griffen werden kann, abgelegt werden.

4vgl.: Abschnitt 2.3.1

11


Im Fall von Dateien kann also z. B. der Schlussel festgelegt werden, indem mit derHashfunktion der Hashwert des Dateinamens berechnet wird. Der zum Hashwert desDateinamens gespeicherte Wert kann dann sowohl die Datei selbst sein, als auch eineBeschreibung des Peers, der die Datei bereithalt. Im Fall von Ressourcen wie CPU-Zeit, welche nicht von einem Peer zum anderen ubertragen werden kann, muss alsWert jedoch zwingend eine Beschreibung des Peers gespeichert werden, welcher dieCPU-Zeit bereitstellt.

Die Idee von verteilten Hashtabellen (DHTs) ist es nun, alle in einem P2P-Netzwerkbereitgestellten Ressourcen logisch in einer einzigen Hashtabelle zu erfassen, diesejedoch physikalisch uber die Peers zu verteilen. Dabei wird zunachst jedem Peer xein eindeutiges Teilintervall [ix..jx] des Wertebereichs der Hashfunktion zugewiesen.Ein Peer speichert nun die Werte fur alle Schlussel key fur die gilt key ∈[ix..jx].

Die Art der Verteilung der DHT, das Auffinden des fur einen bestimmten Schlusselzustandigen Peers, sowie die dazu verwendeten Verteil- und Routingalgorithmen sinddabei jedoch sehr unterschiedlich. So benutzen z. B. die P2P-Systeme Pastry [39],Tapestry [18] und Kademlia [27] auf Baumen basierende Algorithmen, wahrend Vi-ceroy [26] auf Butterfly-Netzwerken [25] beruht. CAN [36] hingegen implementierteinen mehrdimensionalen Routingalgorithmus.

CAN (Content-Addressable-Network) benutzt eine mehrdimensionale Datenstrukturund unterteilt den Wertebereich fur die Schlussel in den d -dimensionalen Koordi-natenraum eines d -Torus. Jeder Peer speichert Routinginformationen uber seine di-rekten Nachbarn im Koordinatenraum. Zwei Peers sind dabei benachbart, wenn ihreKoordinatenbereiche entlang d -1 Dimensionen uberlappen und in einer Dimensionaneinander grenzen. In einem d -dimensionalen Raum besitzt somit jeder Peer O(d)Nachbarn. Bei der Suche wird ein greedy-Algorithmus angewandt: Liegt der gesuchteSchlussel nicht in der Koordinatenzone eines Peers, so leitet er die Suche an denjeni-gen seiner Nachbarn weiter, dessen Koordinatenzone am nachsten an der gesuchtenliegt. Ist der d -dimensionale Raum in n Teile aufgeteilt und besitzt jeder Peer O(d)Nachbarn, so wird eine Suche von O(dn1/d) Peers weitergeleitet, bis sie ihr Ziel er-reicht. Abbildung 2.4 zeigt ein CAN mit 2-dimensionalem [0,1]×[0,1] Koordinaten-raum. Zur Vereinfachung wurde der entsprechende 2-Torus in die Ebene projiziert.Die Pfeile zeigen einen moglichen Suchpfad fur eine von Peer 8 gestartete Suche nachSchlussel s=(0.6,0.6), welcher im Zustandigkeitsbereich von Peer 5 liegt.

12

2.4 Fazit

5(0.5,0.75,0.5,0.75)

(0.5,0.75,0.75,1) (0.75,1,0.75,1)

(0.75,1,0.5,0.75)

(0,0.25,0.75,1)

(0,0.25,0.5,0.75)

8(0,0.25,0,0.25)

4(0.25,0.5,0,0.25)

9(0.5,0.75,0,0.25)

3 (0.75,1,0.25,0.5)

(0.75,1,0,0.25)

6

7

(0,1) (1,1)

(1,0)(0,0)

2(0.25,0.5,0.5,0.75)

1(0.25,0.5,0.25,0.5)

Abbildung 2.4: 2-dimensionales CAN

2.4 Fazit

Unter den verschiedenen P2P-Ansatzen ermoglichen es strukturierte Ansatze als ein-zige, verlassliche Aussagen uber die tatsachliche Verfugbarkeit einer Ressource zutreffen, da der Peer, der fur den Schlussel, der die gesuchte Ressource beschreibt,verantwortlich ist, auf jeden Fall gefunden wird. Insbesondere ist es jedoch moglich,Angaben daruber zu machen, uber wie viele Peers eine Suche weitergeleitet werdenmuss, bis die gesuchte Ressource gefunden wird. So wird in CAN eine Suche vonO(dn1/d) Peers weitergeleitet bis sie ihr Ziel erreicht, wahrend Architekturen wieKademlia erreichen, dass in Netzwerken mit n Peers eine Suche mit hoher Wahr-scheinlichkeit O(log n) mal weitergeleitet werden muss.5

Skip-Listen basierte Algorithmen haben gegenuber DHT basierten Ansatzen den Vor-teil, dass die Sortierung der Strings, die die Ressourcen beschreiben, nicht durch eineHashfunktion verandert wird. So werden einander ahnliche Ressourcen, also der Res-sourcen deren Beschreibung mit dem gleichen Prafix beginnt, von einander benach-barten Peers verwaltet, so dass eine Ahnlichkeitssuchen bzw. Range-Queries fur Res-sourcen moglich sind. DHT-Ansatze wiederum haben gerade durch die Verwendungder Hashfunktion den Vorteil, dass sie eine bessere Lastbalancierung (load-balancing)als Skip-Listen basierte Algorithmen unter den Peers herstellen, da die Hashfunktiondie Zustandigkeit fur die Ressourcen besser auf die Peers verteilt [6].6

5mit d = (log2 n)/2 ist auch bei CAN eine Pfadlange von O(log n) moglich6vgl.: Abschnitt 3.4

13

2.4 Fazit

Eine Gemeinsamkeit den meisten strukturierten Ansatzen ist jedoch, dass sie nichtimmer sehr intuitiv nachzuvollziehen sind und recht komplizierte Routingalgorith-men implementieren. Chord ist neben den bereits erwahnten Ansatzen ein weitererstrukturierter DHT-Ansatz. Wie z. B. Kademlia bietet Chord dabei auch ein Routingin O(log n) Schritten, ist aber wesentlich intuitiver nachvollziehbar.

14

3 Der Chord-Algorithmus

Chord ist ein strukturierter, auf verteilten Hashtabellen (DHT) beruhender P2P-Ansatz. Unter den DHT-Ansatzen ist Chord einer der intuitivsten. Zur Verteilungder Schlussel auf die Peers nutzt Chord consistent hashing [21]. Chord stellt nur eineeinzige Funktion zur Verfugung: die effiziente Lokalisierung von Schlusseln. Dabei fin-det Chord aus n Peers den fur einen Schlussel zustandigen Peer in O(log n) Schritten.Hierbei benotigt ein Peer Informationen uber O(log n) andere Peers.

3.1 Das Chord-Systemmodell

Die Grundidee von Chord lasst sich folgendermaßen veranschaulichen: Die Peers wer-den in einer Ringstruktur, dem Chord-Ring organisiert. Hierzu erhalt jeder Peer xeine eindeutige m-bit lange IDx (ChordID). Dafur wird zunachst mit Hilfe einesHash-Algorithmus wie SHA-1 [1] der Hashwert hx der IP-Adresse des Peers x be-rechnet. Die so gebildeten Hashwerte hx sind jedoch moglicherweise langer als m-bitund werden deshalb auf einen Ring IDx = hx mod 2m abgebildet. Der durch dieseAbbildung entstehende Ring heißt Chord-Ring. Der dabei verwendete Parameter mheißt Exponent des Chord-Rings. Er bestimmt die maximal mogliche Anzahl PeersN = 2m.

Die ID des Peers x (x.ID) bestimmt, an welcher Stelle des Chord-Rings sich x befin-det. Die Nachbarn, d.h. der Vorganger (predecessor) und der Nachfolger (successor)von x, ergeben sich aus der auf den IDs definierten Ordnung. Der letzte Peer y furden gilt y.ID < x.ID ist der Vorganger von x (x.predecessor). Der Nachfolger z vonx (x.successor) ist der erste Peer fur den gilt z.ID > x.ID.

Die im DHT-Konzept vorgesehene Verteilung der Schlussel erfolgt bei Chord so, dassder Peer fur den Schlussel key zustandig ist, der key als erster auf dem Chord-Ringfolgt. Schlussel key wird also dem ersten Peer x zugeordnet, fur den gilt: x.ID ≥ key.Der so bestimmte Peer x wird successor(key) genannt. Sei y = x.predecessor, danngilt:

15

3.2 Das Auffinden von Schlusseln im Chord-Ring

∀key ∈ (y.ID, x.ID] : successor(key) = x

Abbildung 3.1 zeigt einen Chord-Ring mit dem Exponenten m = 6 und 10 Peers, die6 Schlussel verwalten. So ist z. B. der Schlussel S34 Peer P35 zugeordnet, da P35der erste Peer ist, der S34 folgt.

P1

P14

P22

P31

P35

P40

P48

P57

P62S12

S34

S24

S28

S54

S57

P53

Abbildung 3.1: Chord-Ring, 10 Peers und 6 Keys


Die einzige Funktion, die Chord nach Außen bereitstellt, ist die Funktion lookup(key).Diese Funktion findet den fur den Schlussel key zustandigen Peer. Sucht Peer x nachSchlussel key, so wird der Suchprozess durch den Aufruf der Funktion x.lookup(key)gestartet. Im folgenden wird der genaue Ablauf der Suche beschrieben.

3.2.1 Einfache Suche

Bei der einfachen Suche nach einem Schlussel key, wie sie von Algorithmus 1 durch-gefuhrt wird, uberpruft Peer x zunachst, ob sein Nachfolger der verantwortliche Peerist. Ist dies der Fall, so ist der Suchprozess beendet, das Ergebnis ist x.lookup(key) =x. Ist der Nachfolger von x jedoch nicht selbst verantwortlich, so fragt x seinen Nach-folger y = x.successor, indem er dessen Suchfunktion y.lookup(key) aufruft. Diesgeschieht solange, bis der fur key zustandige Peer gefunden wurde.

16


In einem Chord-Ring mit n Peers betragt die Pfadlange der Suche somit O(n), wobeidie Pfadlange angibt, wie oft der Lookup an einen anderen Peer weitergeleitet wurde.Abbildung 3.2 stellt den Verlauf der Suche dar, wenn Peer P14 den Schlussel 58 suchtund der Lookup jeweils an den Nachfolger weitergeleitet wird. Insgesamt wird dieSuche 7 mal weitergeleitet.

Algorithmus 1 Einfache Suchex.lookup(key)

if key ∈ (x.ID,successor.ID]return successor;

elsereturn successor.lookup(key);

Diese Art der Suche ist zwar intuitiv, jedoch nicht sehr effizient. Da die Pfadlangefur die Suche linear zu der Anzahl der Peers im Chord-Ring steigt, steigt auch dieAnzahl der Nachrichten linear mit der Anzahl der Peers an, so dass dieses Vorgehendie Skalierbarkeit eines Chord-Rings stark einschrankt.

P1

P14

P22

P31

P35

P40

P48

P57

P62S12

S34

S24

S28

S54

S57

lookup(58)

P53

Abbildung 3.2: Einfache Suche

17


3.2.2 Skalierbare Suche mit Fingertabellen

Eine Moglichkeit, effizienter als linear zur Anzahl der Peers zu suchen, besteht darin,Peers beim Weiterleiten einer Suche zu uberspringen und so mit einer Weiterleitunggroßere Stecken zuruckzulegen. Hierzu muss ein Peer jedoch mehr Peers als nur seinendirekten Nachfolger kennen bzw. mehr uber die Verteilung der Peers im Chord-Ringwissen. Bei der skalierbaren Suche verwaltet deshalb jeder Peer eine Tabelle mit In-formationen uber O(log N ) andere Peers im Chord-Ring. Die Eintrage dieser Tabelleheißen Finger, die Tabelle selbst heißt Fingertabelle. In Chord umfasst die Große derFingertabelle m Eintrage, wobei m der Exponent des Chord-Rings ist.

Die Finger dienen bei der skalierbaren Suche als Sprungmarken zu anderen Peers imChord-Ring. Mit ihrer Hilfe kann ein Lookup nun uber großere Distanzen weiterge-leitet werden.

Der i -te Finger von x ist der Peer, der fur den Schlussel key verantwortlich ist, welcherum 2i−1 großer ist als der großte Schlussel, fur den x verantwortlich ist. Der großteSchlussel, fur den x verantwortlich ist, ist x.ID. Somit gilt fur die Fingertabelle vonPeer x :

x.finger[i] = successor(keyi) : keyi = x.ID + 2i−1, i ∈ [0,m]

Insbesondere gilt, dass der erste Finger von x der Nachfolger von x ist.

x.finger[0] = x.successor

Mit dieser Strategie legt ein Lookup mit jeder Weiterleitung mindestens die Halfteder Distanz zum gesuchten Peer zuruck. Abbildung 3.3 zeigt die Fingertabelle vonPeer P14 sowie die Lage der fur die Finger berechneten Schlussel. Der entsprechendeFinger ist immer der folgende Peer. So ist z. B. der fur Finger 6 berechnete SchlusselP14 + 26−1 = 46 und P48 der entsprechende Finger.

Bei der skalierbaren Suche kommen die Methoden von Algorithmus 2 zum Einsatz.Ist der Nachfolger von Peer x nicht zustandig, so wahlt er aus der Fingertabelle denje-nigen Finger aus (closest preceeding node(key)), der dem gesuchten Schlussel key amnachsten ist und im Chord-Ring noch vor key liegt. An diesen leitet x den Lookupweiter. Mit jeder Weiterleitung wird so die Distanz zum gesuchten Peer mindestenshalbiert. Hierdurch entspricht dies einer binaren Suche, welche bei einer Menge von nEingabewerten, innerhalb von O(log n) Schritten beendet wird. Somit wird erreicht,

18


P1

P14

P22

P31

P35

P40

P48

P57

P62 Finger Tabelle

P48P14+32

P31P14+16

P22P14+8

P22P14+4

P22P14+2

P22P14+1

+1

+2

+4

+8

+16

+32

P53

Abbildung 3.3: Fingertabelle von Peer 14

Algorithmus 2 Skalierbare Suchex.lookup(key)

if key ∈ (x.ID,successor.ID]return successor;

elsey = x.closest preceding node(key);return y.lookup(key);

x.closest preceding node(key)

for i = m downto 1if finger[i].ID ∈ (x.ID, key)return finger[i];

return x;

19

3.3 Der Chord-Peer

dass ein Lookup in einem Chord-Ring mit n Peers nur noch O(log n) mal weiterge-leitet werden muss.

Abbildung 3.4 zeigt den Verlauf einer Suche mit Hilfe der Fingertabelle. Sucht P14nach Schlussel 58, so ist P48 der Peer in der Fingertabelle von P14, der Schlussel58 am nachsten ist, weshalb dieser die Suche als nachstes erhalt. Aus der Fingerta-belle von P48 ist P57 dem gesuchten Schlussel am nachsten, so dass P48 an P57weiterleitet. Da der Nachfolger von P57 der zustandige Peer ist, wird die Suche er-folgreich beendet. Insgesamt wurde die Suche 2 mal weitergeleitet, wahrend sie beider einfachen Suche 7 mal weitergeleitet wurde.

Finger Tabelle

P1

P14

P22

P31

P35

P40

P48

P57

P62 Finger Tabelle

P48P14+32

P31P14+16

P22P14+8

P22P14+4

P22P14+2

P22P14+1

P14+32P48+8

P53lookup(58)

P22P48+32

P1P48+16

P57P48+8

P53P48+4

P53P48+2

P22P48+1

Abbildung 3.4: Suche mit Hilfe der Fingertabelle

3.3 Der Chord-Peer

P2P-Netzwerke wie Chord sind darauf ausgelegt, dass standig Peers hinzukommenoder ausfallen konnen. Da sich dabei die Topologie des Netzwerkes andert, imple-mentieren die Peers Algorithmen, die die Integration neuer Peers ermoglichen oderdie ”Reparatur“ des Chord-Rings und der Fingertabellen vornehmen, wenn Peersausfallen. Zusammen bilden diese Algorithmen das Chord-Stabilisierungsprotokoll.

20

3.3 Der Chord-Peer

3.3.1 Die Chord-Stabilisierungsalgorithmen

Die Algorithmen des Chord-Stabilisierungsprotokolls werden von jedem Peer in peri-odischen Zeitabstanden aufgerufen. Der Zeitabstand zwischen zwei Durchfuhrungendes Stabilisierungsprotokolls ist das Stabilisierungsintervall. Die Ausfuhrung der Sta-bilisierungsalgorithmen findet im Hintergrund statt. Die Algorithmen des Stabilisie-rungsprotokolls sind:

• x.stabilize(): Pruft, ob der Vorganger y’ des Nachfolgers y von Peer x zwi-schen x selbst und seinem aktuellen Nachfolger y liegt. Ist der Vorganger desNachfolgers nicht der fragende Peer selbst (y′ 6= x), und liegt y’ zwischen x undy so andert x seinen Nachfolger dementsprechend ab (x.successor = y′).1

• y.getPredecessor(): Wird von x wahrend x.stabilize() aufgerufen, wobei yder Nachfolger von x ist. Die Funktion liefert den Vorganger y’ des Nachfolgersy.predecessor.

• y.notify(x): Wird von x wahrend x.stabilize() aufgerufen und kundigt Peer ydie Existenz von x an. Liegt x zwischen dem aktuellen Vorganger y’ von y undy selbst, so wird x der neue Vorganger von y (y.predecessor = x).2

• x.checkPredecessor(): Testet ob x.predecessor ausgefallen ist.3

• x.fix fingers(): Aktualisiert die Eintrage der Fingertabelle.4

Die Arbeitsweise dieser Funktionen wird im verbleibenden Teil dieses Abschnittsanhand von Beispielen erlautert. So dienen die Funktionen stabilize() sowie get-bzw. check Predecessor() und notify() der Erhaltung und Wiederherstellung der kor-rekten Vorganger-Nachfolger-Beziehungen wenn Peers hinzukommen oder ausfallen,wahrend fix fingers() die Fingertabelle aktuell halt.

3.3.2 Erzeugen eines Chord-Rings und Integration von Peers

Dieser Abschnitt erlautert das Erzeugen eines neuen Chord-Rings mit zunachst nureinem Peer. Im Anschluss daran wird das Hinzufugen weiterer Peers, sowie die Rolle,die das Stabilisierungsprotokoll dabei spielt, veranschaulicht.

1siehe Algorithmus 52siehe Algorithmus 53siehe Algorithmus 64siehe Algorithmus 7

21

3.3 Der Chord-Peer

Erzeugen des Chord-Rings

Soll ein neuer Chord-Ring erzeugt werden, so geschieht dies mit Hilfe der Funktioncreate(). Ruft ein Peer x diese Funktion auf, so wird damit ein neuer Chord-Ring,der nur aus Peer x besteht, erzeugt. In diesem Fall ist x fur alle Schlussel zustandig,dementsprechend ist x sein eigener Nachfolger (x.successor = x).

Algorithmus 3 create()-Funktionx.create

successor = x;predecessor = null;

Integration weiterer Peers

Zur Integration eines Peers x in einen bestehenden Chord-Ring wird die Funktionjoin() benutzt. Hierbei muss Peer x bereits ein beliebiger Teilnehmer v des Ringsbekannt sein.

Algorithmus 4 join()-Funktionx.join(v)

predecessor = null;successor = v.lookup(x.ID);

In Abbildung 3.5 werden die Phasen der Integration eines Peers P25 in einen beste-henden Chord-Ring gezeigt. Peer P25 belegt dabei den Platz zwischen den Peers P31und P22. Zunachst erfragt P25 den Exponenten des Chord-Rings von einem beliebi-gen ihm bekannten Peer v des Chord-Rings. Danach ermittelt P25 seine eigene ID(P25.ID = 25), indem er diese aus seiner IP-Adresse mittels der Hashfunktion unddem Exponenten bestimmt.5 Die ID von P25 gibt nun den Platz vor, welchen P25spater im Chord-Ring belegt.Nachdem Peer P25 seine ID bestimmt hat, ermittelt er seinen Nachfolger. Dies ge-schieht, indem P25 den Peer bestimmt, der fur den Schlussel key = 25 zustandigist. Hierzu benotigt er nun Peer v, dessen Lookup-Funktion dazu benutzt wird, PeerP31 = v.lookup(25) zu finden. Der so ermittelte Peer P31 ist der Nachfolger von P25,weshalb P25 den Zeiger P25.successor = P31 setzt (Abbildung 3.5b). Die Peers P25,P31 und P22 haben nun die folgenden Zustande:

5vgl.: Abschnitt 3.1

22

3.3 Der Chord-Peer

Algorithmus 5 stabilize() und notify()x.stabilize()

s = successor.get predecessor;if s ∈ (x.ID, successor.ID) then

successor = s;successor.notify(x);

x.notify(y)

if predecessor == null or y.ID ∈ (predecessor.ID, x.ID) thenpredecessor = y;

P25.successor = P31 P25.predecessor = nullP31.successor P31.predecessor = P22P22.successor = P31 P22.predecessor

Nachdem P25 seinen Nachfolger P31 ermittelt hat, teilt er diesem mit, dass er an-nimmt, dessen neuer Vorganger zu sein. Dies geschieht durch Aufruf der Notify-Funktion P31.notify(P25). Peer P31 erhalt diese Notify-Nachricht und pruft nun, obP25 wirklich zwischen ihm und seinem aktuellen Vorganger P22 liegt und somit alsneuer Vorganger ubernommen werden kann (P25.ID ∈ (P22.ID, P31.ID)). Ist diesder Fall, so andert P31 seinen Vorganger auf P31.predecessor = P25 ab (Abbildung3.5c). Die Peers P25, P31 und P22 haben nun die folgenden Zustande:


Zum jetzigen Zeitpunkt besitzen Peer P25 und Peer P22 noch den gleichen Nachfol-ger Peer P31. Damit die Integritat des Chord-Rings wiederhergestellt wird und allePeers auf den richtigen Nachfolger verweisen, muss P22 seinen Nachfolger auf denneu hinzugekommenen Peer P25 abandern.Dies geschieht bei der nachsten Ausfuhrung des Stabilisierungsprotokolls durch P22.Hierbei fuhrt P22 die Funktion P22.stabilize() aus. Dabei fragt P22 den Vorgangerseines aktuellen Nachfolgers P31 durch P31.getPredecessor() ab. Hierdurch erhaltP22 die Information, dass Peer P25 der neue Vorganger von P31 ist. Jetzt pruft P22,ob P25 tatsachlich zwischen ihm und seinem aktuellen Nachfolger P31 liegt und somitals neuer Nachfolger ubernommen werden kann (P25.ID ∈ (P22.ID, P31.ID)). Ist

23

3.3 Der Chord-Peer

dies der Fall, so setzt P22 seinen Nachfolger auf P22.successor = P25 (Abbildung3.5d). Die Peers P25, P31 und P22 haben nun die folgenden Zustande:


Zum Abschluss der Stabilisierung ruft P22 die Funktion notify() auf. Da er gera-de seinen Nachfolger auf P25 abgeandert hat, lautet der entsprechende Aufruf alsoP25.notify(P22). Da P25 bis zu diesem Zeitpunkt noch keinen Vorganger besitzt,setzt P25 seinen Vorganger auf P25.predecessor = P22 (Abbildung 3.5e). Die PeersP25, P31 und P22 haben nun die folgenden Zustande:

P25.successor = P31 P25.predecessor = P22P31.successor P31.predecessor = P25P22.successor = P25 P22.predecessor

P1

P14

P35

P40

P48

P57

P62

P53

P22

P31

(a)

P1

P14

P35

P40

P48

P57

P62

P53

P22

P31

P25

(b)

P1

P14

P35

P40

P48

P57

P62

P53

P22

P31

P25

(c)

P1

P14

P35

P40

P48

P57

P62

P53

P22

P31

P25

(d)

P1

P14

P35

P40

P48

P57

P62

P53

P22

P31

P25

(e)

Abbildung 3.5: Integration eines neuen Peers

Hiermit verweisen nun alle Vorganger und Nachfolger der Peers P31, P25 und P22auf die richtigen Peers. Die Integration von P25 ist somit abgeschlossen.

Integration des zweiten Peers

Die Integration des zweiten Peers in den Chord-Ring stellt einen Sonderfall dar. Wieschon erwahnt besteht der Chord-Rings nach seiner Erzeugung zunachst aus nur

24

3.3 Der Chord-Peer

einem Peer x, der sich selbst zum Nachfolger und keinen Vorganger hat. Tritt nunein zweiter Peer y in den Chord-Ring ein, so lasst y zunachst seinen Nachfolger vonx bestimmen. Peer y erhalt auf diese Weise seinen Nachfolger Peer x. Zu diesemZeitpunkt haben die Peers x und y die folgenden Zustande:

x.successor = x x.predecessor = nully.successor = x y.predecessor = null

Bei der Ausfuhrung des Stabilisierungsprotolls ruft y die Funktion x.getPredecessor()sowie die Funktion x.notify(y) auf. Wahrend x.getPredecessor() keine Veranderungbei y bewirkt (x ist bereits der Nachfolger von y) so wird x durch den Aufruf vonx.notify(y) dazu veranlasst, y zu seinem Vorganger zu machen. Nun haben die Peersx und y die Zustande:

x.successor = x x.predecessor = yy.successor = x y.predecessor = null

In diesem Zustand kommt es nun zu einem Stillstand. Da x sein eigener Nachfolgerist, ruft x bei der Durchfuhrung des Stabilisierungsprotokolls x.getSuccesor() undx.notify(x) auf. Beide Aufrufe andern weder den Zustand von x, noch den Zustandvon y. Peer y ruft bei der Stabilisierung x.getSuccessor() und x.notify(y) auf. Auchhier andern beide Aufrufe weder den Zustand von x noch den Zustand von y. Diekorrekten Vorganger-Nachfolgerbeziehungen zwischen den Peers werden also nichthergestellt. Insbesondere wird x denken, dass er immer noch fur alle Schlussel ver-antwortlich ist, so dass es zu falschen Lookups kommt.

Dieses Problem kann gelost werden, indem x seinen Nachfolger auf y setzt, sobaldy von ihm seinen Nachfolger bestimmen lasst. Hierzu verwendet y den normalenLookup-Mechanismus. Wird jedoch der normale Lookup-Mechanismus verwendet, sobesteht fur Peer x kein Unterschied zwischen der Bestimmung des Nachfolgers undder Suche nach einen Schlussel. Dementsprechend andert x auch seinen Nachfolgernicht direkt ab. Aus diesem Grund mussen konventionelle Lookups von der Suchenach dem Nachfolger unterscheidbar sein.6

Sind konventionelle Lookups von der Bestimmung des Nachfolgers unterscheidbarund erhalt x nun von y den Auftrag, dessen Nachfolger zu bestimmen, so andert


25

3.3 Der Chord-Peer

x seinen Nachfolger auf x.successor = y ab. Die Peers x und y haben somit diefolgenden Zustande:

x.successor = y x.predecessor = nully.successor = x y.predecessor = null

Nachdem x und y jeweils einmal das Stabilisierungsprotokoll ausgefuhrt haben, be-sitzen beide die korrekten Vorganger und Nachfolger.

Das beschriebene Problem tritt jedoch nur in diesem speziellen Fall auf. Tritt nun eindritter Peer z in den Chord-Ring ein, so fuhrt das in Abschnitt 3.3.1 beschriebeneStabilisierungsprotokoll zu korrekten Ergebnissen.

3.3.3 Die Nachfolgerliste

Das Funktionieren des Chord-Algorithmus basiert darauf, dass jeder Peer den kor-rekten Nachfolger kennt. Wenn z. B. im Chord-Ring aus Abbildung 3.6 Peer P22ausfallt, besitzt P14 keinen Nachfolger mehr. Daruber hinaus wird er nicht wissen,dass P32 sein neuer Nachfolger ist. In der Folge wird P14 nicht wissen, dass er selbstfur Schlussel 30 verantwortlich ist. Einen entsprechenden Lookup wird er verwerfen,da die Finger P32 und P48 hinter dem gesuchten Schlussel liegen. Fur den Fall, dassP14 dennoch den Lookup z. B. an P32 weiterleitet, wird P32 den Lookup gemaßseiner Fingertabelle an P1 weiterleiten. Da P22 ausgefallen ist, ist von den Fingernvon P1 wiederum P14 dem gesuchten Schlussel 30 am nachsten, womit der Loo-kup wieder an seinem Ausgangspunkt angelangt. So konnen falsche oder fehlendeNachfolger zu falschen Lookups, bzw. zu Zyklen fuhren.7

Um Chord dahingehend robuster zu machen, besitzt jeder Peer nicht nur einen Nach-folger, sondern eine Liste mit den ersten j Nachfolgern. Fallt der Nachfolger aus, sowird der erste nicht ausgefallene Peer in der Nachfolgerliste der neue Nachfolger.

Der Fall, dass ein Peer keinen Nachfolger mehr hat, tritt somit nur noch dann ein,wenn alle j Nachfolger gleichzeitig ausfallen. Wenn jeder Peer mit der Wahrschein-lichkeit p ausfallt und jeder Peer j Nachfolger besitzt, dann ist die Wahrscheinlich-keit, dass ein Peer in seiner Nachfolgerliste keinen nicht ausgefallenen Nachfolgermehr findet gleich pj . Bei einer ausreichend langen Nachfolgerliste wird dadurch derChord-Ring sehr robust. So zeigen die Autoren von [43], dass die Peers sogar dann

7Beginnt P14 die Suche bei P48, so entsteht ebenfalls ein Zyklus, da P48 auch an P1 weiterleitet.

26

3.3 Der Chord-Peer

P1

P14

P22

P32

P35

P40

P48

P57

P62 Finger Tabelle

P48P14+32

P32P14+16

P22P14+8

P22P14+4

P22P14+2

P22P14+1

P53

Finger Tabelle

P35P1+32

P22P1+16

P14P1+8

P14P1+4

P14P1+2

P14P1+1

Finger Tabelle

P1P32+32

P48P32+16

P40P32+8

P40P32+4

P35P32+2

P35P32+1

Abbildung 3.6: Zyklus beim Weiterleiten einer Suche

mit hoher Wahrscheinlichkeit einen nicht ausgefallenen Nachfolger in der Nachfolger-liste finden, wenn die Lange der Nachfolgerliste j = Ω(logN) betragt und die Peersmit der Wahrscheinlichkeit p = 1

2 ausfallen.

Da jederzeit neue Peers im Chord-Ring hinzukommen oder wegfallen konnen, mussjeder Peer in regelmaßigen Zeitabstanden die Liste der Nachfolger aktualisieren. An-statt die ersten j Nachfolger mit Hilfe der Lookup-Funktion8 zu bestimmen, gehenPeers bei der Aktualisierung davon aus, dass ihr Nachfolger generell aktuellere In-formationen uber seine Nachfolger besitzt als sie selbst, da er diesen naher ist undso wiederum von seinen Nachfolgern aktuellere Informationen bezieht. Aus diesemGrund aktualisieren die Peers ihre Nachfolgerliste, indem sie bei ihrem Nachfolgereine Kopie von dessen Nachfolgerliste beziehen. Aus dieser Liste wird der letzte Ein-trag geloscht und dafur der eigene Nachfolger, also der ”Spender“ der Liste, an derersten Stelle eingefugt. Auf diese Weise behalt die Nachfolgerliste die Lange j.

3.3.4 Verlassen und Reparatur des Chord-Rings

Wie bereits erwahnt, kommen in einem Chord-Ring nicht nur neue Peers hinzu. DiePeers konnen auch absichtlich oder aber auch ohne vorherige Ankundigung ausfallen.Letzteres kann z. B. dann eintreten, wenn Netzwerkverbindungen zwischen den Peers

8succesori = lookup(successori−1.ID + 1)

27

3.3 Der Chord-Peer

ausfallen oder der Rechner ”absturzt“. In diesem Fall sorgen die Chord-Algorithmendafur, dass alle Peers wieder die korrekten Nachfolger und Vorganger erhalten, d. h.sich der bestehende Chord-Ring wieder stabilisiert.

Fallt z. B. wie Abbildung 3.6 Peer P22 aus, so wird P32 der neue Nachfolger vonP14, da P32 der erste nicht ausgefallene Peer in der Nachfolgerliste von P14 ist. Beider nachsten Durchfuhrung des Stabilisierungsprotokolls ruft P32 neben stabilize()auch die Funktion check predecessor() auf. Damit erkennt P32, dass P22 ausgefallenist und setzt seinen Vorganger P32.predecessor = NULL.

Bei der nachsten Durchfuhrung des Stabilisierungsprotokolls durch P14 ruft dieserP32.notify(P14) auf. Damit erhalt P32 die Mitteilung, dass P14 der neue Vorgangervon P32 ist. Somit und setzt P32 seinen Vorganger auf P32.predecessor = P14.

Algorithmus 6 check predecessor()x.check predecessor()

if predecessor has failedpredecessor = null;

Verlasst ein Peer x den Chord-Ring absichtlich, so kann dies von den verbleibendenPeers als Ausfall behandelt werden. Da x den Chord-Ring jedoch absichtlich verlasst,lasst sich der Chord-Algorithmus dadurch optimieren, dass x seine Nachbarn vorherdaruber ”informiert“ dass er den Chord-Ring verlasst. Wenn u der Vorganger und vder Nachfolger von x ist, so sendet x an u eine Nachricht mit dessen neuen Nach-folger v. Der Nachfolger v erhalt dementsprechend eine Nachricht mit seinem neuenVorganger u. Dies ist vor allem aber auch deshalb sinnvoll, da ein Peer die Schlussel,fur die er verantwortlich ist, vor Verlassen des Chord-Rings an einen anderen Peerubertragen sollte.

3.3.5 Aktualisierung der Fingertabelle

Da sich die Topologie des Chord-Rings verandern kann, ist es moglich, dass Eintrageder Fingertabelle auf nicht mehr existierende Peers verweisen oder dass ein neuerPeer zwischen den Fingern i − 1 und i in den Chord-Ring integriert wurde. Um dieKorrektheit der Fingertabelle sicherzustellen, muss in beiden Fallen eine Aktualisie-rung der Fingertabelle vorgenommen werden. Aus diesem Grund werden die Eintrageder Fingertabelle wie in Algorithmus 7 in regelmaßigen Abstanden aktualisiert, wobei

28

3.4 Lastbalancierung

bei jeder Aktualisierung jeweils nur ein Finger i aktualisiert wird. Der Finger i vonPeer x wird dabei durch eine Suche nach dem Schlussel keyi = x.ID+2i−1 ermittelt.

finger[i] = lookup(x.ID + 2i−1)

Algorithmus 7 Aktualisieren der Fingertabellex.fix fingers()

i = i + 1;if i > m

i = 1;finger[i] = lookup(x.ID + 2i−1);

Das Aktualisieren der Finger wird unabhangig von eventuellen anderen Suchen imHintergrund ausgefuhrt. Da in jedem Durchlauf nur ein Finger aktualisiert wird,dauert es bei einer Fingertabelle mit m Eintragen m Zeitintervalle bis alle Fingeraktualisiert wurden.

3.4 Lastbalancierung

Durch die Verwendung einer Hashfunktion wie SHA-1 sind die berechneten ChordIDsmit hoher Wahrscheinlichkeit gleichmaßig auf dem Chord-Ring verteilt. Dadurch istjeder Peer fur annahernd die gleiche Anzahl Schlussel zustandig. Setzt man voraus,dass alle Schlussel mit der gleichen Haufigkeit gesucht werden, dann erhalt jeder Peerungefahr die gleiche Anzahl an Lookups, und es kommt zu einen guten Lastbalancie-rung load-balancing zwischen den Peers.

Meistens sind jedoch nicht alle Ressourcen bei den Benutzern des P2P-Netzwerksgleich popular. So ist es z. B. sehr wahrscheinlich, dass in einem P2P-Netzwerk, dassdem Austausch von Musikdateien dient, der Schlussel besonders haufig gesucht wird,der den Titel beschreibt, der gerade an der Spitze der Horercharts steht. Hierdurchwerden, unabhangig davon, dass jeder Peer fur die gleiche Anzahl an Schlusseln ver-antwortlich ist, die Peers, die fur populare Schlussel verantwortlich sind, wesentlichstarker belastet als andere. Man spricht in diesem Zusammenhang von Routing HotSpots. Es existieren zwei Strategien mit denen es moglich ist, die Belastung einzelnerPeers durch Routing Hot Spots zu verringern [36]:

• Caching : Beim Caching speichern die Peers zusatzlich zu den Schlusseln, diesie selbst verwalteten, die Schlussel, nach denen sie in letzter Zeit selbst gesucht

29

3.5 Sicherheit

haben. Erreicht sie dann eine Suche nach einem solchen Schlussel, so konnen diePeers direkt antworten, so dass der Lookup nicht mehr weitergeleitet werdenmuss. Da die Peers die Schlussel cachen, die sie selbst gesucht haben, werdenso gerade populare Schlussel von vielen Peers gespeichert.

• Replikation: Durch Replikation kann ein Peer x einen popularen Schlussel beiseinen Nachbarn replizieren, so dass diese dann auch dafur zustandig sind. Diesekonnen dann wiederum den Schlussel bei ihren Nachbarn replizieren, so dassim Idealfall die gesamte Umgebung von x fur den Schlussel verantwortlich istund sich die Last gleichmaßig darin verteilt.

Ein Umstand, der ein effektives load-balancing erschwert, sind heterogene Peer Po-pulationen.9 Es sollte moglich sein, dass leistungsfahigere Peers fur mehr Schlusselverantwortlich sind als Peers mit geringer Leistung. Dies kann z. B. dadurch erreichtwerden, indem jeder Peer mehrere virtuelle Peers ausfuhrt, wobei die Schlussel bzw.die Hashtabelle gleichmaßig unter den virtuellen Peers aufgeteilt werden. Leistungs-starke Peers konnen die Gesamtanzahl der Schlussel fur die sie zustandig sind, da-durch erhohen, indem sie mehr virtuelle Peers ausfuhren als leistungsschwache Peers.

3.5 Sicherheit

Die hier beschriebene Spezifikation von Chord geht nicht auf mogliche Schwachstel-len ein, die ein Angreifer ausnutzen konnte. In [41] werden verschiedene denkbareAttacken vorgestellt.Suchen sind z. B. dadurch verwundbar, dass ein Peer boswillig falsche Routingin-formationen zuruck liefert oder indem er einen Lookup einfach nicht weiterleitet.Die Integritat eines Chord-Rings lasst sich durch haufiges Eintreten und schnellesVerlassen des Rings beeintrachtigen. Wie sich das auswirkt, wird u. a. in Kapitel 5untersucht. Ein Effekt einer solchen Attacke ist, dass sich die Bereiche, fur die diePeers zustandig sind, standig andern. Deshalb mussen permanent große Mengen anSchlusseln und den dazu gehorenden Informationen zwischen den Peers ausgetauschtwerden. Dies kann zu einer Uberlastung von Teilen des Netzwerks fuhren. Hierdurchkann es dann wiederum zur Verzogerung von Lookups kommen. Eine weitere Auswir-kung einer solchen Attacke ist, dass es vermehrt zu nicht mehr aktuellen Eintragen inden Fingertabellen kommen kann und ein Lookup ofter weitergeleitet werden muss,d. h. dass die Pfadlange fur den Lookup ansteigt.

9In heterogenen Populationen besitzen nicht alle Peers die gleiche Hardwareausstattung. So beob-

achtet [40] besonders bei der Netzwerkbandbreite große Unterschiede.

30

3.6 Verwandte Arbeiten

3.6 Verwandte Arbeiten

S-Chord [28] ist eine Erweiterung von Chord. Im Unterschied zu Chord kann hierein Lookup nicht nur an den Nachfolger weitergeleitet werden, sondern auch an denVorganger. Somit erzielt S-Chord eine gegenuber Chord um bis zu 25% verringertePfadlange bei Lookups.Durch die Verwendung dieses symmetrischen Routingprotokolls besitzt S-Chord be-sondere Eigenschaften wie die der routing-entry-symmetry. Das bedeutet, dass furzwei beliebige Peers x und y gilt: Zeigt von x ein Finger auf y, so zeigt auch einervon y auf x.Die routing-entry-symmetry ermoglicht eine schnellere Aktualisierung der Fingerta-bellen durch in-place-notification. Das bedeutet, dass ein Peer x, der absichtlich dasNetzwerk verlasst, alle Peers deren Finger auf x zeigen, daruber informieren kann. Dieinformierten Peers konnen dann direkt ihre Fingertabellen entsprechend abandern.

Neben Erweiterungen von Chord existieren auch auf Chord basierende P2P-Routing-Algorithmen. Koorde [19] ist ein solcher auf Chord basierender Routing Algorithmus,der de Bruijn Graphen [13] verwendet. Wie Chord erreicht dieser Algorithmus in ei-nem Netzwerk mit n Peers eine Pfadlange fur Lookups von O(log n). Im Unterschiedzu Chord erreicht Koorde diese Schranke jedoch mit Informationen uber nur zwei wei-tere, also O(1) Peers, jedoch sind die Moglichkeiten der Lastbalancierung einschranktund die verwendeten Algorithmen weniger intuitiv als bei Chord.

31

4 Implementierung

Dieses Kapitel dient der Erlauterung der im Rahmen dieser Arbeit durchgefuhrtenImplementierung des in Kapitel 3 vorgestellten Chord-Protokolls. Es beschrankt sichdabei auf die wichtigsten Klassen sowie die grundlegenden Merkmale des Klassen-designs. Zur grafischen Darstellung der wichtigsten Sachverhalte wurde die UnifiedModeling Language (UML) [42] verwendet.

Die vorliegende Implementierung realisiert die effiziente Lokalisierung von Schlusseln,und somit die Grundlagen einer auf einer verteilten Hashtabelle beruhenden P2P-Anwendung. Die Architektur einer auf Chord basierenden P2P-Anwendung, wird in[11] skizziert.

Die Implementierung von Chord erfolgte in Java und bildet das in sich abgeschlossenePackage Chord. Insgesamt besteht die Implementierung aus rund 6100 Zeilen Java-Quellcode, wobei ca. 1600 Zeilen auf Testklassen entfallen, welche der Durchfuhrungund Auswertung der in Kapitel 5 beschriebenen Experimente dienten.

Neben der im Rahmen dieser Arbeit durchgefuhrten Java-Implementierung existiertbereits eine in C++ durchgefuhrte Implementierung, die fur CFS (Cooperative FileSystem)[12] verwendet wird. Diese kann unter [34] bezogen werden.

4.1 Klassendesign

Im Folgenden werden die wichtigsten Klassen des Packages Chord kurz dargestellt.Im Einzelnen sind das die Klassen: DHTNode, Location, LookupKeyThread, Lookup-FingerThread, FingerTableStabilizer, Stabilizer, DHTServer, PeerConnectionServer,PeerConnectionClient, RemoteMessage und Mediator.

4.1.1 Die Klasse DHTNode

Die Klasse DHTNode ist die zentrale Klasse von Chord. Sie bildet einen Chord-Peermit seinen einzelnen Komponenten wie Nachfolgerliste und Fingertabelle ab und stellt

32

4.1 Klassendesign

die Funktionen, die außerhalb des Packages Chord verfugbar sind, bereit.

Ein Chord-Peer besitzt eine Nachfolgerliste successors vom Typ SuccessorList undeine Fingertabelle fingertable vom Typ FingerTable. Die Aktualisierung der Fingerta-belle und die Ausfuhrung des Stabilisierungsprotokolls erfolgen durch die eigenstandi-gen Threads fstabilizer und stabilizer, Instanzen der Klasse Stabilizer bzw. Finger-TableStabilizer. Wird ein Chord-Peer von einem anderen Chord-Peer kontaktiert, sowird die eingehende Verbindung von Komponente serverclass einer Instanz der KlasseDHTServer angenommen. Eine detaillierte Beschreibung der Klassen Stabilizer, Fin-gerTableStabilizer und DHTServer erfolgt in den gleichnamigen Abschnitten diesesKapitels.1

successors: SuccessorList

fingertable: FingerTable

mediator: Mediator

stabilizer: Stabilizer

fstabilizer: FingerTableStabilizer

serverclass: DHTServer

DHTNode()

create()

join(in Location)

lookup(in long)

getAppPort()

setAppPort(in int)

finalize()

isConnected()

DHTNode

Abbildung 4.1: UML-Klassendiagramm: DHTNnode

Die vom Chord-Peer durch die Klasse DHTNode bereitgestellten Funktionen sind:Suche nach Schlusseln (lookup()), Instantiieren eines neuen Chord-Rings (create()),Eintritt in einen bestehenden Chord-Ring (join()) und Verlassen des Chord-Rings(finalize()).

Chord ist eine reine Lookup-Anwendung, die von anderen P2P-Anwendungen zurLokalisierung von Schlusseln bzw. zur Lokalisierung der fur die Schlussel verantwort-lichen Peers genutzt wird. Mochte eine P2P-Anwendung mit einer anderen P2P-Anwendung direkt kommunizieren und Daten austauschen, so benotigt sie dafur

1Die Klassen SuccessorList und FingerTable dienen ausschließlich der Kapselung der Referenzen

auf die jeweiligen Peers und stellen außer get- und set-Methoden keine weitere Funktionalitat

bereit.

33

4.1 Klassendesign

einen von Chord unabhangigen Kommunikationskanal bzw. Netzwerkport. Da diePeers jedoch nur auf der Ebene von Chord (Chordebene) und nicht auf der Ebeneder auf Chord beruhenden P2P-Anwendung (Anwendungsebene) von der Existenzanderer Peers erfahren konnen, muss der auf Austausch, des auf Anwendungsebenezum Einsatz kommenden Netzwerkports, auf Chordebene stattfinden. Aus diesemGrund implementiert DHTNode, zusatzlich zur eigentlichen Chord-Funktionalitat,die Funktion setAppPort(). Diese ermoglicht die Ubergabe des auf Anwendungsebe-ne benutzten Netzwerkports (ApplicationPort) an den Chord-Peer.Des Weiteren ist es auf Anwendungsebene wichtig zu wissen, ob der benutzte Chord-Peer uberhaupt mit dem Chord-Ring verbunden ist. Aus diesem Grund wurde dieFunktion isConnected() implementiert. Durch sie lasst sich uberprufen, ob der DHT-Node mit dem Chord-Ring verbunden ist.

4.1.2 Die Klasse Location

Ein Objekt der Klasse Location bildet die ”Adresse“ eines Peers ab und dient da-mit der Beschreibung eines Chord-Peers. Zur Adresse eines Chord-Peers gehoren dieChordID des Peers, sowie die IP-Adresse und der (Chord-)Port, auf dem der abge-bildete Peer von anderen Peers kontaktiert werden kann.

Location()

setChordPort()

getChordPort()

setChordId()

getChordId()

setIP()

getIP()

setApplicationPort()

getApplicationPort()

Location

Abbildung 4.2: UML-Klassendiagramm: Location

Da in Location alle wichtigen Informationen uber einen Peer erfasst sind, eignet sichdiese Klasse zur Speicherung von Zeigern auf andere Peers. So werden der Vorgangersowie die Nachfolger und die Finger eines Peers durch Objekte der Klasse Locationreprasentiert. Ferner bietet sich Location als Informationstrager bei der Ausfuhrungdes Stabilisierungsprotokolls an. Wird z. B. ein Peer nach seinem Vorganger ge-fragt, so versendet er als Antwort darauf ein Objekt der Klasse Location, welches

34

4.1 Klassendesign

den Vorganger beschreibt. Neben dem Stabilisierungsprotokoll verwendet auch derLookup-Mechanismus die Klasse Location. Hierbei wird Location einerseits verwen-det, um in der Lookup-Nachricht den Ausgangspunkt des Lookups zu vermerken,andererseits ist der Ruckgabewert von DHTNode.lookup() vom Typ Location.

Da der Ruckgabewert von DHTNode.lookup() vom Typ Location ist, ist Locationneben DHTNode die einzige Klasse, die Funktionen bereitstellt, die außerhalb desPackages Chord aufgerufen werden konnen. So kann eine auf Chord basierende P2P-Anwendung mit den Funktionen getIP() und getApplicationPort() die Daten (IP-Adresse, ApplicationPort) aus dem von DHTNode.lookup() zuruckgegebenen ObjektLocation herauslesen, die auf Anwendungsebene benotigt werden, um auf die gesuchteRessource zuzugreifen.2

4.1.3 Die Klasse LookupKeyThread und LookupFingerThread

Die Klasse LookupKeyThread implementiert die Suche nach Schlusseln. Die Reali-sierung dieser Klasse als Thread war deshalb notig, da das Auffinden von Fingernebenfalls uber die Suche nach Schlusseln erfolgt. Ware die Suche nicht als Threadrealisiert, so hatte die Aktualisierung der Finger den Suchmechanismus ”blockiert“.Ein Benutzer hatte dann wahrend der Aktualisierung eines Fingers keine Lookupsdurchfuhren konnen. Hatte ein Benutzer auf der anderen Seite einen Lookup durch-gefuhrt, so ware die Aktualisierung der Finger fur diese Zeit nicht moglich gewesen.Durch die Realisierung als Thread konnen mehrere Schlussel gleichzeitig gesucht wer-den, so dass die Aktualisierung der Finger parallel zu den vom Benutzer durchgefuhr-ten Suchen ablaufen kann.

Bei der Durchfuhrung des Lookups selbst wird zunachst eine Instanz von LookKey-Thread erzeugt und mit run() gestartet. Zur eigentlichen Durchfuhrung des Lookupswird die Methode lookup() aufgerufen. Ist die Suche erfolgreich, so gibt lookup() einObjekt vom Typ Location zuruck, welches den verantwortlichen Peer beschreibt. Istdie Suche nicht erfolgreich, liefert lookup() den Wert NULL.

Die maximale Pfadlange, die ein Lookup erreichen kann, wurde begrenzt, da wie be-reits in Abschnitt 3.3.3 gezeigt, in einem Chord-Ring Zyklen entstehen konnen, sodass ein Lookup permanent zwischen zwei oder mehreren Peers hin- und her gesen-

2Der ApplicationPort wird uber die Methode setAppPort() der Klasse DHTNode gesetzt, vgl. Ab-

schnitt 4.1.1

35

4.1 Klassendesign

mediator: Mediator

fingerkey: long

fingerindex: int

LookupFingerThread(in Mediator, in FingerTableStabilizer)

setFingerindex(in int)

setFingerkey(in long)

updateFinger()

run()

LookupFingerThread

result: boolean

mediator: Mediator

LookupKeyThread(in Mediator)

setResult()

lookup(in long)

run()

LookupKeyThread

Abbildung 4.3: UML-Klassendiagramm: LookupThreads

det wird. Der zustandige Peer dabei jedoch nie erreicht. Um eine Uberlastung derPeers durch das Weiterleiten solcher ”toter Lookups“ zu vermeiden, werden diesenach maximal 2m Schritten nicht mehr weitergeleitet. Dies ist ein sinnvoller Wert,da Chord eine Pfadlange von O(log n) verspricht, wobei n ∈ N ∧N = 2m. Es ist al-so sehr wahrscheinlich, dass ein Lookup innerhalb von 2m Schritten sein Ziel erreicht.

Die Klasse LookupFingerThread wurde von LookupKeyThread abgeleitet und hin-sichtlich der Aktualisierung der Finger erweitert. So wird vor der Suche der Indexdes zu aktualisierenden Fingers uber setFingerindex() und der zu suchende Schlusseldurch setFingerkey() ubergeben. Gestartet wird der Thread durch den Aufruf derMethode run(). Die von run() aufgerufene Methode updateFinger() ruft sodann dievon LookupKeyThread geerbte Funktion lookup() auf, welche den gesuchten Fin-ger zuruck gibt. Das Ergebnis wird anschließend durch Aufruf der Methode Media-tor.setFinger() in die Fingertabelle geschrieben.3

4.1.4 Die Klasse FingerTableStabilizer

Die Klasse FingerTableStabilizer dient der regelmaßigen Aktualisierung der Fingerta-belle. Diese Klasse wurde, wie die Suche der Finger selbst, als eigenstandiger Threadkonzipiert, da auch die Aktualisierung der Fingertabelle unabhangig von eventuellenBenutzerinteraktionen ausgefuhrt werden muss.

Die von java.lang.Thread geerbte Methode run() wurde so implementiert, dass sie inregelmaßigen Zeitabstanden eine Instanz von LookupFingerThread erzeugt, die einen

3vgl:: Abschnitt 4.1.8

36

4.1 Klassendesign

der Finger aktualisiert.

Soll Finger i des Peers x aktualisiert werden, so wird zunachst eine Instanz von Loo-kupFingerThread erzeugt. Anschließend werden dieser Instanz der Index des Fingersund der entsprechende zu suchende Schlussel mit den Methodenaufrufen setFingerin-dex(i) und setFingerKey(x.ID+2i−1) ubergeben. Nun wird der Thread durch Aufrufder Methode run() gestartet. Dieser sucht dann selbstandig den gewunschten Fingerund aktualisiert den entsprechenden Eintrag in der Fingertabelle.

Dadurch, dass fur jeden zu aktualisierenden Finger ein eigener Thread gestartet wird,der selbstandig den entsprechenden Peer sucht und dann den Eintrag in der Fin-gertabelle abandert, kann die Aktualisierung von Finger i + 1 unabhangig von derAktualisierung des Fingers i durchgefuhrt werden. Dies hat den Vorteil, dass es nichtvorkommen kann, dass sich die Aktualisierung von Finger i + 1 dadurch verzogert,dass die Aktualisierung von Finger i noch nicht abgeschlossen ist, weil der entspre-chende Peer noch nicht gefunden wurde. Diese voneinander unabhangige und mit-unter parallele Aktualisierung der Finger ist aber nur dann moglich, wenn auch dieSuche nach Schlusseln parallel erfolgen kann, wie es durch die Implementierung vonLookupKeyThread und LookupFingerThread ermoglicht wird.

Das Zeitintervall, das zwischen der Aktualisierung von Finger i und i+1 ist in ei-ner Konfigurationsdatei einstellbar. Es wird in Millisekunden uber den ParameterFIX FINGERS INTERVAL angegeben.4

4.1.5 Die Klasse Stabilizer

Die Klasse Stabilizer dient der Ausfuhrung des Stabilisierungsprotokolls (Stabilisie-rung) wie es bereits in Abschnitt 3.3.1 beschrieben wurde. Die Stabilisierung wirdin regelmaßigen Zeitabstanden ausgefuhrt. Sie stellt die Korrektheit des Nachfolgersund des Vorgangers sicher, indem ein neu hinzugekommener Peer zwischen dem Peerselbst und seinem Nachfolger zum neuen Nachfolger gemacht wird. Die Korrektheitdes Vorgangers wird sichergestellt, indem dieser auf Erreichbarkeit gepruft und wennnotig geloscht wird. Die Zeit zwischen zwei Stabilisierungen, wird in Millisekundenuber den Parameter STABILIZATION INTERVALL in der Konfigurationsdatei an-gegeben.

4Eine Aufstellung der in der Konfigurationsdatei einstellbaren Parameter befindet sich in Anhang

D.

37

4.1 Klassendesign

Nach der eigentlichen Stabilisierung fuhrt Stabilizer die in Abschnitt 3.3.3 beschrie-bene Aktualisierung der Nachfolgerliste durch. Die Nachfolgerliste wird dabei jedochnicht nach jeder Stabilisierung aktualisiert. Sie wird dann aktualisiert, wenn sichdurch die Stabilisierung der Nachfolger andert, spatestens jedoch wenn eine bestimm-te Anzahl Stabilisierungen durchgefuhrt worden ist. Die Anzahl der Stabilisierungen,die durchgefuhrt werden bevor die Nachfolgerliste aktualisiert wird, ist durch denParameter FIND SUCCS INTERVAL in der Konfigurationsdatei einstellbar. Ebensowie die Haufigkeit, mit der die Nachfolgerliste aktualisiert wird, lasst sich auch dieHaufigkeit angeben, mit der bei der Stabilisierung der Vorganger auf Erreichbarkeitgetestet wird. Dies erfolgt uber den Parameter CHECK PRED INTERVAL in derKonfigurationsdatei.

Wie die Aktualisierung der Finger soll auch die Stabilisierung unabhangig von Be-nutzerinteraktionen wie der Durchfuhrung eines Lookups sein und wurde aus diesemGrund als eigenstandiger Thread realisiert. Auch hier wurde die Ausfuhrung derStabilisierung die Durchfuhrung eines Lookups fur die Dauer der Stabilisierung blo-ckieren.

4.1.6 Die Klassen DHTServer, PeerConnectionServer und -Client

Die Klassen DHTServer, PeerConnectionServer und PeerConnectionClient realisie-ren die Kommunikationschnittstelle zu anderen Peers. Die Klasse DHTServer nimmtankommende Verbindungen an. Die Klasse PeerConnectionServer verarbeitet vonanderen Peers eingehenden Nachrichten, wahrend Anfragen an andere Peers durchdie Klasse PeerConnectionClient realisiert werden.

Aus Grunden der Vereinfachung wurde das TCP-Protokoll [37] zur Ubertragung vonNachrichten uber das Netzwerk verwendet. Es bietet den Vorteil, dass es die Ver-wendung von Java-ObjectStreams ermoglicht. Mit Hilfe von Java-ObjectStreams istes moglich, Instanzen von Java-Objekten zu serialisieren und uber das Netzwerk zuversenden. Des Weiteren bietet das TCP-Protokoll den Vorteil, dass die uber dasNetzwerk ubermittelten Daten, im Gegensatz zum UDP-Protokoll [33], immer undin der Reihenfolge beim Empfanger eintreffen, in der sie gesendet wurden.

Eingehende Verbindungen von anderen Chord-Peers werden zunachst von der InstanzDHTNode.serverclass der Klasse DHTServer angenommen. Die einzige Aufgabe vonDHTServer ist es, einen Socket bereitzustellen, auf dem andere Peers Kontakt auf-

38

4.1 Klassendesign

nehmen konnen. Dabei erzeugt DHTServer fur jede neu eingehende Verbindung eineneue Instanz von PeerConnectionServer. Die so erzeugte Instanz von PeerConnecti-onServer verarbeitet die eingehenden Nachrichten des damit verbundenen Peers undsendet entsprechende Antworten zuruck.5

Nimmt ein Peer aktiv Verbindung zu einem anderen Peer auf, so geschieht dies mitHilfe der Klasse PeerConnectionClient. Dies ist immer dann der Fall, wenn ein Lookupoder das Stabilisierungsprotokoll durchgefuhrt wird. Zur Durchfuhrung von Lookupswird die Funktion lookup() vom entsprechenden LookupKeyThread oder LookupFin-gerThread aufgerufen. Bei der Ausfuhrung des Stabilisierungsprotokolls werden dieFunktionen stabilizeNode(), notifyNode() und getSuccessors() aus der Klasse Stabili-zer heraus aufgerufen.

PeerConnectionClient(in Location)

lookupResponse(in LookupMessage)

lookup(in LookupMessage)

findSuccessor(in Location)

getExponent()

getSuccessors()

leaveChordRing(in Object)

stabilizeNode()

notifyNode(in Location)

PeerConnectionClient

mediator: Mediator

processCommand(in RemoteMessage)

run()

PeerConnectionServer

Abbildung 4.4: UML-Klassendiagramm: PeerConnectionClient und -Server

Ferner baut ein Peer aktiv Verbindungen zu anderen Peers auf, wenn er in den Chord-Ring eintritt oder diesen absichtlich verlasst. Wenn ein Peer den Chord-Ring verlasst,so benachrichtigt er seine Nachbarn durch Aufruf der Methode leaveChordRing().In dem Fall, dass eine Peer jedoch in den Chord-Ring eintreten mochte, muss erzunachst den Exponenten des Chord-Rings sowie seinen Nachfolger kennen. Diesewerden durch getExponent() und findSuccessor() vom verbundenen Peer abgefragt.

Eine weiterer Grund, eine Verbindung zu einem anderen Peer zu offnen, ist die Be-antwortung von Lookups. Hier wird dem suchenden Peer durch Aufruf der MethodelookupResponse() eine Antwort auf seinen Lookup gesendet.

5Eine Tabelle der moglichen Nachrichten befindet sich in Anhang C.

39

4.1 Klassendesign

4.1.7 Die Klasse RemoteMessage

In der Klasse RemoteMessage werden an andere Peers zu versendende Daten bzw.Java-Objekte gekapselt. Hierzu besitzt RemoteMessage die Felder messagecommandund messagebody sowie die zum Zugriff auf die Felder benotigten get- und set-Methoden. Das Feld messagecommand ist vom Typ byte. Anhand dieses Feldes wer-den die Art der Nachricht sowie die im Feld messagebody transportierten Objekteklassifiziert. Da je nach Nachricht in messagebody unterschiedliche Objekte transpor-tiert werden, ist Feld messagebody vom Typ Object. Die Große einer RemoteMessageist damit abhangig von den zu ubertragenden Objekten. Tabelle 4.1 gibt Beispielefur die konkreten Werte von messagecommand und messagebody.

Nachricht messagecommand messagebody

GET EXPONENT 30 NULL

EXPONENT IS 31 Byte

NOTIFY 2 Location

KEY LOOKUP 70 LookupMessage

Tabelle 4.1: Beispiele fur RemoteMessages

4.1.8 Die Klasse Mediator

Die Klasse Mediator dient der Entkopplung der einzelnen Klassen, entsprechend demgleichnamigen Mediator-Entwurfsmuster [14]. Mediator bildet die Schnittstelle zwi-schen den einzelnen Komponenten eines Chord-Peers.

Weiterhin verwaltet Mediator sowohl die Nachfolgerliste vom Typ SuccessorList wieauch den Vorganger und die Fingertabelle vom Typ FingerTable und stellt Metho-den zum synchronisierten Zugriff auf diese bereit. Der synchronisierte Zugriff istdeshalb wichtig, da es durch die Verwendung von Threads vorkommen kann, dasszwei Threads gleichzeitig auf das gleiche Objekt zugreifen mochten. So kann es z. B.dazu kommen, dass bei der Ausfuhrung des Stabilisierungsprotokolls der Nachfolgergerade abgeandert wird, jedoch zur gleichen Zeit ein Lookup ausgefuhrt wird, wes-halb der aktuelle Nachfolger abgefragt wird.

Zur Abfrage und Veranderung des Nachfolgers, des Vorgangers und der Finger stelltMediator die get- und set-Methoden get-/setSuccessor(), get-/setPredecessor() undget-/setFinger() bereit. Die Methode setSuccessor() wird z. B. dann aufgerufen, wenn

40

4.1 Klassendesign

successors: SuccessorList

fingertable: FingerTable

Mediator()

keyIsBetween(in long, in long, in long)

closestNode(in long)

localLookup(in long)

lookup(in LookupMessage)

storeLookupResponse(in LookupMessage)

getLookupResponse(in long)

deregisterLookup(in LookupKeyThread, in LookupMessage)

registerLookup(in LookupKeyThread, in LookupMessage)

leave()

getPredecessor()

checkPredecessor()

setPredecessor(in Location)

setSuccessors(in LinkedList)

getSuccessors()

setSuccessor(in Location)

getSuccessor()

setFinger(in int, in Location)

getFinger(in int)

Mediator

Abbildung 4.5: UML-Klassendiagramm: Mediator

ein Peer das Stabilisierungsprotkoll ausfuhrt und dabei durch den Aufruf der Me-thode PeerConnectionClient.stabilizeNode() einen neuen Nachfolger erhalt und denentsprechenden Eintrag in der Nachfolgerliste somit abandert. Die Methode getPrede-cessor() wird z. B. dann benutzt, wenn Stabilizer den Nachfolger auf Erreichbarkeitpruft, oder wenn PeerConnectionServer eine Anfrage nach dem Vorganger beant-wortet. Die Methoden zum Zugriff auf die Finger werden bei der Aktualisierung derFingertabelle sowie beim Weiterleiten eines Lookups an einen Finger benutzt.

Der Zugriff auf die Nachfolgerliste erfolgt mit den Methoden get-/setSuccessors(). DieMethode getSuccessors() wird dabei z. B. aus einer Instanz der Klasse PeerConnec-tionServer aufgerufen, wenn ein Peer die Nachfolgerliste des Peers abfragt. Dies istdann der Fall, wenn von einem anderen Peer durch den Aufruf von PeerConnection-Client.getSuccessors() eine entsprechende Anfrage an den Peer gestellt wird.

Zur Uberprufung des Nachfolgers auf Erreichbarkeit wird die Methode checkPrede-cessor() eingesetzt. Durch Aufruf der Methode leave() wird den Nachbarn mitgeteilt,dass der Peer den Chord-Ring verlasst.

41

4.2 Kommunikation und Interaktion

Neben den Methoden zum Zugriff auf die Nachfolger, die Finger und den Vorgangerunterstutzt Mediator die Durchfuhrung von Lookups. Hier ist die Funktion keyIsBet-ween() von zentraler Bedeutung. Mit ihrer Hilfe wird fur Peer x und seinen Vorgangery, sowie einen Schlussel key uberpruft, ob Peer x fur den Schlussel key zustandig ist,d. h. ob y < key ≤ x. Die weiteren Funktionen zur Durchfuhrung von Lookupswerden in Abschnitt 4.2.2 genauer erlautert.


Dieser Abschnitt erlautert die Interaktion zwischen den Klassen sowie die unter denPeers stattfindende Kommunikation.

4.2.1 Betreten und Verlassen des Chord-Rings

Betreten des Chord-Rings

Dieser Abschnitt erlautert die praktische Umsetzung von Abschnitt 3.3.2: die Inte-gration von neuen Peers in den Chord-Ring.

Mochte ein Peer x einen bestehenden Chord-Ring betreten, so muss er zunachsteinen beliebigen Peer z des Chord-Rings kennen. Diesen muss er dann kontaktierenund ihn zuerst nach dem Exponenten des Chord-Rings fragen. Dies geschieht, in-dem Peer x die Nachricht GET EXPONENT an z sendet. Peer z gibt darauf hindie Antwort EXPONENT IS. In dieser Nachricht ist der Exponent des Chord-Ringenthalten. Nachdem x nun den Exponenten des Chord-Rings kennt, muss der Nach-folger von x im Chord-Ring ermittelt werden. Diesen lasst x von z durch Suche desfur x.ID zustandigen Peers feststellen. Da z, wie bereits in Abschnitt 3.3.2 erklart,den speziellen Fall der Ermittlung des Nachfolgers von der konventionellen Suchenach einem Schlussel unterscheiden konnen muss, verwendet x die spezielle Nach-richt FIND SUCCESSOR.6 Erhalt z diese Nachricht, so wird bei ihm der konventio-nelle Lookup-Mechanismus in Gang gesetzt, mit dem dann der fur x.ID zustandigePeer, also der Nachfolger y von x, gesucht wird. Sobald Peer y gefunden wurde,der Lookup-Prozess also abgeschlossen ist, ubermittelt z das Ergebnis an x. Hierzusendet z die Nachricht FOUND SUCCESSOR an x zuruck. Peer x setzt nun seinenNachfolger auf den ubermittelten Wert y. Nachdem x nun seinen Nachfolger kennt,ist der eigentliche Beitritt in den Chord-Ring abgeschlossen. Die weiteren Schritte


42


zur vollstandigen Integration von x in den Chord-Ring werden durch das Stabilisie-rungsprotokoll ausgefuhrt. Hierbei wird y uber die Existenz von x informiert, so dassx zum Vorganger von y wird. Peer x bezieht seinen Vorganger, indem er von y’, demalten Vorganger von y, benachrichtigt wird.7

Verlassen des Chord-Rings

Wie schon in Abschnitt 3.3.4 erwahnt, ist Chord darauf ausgelegt, dass Peers ohneVorankundigung ausfallen. Verlasst ein Peer jedoch den Chord-Ring absichtlich, soist es sinnvoll, dass der entsprechende Peer seinen Nachfolger und seinen Vorgangervorab daruber informiert.8

Fur diesen Fall ist die Nachricht LEAVE vorgesehen. Diese wird von Peer x an seineNachbarn gesendet bevor er den Chord-Ring absichtlich verlasst. Mit Hilfe dieserNachricht wird es dem Vorganger y und dem Nachfolger z von x ermoglicht, ihrenNachfolger bzw. Vorganger direkt und ohne Ausfuhrung des Stabilisierungsprotolls,auf z bzw. y abzuandern.

Die Nachricht LEAVE enthalt dabei eine Liste mit zwei Elementen von Typ Location.Das erste Element bildet x selbst ab. Je nach Empfanger, bildet das zweite Element,entweder den Vorganger y oder den Nachfolger z ab. Anhand des ersten Elementskonnen y und z unterscheiden, ob sie die LEAVE-Nachricht von ihrem Vorganger odervon ihrem Nachfolger erhalten. Dementsprechend ersetzt sowohl Peer y als auch Peerz seinen Vorganger bzw. Nachfolger durch den Peer, der durch das zweite Elementder Liste reprasentiert wird. Hierdurch wird also y zum Vorganger von z, wahrend zzum Nachfolger von y wird.

Wenn also x den Chord-Ring verlasst, so sendet er an seinen Vorganger y die Nach-richt LEAVE mit der Liste (x, z) und an seinen Nachfolger z die Nachricht LEAVEmit der Liste (x, y). Erhalt Peer y die Nachricht, so andert y seinen Nachfolger aufden ubermittelten Peer z ab, wahrend z seinen Vorganger auf y abandert.

4.2.2 Durchfuhrung von Lookups

Routingmoglichkeiten

Fur die Implementierung des Lookup-Prozesses ist das fur die Weiterleitung vonLookups gewahlte Routingkonzept von entscheidender Bedeutung. Dabei werden zwei

7vgl.: Abschnitt 3.3.28vgl.: Abschnitt 3.3.4

43


Vorgehensweisen unterschieden:

• iterativ : Bei der iterativen Suche werden alle Anfragen vom suchenden Peergestellt. Er befragt dabei eine Folge von n Peers, wobei ihm Peer i-1 mitteilt,dass Peer i der nachste zu befragende Peer auf dem Suchpfad ist. Dies geschiehtsolange bis der richtige Peer gefunden wird.

• rekursiv : Bei der rekursiven Suche wird der Lookup vom suchenden Peer initi-iert indem dieser eine Anfrage an einen anderen Peer stellt. Im Anschluss daranwird der Lookup aber von Peer zu Peer weitergeleitet. Hat die Suche ihr Zielerreicht, so wird die Antwort uber den gleichen Weg zuruckgeroutet.

Der Vorteil der iterativen Suche besteht darin, dass sich der suchende Peer dem ge-suchten Peer mit jeder Iteration weiter annahert. Somit erhalt er implizit Informatio-nen zum Fortschritt des Suchprozesses. Da jegliche Kommunikation vom suchendenPeer ausgeht, besitzt dieser standigen Einfluss auf den weiteren Verlauf der Sucheund kann diese auch jederzeit abbrechen. Werden wahrend einer iterativen Suche nPeers befragt, so betragt die Anzahl der benotigten Nachrichten 2n.

Der Vorteil der rekursiven Suche wiederum besteht darin, dass der suchende Peerunabhangig davon, dass der Lookup uber n Peers weitergeleitet wird, nur eine Nach-richt senden und deshalb auch nur eine TCP-Verbindung aufbauen muss, wahrend erbei der iterativen Suche n Nachrichten sendet und damit auch n TCP-Verbindungenaufbauen muss. Der Nachteil an rekursiven Aufrufen ist, dass dem suchenden Peerwahrend der Suche keine Informationen uber den Fortschritt der Suche zur Verfugungstehen. Sobald der Lookup gesendet wurde, hat der suchende Peer keinen Einflussmehr auf den weiteren Verlauf der Suche. Die Antwort erhalt er von dem Peer, demer den Lookup gesendet hat. Bei der rekursiven Suche wird die Antwort uber diegleichen n Peers, uber die sie vom suchenden Peer zum fur einen Schlussel verant-wortlichen Peer gelangt ist, zuruckgesendet. In diesem Fall betragt die Anzahl derNachrichten ebenfalls 2n.

Die Anzahl der fur eine Suche benotigten Nachrichten, sowie die Anzahl der vomsuchenden Peer benotigten TCP-Verbindungen lasst sich durch einen semi-rekursivenAnsatz verringern. Der Lookup wird dabei wie bei der rekursiven Suche jeweils an dendem gesuchten Peer am nachsten gelegenen bekannten Peer weitergeleitet. Wird dergesuchte Peer erreicht, so antwortet dieser jedoch dem Initiator der Suche direkt. Beidiesem Ansatz muss der suchende Peer wie beim rekursiven Ansatz nur eine TCP-

44


Verbindung aufbauen, wahrend die Anzahl der benotigten Nachrichten n+1 betragt.Wichtig bei diesem Vorgehen ist, dass im Lookup immer dessen Ursprung angegebenwird. Fur die Implementierung wurde der semi-rekursive Ansatz gewahlt.

Initiierung von Lookups

Vom Benutzer durchgefuhrte Lookups werden durch den Aufruf der Methode loo-kup(key) der Klasse DHTNode eingeleitet. Das UML-Sequenzdiagramm fur die Durch-fuhrung eines Lookups wird von Abbildung 4.6 gezeigt. Der suchende Peer ist dabeinicht der fur den Schlussel verantwortliche Peer. Die Darstellung bezieht sich aufdie wesentlichen Schritte, weshalb z. B. die Bestimmung des Peers, an den die Sucheweitergeleitet wird, oder die Erzeugung der Instanz von PeerConnectionServer durchdie Klasse DHTServer nicht mit eingeflossen sind.

Mit dem Aufruf DHTNode.lookup(key) der Peers x wird eine neue Instanz l der KlasseLookupKeyThread generiert, welche mit l.run() gestartet wird. Ist dies geschehen, sowird der Suchvorgang durch Aufruf der Methode l.lookup(key) des erzeugten Lookup-KeyThreads l fortgefuhrt. Zunachst testet l, ob Peer x nicht selbst fur den gesuchtenSchlussel zustandig ist. Diese Uberprufung erfolgt durch den Aufruf der MethodeMediator.localLookup(). Ist Peer x selbst zustandig, so wird direkt eine Instanz vonLocation zuruckgeliefert, welche Peer x beschreibt.

Ist x jedoch nicht fur den Schlussel verantwortlich, so muss der Lookup weiter-geleitet werden. Hierzu meldet sich die Instanz l von LookupKeyThread bei derKlasse Mediator an. Diese Anmeldung erfolgt durch den Methodenaufruf Media-tor.registerLookup(key,l). Nach erfolgter Anmeldung des Lookups fallt LookupKey-Thread in einen Zustand, in dem er auf das Ergebnis des Lookups wartet. Hierbeiwartet l solange, bis der Schlussel gefunden wurde oder die maximale Suchzeit er-reicht ist.9

Die weitere Bearbeitung des Lookups wird unterdessen von Mediator durchgefuhrt.Mediator wahlt nun aus der Fingertabelle den Peer y aus, an den der Lookup weiter-geleitet wird. Diese Auswahl erfolgt durch die Methode Mediator.closestNode(key).Nachdem Peer y ermittelt wurde, wird eine Netzwerkverbindung zu diesem aufge-baut. Diese wird mittels einer Instanz der Klasse PeerConnectionClient hergestellt.Ist die Verbindung zwischen den Peers x und y hergestellt, so wird der Lookup versen-det. Dies erfolgt durch den Methodenaufruf PeerConnectionClient.lookup(key). Hier-

9Die maximale Suchzeit ist in der Konfigurationsdatei einstellbar. Vgl.: Anhang D

45


DHTNode LookupKeyThread Mediator PeerConnectionClient

lookup(key)

lookup(key)

registerLookup(key,this)

lookup(key)

PeerConnectionServer

storeLookupResponse(key,Location)

setResult

wait

getLookupResponse(key)

deregisterLookup(key,this)

Location

Location

Location

localLookup(key)

KEY_LOOKUP

KEY_FOUND

Abbildung 4.6: UML-Sequenzdiagramm: Durchfuhrung von Lookups

bei wird die Nachricht KEY LOOKUP versendet. Sie enthalt den gesuchten Schlusselsowie die IP-Adresse und den Chord-Port des suchenden Peers x.10

Nachdem der Lookup weitergeleitet wurde, ist der aktive Teil des Lookups beendet.Es verbleibt die Instanz l von LookupKeyThread, welche auf das Ergebnis des Loo-kups wartet. Diese wird wieder aktiviert, wenn sich der fur den gesuchten Schlusselverantwortliche Peer meldet, oder die maximale Suchzeit erreicht ist. Wird die maxi-male Suchzeit erreicht, so meldet l den Lookup bei der Instanz von Mediator wiederab. Die Methode LookupKeyThread.lookup(key) wird in diesem Fall mit dem Ruckga-bewert NULL beendet, so dass in der Folge auch die Methode DHTNode.lookup(key)mit dem Ergebnis NULL beendet wird.

Wird im Laufe des Suchprozesses der verantwortliche Peer p erreicht, so meldet die-ser sich beim suchenden Peer x. Hierzu kontaktiert er x unter der IP-Adresse undChord-Port, die von x in der Nachricht LOOKUP KEY vermerkt wurde. Von Peerx wird nun eine neue Instanz s der Klasse PeerConnectionServer fur die von p auseingehende Verbindung generiert. Diese verarbeitet die von p gesendete NachrichtKEY FOUND. Mit dieser Nachricht ubermittelt p eine Beschreibung loc von sich,und dass er fur den gesuchten Schlussel zustandig ist. PeerConnectionServer s meldetnun an Mediator, dass Schlussel key gefunden wurde und dass p, welcher durch loc

10Details zu Aufbau und Verwendung der versendeten Nachrichten erlautert Anhang C.

46


beschrieben wird, der zustandige Peer ist. Hierzu ruft PeerConnectionServer die Me-thode Mediator.storeLookupResponse(key,loc) auf. Fur den Fall, dass die maximaleSuchdauer uberschritten wurde und LookupKeyThread den Lookup schon wieder ab-gemeldet hat, verwirft Mediator das Ergebnis. Wurde die maximale Suchdauer jedochnoch nicht uberschritten, informiert Mediator die Instanz l von LookupKeyThread,welche auf das Ergebnis der Suche wartet daruber, dass die Suche nach Schlussel keyerfolgreich verlaufen ist.11 Die Benachrichtigung erfolgt durch den Aufruf LookupKey-Thread.setResult(). Nachdem LookupKeyThread l benachrichtigt wurde, fragt dieserdas Ergebnis der Suche vom Mediator ab. Dies erfolgt mittels Aufruf der Metho-de Mediator.getLookupResponse(key), deren Ruckgabewert die Beschreibung loc desverantwortlichen Peers ist. Nachdem LookupKeyThread l das Ergebnis vom Mediatorabgefragt hat, meldet l den Lookup beim diesem ab. Hierzu ruft LookupKeyThreadl die Methode Mediator.deregisterLookup(key,l) auf. Ist die Abmeldung erfolgt, wirddie Methode LookupKeyThread.lookup(key) mit dem Ruckgabewert loc beendet. Da-nach wird LookupKeyThread selbst beendet.

Nachdem LookupKeyThread.lookup(key) beendet wurde, kann nun auch DHTNo-de.lookup(key) beendet werden. Wenn der gesuchte Schlussel gefunden wurde, liefertDHTNode.lookup(key) den Ruckgabewert loc, wurde der Schlussel nicht gefunden, soist der Ruckgabewert NULL.

Weiterleitung und Beantwortung von Lookups

Die Weiterleitung und Beantwortung von Lookups ist neben der aktiven Suche nacheinem Schlussel ein weiterer Aspekt des Suchmechanismus. In diesem Fall erhalt derPeer zunachst die Nachricht KEY LOOKUP von einem anderen Peer. Diese wird uberdie Klasse PeerConnectionServer empfangen. Erhalt eine Instanz von PeerConnecti-onServer eine KEY LOOKUP Nachricht, so ruft sie die Funktion Mediator.lookup()auf und ubergibt den in der Nachricht enthaltenen gesuchten Schlussel sowie dieebenfalls in der Nachricht enthaltene Information uber die ursprungliche Herkunftdes Lookups. Mediator pruft nun, ob der eigene Chord-Peer fur den Schlussel verant-wortlich ist. Ist dieser fur den Schlussel verantwortlich, so wird dem suchenden Peereine entsprechende Antwort gesendet. Hierzu wird eine Verbindung zum suchendenPeer aufgebaut. Dies geschieht mit Hilfe der Informationen uber die Herkunft desLookups und einer Instanz c der Klasse PeerConnectionClient. Ist die Verbindung

11Da die Durchfuhrung von Lookups durch Threads realisiert wurde, kann es vorkommen, dass

mehrere LookupKeyThreads gleichzeitig den gleichen Schlussel key suchen. In diesem Fall werden

alle wartenden LookupKeyThreads benachrichtigt.

47


aufgebaut, so wird die Antwort auf den Lookup an den suchenden Peer gesendet.Dies erfolgt durch den Aufruf der Methode c.lookupResponse().Ist der Peer nicht selbst verantwortlich, so muss er den Lookup weiterleiten. Hierzuwahlt er aus seiner Fingertabelle denjenigen Peer aus, der dem gesuchten Schlusselam nachsten liegt. Anschließend baut er mit Hilfe einer Instanz c von PeerConnec-tionClient eine Verbindung zu diesem Peer auf. Ist die Verbindung zustande gekom-men, so wird der Lookup weitergeleitet. Dies erfolgt durch den Aufruf der Methodec.lookup(key).

Abbildung 4.7 zeigt das UML-Sequenzdiagramm fur den Fall, dass der Peer fur dengesuchten Schlussel selbst verantwortlich ist. Falls der Peer den Lookup nur weiter-leitet, wurde die Methode lookup(key) der Klasse PeerConnectionClient aufgerufenwerden. Die versendete Nachricht ware in diesem Fall KEY LOOKUP.

PeerConnectionServer PeerConnectionClientMediator

lookup(key,origin)

localLookup(key)

KEY_LOOKUP

lookupResponse(key)

KEY_FOUND

Abbildung 4.7: UML-Sequenzdiagramm: Antwort auf Lookups

4.2.3 Aktualisierung der Fingertabelle

Die Aktualisierung der Fingertabelle erfolgt in regelmaßigen Zeitabstanden (Runden).Es wird dabei in jeder Runde genau ein Finger aktualisiert. Hierzu generiert dieKlasse FingerTableStabilizer fur jede Aktualisierung eine neue Instanz l der KlasseLookupFingerThread und startet den Thread mit l.run().Bevor jedoch der Finger gesucht werden kann, werden der Schlussel key, fur den derFinger verantwortlich sein soll, sowie der Platz i des Fingers in der Fingertabelle anLookupFingerThread l ubergeben. Dabei gilt, dass key = 2i−1 ist.Jetzt wird die Suche mit l.updateFinger() gestartet. Die aufgerufene Methode upda-teFinger() sucht zunachst den fur key zustandigen Peer. Dies geschieht mittels der

48


Funktion lookup(key), welche LookupFingerThread von der Superklasse LookupKey-Thread vererbt wurde. Ist die Suche nach Finger i erfolgreich, so ist das Ergebnisloc = lookup(key) eine Instanz von Location, die den entsprechenden Finger be-schreibt. Nun aktualisiert LookupFingerThread Eintrag i der Fingertabelle mit demgerade ermittelten Eintrag loc. Dies erfolgt durch den Aufruf der Methode Media-tor.setFinger(i,loc). Nach Beendigung dieses Methodenaufrufs ist die Aktualisierungdes Fingers abgeschlossen und l wird beendet.

Das UML-Sequenzdiagramm in Abbildung 4.8 zeigt die erlauterten Methodenaufrufezur Aktualisierung eines Fingers.

FingerTableStabilizer MediatorLookupFingerThread

setFingerkey(key)

setFingerindex(i)

updateFinger()

lookup(key)

setFinger(i,loc)

Abbildung 4.8: UML-Sequenzdiagramm: Aktualisierung eines Fingers

4.2.4 Ausfuhrung des Stabilisierungsprotokolls

Die Ausfuhrung des Stabilisierungsprotokolls erfolgt wie in Abschnitt 3.3.1 beschrie-ben. Die Peers fragen dabei zunachst den Vorganger ihres Nachfolgers ab. Dies erfolgtdurch Versenden der Nachricht GET PREDECESSOR, welche vom Nachfolger mitPREDECESSOR IS beantwortet wird.12 Nun wird uberpruft, ob der Vorganger desNachfolgers als neuer Nachfolger in Betracht kommt. Ist dies der Fall, so wird derNachfolger entsprechend abgeandert.

Nachdem dieser Teil des Stabilisierungsprotokolls abgeschlossen ist, informieren diePeers ihren Nachfolger uber die eigene Existenz. Dies geschieht durch Versenden derNachricht NOTIFY an den Nachfolger.

12Details zu Aufbau und Verwendung der versendeten Nachrichten erlautert Anhang C.

49


Zum Abschluss der Stabilisierung wird die Nachfolgerliste vom Nachfolger mit Hil-fe der Nachricht GET SUCCESSORS abgefragt. Der Nachfolger antwortet mit derNachricht SUCCESSORS ARE, welche seine Nachfolgerliste enthalt.

Das in Abschnitt 3.3.3 beschriebene Verfahren zur Ubernahme der Nachfolgerliste,d. h. den letzten Peer in der Nachfolgerliste zu loschen und an erster Stelle deneigenen Nachfolger einzufugen, erweist sich in der Praxis als nicht ausreichend. Diesgilt insbesondere fur Chord-Ringe mit wenigen Peers, wenn die maximale Lange derNachfolgerliste die Anzahl der Peers im Chord-Ring ubersteigt. Ubersteigt die Langeder Nachfolgerliste die Anzahl der Peers im Chord-Ring, so fuhrt das beschriebeneVerfahren dazu, dass sich Teile der Liste wiederholen und somit mehr Daten uber-tragen werden als notig. Aus diesem Grund werden sich wiederholende Eintrage beider Ubernahme der Nachfolgerliste entfernt.

P1

P14

P22

P35

P53

P53, P1, P14

P1, P14, P22

P14, P22, P35

P22,P35,P53

P35, P53, P1

P1

P14

P22

P35

P53

P1, P14

P14, P22, P35

P22,P35,P53

P35, P53, P1

1

P1

P14

P22

P35

P53

P1, P14, P22

P14, P22, P35

P22,P35,P53

P35, P14, P1

2

P1

P14

P22

P35

P53

P1, P14, P22

P14, P22, P35

P22, P35, P1

P35, P1, P14

3

Abbildung 4.9: Vererbung der Nachfolgerliste

Ein weiteres Problem der Nachfolgerliste ist, dass ausgefallene Peers nicht direkt ausden Nachfolgerlisten aller Peers geloscht werden. Sei y ein beliebiger Peer mit demVorganger x, dem Nachfolger z und einer Nachfolgerliste der Lange j. Fallt Peer yaus, so wird z der neue Nachfolger von x. Fuhrt x nun das Stabilisierungsprotokollaus, so bezieht er eine neue Nachfolgerliste von z. Somit wird y aus der Nachfolgerlistevon x geloscht, jedoch existiert der Eintrag immer noch in den Nachfolgerlisten derersten j-1 Vorganger von x. Bei der folgenden Stabilisierung vererbt nun x wiederum

50

4.3 Datenvolumen

seine Nachfolgerliste an seinen Vorganger. Nun existiert der Eintrag y nur noch inden ersten j-2 Vorgangern von x. Dieser Vorgang setzt sich fort, bis aus allen Nachfol-gerlisten der Eintrag y geloscht wurde. Es dauert also mindestens j Stabilisierungen,bis ein ausgefallener Peer aus allen Nachfolgerlisten geloscht wurde.

Abbildung 4.9 veranschaulicht den beschriebenen Sachverhalt an einem Chord-Ringmit 5 Peers und einer Nachfolgerliste der Lange j = 3. Fallt P53 aus, so dauert esj = 3 Stabilisierungen, bis P53 aus allen Nachfolgerlisten verschwunden ist.

4.3 Datenvolumen

Dieser Abschnitt analysiert die Große der versendeten Nachrichten. Diese lassen sichin zwei Kategorien einordnen:

• einmal versendete Nachrichten: Diese Nachrichten werden beim Eintritt undVerlassen des Chord-Rings gesendet. Sie werden zur Abfrage des Exponenten,zum erstmaligen Auffinden des Nachfolgers bei Eintritt in den Chord-Ring,sowie zur Ubermittlung des Vorgangers bzw. Nachfolgers beim Verlassen desChord-Rings versendet. Hierzu zahlen die Nachrichten GET EXPONENT, EX-PONENT IS, FIND SUCCESSOR, FOUND SUCCESSOR und LEAVE.

• mehrmals versendete Nachrichten: Diese Nachrichten werden zur Suche nachSchlusseln und zur Stabilisierung des Chord-Rings eingesetzt. Dazu zahlen dieNachrichten GET PREDECESSOR, PREDECESSOR IS, GET SUCCESSORS,SUCCESSORS ARE, NOTIFY sowie KEY LOOKUP und KEY FOUND.

Das durch einmalig versendete Nachrichten verursachte Datenvolumen ist konstant,so dass der Anteil, den diese Nachrichten am gesamten Datenvolumen haben, mitder Zeit sinkt. Aus diesem Grund beschrankt sich dieses Kapitel auf die Nachrichten,die mehrmals verwendet werden. Diese sind fur den großten Teil des verursachtenDatenvolumens verantwortlich.

Wie in Abschnitt 4.1.7 bereits beschrieben, bestehen die von den Peers versendetenNachrichten immer aus einem Kommando messagecommand und einem Feld mes-sagebody, in dem je nach Kommando unterschiedliche Objekte gespeichert werden.Nachfolgend wird beschrieben, welche Informationen diese Nachrichten im Einzelnentransportieren und wie sich daraus die Nachrichtengroße errechnet. Die Betrachtungder Nachrichtengroße orientiert sich dabei an der Große der in der jeweiligen Instanz

51

4.3 Datenvolumen

von RemoteMessage ubertragenen Informationen. Die Große der ubertragenen In-formationen berechnet sich aus der Große der Objekte im Feld messagebody plus 1Byte im Feld command, da Kommandos durch ein Byte reprasentiert werden. Insbe-sondere findet die Betrachtung dabei anhand der Große der von Chord verwendetenDatentypen, also unabhangig von ihrer konkreten Java-Reprasentation, statt. EineZeichenkette von 15 Zeichen wird z. B. mit 15 Bytes gezahlt, unabhangig davon,dass diese durch ein Objekt des Typs java.lang.String reprasentiert wird, welchespotenziell mehr als 15 Bytes beansprucht.

4.3.1 Datenvolumen je Lookup

Zur Durchfuhrung von Lookups werden die beiden Nachrichten KEY LOOKUP undKEY FOUND verwendet. Diese beiden Nachrichten transportieren im Feld message-body jeweils ein Objekt der Klasse LookupMessage, in der die zum Lookup benotigtenDaten, also der gesuchte Schlussel, der suchende Peer und die bisherige Anzahl anWeiterleitungen, gekapselt werden.13 Zur Reprasentation des gesuchten Schlusselswird der Java-Typ long verwendet, der 64-Bit Werte darstellt, also 8 Bytes benotigt.Die Anzahl der Weiterleitungen wird der Java-Typ short eingesetzt, welcher 2 Bytesbenotigt.14 Der suchende Peer wird durch eine Instanz von Location reprasentiert,welche insgesamt 31 Bytes umfasst.15 Insgesamt betragt das Datenvolumen der Nach-richten KEY LOOKUP und KEY FOUND:

Kommando byte 1 Bytegesuchter Schlussel long 8 Bytessuchender Peer Location 31 BytesWeiterleitungen bisher short 2 Bytes

Summe 42 Bytes

Wird nun in einem Chord-Ring mit n Peers ein Lookup durchgefuhrt, so wird derverantwortliche Peer mit hoher Wahrscheinlichkeit innerhalb von O(log n) Schrittengefunden. Somit werden O(log n) Nachrichten des Typs KEY LOOKUP benotigt.Wird schließlich der verantwortliche Peer gefunden, so sendet dieser die NachrichtKEY FOUND an den suchenden Peer zuruck. Durch die Suche nach einem Schlussel13Das UML-Klassendiagramm der Klasse LookupMessage befindet sich in Anhang A. Die bereitge-

stellten Methoden dienen dem Zugriff auf die gleichnamigen Felder.14Da die maximale Anzahl der Weiterleitungen durch 2m begrenzt ist und fur m der Java-Typ byte

benutzt wurde, muss fur die Anzahl der Weiterleitungen mindestens der Java-Typ short benutzt

werden, da es sonst zu einem Uberlauf kommen kann.15Eine detaillierte Aufschlusselung von Location befindet sich in Anhang C.

52

4.3 Datenvolumen

wird also insgesamt die folgende Menge an Daten versandt:

KEY LOOKUP 42*log(n) BytesKEY FOUND 42 Bytes

Summe 42*(1+log(n)) Bytes

4.3.2 Datenvolumen je Stabilisierung

Jeder Peer im Chord-Ring fuhrt in regelmaßigen Zeitabstanden t das in Abschnitt3.3.1 beschriebene Stabilisierungsprotokoll aus. Hierbei kontaktieren die Peers ihreNachbarn und tauschen Informationen mit diesen aus.Peer x fragt dabei den Vorganger seines Nachfolgers y ab, worauf y die entsprechen-de Information zurucksendet. Hierfur werden Nachrichten GET PREDECESSOR furdie Anfrage von x an y und PREDECESSOR IS fur die Antwort von y an x, benutzt.Mochte x seinen Nachfolger y uber seine Existenz informieren, so sendet x die Nach-richt NOTIFY an y. Zur Abfrage und Ubermittlung der Nachfolgerliste werden dieNachrichten GET SUCCESSORS und SUCCESSORS ARE benutzt.

Die Große der Nachrichten berechnet sich analog zum in Abschnitt 4.3.1 beschriebe-nen Verfahren.16 Eine Sonderstellung nimmt die Nachricht SUCCESSORS ARE ein.Ihre Große ist von der Lange j der Nachfolgerliste abhangig. Je großer j wird, destomehr Objekte vom Typ Location werden mit SUCCESSORS ARE transportiert. DieGroßen der bei der Stabilisierung versendeten Nachrichten sind im Einzelnen:

GET PREDECRESSOR byte 1 BytePREDECRESSOR IS byte+Location 32 BytesNOTIFY byte+Location 32 BytesGET SUCCESSORS byte 1 ByteSUCCESSORS ARE byte+Location*j 1+32*j Bytes

In der folgenden Analyse wird nun angenommen, dass alle Peers auf der gleichenImplementierung beruhen, insbesondere wird angenommen, dass die Zeit t zwischenzwei Ausfuhrungen des Stabilisierungsprotokolls bei allen Peers gleich ist. Ferner wirdangenommen, dass keine neuen Peers hinzukommen oder den Chord-Ring verlassen,d. h. es sich um einen statischen Chord-Ring handelt.Wenn die Dauer t einer Stabilisierungsperiode bei allen Peers gleich ist, fuhrt jederPeer im Chord-Ring im Zeitintervall [t0, t1) : t0+t = t1 eine Stabilisierung aus. Dabei16Aufbau und Große der Nachrichten sind in Tabelle C.1 in Anhang C dargestellt.

53

4.3 Datenvolumen

versendet jeder Peer x im Intervall [t0, t1) bei der Durchfuhrung der Stabilisierungeinmal die Nachricht NOTIFY, GET PREDECESSOR und GET SUCCESSORS.Wenn im Intervall [t0, t1) jeder Peer x im Chord-Ring eine Stabilisierung durchfuhrt,so fuhrt auch jeweils der Vorganger y des Peers x eine Stabilisierung durch. Dasbedeutet wiederum, dass Peer x im Intervall [t0, t1) nicht nur die Nachrichten NO-TIFY, GET PREDECESSOR und GET SUCCESSORS an seinen Nachfolger sen-det, sondern zusatzlich seinem Vorganger y die Anfrage GET PREDECESSOR undGET SUCCESSORS beantworten muss. Hierzu sendet er die Nachrichten PREDE-CESSOR IS und SUCCESSORS ARE.17

Eine Besonderheit der vorliegenden Implementierung besteht darin, dass die Nach-folgerliste nicht bei jeder Stabilisierung aktualisiert werden muss. Die Haufigkeit derAktualisierung ist durch einen Parameter u der Konfigurationsdatei veranderbar.18

Dieser gibt an, wie viele Stabilisierungen durchgefuhrt werden, bis eine Aktualisierungder Nachfolgerliste stattfindet. Ein Peer versendet somit insgesamt je Stabilisierungs-intervall die Nachrichten:

GET PREDECRESSOR 1 BytesPREDECRESSOR IS 32 BytesNOTIFY 32 BytesGET SUCCESSORS 1

u BytesSUCCESSORS ARE 1+32∗j

u Bytes

Summe 65 + 2+32∗ju Bytes

17Ware der Chord-Ring nicht statisch, so konnten mehrere Peers den gleichen Nachfolger x besit-

zen, weshalb x im Intervall [ti, ti+1) mehr als eine Nachricht PREDECESSOR IS bzw. SUCCES-

SORS ARE senden musste.18Eine Aufstellung der Parameter der Kondigurationsdatei befindet sich in Anhang D.

54

5 Experimentelle Analyse

In den bisherigen Kapiteln wurde der Chord-Algorithmus aus theoretischer Perspek-tive betrachtet. Die dabei getroffenen Aussagen bezogen sich hauptsachlich auf ge-nerelle Eigenschaften von Chord, wie der Durchfuhrung von Lookups mit PfadlangeO(log n), oder der Robustheit von Chord-Ringen gegenuber Ausfallen von Peers.Zu den rein implementierungsspezifischen Eigenschaften gehorten der Bandbreiten-verbrauch der versendeten Nachrichten. Dieses Kapitel beschaftigt sich nun mit derexperimentellen Uberprufung dieser grundlegenden Eigenschaften.

Hierzu wurden, auf der Grundlage der in Kapitel 4 beschriebenen Implementierung,verschiedene Experimente durchgefuhrt. Da mit diesen Experimenten die grundlegen-de Eigenschaften von Chord, wie die Suche mit logarithmischer Pfadlange, bestatigtwerden sollten, reichte es aus, die Experimente auf einem System durchzufuhren, beidem die Netzwerkkommunikation der Peers uber die Loopback-Adresse localhost er-folgt. Hierzu wurde ein PC mit 3GHz Intel Pentium IV CPU, sowie Java Version 1.4.2verwendet. Neben den in dieser Arbeit durchgefuhrten Experimenten wurden weite-re Experimente durchgefuhrt, bei denen Chord in einem realen Netzwerk eingesetztwurde [8, 9].

5.1 Der statische Chord-Ring

Ziel dieses Abschnitts ist die Analyse der Durchfuhrung eines Lookups im statischenChord-Ring. Das Augenmerk liegt dabei auf der Lange des Suchpfades, sowie der furden Lookup benotigten Zeit.

5.1.1 Lookups im statischen Chord-Ring

Zur Untersuchung der Lookups im statischen Chord-Ring wurden Chord-Ringe mitunterschiedlicher Peeranzahl N=5, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 32, 48,64 instantiiert. Die ChordID der Peers wurde zufallig gewahlt. Fur jede Peeranzahln ∈ N wurden von jedem der n Peers aus, 5001 zufallig gewahlte Schlussel gesucht.Die Suche erfolgte dabei in Runden, wobei in jeder Runde nacheinander von jedem der

55


n Peers ein Schlussel gesucht wurde. Insgesamt wurden also in den 5001 Runden k =n∗5001 Schlussel gesucht. Fur jeden Schlussel wurde dabei die Lange des Suchpfadesund die Suchdauer ermittelt.

Dauer der Suche

Zur Betrachtung der Suchdauer wurden fur jede Peeranzahl n ∈ N eine Messreihe er-stellt. Anschließend wurde die Suchdauer von allen k = n∗5001 gesuchten Schlusselnausgewertet und das 25%-Quartil, der Median, das 75%-Quartil, sowie das arithme-tische Mittel von allen k Suchdauern gebildet. Abbildung 5.1 stellt die Ergebnissegrafisch dar.

Je großer die Pfadlange bei der Durchfuhrung eines Lookups ist, je mehr Peer habenden Lookup weitergeleitet. Da jede Weiterleitung eine gewisse Zeit beansprucht, istdie mit der Anzahl der Peers steigende Dauer zur Durchfuhrung eines Lookups einerstes Indiz dafur, dass mit steigender Peeranzahl auch die die Pfadlange einer Suchetatsachlich ansteigt.

0

20

40

60

80

100

120

140

160

180

0 10 20 30 40 50 60 70

Peeranzahl

Lo

oku

pzeit

[m

s]

25%-Quartil Median 75%-Quartil Mittel

Abbildung 5.1: Durchschnittlich Suchdauer im statischen Chord-Ring

Da die Peers alle auf einem System ausgefuhrt wurden, und kein echtes Netzwerk ver-

56


wendet wurde, sagen die gemessenen Zeiten jedoch nichts uber die Zeiten aus, wennChord in einem echten Netzwerk eingesetzt wird. In einem echten Netzwerk kann esso z. B. vorkommen, dass nicht alle Verbindungen zwischen den Peers die Daten mitder gleichen Geschwindigkeit ubertragen, so dass es hier zu Zeitverzogerungen unddamit zu langeren Lookup-Zeiten kommen kann.

Lange des Suchpfades

Zur Messung der Lange des Suchpfades wurden fur jedes n ∈ N jeweils 10 Messrei-hen erstellt. Insgesamt wurden also fur jede Peeranzahl k = 10 ∗ n ∗ 5001 zufalligeSchlussel gesucht. Bei der Auswertung wurden dann fur jedes n ∈ N die aufgetrete-nen Pfadlangen L aus allen 10 Messreihen bestimmt. Im Anschluss daran wurden furjedes l ∈ L alle Suchen mit der entsprechenden Pfadlange gezahlt. Abbildung 5.2 dieErgebnisse fur n=8, 16, 32, 48, 64 Peers.

8 16 32 48 64

Peers

An

zah

l d

er

Su

ch

en

Pfadlänge 0 1 2 3 4 5 6 7

Abbildung 5.2: Pfadlange: Suche im statischen Chord-Ring (absolut)

In dieser Abbildung bestatigt sich, dass die Pfadlange mit wachsender Peeranzahlansteigt. Dabei steigt die Pfadlange wie erwartet logarithmisch zur Anzahl der Peers.So betragt z. B. die ermittelte maximale Pfadlange fur Chord-Ringe mit 8 Peers4 Schritte, mit 16 Peers 5 Schritte und fur Chord-Ringe mit 32 Peers 6 Schritte.

57


Die Verteilung der auftretenden Pfadlangen entspricht dabei ungefahr einer Gauß-Verteilung. Die absolute Anzahl der Suchen der Pfadlange l wachst mit steigenderPeeranzahl n, da fur jede Messreihe 10 ∗ n ∗ 5001 Schlussel gesucht wurden. DiePfadlange L = 0 entsteht, da ein Peer auch selbst fur den von ihm gesuchten Schlusselzustandig sein kann und deshalb keinen anderen Peer befragen muss.

Chord verspricht, dass die Pfadlange fur Suchen in einem Chord-Ring mit n Peersmit hoher Wahrscheinlichkeit O(log n) betragt. Um dies zu uberprufen wurde furjedes n der Anteil aller innerhalb der Pfadlange l erfolgreichen Suchen berechnet.Abbildung 5.3 stellt die Ergebnisse fur Chord-Ringe mit n=8, 16, 32, 48, 64 Peersdar.1

0%

10%

20%

30%

40%

50%

60%

70%

80%

90%

100%

110%

0 1 2 3 4 5 6 7 8

Pfadlänge

An

teil

der

been

dete

n S

uch

en

8 16 32 48 64

Abbildung 5.3: Pfadlange: Suche im statischen Chord-Ring (prozentual)

Hierbei stellte sich heraus, dass der Anteil der erfolgreichen Suchen mit Erreichen derPfadlange bl = log nc in fast allen Fallen mehr als 99% betragt. Es wird also nur fureinen sehr geringen Teil der Suchen eine großere Pfadlange benotigt. Die Pfadlangefur Suchen liegt also mit hoher Wahrscheinlichkeit in O(log n).

1Eine Auswertung des Experiments in tabellarischer Form bietet Tabelle B.1 in Anhang B.

58


5.1.2 Nachrichtenaufkommen durch Lookups

Nachdem im Abschnitt 5.1.1 gezeigt wurde, dass ein Lookup mit hoher Wahrschein-lichkeit nach O(log n) Schritten beendet ist, befasst sich dieser Abschnitt nun damit,wie viele Nachrichten insgesamt fur eine Suche benotigt werden.

Zur Zahlung der Lookup-Nachrichten, die insgesamt im Chord-Ring versendet wer-den, wurde ein Experiment durchgefuhrt. Da die Pfadlange und somit die Anzahl derfur einen Lookup benotigten Nachrichten von der Anzahl der Peers abhangt, wurdenMessreihen fur die Menge der Peers N=5, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28,32, 48, 64 durchgefuhrt. Die ChordIDs der Peers waren dabei zufallig gewahlt. Beider Durchfuhrung des Experiments wurden in jedem Chord-Ring der Große n ∈ N

von jedem Peer je 5001 zufallig gewahlte Schlussel gesucht. Uber die Dauer des Ex-periments wurden fur jeden Peer die Anzahl der von ihm weitergeleiteten Lookupssowie die Anzahl der von ihm gesuchten Schlussel gezahlt.

Wie in Abschnitt 5.1.1 bereits erwahnt, kann ein Peer auch selbst fur den von ihmgesuchten Schlussel verantwortlich sein. Deshalb muss er nicht fur alle der 5001 vonihm gesuchten Schlussel einen Lookup durchfuhren. Aus diesem Grund wurde au-ßerdem fur jeden Peer die Anzahl der Schlussel gezahlt, fur die der Peer tatsachlicheinen Lookup durchfuhren musste.

Ein Problem bei diesem Experiment stellte das Aktualisieren der Fingertabelle dar,da hierbei ebenfalls nach Schlusseln gesucht wird.2 Die Anzahl der Aktualisierungender Finger, und die damit einhergehenden Lookup-Nachrichten, nehmen mit der Dau-er des Experiments zu. Um die Ergebnisse aus den Einzelexperimenten miteinandervergleichen zu konnen, musste jedoch in jedem Experiment von jedem Peer die glei-che Anzahl Schlussel gesucht werden. Da mit steigender Peeranzahl im Chord-Ringjedoch insgesamt mehr Schlussel gesucht wurden, nahm die Dauer der Experimenteund damit die Anzahl der durch die Aktualisierung der Fingertabelle verursachtenLookups zu.

Aus diesem Grund wurden fur dieses Experiment statische Chord-Ringe verwendet.Da sich diese nicht verandern, war es moglich fur jeden Peer die Fingertabelle ein-malig zu berechnen und anschließend die Aktualisierung der Finger abzuschalten.3

2vgl.: Abschnitte 2, 3.3.5 und 4.1.33Ein Abschalten der Stabilisierung wurde trotz der Verwendung statischer Chord-Ringe nicht durch-

gefuhrt, da sie die Ergebnisse des Experiments nicht beeinflusst.

59


Da eine Nachricht mit hoher Wahrscheinlichkeit maximal O(log n) mal weitergelei-tet wird, betragt die Anzahl der Nachrichten, die fur einen Lookup benotigt wer-den O(log n). Sucht eine Peer nun nach k Schlusseln, so werden dafur k ∗ O(log n)Lookup-Nachrichten benotigt. Suchen alle n Peers nach k Schlusseln, so werden dafurinsgesamt n∗k ∗O(log n) Lookup-Nachrichten gebraucht. Sind die Peers gleichmaßiguber den Chord-Ring verteilt, so ist mit hoher Wahrscheinlichkeit jeder der Peers furk = k∗n

n der gesuchten Schlussel verantwortlich. Ferner wird jeder Peer die gleicheAnzahl an Nachrichten weiterleiten.

Bei der Auswertung des Experiments wurde deshalb das arithmetische Mittel aus denvon den einzelnen Peers ermittelten Werten gebildet. Dies erfolgte fur die insgesamtvon einem Peer gesendeten Nachrichten (gesamt), die von einem Peer gestellten Loo-kups (erzeugt) und die von einem Peer weitergeleiteten Nachrichten (weitergeleitet).Dabei gilt: gesamt = erzeugt + weitergeleitet

0

2000

4000

6000

8000

10000

12000

14000

16000

0 10 20 30 40 50 60 70

Peeranzahl

Lo

ok

up

-Na

ch

ric

hte

n p

ro P

ee

r

gesamt erzeugt weitergeleitet O(log n)

Abbildung 5.4: Nachrichtenanzahl (KEY LOOKUP)

Abbildung 5.4 zeigt, dass die Anzahl der Lookup-Nachrichten pro Peer (gesamt) lo-garithmisch mit der Anzahl n der im Chord-Ring vorhandenen Peers ansteigt.

Sind n Peers gleichmaßig im Chord-Ring verteilt, und werden in diesem k zufalliggewahlte Schlussel gesucht, so ist jeder der n Peer mit hoher Wahrscheinlichkeit fur

60

5.2 Der dynamische Chord-Ring

genau einen Schlussel verantwortlich. Werden in einem Chord-Ring mit n Peers voneinem einzigen Peer k zufallig gewahlte Schlussel gesucht, so muss dieser Peer mithoher Wahrscheinlichkeit fur nur k-1 Schlussel einen Lookup durchfuhren. Bei einemder k Schlussel wird er jedoch direkt entscheiden konnen, dass sein Nachfolger derzustandige Peer ist.

In der vorliegenden Implementierung pruft ein Peer jedoch zusatzlich, ob er nichtselbst der verantwortliche Peer ist. Dies ist ohne weiteres moglich, da ein Peer nichtnur seinen Nachfolger, sondern auch seinen Vorganger kennt. Durch dieses Vorgehenmuss der Peer dann nur noch fur k-2 Schlussel einen Lookup durchfuhren. Insgesamtnimmt die Anzahl der tatsachlich durchzufuhrenden Lookups mit der Anzahl derPeers im Chord-Ring zu, wie die Kurve erzeugt in Abbildung 5.4 zeigt.Die Kurve zeigt ebenfalls, dass sich die Anzahl der tatsachlich durchzufuhrendenLookups mit steigender Peeranzahl n an k = 5001 annahert, da ein Peer fur die kzufallig gewahlten Schlussel in n−2

n ∗ k Fallen einen Lookup durchfuhren muss.Hier ist auch zu erkennen, dass in Chord-Ringen mit vielen Peers, kein großer Vor-teil entsteht, wenn ein Peer zusatzlich entscheidet, ob er selbst fur einen Schlusselverantwortlich ist. Wurde er dies nicht tun und nur entscheiden, ob sein Nachfolgerfur einen gesuchten Schlussel verantwortlich ist, so musste der Peer in n−1

n ∗ k Falleneinen Lookup durchfuhren.In diesem Fall wurden n−1

n−2 mal mehr Lookup-Nachrichten erzeugt werden. Da aberfur Chord-Ringe mit vielen Peers

limn→∞

n− 1n− 2

= 1

gilt, ist der Vorteil praktisch nur fur Chord-Ringe mit wenigen Peers vorhanden.


In nachsten Schritt wurden dynamische Chord-Ringe untersucht. Hierbei wurdensowohl die Durchfuhrung von Lookups, als auch die Korrektheit des Stabilisierungs-protokolls untersucht.

5.2.1 Lookups im dynamischen Chord-Ring

Wie bei den Experimenten zum statischen Chord-Ring wurden bei diesem Experi-ment Chord-Ringe mit unterschiedlicher Peeranzahl N=8, 16, 32, 48, 64 unter-sucht. Die ChordID der Peers wurde wieder zufallig gewahlt. Im Gegensatz zum sta-

61


tischen Chord-Ring wurden jedoch wahrend der gesamten Laufzeit des Experimentsneue Peers hinzugefugt bzw. es verließen Peers den Chord-Ring. Um die Peeranzahlwahrend der Dauer der Experimente konstant zu halten wurde ein Peeraustauschausgefuhrt, d. h. es wurde immer dann ein neuer Peer hinzugefugt, wenn ein andererden Chord-Ring verließ. Der Peer, der den Chord-Ring verließ, wurde aus den n ∈ N

Peers des Chord-Rings zufallig ausgewahlt, d. h. jeder Peer verließ mit der Wahr-scheinlichkeit p = 1

N den Chord-Ring.

Im Folgenden wird die Zeitdauer, die zwischen dem Austauschen zweier Peers liegt, alsJoin-Leave-Zeit bezeichnet. Die sich daraus ergebende Frequenz, mit der Peers aus-fallen und hinzukommen, wird mit Join-Leave-Frequenz bezeichnet. Die Join-Leave-Frequenz gibt die Veranderungsrate des Chord-Rings an. Dabei gilt:Join− Leave− Frequenz = 1

Join−Leave−Zeit .

Um untersuchen zu konnen, wie sich unterschiedliche Join-Leave-Zeiten auf die Loo-kups auswirken, wurden fur jede Peeranzahl n ∈ N Messreihen mit den Join-Leave-Zeiten T=1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 20, 25, 30, 35 Sekunden durchgefuhrt. Furjedes Tupel (N,T) wurden dann jeweils 5 Chord-Ringe instantiiert. In jedem Chord-Ring wurden dann nacheinander 5001 Schlussel gesucht. Fur jeden neuen gesuchtenSchlussel wurde dabei ein Peer als suchender Peer zufallig aus den vorhandenen Peersbestimmt.Wahrend der Experimente wurden von jedem Peer alle 1.5 Sekunden eine Stabili-sierung durchgefuhrt, sowie ein Finger aktualisiert. Der Exponent der Chord-Ringsbetrug m = 16, d. h. jeder Peer hatte 16 Finger.

Fehlgeschlagene Versuche

Abbildung 5.5 zeigt den Anteil der Schlussel, fur die der verantwortliche Peer in-nerhalb der maximalen Suchdauer von 35 Sekunden oder der maximalen Pfadlange2m nicht gefunden werden konnte. Sie zeigt, dass die Anzahl der fehlgeschlagenenLookups fur gleich bleibende Join-Leave-Zeiten bei steigender Peeranzahl abnimmt.Ebenso sinkt die Anzahl fehlgeschlagener Lookups, wenn die Peeranzahl konstantbleibt, die Join-Leave-Frequenz jedoch abnimmt, d. h. die Join-Leave-Zeit vergroßertwird.Ein Teil der fehlgeschlagenen Versuche lasst sich auf die Begrenzung der Pfadlangeauf 2m zuruckfuhren.4 Der Anteil den diese aber an den insgesamt fehlgeschlagenen


62


0

0.1

0.2

0.3

0.4

0.5

0.6

0 5 10 15 20 25 30 35 40

Join-Leave-Zeit [s]

nic

ht

gefu

nd

en

e S

ch

lüssel

[%]

8 Peers 16 Peers 32 Peers 48 Peers 64 Peers

Abbildung 5.5: Anteil fehlgeschlagener Suchen im dynamischen Chord-Ring

Versuche haben ist jedoch sehr gering. Diese Vermutung legt zumindest die Verteilungder Pfadlangen fur Lookups in dynamischen Chord-Ringen, wie sie in den Abbildun-gen 5.7 und 5.8 dargestellt sind, nahe.

Der Großteil der fehlgeschlagenen Versuche lasst sich jedoch auf die Korrektheit derFingertabellen zuruckfuhren. Je mehr Eintrage der Fingertabelle nicht korrekt sindund/oder auf ausgefallene Peers verweisen, je großer wird die Wahrscheinlichkeit,dass es im Laufe eines Lookups zu Zyklen im Suchpfad kommt. Hierdurch kommtes zur Uberschreitung der maximalen Suchdauer, so dass timeouts auftreten. Zu-dem birgt eine nicht korrekten Fingertabelle einen gewissen Ruckkopplungseffekt, dazur Aktualisierung der Fingertabelle Lookups durchgefuhrt werden, die ebenfalls mithoherer Wahrscheinlichkeit fehlschlagen.

Wenn z. B. alle tfix = 1.5 Sekunden ein Finger aktualisiert wird, dauert es bei 16 Fin-gern mindestens 24 Sekunden bis alle Finger aktualisiert wurden.5 Wenn jeder Peermit der Wahrscheinlichkeit p = 1

N ausfallt und pro Sekunde ein Peer ausgetauschtwird (tjl = 1), dann werden in diesen 24 Sekunden insgesamt 24 Peers ausgetauscht.

5Wird auf Grund der Dynamik, der fur einen Schlussel zustandige Peer nicht gefunden, kann die

komplette Aktualisierung der Finger langer dauern.

63


In einem Chord-Ring mit n = 8 Peers wird so in 24 Sekunden mit hoher Wahrschein-lichkeit jeder Peer mindestens einmal ausgetauscht, so dass es sehr wahrscheinlichist, dass die Fingertabelle nicht korrekt ist.

Ein Maß fur die Korrektheit der Fingertabelle ist die Anzahl der nicht korrektenFinger Λ.Sei: n = Anzahl der Peers

m = Anzahl der F inger

tfix = Finger Aktualisierungsintervall

tjl = Join− Leave− Zeit

Dann berechnet sich die Anzahl der nicht korrekten Finger:

Λ = min

m ∗ tfix

tjl, n

Im obigen Beispiel sind somit Λ = 8 Finger nicht korrekt gesetzt.

Wie in [43] gezeigt wird, sind in einem Chord-Ring mit n Peers jedoch nur O(log n)Eintrage der Fingertabelle tatsachlich verschieden. Es ist also moglich, dass sich zweinicht korrekte Eintrage der Fingertabelle auf den gleichen Peer beziehen. Das MaßΛ muss somit verfeinert werden.

Sei: n = Anzahl der Peers im Chord−Ring

Dann ist das Maß fur die Korrektheit der Fingertabelle:

λ =log n

Λ=

log n ∗ tjlm ∗ tfix

Die Korrektheit der Fingertabelle λ steigt also je mehr Peers im Chord-Ring vorhan-den sind, da mit steigender Peeranzahl mehr Eintrage der Fingertabelle tatsachlichunterschiedlich sind. Hierdurch wirkt sich der Ausfall eines Peers im besten Fall dannnur noch auf einen Eintrag der Fingertabelle aus. So betragt das Maß fur die Kor-rektheit der Fingertabelle in einem Chord-Ring mit n = 16 Peers, bei tjl = 1 Sekundeund tfix = 1.5 Sekunden λ = 1

6 , wahrend im obigen Beispiel mit n = 8 Peers λ = 18

betragt.Außer mit einer steigenden Peeranzahl erhoht sich λ, je großer die Join-Leave-Zeitenim Vergleich zum Aktualisierungsintervall der Finger werden. Je großer der Quotienttjl

tfixwird, desto mehr Finger werden zwischen dem Austausch zweier Peers aktuali-

siert, wodurch sich wiederum die Korrektheit der Fingertabelle verbessert. So betragt

64


im Chord-Ring aus dem obigen Beispiel das Maß fur die Korrektheit der Fingerta-belle λ = 1

8 . Werden die Peers nun nicht mehr so haufig ausgetauscht, sondern z. B.nur alle tjl = 2 Sekunden so steigt das Maß fur die Korrektheit der Fingertabelle aufλ = 1

4 . Allgemein gilt: Je großer λ desto korrekter die Fingertabelle.

Dauer der Suche

Bei der Auswertung der Experimente wurden fur jedes Tupel (N,T) das arithmeti-sche Mittel uber alle Suchdauern der in den 5 Einzelexperimenten gesuchten Schlusselgebildet. Abbildung 5.6 zeigt, dass die Suchdauer abnimmt, je großer die Join-Leave-Zeit wird, d. h. je mehr Zeit zwischen dem Austausch zweier Peers vergeht. Umgekehrtnimmt die durchschnittliche Suchdauer mit kurzeren Join-Leave-Zeiten zu, da bei ho-her Veranderungsrate die Eintrage der Fingertabelle mit hoherer Wahrscheinlichkeitnicht korrekt sind als bei niedrigen Veranderungsraten. Dadurch dass die Eintrageder Fingertabelle bei kurzen Join-Leave-Zeiten weniger korrekt sind, verschiebt sichdie Verteilung der Pfadlangen so, dass der Anteil der Suchen mit großerer Pfadlangehoher ist als bei einer großen Join-Leave-Zeit. Auch treten die Ausreißer bei denPfadlangen, d. h. Pfadlangen die deutlich großer als log n sind, nur bei kleinen Join-Leave-Zeiten auf. Neben der Abhangigkeit der durchschnittlichen Suchdauer von der

0

50

100

150

200

250

300

350

400

0 5 10 15 20 25 30 35 40

Join-Leave-Zeit [s]

Lo

oku

p-D

au

er

[ms]

8 Peers 16 Peers 32 Peers 48 Peers 64 Peers

Abbildung 5.6: Durchschnittliche Suchzeit fur dynamische Chord-Ringe

65


Join-Leave-Zeit, ist in Abbildung 5.6 eine Abhangigkeit von der Anzahl der im Chord-Ring vorhandenen Peers zu erkennen. So nimmt die durchschnittliche Suchdauer mitsteigender Peeranzahl zu. Dies hangt wiederum damit zusammen, dass die Pfadlangemit der Anzahl der Peers im Chord-Ring wachst.

Lange des Suchpfades

Im Vergleich zu den Lookups im statischen Chord-Ring andert sich die Lange derSuchpfade in dynamischen Chord-Ringen nicht wesentlich. Bei Suchen in Chord-Ringen mit kurzen Join-Leave-Zeiten treten vereinzelt großere Pfadlangen auf. Dieselassen sich auf nicht mehr aktuelle Eintrage in den Fingertabellen zuruckfuhren.Wie bei Lookups im statischen Chord-Ring entspricht auch hier die Verteilung derPfadlangen wieder ungefahr einer Gauß-Verteilung.

16 Peers

1

10

100

1000

10000

0 5 10 15 20 25 30

Pfadlänge

Gesam

tan

zah

l

Join/Leave [s] 1 2 3 4 5 6 7 8 9 10 15 20 25 30 35

Abbildung 5.7: Pfadlange fur 16 Peers in dynamischen Chord-Ringen mit verschie-denen Join-Leave-Zeiten

An dieser Stelle werden exemplarisch die Pfadlangen fur Chord-Ringe mit 16 bzw.64 Peers in den Abbildungen 5.7 und 5.8 dargestellt.6 Die Abbildungen zeigen, dassdie Pfadlangen fur Lookups auch fur dynamische Chord-Ringe immer noch mit hoher

6Die Pfadlangen fur Chord-Ringe mit 8, 32 und 48 Peers befinden sich im Anhang B.

66


64 Peers

1

10

100

1000

10000

0 5 10 15 20 25 30

Pfadlänge

Gesam

tan

zah

l

Join/Leave [s] 1 2 3 4 5 6 7 8 9 10 15 20 25 30 35

Abbildung 5.8: Pfadlange fur 64 Peers in dynamischen Chord-Ringen mit verschie-denen Join-Leave-Zeiten

Durchschnittliche Pfadlängen

0

1

2

3

4

5

0 10 20 30 40 50 60 70

Peers

du

rch

sc

hn

ittl

ich

e P

fad

län

ge

t_jl = 10 Sekunden t_jl = 35 Sekunden log n

Abbildung 5.9: Durchschnittliche Pfadlange in dynamischen Chord-Ringen

67


Wahrscheinlichkeit in O(log n) liegen, wenngleich die Pfadlangen im Schnitt ein weniglanger sind. So sind im statischen Chord-Ring mit 16 Peer die meisten Suchen nacheiner Pfadlange von 5 Schritten erfolgreich, wahrend in dynamischen Chord-Ringenmit 16 Peers die meisten Suchen erst mit der Pfadlange 6 abgeschlossen sind. Dass diePfadlangen wie im Fall von statischen Chord-Ringen logarithmisch zur Peeranzahlansteigen, zeigt Abbildung 5.9. Diese bildet die durchschnittliche Pfadlange fur dieJoin-Leave-Zeiten tjl = 10 und tjl = 35 ab.

5.2.2 Systemstabilitat

Dieser Teil untersucht die Korrektheit des Stabilisierungsprotokolls. Hierzu wird un-tersucht, ob es unter bestimmten Voraussetzungen dazu kommen kann, dass das Sta-bilisierungsprotokoll die Korrektheit der Nachfolger nicht mehr gewahrleisten kann.So besitzt Chord u. a. die Eigenschaft, dass die Halfte aller Peers gleichzeitig aus-fallen kann, der Chord-Ring jedoch verbunden bleibt.7 Neben der experimentellenUberprufung dieser Eigenschaft untersucht dieser Abschnitt die Korrektheit des Sta-bilisierungsprotokoll auf Abhangigkeit von folgenden Einflussen: Anzahl der Peersim Chord-Ring, Zeit zwischen zwei Ausfuhrungen des Stabilisierungsprotokolls undVeranderungsrate des Chord-Rings.

Ein recht intuitives Maß, welches von den Faktoren Peeranzahl, Zeit zwischen zweiStabilisierungen und Veranderungsrate eines Chord-Rings abhangt, ist die Halbwert-zeit (half-life) eines P2P-Systems [24]. Diese ist wie folgt definiert:

”Gegeben sei zur Zeit t ein P2P-System mit N aktiven Peers. Die doubling time vont ist die Zeit, die von t aus vergeht, bis N zusatzliche Peers hinzugekommen sind. Diehalving time von t ist die Zeit, die von t aus vergeht, bis sich die Anzahl der Peershalbiert hat. Die half-life von t ist die kleinere der beiden Zeiten doubling time undhalving time. Die half-life eines P2P-Systems ist das Minimum aller half-life Zeitent.“

Uber die Halbwertzeit lasst sich folgende Aussage treffen:Ein beliebiges P2P-System mit N Peers bleibt dann verbunden, wenn fur eine beliebi-ge Sequenz aus Joins und Leaves jeder Peer innerhalb der half-life Zeit τ mindestensΩ(log N) mal benachrichtigt wird [24].


68


Bei Chord erfolgt diese Benachrichtigung der Peers durch das Stabilisierungsproto-koll. Zur Uberprufung des Stabilisierungsprotokolls auf die Abhangigkeit von Peeran-zahl, der Veranderungsrate sowie der Zeit zwischen zwei Stabilisierungen, wurdenverschiedene Experimente durchgefuhrt. In allen durchgefuhrten Experimenten wur-de dabei der gleiche grundlegende Versuchsaufbau V1 verwendet:

Zu Beginn des Experiments wurden zunachst stabile Chord-Ringe der Großen N=8,16, 32, 64, 128 erzeugt. Die ChordID’s der Peers wurden zufallig gewahlt. Im Ver-lauf des Experiments wurde bei jeder Stabilisierung die Liste der ersten j = 16Nachfolger vom Nachfolger bezogen und der Vorganger auf Erreichbarkeit gepruft.Aus den Chord-Ringen wurden dann im Abstand von tjl ∈ T =0.25, 0.5, 0.75, 1,2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 20, 25, 30, 35 Sekunden ein Peer entfernt. Damitsich die Große des Chord-Rings nicht anderte, wurde jeweils nach der Entfernungeines Peers ein neuer Peer hinzugefugt. Der Peer, der entfernt wurde, wurde mit derWahrscheinlichkeit p = 1

N aus allen Peers des Chord-Rings ausgewahlt. Der Peer,welcher den Nachfolger des neu hinzugekommenen Peers bestimmte, wurde ebenfallsmit der Wahrscheinlichkeit p aus den verbleibenden Peers ausgewahlt.

Fur jedes Tupel (N,T) wurden jeweils 20 Experimente durchgefuhrt, wobei die Dauerder Phase in der die Peers ausgetauscht wurden auf 10 Minuten beschrankt war. NachBeendigung der Austauschphase wurden zunachst N Stabilisierungen abgewartet, sodass die Vorganger- und Nachfolgerbeziehungen vom Stabilisierungsprotokoll korri-giert werden konnten. Danach wurde die Topologie des resultierenden Chord-Rings ineiner XML-Datei im GraphXML-Format [17] gespeichert. Hierzu wurden von jedemPeer dessen ChordID, sowie sein Vorganger und Nachfolger bestimmt.

Bei der Auswertung wurden fur jedes Tupel (N,T) die resultierenden XML Dateienanalysiert. Hierbei wurde ermittelt, wie viele Peers im Chord-Ring verblieben warenund ob alle Peers die korrekten Vorganger und Nachfolger besaßen. Ein Chord-Ring,bei dem alle Peers den korrekten Vorganger bzw. Nachfolger besitzen, wird im Fol-genden intakter Chord-Ring genannt.

Um zu analysieren inwiefern es sich auf die Korrektheit des Stabilisierungsprotokollsauswirkt, ob die Peers ausfallen oder den Chord-Ring absichtlich verlassen, wurdenauf Grundlage des Versuchsaufbaus V1 zunachst zwei Experimente mit der gleichenDauer von tstab = 1.5 Sekunden zwischen den Stabilisierungen durchgefuhrt. Im ers-ten Experiment, dem Join-Leave-Fall, verließen die Peers den Chord-Ring absichtlich

69


und informierten vorher ihre Nachbarn.8 Im zweiten Experiment, dem Join-Fail-Fall,fielen die Peers einfach aus. Im Anschluss daran wurde untersucht, inwiefern sich un-terschiedliche Stabilisierungszeiten tstab auswirken. Hierzu wurde auf Grundlage vonV1 ein weiteres Experiment durchgefuhrt, wobei die Peers ohne Ankundigung ausfie-len und tstab = 3 Sekunden betrug. Im vierten und letzten Experiment wurde dannnoch das Funktionieren des Stabilisierungsprotokolls im Extremfall untersucht. Da-zu wurde untersucht, ob der Chord-Ring intakt bleibt, wenn die Halfte aller Peersgleichzeitig ausfallt.9 Im Folgenden werden die Ergebnisse der einzelnen Experimentegenauer beschrieben.

Stabilitat im Join-Leave-Fall (Stabilisierungsintervall tstab = 1.5s)

Wie bereits beschrieben, wurde dieses Experiment auf Grundlage von VersuchsaufbauV1 mit der Zeit tstab = 1.5 Sekunden zwischen den Stabilisierungen durchgefuhrt. DiePeers verließen dabei den Chord-Ring mit Vorankundigung.

0

0.2

0.4

0.6

0.8

1

1.2

100 1000 10000 100000Join-Leave-Zeit [ms]

An

teil in

tak

ter

Ch

ord

-Rin

ge

8 16 32 48 64 128

Abbildung 5.10: Stabilitat im Join-Leave-Fall, tstab = 1.5s

Die Ergebnisse des Experiments in Abbildung 5.10 zeigen, dass die Chord-Ringemit mehr als 16 Peers auch dann mit hoher Wahrscheinlichkeit intakt bleiben, wenn

8vgl.: Abschnitt 3.3.4 und 4.2.19vgl.: Abschnitt 3.3.3

70


die Zeitdauer zwischen dem Ausfallen zweier Peers mit tjl = 0.25 Sekunden sehrklein wird, d. h. pro Sekunde 4 Peers ausgetauscht werden. Die Ausnahme bildendabei Chord-Ringe mit 8 Peers. Hier ist der Anteil der intakten Ringe fur sehr hoheVeranderungsraten sehr gering. Ab einer Join-Leave-Zeit von 5 Sekunden sind dieErgebnisse jedoch denen von Chord-Ringen mit 16 oder mehr Peers vergleichbar.

0

20

40

60

80

100

120

140

160

180

100 1000 10000 100000Join-Leave-Zeit [ms]

vo

m C

ho

rd-R

ing

getr

en

nte

Peers

[ab

so

lut]

8 16 32 48 64 128

Abbildung 5.11: Vom Ring getrennte Peers im Join-Leave-Fall, tstab = 1.5s

Abbildung 5.11 stellt die absolute Anzahl der vom Chord-Ring getrennten Peers dar.Obwohl, wie Abbildung 5.10 zeigt, die Chord-Ringe auch fur kleine tjl intakt blei-ben, so sinkt die Anzahl der Peers, die im Chord-Ring verblieben sind, je kleiner tjl

wird. Die absolute Anzahl der wahrend des Experiments vom Chord-Ring getrenntenPeers, also der Peers, die keinen Nachfolger mehr besaßen, wird somit also großer jekleiner tjl wird. Umgekehrt wird die Anzahl der vom Chord-Ring getrennten Peerskleiner je großer tjl.

Ein Peer x wird dann vom Chord-Ring getrennt, wenn er den Chord-Ring geradeerst betreten hat, noch nicht voll in den Chord-Ring integriert ist und vor allemnoch keine Nachfolgerliste bezogen hat. In diesem Fall besitzt x nur einen, namlichseinen direkten Nachfolger x.successor. Fallt dieser aus, so besitzt x keine weiteren

71


Nachfolger mehr und wird folglich vom Chord-Ring getrennt.

Im Gegensatz zum negativen Zusammenhang zwischen der Anzahl der vom Chord-Ring getrennten Peers und der Join-Leave-Zeit tjl, lasst sich aus den Ergebnissendes Experiments jedoch keine direkte Abhangigkeit zwischen der Anzahl der vomChord-Ring getrennten Peers, und der Peeranzahl selbst herleiten. So werden vonChord-Ringen mit vielen Peers ungefahr genau so viele Peers getrennt wie von Chord-Ringen mit wenigen Peers. Die Ausnahme bilden hier Chord-Ringe mit 8 Peers. Dadiese nicht intakt sind, werden alle ihre Peers als vom Chord-Ring getrennte Peersgezahlt. Da in Chord-Ringen mit vielen Peers ahnlich viele Peers vom Chord-Ringgetrennt werden wie in Chord-Ringen mit wenigen Peers, bedeutet das, dass vonChord-Ringen mit wenigen Peers bei gleicher Join-Leave-Zeit tjl im Verhaltnis zurGroße des Rings mehr Peers getrennt werden als bei Chord-Ringen mit vielen Peers.

Als Besonderheit ist noch zu erwahnen, dass in Chord-Ringen mit 8 bzw. 16 Peersuberhaupt keine Peers vom Chord-Ring getrennt werden durften, da in einer 16 Peerslangen Nachfolgerliste alle anderen Peers erfasst sein mussten. Hier kommt zum Tra-gen, dass ausgefallene Peers nicht direkt aus allen Nachfolgerlisten entfernt werden.10

Gerade bei hohen Veranderungsraten sind dann viele Eintrage der Nachfolgerlistenicht mehr aktuell, so dass die Wahrscheinlichkeit, dass ein Peer keinen Nachfolgermehr ermitteln kann, steigt.

Stabilitat im Join-Fail-Fall (Stabilisierungsintervall tstab = 1.5s)

Wie bereits beschrieben, wurde auch in diesem Experiment vom Versuchsaufbau V1

ausgegangen, wobei die Zeit zwischen zwei Stabilisierungen erneut tstab = 1.5 Sekun-den betrug. Erneut wurde eine vollstandige Messreihe durchgefuhrt, wobei die Peersden Chord-Ring diesmal ohne Vorankundigung verließen.

Abbildung 5.12 stellt die Auswertung dieses Experiments dar. Auch hier sind Chord-Ringe mit mehr als 16 Peers mit hoher Wahrscheinlichkeit intakt, wobei Chord-Ringemit 8 Peers erneut die Ausnahme bilden. Ab einer Join-Leave-Zeit von 15 Sekundensind jedoch auch hier die Ergebnisse mit Chord-Ringen mit 16 oder mehr Peersvergleichbar.Der negative Zusammenhang zwischen der Anzahl der vom Chord-Ring getrenntenPeers und der Join-Leave-Zeit tjl liegt auch in diesem Experiment vor. Auch in die-


72


0

0.2

0.4

0.6

0.8

1

1.2

100 1000 10000 100000Join-Fail-Zeit [ms]

An

teil in

tak

ter

Ch

ord

-Rin

ge

8 16 32 48 64 128

Abbildung 5.12: Stabilitat im Join-Fail-Fall, tstab = 1.5s

0

20

40

60

80

100

120

140

160

180

100 1000 10000 100000Join-Fail-Zeit [ms]

vo

m C

ho

rd-R

ing

getr

en

nte

Peers

[ab

so

lut]

8 16 32 48 64 128

Abbildung 5.13: Vom Ring getrennte Peers im Join-Fail-Fall, tstab = 1.5s

73


sem Fall ist jedoch kein eindeutiger Zusammenhang zwischen der absoluten Anzahlder vom Chord-Ring getrennten Peers und der Anzahl der Peers im Chord-Ring zuerkennen.

Auffallig ist, wie Abbildung 5.13 zeigt, dass sich die Anzahl der vom Chord-Ringgetrennten Peers gegenuber dem Join-Leave-Fall im Join-Fail-Fall nur geringfugigerhoht. Insgesamt kommt es gegenuber dem Join-Leave-Fall zu einer geringen Ver-lagerung der gesamten Kurve nach rechts. Besonders gut ist das an der Kurve fur 8Peers zu erkennen. Diese nahert sich im Join-Fail-Fall erst spater und auch nicht soschnell an die Kurven fur Chord-Ringe ab 16 Peers an.

Die Ankundigung, den Chord-Ring zu verlassen, verbessert das Stabilisierungsproto-koll also nicht wesentlich. Wohl birgt sie aber den Vorteil, dass gespeicherte Schlusselvor Verlassen des Chord-Rings an andere Peers ubertragen werden konnen.

Stabilitat im Join-Fail-Fall (Stabilisierungsintervall tstab = 3s)

Bis jetzt wurde untersucht, wie sich unterschiedliche Veranderungsraten auf Chord-Ringe mit unterschiedlicher Peeranzahl auswirken. Dabei stellte sich heraus, dass dieAnzahl der vom Chord-Ring getrennten Peers geringer wird, je geringer die Verande-rungsrate wird. Daruber hinaus war kein eindeutiger Zusammenhang zwischen derAnzahl der vom Chord-Ring getrennten Peers und der Anzahl der aktiven Peersfestzustellen. Ferner hat sich gezeigt, dass sich die Ankundigung eines Peers, denChord-Ring zu verlassen, nicht wesentlich auf das Stabilisierungsprotokoll auswirkt.

Dieser Abschnitt untersucht nun wie sich die Haufigkeit, mit der das Stabilisierungs-protokoll ausgefuhrt wird, auswirkt. Hierzu wurde erneut ein auf Versuchsaufbau V1

basierendes Experiment durchgefuhrt. Die Peers benachrichtigten die anderen Peersnicht bevor sie ausfielen, die Dauer zwischen zwei Stabilisierungen betrug tstab = 3Sekunden.

Bei der Auswertung zeigte sich erneut das gleiche Ergebnis. So sind Chord-Ringe mit16 oder mehr Peers mit hoher Wahrscheinlichkeit intakt. Erneut sind die Ergebnissefur Chord-Ringe mit 8 Peers erst bei einer Join-Leave-Zeit von 15 Sekunden mit denErgebnissen in Chord-Ringen mit 16 oder mehr Peers vergleichbar. Im Unterschiedzum Fall tstab = 1.5 verlauft die Kurve jedoch anfangs flacher und steigt dann steilan, wobei sie im Fall tstab = 1.5 eher gleichmaßig ansteigt.

Der negative Zusammenhang zwischen der Anzahl der vom Chord-Ring getrenntenPeers und der Join-Leave-Zeit tjl wird durch dieses Experiment erneut bestatigt.

74


0

0.2

0.4

0.6

0.8

1

1.2

100 1000 10000 100000Join-Fail-Zeit [ms]

An

teil in

tak

ter

Ch

ord

-Rin

ge

8 16 32 48 64 128

Abbildung 5.14: Stabilitat im Join-Fail-Fall, tstab = 3s

0

20

40

60

80

100

120

140

160

180

100 1000 10000 100000Join-Fail-Zeit [ms]

vo

m C

ho

rd-R

ing

getr

en

nte

Peers

[ab

so

lut]

8 16 32 48 64 128

Abbildung 5.15: Vom Ring getrennte Peers im Join-Fail-Fall, tstab = 3s

75


Wie in den vorangegangenen Experimenten lasst sich aber auch hier kein eindeutigerZusammenhang zwischen der absoluten Anzahl der vom Chord-Ring getrennten Peersund der Anzahl der Peers im Chord-Ring feststellen.

Des Weiteren verandert sich die Anzahl der vom Chord-Ring getrennten Peers ge-genuber den Experimenten mit tstab = 1.5 nicht wesentlich, wobei auch hier Chord-Ringe mit 8 Peers wieder die Ausnahme bilden. Hier verlauft die Kurve anfangs flacherund fallt dann steil ab, wobei die Anzahl der abgetrennten Peers im Fall tstab = 1.5eher gleichmaßig abnimmt. Dabei bestatigt sich zumindest im Ansatz, dass bei einerhalf-life τ mehr Peers vom Chord-Ring getrennt werden, wenn die Zeit tstab zwischenzwei Benachrichtigungen großer wird.

Stabilitat im Extremfall - Der gleichzeitige Ausfall von 50% der Peers

Eine Eigenschaft von Chord ist es, dass die Halfte aller Peers gleichzeitig ausfallenkann, ohne dass der Chord-Ring zerfallt.11 Diese Eigenschaft wurde fur Chord-Ringemit N=8, 16, 32, 64, 128 Peers in zwei Experimenten uberpruft. Hierzu wurdenjeweils fur jedes n ∈ N jeweils zwei Experimente durchgefuhrt, die wiederum aus 40Einzelexperimente bestanden. Die Lange der Nachfolgerliste jedes Peers betrug dabeik = 16 Eintrage.

Nachdem der Chord-Ring instantiiert und alle Vorganger und Nachfolger korrekt ge-setzt waren, wurde die Halfte aller n Peers wieder aus dem Chord-Ring entfernt. Dieentfernten Peers wurden zufallig gewahlt und verließen den Chord-Ring im erstenExperiment mit und im zweiten Experiment ohne Ankundigung.

Nachdem die Peers entfernt wurden erfolgte eine Wartezeit, so dass jeder der verblie-benen Peers mindestens n-mal das Stabilisierungsprotokoll ausfuhren konnte. NachVerstreichen dieser Zeit wurde die Topologie des resultierenden Chord-Rings wie imVersuchsaufbau V1 beschrieben gespeichert.

Bei der Auswertung der Experimente zeigte sich, dass sowohl im Experiment, indem die Peers den Chord-Ring mit Ankundigung verließen, als auch im Experiment,in dem die Peers den Chord-Ring ohne Ankundigung verließen, in allen Fallen einintakter Chord-Ring mit n

2 aktiven Peers entstanden war.


76

5.3 Bandbreitenverbrauch


Dieser Abschnitt analysiert, wie viel Netzwerkbandbreite von den Peers fur das Ver-senden von Nachrichten benotigt wird. Dabei wird zwischen der durch Lookupsund der durch die Ausfuhrung des Stabilisierungsprotokolls verbrauchten Bandbrei-te unterschieden. Hierbei wurden fur die Durchfuhrung von Lookups die Nachrich-ten KEY LOOKUP und KEY FOUND, und im Fall des Stabilisierungsprotokollsdie Nachrichten GET PREDECESSOR, PREDECESSOR IS, GET SUCCESSORS,SUCCESSORS ARE und NOTIFY gezahlt.12

Zur Messung der versendeten Daten wurden verschiedene Experimente durchgefuhrt.Dabei wurden jeweils Anzahl und tatsachliche Große, der insgesamt versendeten re-levanten Nachrichten bestimmt. Im Gegensatz zu Abschnitt 4.3 bezog sich die Großeder Nachrichten hier jedoch auf die tatsachliche Große der versendeten Nachricht,also inklusive des Overheads, der durch die Verwendung von Java-ObjectStreamsentsteht.13

5.3.1 Bandbreitenverbrauch durch Lookups

Die durch das Versenden von Lookup-Nachrichten genutzte Bandbreite wurde anhandder vorliegenden Implementierung gemessen. eine gesonderte Messung des eingehen-den Verkehrs erfolgte nicht, da die Nachrichten KEY LOOKUP und KEY FOUNDdie gleiche Große besitzen und fur jeden Peer die Summe der bei ihm eingehendenNachrichten gleich der Summe der von ihm gesendeten Nachrichten ist.

Die Peers senden fur jeden von ihnen gesuchten Schlussel jeweils eine NachrichtKEY LOOKUPgen. Ist die Suche erfolgreich, so empfangen sie dafur die NachrichtKEY FOUNDin.

KEY LOOKUPgen = KEY FOUNDin (5.1)

Erhalt ein Peer den Lookup eines anderen Peers, so empfangt er diesen uber dieNachricht KEY LOOKUPin. Nun ist er entweder selbst der verantwortliche Peer, indiesem Fall sendet er KEY FOUNDout, oder er ist nicht verantwortlich und leitetden Lookup an einen seiner Finger weiter. In diesem Fall sendet er die NachrichtKEY LOOKUPfwd.

KEY LOOKUPin = KEY FOUNDout + KEY LOOKUPfwd (5.2)

Die insgesamt gesendeten KEY LOOKUP Nachrichten setzen sich dabei aus den

12vgl.: Abschnitt 4.313vgl.: Abschnitt 4.3

77


selbst erzeugten und den weitergeleiteten Nachrichten zusammen.

KEY LOOKUPout = KEY LOOKUPgen + KEY LOOKUPfwd (5.3)

Insgesamt gilt also, dass die Anzahl der eingehenden Nachrichten der Anzahl derausgehenden Nachrichten entspricht.

KEY LOOKUPin + KEY FOUNDin = KEY LOOKUPout + KEY FOUNDout (5.4)

Da die Pfadlange fur Lookups von der Peeranzahl abhangt, ist auch zu erwarten, dassdie fur Lookups benotigte Bandbreite mit der Anzahl der aktiven Peers ansteigt. Umdies zu uberprufen, wurde die benotigte Bandbreite in statischen Chord-Ringen mitN= 8, 16, 32, 64 aktiven Peers gemessen. Hierbei wurden fur jedes n ∈ N jeweilsin Einzelexperimenten 15 Minuten lang zufallig gewahlte Schlussel nacheinander ge-sucht. Fur jeden Schlussel wurde der suchende Peer zufallig aus den n Peers bestimmt.Die ChordID’s der Peers wurden zufallig gewahlt, so dass die Peers gleichmaßig uberden Chord-Ring verteilt wurden. Durch die zufallige Verteilung der Peers auf demChord-Ring, sowie die zufallige Auswahl des Peers zur Suche eines zufallig gewahl-ten Schlussels ist es sehr wahrscheinlich, dass jeder Peer im Experiment gleich starkbelastet wird.14 Aus diesem Grund wurden bei der Auswertung des Experiments diejeweiligen Durchschnittswerte von allen Experimenten bzw. Peers gebildet.

Zur Durchfuhrung dieses Experiments wurden statische Chord-Ringe verwendet. DieDurchfuhrung eines solchen Experiments in dynamischen Chord-Ringen ist deshalbproblematisch, da die Peers standig wechseln. So sind z. B. Peers, die nur kurz amChord-Ring teilnehmen, nicht in den Fingertabellen der anderen Peers verzeichnet.Dadurch erhalten sie weniger Lookups und mussen auch weniger Lookups weiterlei-ten als andere Peers, was die gemessenen Daten verfalscht.

Da bei den Experimenten statische Chord-Ringe zum Einsatz kamen, wurde keineAktualisierung der Finger durchgefuhrt. Aktualisiert ein Peer x in einem statischenChord-Ring den Finger i, so sendet er einen Lookup nach Schlussel k = x.ID + 2i−1.Wenn sich die Topologie des Chord-Rings jedoch nicht andert, so ist der erste Peeran den dieser Lookup gesendet wird, i selbst, da der erste Finger ist, der dem gesuch-ten Schlussel am nachsten ist und auf dem Chord-Ring nicht hinter dem gesuchtenSchlussel liegt.15 Der Lookup kann somit ohne nochmalige Weiterleitung direkt von ibeantwortet werden. Fur die Aktualisierung der Finger werden somit weniger Nach-richten und damit Bandbreite benotigt als fur andere Lookups. Wurde die verwendete14vgl.: Tabelle B.415vgl.: Abschnitt 2

78


Bandbreite unter diesen Bedingungen gemessen, so wurden die Ergebnisse auch hier-durch verfalscht.

Um zunachst die von einem Lookup verursachte Datenmenge zu ermitteln, wurde dieSumme der von allen Chord-Peers gesendeten Datenmenge durch die Gesamtanzahlder gesuchten Schlussel geteilt. Abbildung 5.16 zeigt die so ermittelte Datenmengeund stellt sie der in Abschnitt 4.3 theoretisch berechneten Datenmenge gegenuber. Siezeigt, dass die experimentell ermittelte Datenmenge je Lookup logarithmisch mit derPeeranzahl ansteigt. Dabei betragt das Gesamtvolumen der Nachrichten pro Lookupin einem Chord-Ring mit 8 Peers ca. 0.9 KB, wobei es in einem Chord-Ring mit 64Peers auf ca. 1.7 KB pro Lookup ansteigt.

Datenvolumen je Lookup [KB]

0

0.5

1

1.5

2

8 16 32 64Peers

KB

gemessenes Datenvolumen vorhergesagtes Datenvolumen

Abbildung 5.16: Bandbreite pro Lookup

Anhand der Datenmenge pro Lookup ist es nun moglich die benotigte Bandbreite inKilobyte pro Sekunde in Abhangigkeit von den pro Sekunde durchgefuhrten Lookupszu errechnen. Abbildung 5.17 stellt die anhand von experimentell ermittelten Wertenberechnete Bandbreite, der auf Grundlage der Werte aus Abschnitt 4.3 berechnetenBandbreite gegenuber. So werden in einem Chord-Ring mit 8 Peers z. B. von jedemPeer pro Sekunde ca. 4.5 KB versandt, wenn jeder Peer im Chord-Ring pro Sekunde5 Schlussel sucht. Ohne den durch Java-ObjectStreams verursachten Overhead waren

79


es dagegen nur ca. 0.8 KB/s. Ferner zeigt die Abbildung, dass die verwendete Band-breite in KB/s linear mit der Anzahl der pro Sekunde gesuchten Schlussel ansteigt.Die anhand der vorliegenden Daten errechneten Werte liegen dabei um ca. das 6-fache hoher als die theoretisch vorhergesagten Werte. Das bedeutet, dass durch dieVerwendung der Java-ObjectStreams ungefahr 6-mal mehr Daten versendet werdenals eigentlich notig.

gemessen

0

5

10

15

20

0 2 4 6 8 10 12

Lookups/s

KB

/s

8 Peers 16 Peers 32 Peers 64 Peers

vorhergesagt

0

0.5

1

1.5

2

2.5

3

3.5

0 2 4 6 8 10 12

Lookups/s

KB

/s

8 Peers 16 Peers 32 Peers 64 Peers

Abbildung 5.17: Bandbreite in KB/s fur Lookups pro Sekunde

5.3.2 Bandbreitenverbrauch durch Stabilisierung

Um die fur die Stabilisierung notwendige Netzwerkbandbreite zu bestimmen, wurdedie Anzahl und Große der Nachrichten GET PREDECESSOR, PREDECESSOR IS,NOTIFY, GET SUCCESSORS und SUCCESSORS ARE gemessen. Die Messung er-folgte, wie bereits in Abschnitt 5.3.1 beschrieben, inklusive des Overheads, der durchdie Verwendung von Java-ObjectStreams entsteht.

Unterstellt man, wie schon in Abschnitt 4.3.2 angenommen, dass die Zeit zwischenzwei Ausfuhrungen des Stabilisierungsprotokolls bei allen Peers gleich ist, so ist dieAnzahl der Nachrichten, die ein Peer erhalt, gleich der Anzahl an Nachrichten, die derPeer versendet. Die eingehende Datenmenge entspricht also der ausgehenden Daten-menge. Aus diesem Grund wurde auch hier nur die versendete Datenmenge gemessen.

Wahrend Stabilisierung sendet ein Peer Nachrichten an seinen Vorganger und seinenNachfolger. Im Gegensatz zu Lookups, bei denen die Pfadlange mit der Anzahl derPeers steigt, ist die bei der Durchfuhrung des Stabilisierungsprotokolls anfallende

80


Datenvolumen je Stabilisierung

0.01

0.1

1

10

100

1000

10000

1.5 3 6 12

Stabilisierungsintervall [s]

KB/s gesamt [KB] Stabilisierungen KB/Stabilisierung vorhergesagt [KB/s]

Abbildung 5.18: Bandbreite Stabilisierung

Datenmenge unabhangig von der Peeranzahl. Somit ist die durch die Stabilisierungverbrauchte Netzwerkbandbreite tatsachlich nur von der Große der zu versenden-den Nachrichten sowie der Haufigkeit mit der diese versendet werden abhangig. DieGroße der zu versendenden Nachrichten kann jedoch noch durch die Lange der zuubertragenden Nachfolgerliste variieren. Letztendlich ist aber die Haufigkeit mit derdas Stabilisierungsprotokoll durchgefuhrt wird der entscheidende Faktor fur die an-fallende Datenmenge.

Zur Messung der belegten Bandbreite wurden deshalb mehrere Experimente mit un-terschiedlichen Zeiten tstab = 1.5, 3, 6, 12 Sekunden zwischen zwei Stabilisierungendurchgefuhrt. Hierbei wurde die Anzahl der versendeten Nachrichten sowie derenGroße gemessen. Die maximale Lange der bei einer Stabilisierung zu ubertragendenNachfolgerliste betrug hierbei 16 Nachfolger. Die Nachfolgerliste wurde bei jeder Sta-bilisierung ubertragen. Die Anzahl der Peers im Chord-Ring betrug 32, so dass stetsdie maximale Lange fur die Nachfolgerliste erreicht wurde.16

Abbildung 5.18 zeigt fur die unterschiedlichen Zeiten tstab das insgesamt im Experi-ment gemessene Datenvolumen (gesamt [KB]), den insgesamt gemessenen Bandbrei-16vgl.: Abschnitt 4.2.4

81


tenverbrauch (KB/s) sowie die Anzahl der durchgefuhrten Stabilisierungen. Daruberhinaus stellt sie dem gemessenen Bandbreitenverbrauch pro Stabilisierung den inAbschnitt 4.3.2 theoretisch ermittelten Bandbreitenverbrauch pro Stabilisierung ge-genuber. Dies erfolgt anhand der Geraden vorhergesagt [KB/s] und KB/s. So werdenpro Stabilisierung ca. 2 KB Daten versendet, so dass die belegte Bandbreite bei einemStabilisierungsintervall von tstab = 1.5s ca. 1.2 KB/s betragt. Diese nimmt linear zurVergroßerung von tstab ab. So werden fur tstab = 3s noch 0.6 KB/s und bei 0.3 KB/sfur tstab = 6s versendet. Ahnlich wie im Lookup-Fall sind auch wieder die gemessenenWerte um ca. das 3-fache hoher als die theoretisch berechneten. So betragt z. B. dastheoretisch ermittelte Datenvolumen fur tstab = 1.5s nur 0.3 KB/s und im Fall vontstab = 3s nur 0.2 KB/s.

5.3.3 Mindestbandbreitenverbrauch

Bisher wurde die Bandbreite gemessen, die durch Lookups und die Ausfuhrung desStabilisierungsprotokolls verwendet wird. Die Stabilisierung ist dabei ein Faktor, dereinen konstanten Bandbreitenverbrauch hervor ruft. Die von den Lookups belegteBandbreite variiert jedoch mit der Haufigkeit, mit der diese durchgefuhrt werdenund hangt somit auch vom Benutzer ab. Neben der Stabilisierung ruft jedoch nochein weiterer periodisch ausgefuhrter Vorgang einen konstanten Bandbreitenverbrauchhervor: das Aktualisieren der Finger.

Da das Aktualisieren der Finger durch Lookups realisiert wird, kann die dafur benotig-te Bandbreite mit Hilfe der Ergebnisse aus Abschnitt 5.3.1 angegeben werden. Sobetragt z. B. in einem Chord-Ring mit 16 Peers, das durch das Aktualisieren derFingertabelle verursachte Datenvolumen ca. 0.4 KB/s, wenn alle tfix = 3 Sekundenein Finger aktualisiert wird.

Die Mindestbandbreite, die ein Peer belegt, ergibt sich aus der durch Stabilisierungund Aktualisieren der Fingertabelle belegten Bandbreite. Bei einem Stabilisierungs-intervall von tstab = 3 Sekunden und einem Aktualisierungsintervall fur die Fingervon tfix = 3 Sekunden, betragt z. B. die Mindestbandbreite in einem Chord-Ring mit16 Peers 0.2KB/s+0.4KB/s = 0.6KB/s. Ein Peer versendet also in diesem Fall 0.6KB Daten in der Sekunde. Da die durch das Aktualisieren der Fingertabelle belegteBandbreite jedoch mit der Anzahl der Peers steigt, steigt auch die Mindestbandbreitemit der Anzahl der Peers im Chord-Ring.

82

6 Zusammenfassung und Ausblick

Die vorliegende Arbeit beschaftigt sich mit dem effizienten Routing von Suchen inP2P-Netzwerken am Beispiel des auf verteilten Hashtabellen basierenden Routingal-gorithmus Chord.

Chord organisiert seine Peers in einer Ringstruktur in der jeder Peer zwei Nachbarnbesitzt: einen Vorganger und einen Nachfolger. Mit Hilfe der Fingertabellen, mit de-nen ein Lookup immer mindestens die Halfte der Distanz zum gesuchten Peer uber-springen kann, erreicht Chord, dass der fur einen gesuchten Schlussel verantwortlichePeer innerhalb von O(log n) Schritten gefunden wird. Auf Grund der Dynamik, derP2P-Systeme unterliegen, aktualisieren die Chord-Peers in regelmaßigen Abstandensowohl ihre Nachbarn als auch ihre Finger.

Wie erwartet zeigten die anhand der im Rahmen dieser Arbeit durchgefuhrten Imple-mentierung von Chord durchgefuhrten Experimente, dass Suchen in O(log n) Schrit-ten abgeschlossen sind. Die Verteilung der auftretenden Pfadlangen entspricht dabeiungefahr einer Gauß-Verteilung, so dass die durchschnittliche Pfadlange bei 1

2 log n

Schritten liegt.

Weitere Experimente haben gezeigt, dass die Korrektheit der Fingertabellen zumeinen die Pfadlange und somit die Performanz aber auch den Ausgang von Lookupsmaßgeblich beeinflussen. So hat sich einerseits gezeigt, dass sich die bei den Lookupsauftretenden Pfadlangen vergroßern, je weniger aktuell die Fingertabelle ist. Ande-rerseits hat sich gezeigt, dass bei weniger korrekten Fingertabellen weniger gesuchteSchlussel gefunden werden, wobei der Anteil der nicht gefundenen Schlussel in denExperimenten deutlich unter 1% lag. Fur die Korrektheit der Fingertabelle gilt wie-derum, dass diese einerseits steigt, je mehr Peers im Chord-Ring vorhanden sind, undsie andererseits fallt je ofter Peers dem Chord-Ring beitreten oder diesen verlassen.

Neben den Experimenten in Bezug auf die Durchfuhrung von Lookups, wurden Expe-rimente durchgefuhrt, in denen Chord-Ringe einem ”Stresstest“ unterzogen wurden.

83

6 Zusammenfassung und Ausblick

Hierbei hat sich gezeigt, dass die Vorganger- und Nachfolgerbeziehungen zwischen denPeers auch dann noch zuverlassig durch das Stabilisierungsprotokoll aufrecht erhaltenwerden, wenn Peers in sehr kurzem Abstand den Chord-Ring betreten oder verlassen.

Die Experimente zum Bandbreitenverbrauch eines Chord-Peers ergaben, dass sichdie durch die Chord-Peers belegte Mindestbandbreite im moderaten Bereich bewegt.So betragt diese fur in einem Chord-Ring mit 16 Peers bei ca. 0.6 KB/s wenn alletstab = tfix = 3 Sekunden eine Stabilisierung ausgefuhrt und ein Finger aktualisiertwird. Ferner haben die Experimenten zum Bandbreitenverbrauch bestatigt, dass derGroßteil der belegten Bandbreite erst dann entsteht, wenn viele Schlussel in kurzerZeit gesucht werden.

Fur die Zukunft ergeben sich fur den Chord-Algorithmus weitere Arbeitsfelder wie diegegenseitigen Authentifizierung der Peers untereinander [3] sowie die Verbesserungder Robustheit von Chord gegenuber Angreifern [41], so dass Storungen des P2P-Systems durch einzelne boswillig agierende Peers verringert oder ausgeschlossen wer-den konnen. Ein weiteres Arbeitsfeld eroffnet die Erweiterung des DHT-Ansatzes aufSuchen, die auch die Peers finden, die fur dem gesuchten Schlussel ahnliche Schlusselverantwortlich sind (Range-Queries). Bisher ist der DHT-Ansatz lediglich in der La-ge, fur eine Suche entweder einen exakten Treffer oder uberhaupt kein Ergebnis zuliefern. Hier bietet [48] einen moglichen Ansatz.

84

A UML-Darstellungen FingerTable()

setFinger()

getFinger()

FingerTable

messagecommand: byte

messagebody: Object

RemoteMessage()

getCommand()

setCommand()

getBody()

setBody()

RemoteMessage

mediator: Mediator

Stabilizer()

setMediator()

run()

Stabilizer

ClientFactory()

getClient()

ClientFactory

mediator: Mediator

FingerTableStabilizer()

run()

FingerTableStabilizer

mediator: Mediator

DHTServer()

DHTServer()

setMediator()

run()

DHTServer

neighbours: LinkedList

NeighbourList()

getNeighbour()

NeighbourList

PredecessorList()

setPredecessor()

getPredecessor()

PredecessorList

SuccessorList()

setSuccessor()

setSuccessors()

getSuccessor()

getSuccessors()

SuccessorList

location: Location

searchkey: long

hops: short

LookupMessage()

setSearchKey()

getSearchKey()

setLocation()

getLocation()

getHops()

incHops()

setHops()

LookupMessage

FingerTable()

setFinger()

getFinger()

FingerTable


messagebody: Object

RemoteMessage()

getCommand()

setCommand()

getBody()

setBody()

RemoteMessage

mediator: Mediator

Stabilizer()

setMediator()

run()

Stabilizer

ClientFactory()

getClient()

ClientFactory

mediator: Mediator


run()


mediator: Mediator

DHTServer()

DHTServer()

setMediator()

run()

DHTServer


NeighbourList()

getNeighbour()

NeighbourList

PredecessorList()

setPredecessor()

getPredecessor()

PredecessorList

SuccessorList()

setSuccessor()

setSuccessors()

getSuccessor()

getSuccessors()

SuccessorList

location: Location

searchkey: long

hops: short

LookupMessage()

setSearchKey()

getSearchKey()

setLocation()

getLocation()

getHops()

incHops()

setHops()

LookupMessage

Abbildung A.1: UML-Klassendiagramme (1)

vii

A UML-Darstellungen

FingerTable()

setFinger()

getFinger()

FingerTable


messagebody: Object

RemoteMessage()

getCommand()

setCommand()

getBody()

setBody()

RemoteMessage

mediator: Mediator

Stabilizer()

setMediator()

run()

Stabilizer

ClientFactory()

getClient()

ClientFactory

mediator: Mediator


run()


mediator: Mediator

DHTServer()

DHTServer()

setMediator()

run()

DHTServer


NeighbourList()

getNeighbour()

NeighbourList

PredecessorList()

setPredecessor()

getPredecessor()

PredecessorList

SuccessorList()

setSuccessor()

setSuccessors()

getSuccessor()

getSuccessors()

SuccessorList

location: Location

searchkey: long

hops: short

LookupMessage()

setSearchKey()

getSearchKey()

setLocation()

getLocation()

getHops()

incHops()

setHops()

LookupMessage

FingerTable()

setFinger()

getFinger()

FingerTable


messagebody: Object

RemoteMessage()

getCommand()

setCommand()

getBody()

setBody()

RemoteMessage

mediator: Mediator

Stabilizer()

setMediator()

run()

Stabilizer

ClientFactory()

getClient()

ClientFactory

mediator: Mediator


run()


mediator: Mediator

DHTServer()

DHTServer()

setMediator()

run()

DHTServer


NeighbourList()

getNeighbour()

NeighbourList

PredecessorList()

setPredecessor()

getPredecessor()

PredecessorList

SuccessorList()

setSuccessor()

setSuccessors()

getSuccessor()

getSuccessors()

SuccessorList

location: Location

searchkey: long

hops: short

LookupMessage()

setSearchKey()

getSearchKey()

setLocation()

getLocation()

getHops()

incHops()

setHops()

LookupMessage

FingerTable()

setFinger()

getFinger()

FingerTable


messagebody: Object

RemoteMessage()

getCommand()

setCommand()

getBody()

setBody()

RemoteMessage

mediator: Mediator

Stabilizer()

setMediator()

run()

Stabilizer

ClientFactory()

getClient()

ClientFactory

mediator: Mediator


run()


mediator: Mediator

DHTServer()

DHTServer()

setMediator()

run()

DHTServer


NeighbourList()

getNeighbour()

NeighbourList

PredecessorList()

setPredecessor()

getPredecessor()

PredecessorList

SuccessorList()

setSuccessor()

setSuccessors()

getSuccessor()

getSuccessors()

SuccessorList

location: Location

searchkey: long

hops: short

LookupMessage()

setSearchKey()

getSearchKey()

setLocation()

getLocation()

getHops()

incHops()

setHops()

LookupMessage

Abbildung A.2: UML-Klassendiagramme (2)

viii

B Auswertung der Experimente

Peers gesuchte PfadlangeSchlussel 0 1 2 3 4 5 6 7

5 250050 99896 104054 42780 33206 300060 99956 140018 44963 151238 400080 100051 158354 119382 18367 392510 500100 100156 166015 187353 44141 243412 600120 100209 201651 232359 63097 280114 700140 100395 208364 281123 101356 890016 800160 100366 193424 314564 166934 20822 404718 900180 100437 213280 345965 207312 32094 109020 1000200 99986 237223 387063 224656 47536 373022 1100220 99903 231440 424168 284100 58179 242624 1200240 99294 251772 473386 312296 58669 482026 1300260 100059 248411 474219 367946 100455 7819 134928 1400280 99954 258090 495082 426645 110096 10162 25132 1600320 100330 286741 547564 499502 151377 14784 1648 2400480 100336 288029 678976 821197 426477 81528 3901 3164 3200640 99842 319537 828853 1066717 694405 178061 12637

Tabelle B.1: Pfadlange: Suche im statischen Chord-Ring (absolut)

Peers Summe der bis Pfadlange i abgeschlossenen Suchen0 1 2 3 4 5 6 7

5 39.9504% 81.5637% 98.6723% 100%6 33.3120% 79.9753% 94.9600% 100%8 25.0078% 64.5885% 94.4281% 99.0189% 100%10 20.0272% 53.2237% 90.6868% 99.5133% 100%12 16.6982% 50.3002% 89.0191% 99.5333% 100%14 14.3393% 44.0997% 84.2522% 98.7288% 100%16 12.5433% 36.7165% 76.0293% 96.8920% 99.4942% 100%18 11.1575% 34.8506% 73.2835% 96.3136% 99.8789% 100%20 9.9967% 33.7144% 72.4132% 94.8744% 99.6271% 100%22 9.0803% 30.1162% 68.6693% 94.4915% 99.7795% 100%24 8.2729% 29.2497% 68.6908% 94.7103% 99.5984% 100%26 7.6953% 26.8001% 63.2712% 91.5691% 99.2949% 99.8963% 100%28 7.1381% 25.5695% 60.9254% 91.3939% 99.2564% 99.9821% 100%32 6.2694% 24.1872% 58.4032% 89.6160% 99.0752% 99.9990% 100%48 4.1798% 16.1787% 44.4637% 78.6735% 96.4399% 99.8362% 99.9987% 100%64 3.1200% 13.1054% 39.0066% 72.3410% 94.0408% 99.6051% 100%

rot geschriebene Zahlen markieren blog(Peeranzahl)c

Tabelle B.2: Pfadlange: Suche im statischen Chord-Ring (prozentual)

ix


8 Peers

1

10

100

1000

10000

0 5 10 15 20 25 30Pfadlänge

Gesam

tan

zah

l

Join/Leave [s] 5 6 7 8 9 10 15 20 25 30 35

Abbildung B.1: Pfadlange fur 8 Peers in dynamischen Chord-Ringen mit verschiede-nen Join-Leave-Zeiten

32 Peers

1

10

100

1000

10000

0 5 10 15 20 25 30

Pfadlänge

Gesam

tan

zah

l

Join/Leave [s] 1 2 3 4 5 6 7 8 9 10 15 20 25 30 35

Abbildung B.2: Pfadlange fur 32 Peers in dynamischen Chord-Ringen mit verschie-denen Join-Leave-Zeiten

x


48 Peers

1

10

100

1000

10000

0 5 10 15 20 25 30

Pfadlänge

Gesam

tan

zah

l

Join/Leave [s] 1 2 3 4 5 6 7 8 9 10 15 20 25 30 35

Abbildung B.3: Pfadlange fur 48 Peers in dynamischen Chord-Ringen mit verschie-denen Join-Leave-Zeiten

xi


Peers 8 16 32 64Datenmenge gesamt [KB] 2086.45 953.25 458.22 228.90Lookups/Peer* 2285.07 872.26 353.74 132.17Median 2379 918 355 1320.25-Quartil 2052 794 329 1240.75-Quartil 2647 999.75 378 141Standardabweichung 1032.60 233.92 71.07 21.13Bandbreite pro Peer [KB/s]* 2.29 1.03 0.48 0.23Median 2.39 1.00 0.44 0.220.25-Quartil 1.90 0.67 0.34 0.160.75-Quartil 2.75 1.28 0.62 0.29Standardabweichung 0.77 0.41 0.20 0.10Datenvolumen je Lookup [KB] 0.91 1.09 1.29 1.73Lookups pro Peer und Sekunde 2.51 0.94 0.37 0.13Dauer des Experiments [s]* 908 924 935 975* Durchschnittswerte

Tabelle B.3: Durch Lookups belegte Bandbreite

Stabilisierungsintervall [ms] 1.5 3 6 12Datenmenge gesamt [KB] 1134.51 596.81 317.34 179.99Stabilisierungen* 615 309.73 155.43 77.76Datenvolumen pro Stabilisierung [KB] 1.84 1.92 2.04 2.31Bandbreite [KB/s] 1.21 0.63 0.34 0.19Dauer des Experiments [s]* 932 932 931.61 933.40* Durchschnittswerte

Tabelle B.4: Durch Stabilisierung belegte Bandbreite

xii

C Nachrichten und Nachrichtengroßen

Eine Nachricht besteht aus einem Kommando und den zu dem Kommando gehoren-den Daten. Das Kommando klassifiziert dabei die ihm folgenden Daten. Im Folgen-den werden die in der vorliegenden Implementierung verwendeten Nachrichten kurzerlautert. Tabelle C.1 fasst den Aufbau der Nachrichten und die Große der transpor-tierten Informationen zusammen.

• EXIT - Verbindungsabbau

• GET EXPONENT - Dient zur Abfrage des Exponenten beim Eintritt (join) inden Ring.

• EXPONENT IS - Beinhaltet den Exponenten des Rings. Diese Nachricht istdie Antwort auf GET EXPONENT.

• FIND SUCCESSOR - Dient zu Bestimmung des Nachfolgers beim Eintritt ineinen Chord-Ring.

• FOUND SUCCESSOR - Antwort auf FIND SUCCESSOR. Die ubermitteltenDaten beschreiben den gesuchten Nachfolger.

• LEAVE - Wird beim Verlassen des Rings an den Vorganger und den Nachfol-ger geschickt. Verlasst Peer x den Chord-Ring, so wird diese Nachricht an denVorganger geschickt. In diesem Fall enthalt sie Informationen uber den Peer x,der den Ring verlasst, sowie den Nachfolger von x. Wird die Nachricht an denNachfolger von x geschickt, so beinhaltet sie statt dessen Informationen uberden Vorganger von x. Mit Hilfe dieser Information konnen die benachrichtig-ten Peers unterscheiden, ob sie die Nachricht von ihrem Vorganger oder ihremNachfolger erhalten haben. Wurde die Nachricht vom Nachfolger gesendet, soaktualisiert der Peer seinen Nachfolger, wurde sie vom Vorganger gesendet, sowird der Vorganger aktualisiert.

• NOTIFY - Wird von Peer x an seinen Nachfolger y geschickt, um y uber dieExistenz von x zu informieren. Hierbei ubermittelt x seine ChordID. Wenn x

xiii


zwischen y und dem Vorganger p von y liegt, so andert y seinen Vorganger vonp auf x.

• GET PREDECESSOR - Wird beim Stabilisieren des Rings vom Peer x andessen Nachfolger y gesendet. Liegt der Vorganger p des Nachfolgers y zwischenPeer x und dessen Nachfolger y, so wird p zum neuen Nachfolger von x.

• PREDECESSOR IS - Antwort auf GET PREDECESSOR. Diese Nachrichtenthalt Informationen uber den Vorganger des Peers der diese Nachricht ver-schickt.

• GET SUCCESSORS - Wird an den Nachfolger geschickt, um von diesem eineListe seiner Nachfolger zu erhalten.

• SUCCESSORS ARE - Antwort auf GET SUCCESSORS. Die Nachricht enthalteine Liste mit Informationen uber die Nachfolger des Peers, der diese Nachrichtverschickt.

• KEY LOOKUP - Suche nach einem Schlussel. Die Nachricht enthalt den ge-suchten Schlussel, die Anzahl der Weiterleitungen der Nachricht und die Infor-mationen daruber, an welchen Peer die Antwort gesendet werden soll. Erhaltein Peer diese Nachricht, so pruft er zunachst, ob er selbst fur den gesuchtenSchlussel verantwortlich ist. Falls ja, so antwortet er dem fragenden Peer, fallsnicht, leitet er die Anfrage an den Peer aus seiner Fingertabelle weiter, der demgesuchten Schlussel am nachsten liegt. Die Nachricht wird nicht weitergeleitet,wenn die Anzahl der Sprunge, die sie bisher gemacht hat den Wert 2∗exponent

ubersteigt. Dies verhindert, dass ein Lookup im Fall eines Zyklus immer wie-der weitergeleitet wird, obwohl der suchende Peer nicht mehr auf die Antwortwartet.

• KEY FOUND - Positive Antwort auf die Suche nach einem Schlussel. Die Nach-richt enthalt Informationen uber den zustandigen Peer.

xiv


Nac

hri

cht

Aufb

auB

yte

sE

RR

OR

Com

man

d1

EX

ITC

omm

and

1G

ET

EX

PO

NE

NT

Com

man

d1

EX

PO

NE

NT

IS(C

omm

and,

Byt

e)1+

1=

2FIN

DSU

CC

ESS

OR

(Com

man

d,Loc

atio

n)1+

31=

32FO

UN

DSU

CC

ESS

OR

(Com

man

d,Loc

atio

n)1+

31=

32LE

AV

E(C

omm

and,

Loc

atio

n*2)

1+31

*2=

63N

OT

IFY

(Com

man

d,Loc

atio

n)1+

31=

32G

ET

PR

ED

EC

ESS

OR

Com

man

d1

PR

ED

EC

ESS

OR

IS(C

omm

and,

Loc

atio

n)1+

31=

32G

ET

SUC

CE

SSO

RS

Com

man

d1

SUC

CE

SSO

RS

AR

E(C

omm

and,

Loc

atio

n*M

AX

SUC

CE

SSO

RS)

1+(3

1*M

AX

SUC

CE

SSO

RS)

KE

YLO

OK

UP

(Com

man

d,Loo

kupM

essa

ge)

1+41

=42

KE

YFO

UN

D(C

omm

and,

Loo

kupM

essa

ge)

1+41

=42

Java

Obje

kt

Aufb

auB

yte

sLoo

kupM

essa

ge(s

earc

hkey

,ho

ps,Loc

atio

n)8+

2+31

=41

Loc

atio

n(c

hord

ID,ip

,ch

ordP

ort,

appl

icat

ionP

ort)

8+15

+4+

4=

31C

omm

and

Byt

e1

Wer

tA

ufb

auB

yte

sch

ordI

DLon

g8

ipSt

ring

(15)

15ch

ordP

ort

Inte

ger

4ap

plic

atio

nPor

tIn

tege

r4

sear

chke

yLon

g8

last

Aliv

eLon

g8

hops

Shor

t2

Tab

elle

C.1

:N

achr

icht

enau

fbau

und

-gro

ße

xv

D Die Konfigurationsdatei

DEFAULT RINGEXPONENT = 16 Exponent m des Chord-RingsDa ChordID als long (−263..263 − 1)implementiert wurde undChordID = ID mod 2m ∈ (0..263 − 1)betragt das Maximum fur m = 63

DEFAULT PORT = 22280 der von Port benutzte Netzwerkport

LOOKUP TIMEOUT = 35000 maximale Suchzeit in Millisekunden

MAX SUCCESSORS = 16 maximale Lange der Nachfolgerliste

FIND SUCCS INTERVAL = 1 Anzahl Stabilisierungen bis dieNachfolgerliste erneut bezogen wird

CHECK PRED INTERVAL = 1 Anzahl Stabilisierungen bis derVorganger uberpruft wird

STABILIZATION INTERVALL = 3000 Intervall in [ms] zwischen zweiStabilisierungen

FIX FINGERS INTERVAL = 3000 Intervall in [ms] zwischen derAktualisierung zweier Finger

Tabelle D.1: Parameter der Konfigurationsdatei

xvi

Literaturverzeichnis

[1] FIPS 180-1. Secure hash standard, April 1995.http://www.itl.nist.gov/fipspubs/fip180-1.htm. letzter Abruf: 21.03.2005.

[2] Karl Aberer. P-Grid: A self-organizing access structure for P2P informationsystems. volume 2172, pages 179–194. Springer-Verlag Berlin et al., 2001.

[3] Karl Aberer and Zoran Despotovic. Managing trust in a peer-2-peer informationsystem. In Proceedings of the tenth international conference on Information andknowledge management, pages 310–317. ACM Press, 2001.

[4] Karl Aberer and Manfred Hauswirth. An Overview of Peer-to-Peer InformationSystems. In Distributed Data & Structures 4: Records of the 4th InternationalMeeting (WDAS 2002), volume 14, pages 171–188. Carleton Scientific, March2002.

[5] James Aspnes and Gauri Shah. Skip graphs. In SODA ’03: Proceedings of thefourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 384–393. Society for Industrial and Applied Mathematics, 2003.

[6] Baruch Awerbuch and Christian Scheideler. Peer-to-peer systems for prefixsearch. In PODC ’03: Proceedings of the twenty-second annual symposium onPrinciples of distributed computing, pages 123–132. ACM Press, 2003.

[7] Hari Balakrishnan, M. Frans Kaashoek, David Karger, Robert Morris, and IonStoica. Looking up data in P2P systems. Commun. ACM, 46(2):43–48, 2003.

[8] Matthias Bender, Sebastian Michel, Gerhard Weikum, and Christian Zimmer.The MINERVA project: Database selection in the context of P2P search. In Da-tenbanksysteme in Business, Technologie und Web (BTW2005; 11. Fachtagungdes GI-Fachbereichs Datenbanken und Informationssysteme (DBIS)), volume P-65 of Lecture Notes in Informatics, pages 125–144, Karlsruhe, Germany, March2005. Gesellschaft fur Informatik.

xvii


[9] Matthias Bender, Sebastian Michel, Christian Zimmer, and Gerhard Weikum.Bookmark-driven Query Routing in Peer-to-Peer Web Search. In Jamie Callan,Norbert Fuhr, and Wolfgang Nejdl, editors, Proceedings of the SIGIR Work-shop on Peer-to-Peer Information Retrieval : 27th Annual International ACMSIGIR Conference ; SIGIR 2004 P2PIR Workshop, pages SessionII,1–12, Shef-field, England, 2004. Universitat Duisburg-Essen.

[10] Ian Clarke, Oskar Sandberg, Brandon Wiley, and Theodore W. Hong. Freenet:a distributed anonymous information storage and retrieval system. In Inter-national workshop on Designing privacy enhancing technologies, pages 46–66.Springer-Verlag New York et al., 2001.

[11] Frank Dabek, Emma Brunskill, M. Frans Kaashoek, David Karger, Robert Mor-ris, Ion Stoica, and Hari Balakrishnan. Building peer-to-peer systems withChord, a distributed lookup service. In HOTOS ’01: Proceedings of the EighthWorkshop on Hot Topics in Operating Systems, pages 81–86. IEEE ComputerSociety, 2001.

[12] Frank Dabek, M. Frans Kaashoek, David Karger, Robert Morris, and Ion Stoica.Wide-area cooperative storage with cfs. In SOSP ’01: Proceedings of the eigh-teenth ACM symposium on Operating systems principles, pages 202–215. ACMPress, 2001.

[13] N. de Bruijn. A combinatorial problem. In Proceedings Nederlandse Akademievan Wetenschappen, volume 49, pages 758–764, 1946.

[14] Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design pat-terns: elements of reusable object-oriented software. Addison-Wesley, 1999.

[15] The gnutella protocol specification v0.4, June 2001.http://www9.limewire.com/developer/gnutella protocol 0.4.pdf. letzter Abruf:21.03.2005.

[16] Nicolas Harvey, Michael Jones, Stefan Saroiu, Marvin Theimer, and Alec Wol-man. Skipnet: A scalable overlay network with practical locality properties. InProceedings of USITS, March 2003.

[17] Ivan Herman and M. Scott Marshall. GraphXML - An XML-Based GraphDescription Format. In GD ’00: Proceedings of the 8th International Symposiumon Graph Drawing, pages 52–62. Springer-Verlag Berlin et al., 2001.

xviii


[18] Kirsten Hildrum, John D. Kubiatowicz, Satish Rao, and Ben Y. Zhao. Distri-buted object location in a dynamic network. In SPAA ’02: Proceedings of thefourteenth annual ACM symposium on Parallel algorithms and architectures,pages 41–52. ACM Press, 2002.

[19] M. Frans Kaashoek and David Karger. Koorde: A simple degree-optimal distri-buted hash table. Lecture Notes in Computer Science, 2735:98–107, 2003.

[20] Thomas Karagiannis, Andre Broido, Michalis Faloutsos, and Kc Claffy. Trans-port layer identification of P2P traffic. In IMC ’04: Proceedings of the 4th ACMSIGCOMM conference on Internet measurement, pages 121–134. ACM Press,2004.

[21] David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Matthew Levine,and Daniel Lewin. Consistent hashing and random trees: distributed cachingprotocols for relieving hot spots on the world wide web. In STOC ’97: Pro-ceedings of the twenty-ninth annual ACM symposium on Theory of computing,pages 654–663. ACM Press, 1997.

[22] Jon Kleinberg. Small-world phenomena and the dynamics of information, 2001.

[23] John Kubiatowicz, David Bindel, Yan Chen, Steven Czerwinski, Patrick Eaton,Dennis Geels, Ramakrishna Gummadi, Sean Rhea, Hakim Weatherspoon, ChrisWells, and Ben Zhao. Oceanstore: an architecture for global-scale persistentstorage. In ASPLOS-IX: Proceedings of the ninth international conference onArchitectural support for programming languages and operating systems, pages190–201. ACM Press, 2000.

[24] David Liben-Nowell, Hari Balakrishnan, and David Karger. Analysis of the evo-lution of peer-to-peer systems. In Proceedings of the twenty-first annual sympo-sium on Principles of distributed computing, pages 233–242. ACM Press, 2002.

[25] Bruce M. Maggs and Ramesh K. Sitaraman. Simple algorithms for routingon butterfly networks with bounded queues. In STOC ’92: Proceedings of thetwenty-fourth annual ACM symposium on Theory of computing, pages 150–161.ACM Press, 1992.

[26] Dahlia Malkhi, Moni Naor, and David Ratajczak. Viceroy: a scalable and dy-namic emulation of the butterfly. In PODC ’02: Proceedings of the twenty-firstannual symposium on Principles of distributed computing, pages 183–192. ACMPress, 2002.

xix


[27] Petar Maymounkov and David Mazieres. Kademlia: A peer-to-peer informationsystem based on the xor metric. In IPTPS ’01: Revised Papers from the FirstInternational Workshop on Peer-to-Peer Systems, pages 53–65. Springer-VerlagBerlin et al., 2002.

[28] Valentin Mesaros, Bruno Carton, and Peter Van Roy. S-Chord: Using symmetryto improve lookup efficiency in chord. Report UCL/INFO-2002-08, December2002.

[29] Stanley Milgram. The small world problem. Psychology Today, (1):60–67, 1967.

[30] Paul V. Mockapetris. RFC 1034: Domain Names - Concepts and Facilities.Network Working Group, November 1987.

[31] Paul V. Mockapetris and Kevin J. Dunlap. Development of the domain namesystem. SIGCOMM Comput. Commun. Rev., 25(1):112–122, 1995.

[32] Sharman Networks. KaZaA Website. http://www.kazaa.com. letzter Abruf:21.03.2005.

[33] Jon Postel. User datagram protocol. 1980. RFC768.

[34] The Chord Project. http://pdos.lcs.mit.edu/chord. letzter Abruf: 21.03.2005.

[35] The Freenet Network Project. http://freenet.sourceforge.net. letzter Abruf:21.03.2005.

[36] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Schen-ker. A scalable content-addressable network. In Proceedings of the 2001 con-ference on Applications, technologies, architectures, and protocols for computercommunications, pages 161–172. ACM Press, 2001.

[37] RFC793. Transmission Control Protocol. September 1981. DARPA InternetProgram Protocol Specification.

[38] Antony Rowstron and Peter Druschel. Storage management and caching in past,a large-scale, persistent peer-to-peer storage utility. In SOSP ’01: Proceedings ofthe eighteenth ACM symposium on Operating systems principles, pages 188–201.ACM Press, 2001.

[39] Antony I. T. Rowstron and Peter Druschel. Pastry: Scalable, decentralized ob-ject location, and routing for large-scale peer-to-peer systems. Lecture Notes inComputer Science, 2218:329–350, 2001.

xx


[40] Stefan Saroiu, P. Krishna Gummadi, and Steven Gribble. A measurement studyof peer-to-peer file sharing systems. 2002.

[41] Emil Sit and Robert Morris. Security considerations for peer-to-peer distributedhash tables. In P. Druschel, F. Kaashoek, and A. Rowstron, editors, Peer-to-Peer Systems: First InternationalWorkshop, IPTPS 2002 Cambridge, MA, USA,March 7-8, 2002. Revised Papers, Lecture Notes in Computer Science. Springer-Verlag Berlin et al., 2002.

[42] UML 2.0 Superstructure specification.http://www.omg.org/cgi-bin/doc?ptc/2004-10-02. letzter Abruf: 28.03.2005.

[43] Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaas-hoek, Frank Dabek, and Hari Balakrishnan. Chord: a scalable peer-to-peer loo-kup protocol for internet applications. IEEE/ACM Trans. Netw., 11(1):17–32,2003.

[44] The World Wide Web Consortium (W3C). Extensible Markup Language (XML).http://www.w3c.org/XML. letzter Abruf: 21.03.2005.

[45] Gnutella Website. http://www.gnutella.com. letzter Abruf: 21.03.2005.

[46] Napster Website. http://www.napster.com. letzter Abruf: 21.03.2005.

[47] Beverly Yang and Hector Garcia-Molina. Designing a super-peer network. InProceedings of the 19th International Conference on Data Engineering (IC-DE’03), pages 49–60, March 2003.

[48] Ming Zhang and Kian-Lee Tan. Supporting rich queries in dht-based peer-to-peer systems. In WETICE ’03: Proceedings of the Twelfth International Work-shop on Enabling Technologies, page 95. IEEE Computer Society, 2003.

[49] Shelley Q. Zhuang, Ben Y. Zhao, Anthony D. Joseph, Randy H. Katz, andJohn D. Kubiatowicz. Bayeux: an architecture for scalable and fault-tolerantwide-area data dissemination. In NOSSDAV ’01: Proceedings of the 11th inter-national workshop on Network and operating systems support for digital audioand video, pages 11–20. ACM Press, 2001.

xxi

Documents

Effizientes Routing in Peer-to-Peer Netzwerkenfile/Diplom_Schade.pdf · Netzwerk getrennt werden, lassen sich in der Regel keine verl¨asslichen Aussagen uber¨ die Verfugbarkeit