Freenet - Institut für Verteilte Systeme

Transcrição

Freenet: Designziele
■
Effiziente dynamische Verteilung von Informationen
■
Anonymität für Informationsproduzenten und Konsumenten
■
Sicherheit für Informationsanbieter
■
Resistenz gegenüber Zensur
Struktur des Free Network Protocol (FNP)
■
Transportschicht:
●
■
■
Verschlüsselungsschicht
●
Aufbau verschlüsselter Verbindungen zwischen Knoten
●
Aushandlung eines gemeinsam Schlüssel nach ElGamal,
dann Verschlüsselung der übertragenen Daten mit AES
(Rijndael)
Anwendungsschicht
65
(C) 2004 Hans P. Reiser, Franz J. Hauck, Abteilung Verteilte Systeme, Universität Ulm
P2P.fm: 23.01.06 08:20
P2P.fm: 23.01.06 08:20
●
Algorithmen für Verteilte Systeme (AVS), WS 2004/05
●
Einfügen von Daten
●
Anfordern von Daten
67
P2P.fm: 23.01.06 08:20
P2P.fm: 23.01.06 08:20
Integration eines neuen Knotens in das Netz
66
Freenet: Rahmenbedingungen des Systems
Es können grundsätzlich drei Operation in Freenet
durchgeführt werden:
●
Definiert das eigentliche Freenet-Protokoll zum Austausch
und zur Suche von Informationen
Freenet: Basisoperationen
■
Verbindungsorientierte, zuverlässige Datenübertragung
■
Jegliche Informationen in Freenet werden durch
Hashschlüssel referenziert.
■
Informationen werden auf Grund von lexikografischer Nähe
von Schlüsseln abgelegt und gefunden.
■
Jeder Knoten verfügt über eine Routing-Tabelle, die sich aus
Hashschlüsseln und Knotenadressen zusammensetzt.
Der einem Hashschlüssel zugeordnete Knoten verwaltet
entweder die durch den Schlüssel referenzierten Daten, oder
kennt einen Knoten, der diese Daten verwaltet.
■
Jeder Knoten verfügt über einen sogenannten Data Store.
Dieser verwaltet die von einem Knoten zur Verfügung
gestellten Daten.
68
■
Alle Nachrichten werden über verschlüsselte Verbindungen
übertragen
■
Wichtige Felder der meisten Nachrichten:
●
UniqueID: Eindeutiger ID
●
HTL: Hops to Live Zähler
●
Source: Absender der Nachricht (IP-Adresse und Port)
(wird benötigt, falls zu einer Nachricht eine Antwort
zurückgesendet werden soll, die Verbindung aber
nicht mehr offen ist)
Freenet: Daten anfordern
69
■
Anfrage an den Data Store, ob Daten unter dem gesuchten
Hashschlüssel abgelegt sind. Ist dies der Fall, werden die
Daten zurückgeliefert.
■
Ansonsten wird aus der Routing-Tabelle der Knoten gewählt,
der am ehesten den gesuchten Schlüssel in seinem Data
Store verwaltet. An diesen Knoten wird dann eine Data
Request-Nachricht versendet.
P2P.fm: 23.01.06 08:20
P2P.fm: 23.01.06 08:20
Freenet: Rahmenbedingungen des Systems
■
Beim Nachrichtenempfang wird das Feld HTL dekrementiert
●
Werden die Daten nicht durch den lokalen Data Store
verwaltet, wird der Request an den nächsten geeigneten
Knoten weitergeleitet.
●
Kennt ein Knoten keinen weiteren Knoten oder liegt eine
Schleife vor, antwortet er an den anfragenden Knoten mit
einer Request Failed-Nachricht.
Der anfragende Knoten kann dann die Request-Nachricht an
einen anderen Knoten weiterleiten.
= Data Request
= Data Reply
= Request Faild
KEY
ADDRESS
dfsee
tcp/5.34.27.4:66434
ee3e4
tcp/89.34.36.1:24855
991d2
tcp/64.28.67.48:43653
34dd7
tcp/63.23.67.48:33321
71
P2P.fm: 23.01.06 08:20
P2P.fm: 23.01.06 08:20
Data Request
UniqueID=C24.....
Source=131.188.34.159:84523
TTL=10
SearchKey=8e0...
70
= Data Request
= Data Reply
= Request Faild
72
■
Freenet Daten anfordern
Sinkt das Feld HTL auf den Wert 0 und sind keine Daten
auffindbar, wird eine Data Not Found-Nachricht an den
anfragenden Knoten versendet
■
73
●
neuer Eintrag mit Adresse und Hashschlüssel der Nachricht
in Routingtabelle
●
Bevor ein Knoten die Data Reply-Nachricht
weiterversendet, ersetzt er mit der Wahrscheinlichkeit p das
Feld Data Source durch seine eigene Adresse, sonst bleibt
die Adresse erhalten
75
P2P.fm: 23.01.06 08:20
P2P.fm: 23.01.06 08:20
Nach Verarbeitung der Data Reply-Nachricht gilt die
Anfrage als erfolgreich verarbeitet und der Knoten kann
jegliche Statusinformation zur Anfrage löschen
●
Ist der Knoten Initiator der Anfrage, werden die Daten an den
Anwender zurückgeliefert; ansonsten wird die
Nachricht an den Vorgänger in der Anfragekette
weitergeleitet.
= Data Request
= Data Reply
= Request Failed
74
Freenet: Einfügen von Daten
Beim Empfang einer Data Reply-Nachricht:
●
Empfängt ein Knoten eine Data Reply-Nachricht, so
speichert er den Hash-Schlüssel und die Daten im Data
Store.
■
●
Data Reply
UniqueID=C24300FB7BEA06E3
DataLength=122
Data
...
P2P.fm: 23.01.06 08:20
P2P.fm: 23.01.06 08:20
= Data Request
= Data Reply
= Data Not Found
Verwaltet ein Knoten den gesuchten Schlüssel, so versendet
er eine Data Reply-Nachricht an den anfragenden Knoten
■
Sollen Informationen in das System eingefügt werden, muss
zuerst ein Schlüssel für die einzufügenden Daten generiert
werden
■
Anschließend wird eine Insert Request-Nachricht mit
diesem Hashschlüssel dem lokalen Knoten übergeben
■
Der Insert Request dient dem Finden eines geeigneten
Speicherorts und wird im wesentlichen wie ein Data
Request behandelt
76
■
Ein Knoten, der einen Insert Request erhält, kontrolliert
ob der Schlüssel bereits durch den lokalen Data Store
verwaltet wird. Ist dies nicht der Fall, wird die Insert
Request-Nachricht an den geeignetsten Knoten
weitergeleitet.
■
Verwaltet einer der befragten Knoten den gesuchten
Hashschlüssel bereits, generiert er eine Data ReplyNachricht.
Diese enthält die unter dem Schlüssel abgelegten Daten und wird
entlang der Anfragekette an den Initiator übertragen. Die bereits im
System abgelegten Daten werden also repliziert.
= Insert Request
= Data Reply
= Data Insert
= Insert Reply
77
P2P.fm: 23.01.06 08:20
P2P.fm: 23.01.06 08:20
= Insert Request
= Data Reply
= Data Insert
= Insert Reply
■
78
Verwaltet keiner der befragten Knoten den Hashschlüssel,
wird durch den letzten Knoten (HTL=0) eine Insert ReplyNachricht erzeugt.
■
Der Initiator kann nun die Daten mit einer Data InsertNachricht im Netz verbreiten
Diese signalisiert, dass noch keine Daten mit diesem
Hashschlüssel im System vorhanden sind und wird an den Initiator
der Anfrage zurückgeleitet.
= Insert Request
= Data Reply
= Data Insert
= Insert Reply
79
P2P.fm: 23.01.06 08:20
P2P.fm: 23.01.06 08:20
= Insert Request
= Data Reply
= Data Insert
= Insert Reply
80
Freenet: Integration neuer Knoten
■
Integration erfolgt über Announcement-Protokoll
■
Hauptziel: Schnelle Integration; weitere Anforderungen:
Eine Anzahl von Knoten soll gleichberechtigt in die Zuteilung
des Schlüsselbereichs, für den der neue Knoten
verantwortlich ist, beteiligt sein
●
Der zugeteilte Schlüsselbereich muss völlig zufällig sein
●
Der neue Knoten muss nach dem Announcement
ausreichend Kenntnis über seinen Schlüsselbereich
besitzen, d.h. er kann Anfragen beantworten
●
Alle am Announcement beteiligten Konten besitzen nach der
Integration des neuen Knoten Kenntnis über seinen Adresse
und dem ihm zugeordneten Schlüsselraum
81
Freenet
■
■
Node Announcement - Knoten macht sich einer Reihe von
Knoten bekannt. Jeder der Knoten wählt einen Zufallswert
den er nur in Form eines kumulativen Hashwertes weiter gibt.
■
Announcement Reply - Alle Zufallswerte werden entlang
des Anfragepfades via XOR vermengt
■
Announcement Exceute - Erzeugter Schlüssel wird an alle
beteiligten Knoten vermittelt. Diese überprüfen die korrekte
Erzeugung.
■
Announcement Completed - Alle beteiligten Knoten
übermitteln die zum erzeugten Schlüssel lexikografisch
naheliegenden Schlüssel.
P2P.fm: 23.01.06 08:20
P2P.fm: 23.01.06 08:20
●
Freenet: Integration neuer Knoten: Ablauf
Freenet
enet
Allgemein wird jede in Freenet abgelegte Information durch
einen Hashschlüssel referenziert, der mit Hilfe von SHA1
erzeugt wurde
82
■
Erzeugung eines Signed Subspace Keys (SSK)
Erzeuge eine zufällige Zeichenkette für den
Namensbereich ’mp3/’
Datei
■
Es wird zwischen zwei verschiedene Schlüsselarten
unterschieden:
●
Public-Key-Algorithmus
Ein Content Hash Key (CHK) wird durch die Hashsumme
über eine Datei erzeugt und bildet einen Basismechanismus,
um Dateien global eindeutig zu referenzieren
Name: mp3/Laid-Back-Bakerman.mp3
Datei-Schlüssel = hash( hash(öffenlicher Schlüssel) XOR hash(Name))
Freenet-Datei = Datei + sign(Datei)
Signed Subspace Keys (SSK) erlauben die Erzeugung von
privaten Namensräumen, die von jedem Benutzer gelesen,
aber nur durch den Besitzer des Namensraums geschrieben
werden können
83
Beispiel: SSK@9G4s~jLQJB7ALQg-v2q5xKAJy9YPAgM/mp3/Laid-Back-Bakerman.mp3
SSK@ öffentlicher Schlüssel
+
Name der Datei
P2P.fm: 23.01.06 08:20
P2P.fm: 23.01.06 08:20
●
84
Freenet
P2P.fm: 23.01.06 08:20
■
Wie schnell bzw. in welcher Entfernung können Daten
aufgefunden werden?
■
●
1000 Knoten angeordnet in einer Ringstruktur
●
Jeder Knoten kennt initial nur seine unmittelbaren zwei
Vorgänger und Nachfolger im Ring
●
Jeder Knoten verfügt über einen Data Store der maximal 50
Einträge fassen kann und eine Routing-Tabelle mit maximal
200 Einträgen
85
Es werden in zufälliger Reihenfolge Anfrage- und EinfügeOperationen mit einer HTL von 20 durchgeführt
●
Nach 100 Operationen wird das Netz betrachtet und 300
Suchanfragen mit einer HTL von 500 die durchschnittliche
Pfadlänge bestimmt
Durchschnittliche Pfadlänge von Anfragen
86
Freenet
■
87
P2P.fm: 23.01.06 08:20
P2P.fm: 23.01.06 08:20
●
Freenet
■
Ablauf der Simulation
Ausgangspunkt der Simulation
P2P.fm: 23.01.06 08:20
■
Freenet
Verknüpfungsgrad der Knoten => Small-World-Netz
88
Freenet
■
Wie skaliert Freenet?
■
Ausgangspunkt der Simulation
P2P.fm: 23.01.06 08:20
■
●
20 Knoten angeordnet in einer Ringstruktur
●
Sonst gleiche Bedingungen wie in der ersten Simulation
Freenet
■
●
Einfüge- und Anfrage-Operationen wie in der ersten
Simulation
●
Nach jeder fünften Operation wird ein neuer Knoten dem
Netz hinzugefügt
89
91
P2P.fm: 23.01.06 08:20
P2P.fm: 23.01.06 08:20
Freenet
Wie fehlertolerant ist Freenet?
90
Freenet
■
Durchschnittliche Pfadlänge von Anfragen
Ablauf der Simulation
P2P.fm: 23.01.06 08:20
reenet
■
Weitere Entwicklung: Next generation routing mechanism
■
Probleme des aktuellen Systems
●
Keine Unterscheidung zwischen Knoten mit
unterschiedlicher Anbindung und deshalb oft lange
Antwortzeiten
●
Schwierigkeiten das System zu verbessern, da sich
Simulationen nur bedingt als aussagekräftig erwiesen haben
●
Lange Entwicklungszyklen, da Evaluierung von Änderungen
nur im realen System möglich sind
92
Freenet: Next Generation Routing Mechanism
■
■
Intelligentes Routing basierend auf statistischen Informationen
●
Zeitdauer zum Aufbau von Verbindungen
●
Antwortzeiten
●
Anteil der erfolgreichen Anfragen
■
Strategie: Routing von Nachrichten zu dem Knoten, der die
kleinste Antwortzeit erwarten lässt
●
Lokal berechenbar
●
Gute Abschätzungen auch für unbekannte Schlüssel
●
Schätzung passt sich dynamisch an
93
Zeit zur Lokalisierung des gesuchten Schlüssels (Senden der
Query bis Eintreffen der ersten Daten)
Transferzeit der Daten zusammen (Zeit bis Ende des
Datentransfers
95
P2P.fm: 23.01.06 08:20
P2P.fm: 23.01.06 08:20
Anfragezeiten für unbekannte Schlüssel können abgeschätzt
werden
94
Berücksichtigung abgebrochener Verbindungen
●
Sollte ein Knoten überlastet sein, nimmt er temporär keine
Verbindungen an
●
Man kann die durchschnittliche Anzahl der fehlgeschlagenen
Verbindungsversuche und ihre Dauer bertachten. Diese
werden der geschätzten Routing-Dauer hinzugerechnet
Folge bei überlasteten Knoten: Größere erwartete Antwortzeit
berechnet, daher seltener für Anfragen verwendet
Normalisierung der Anfragezeit auf eine mittleren Dateigröße
(Mittelwert aus lokalem Data Stores)
●
■
Die Antwortzeit einer erfogreichen Anfrage setzt sich zusammen:
Nach jeder erfolgreichen Anfrage werden die
nächstliegenden Referenzpunkt verschoben
Abschätzung der Antwortzeiten: Normierung
●
●
●
Es gibt N Referenzpunkte (typisch: N=10), die sich über den
gesamten Schlüsselraum verteilen
Schlüsselraum
■
●
Antwortzeit
P2P.fm: 23.01.06 08:20
P2P.fm: 23.01.06 08:20
Erwartete Antwortzeit muss geeignet vorhergesagt werden
Algorithmus zur Abschätzung von Antwortzeiten (pro Knoten)
96
P2P.fm: 23.01.06 08:20
■
●
„legitimes“ DataNotFound: Daten existieren nicht
(d.h. Routing über diesen Knoten war „gut“)
●
„illegitimes“ DataNotFound: Daten existieren eigentlich, aber
werden nicht gefunden
(d.h. Routing war „schlecht“)
●
Keine sichere lokale Unterscheidung möglich
Addition der Kosten für geschätztes illegitimes DataNotFound
zu den Routingkosten pro Knoten
●
Anzahl und Dauer der DNF
●
Im Vergleich zum Knoten mit kleinstem Anteil an DNF
97
99
P2P.fm: 23.01.06 08:20
P2P.fm: 23.01.06 08:20
■
Berücksichtigung nicht erfolgreicher Anfragen
P2P.fm: 23.01.06 08:20
■
Freenet
Fazit
●
Durch die Abschätzung der Dauer von Anfragen können in
Zukunft Routingentscheidungen nicht nur auf Grund von
lexikografischer Nähe gefällt werden, sondern zusätzlich
basierend auf der Kapazität und der geographischen Nähe
der zur Auswahl stehenden Knoten
●
Die Erfassung von statistischen Daten und die darauf
basierende Abschätzung von Routingzeiten erlaubt eine
bessere Evaluierung von Veränderungen des Routings
98
100

Freenet - Institut für Verteilte Systeme

Transcrição

Documentos relacionados

Selbstmord Ulm - Der schwäbische Milliardär Adolf Merckle

PDF (Single) - Institut für Betriebssysteme und Rechnerverbund

Satzglieder bestimmen

Institution Herzog Anton Ulrich-Museum Signatur ADürer AB 3.216H

Institution Herzog Anton Ulrich-Museum Signatur ADürer WB 3.218

JUGENDLICHE, MUSIK UND DAS INTERNET

Visualization of Monitoring Topologies in Peer-to

Knotenkunde - Freiwillige Feuerwehr Elsholz

Filius 570 Persönliche Angaben

Lichtbogenhandschweissen771.36 kB - DVS Ulm/Neu-Ulm