1
Q
Beispiel für PTP-Systeme
A
E-Mail, BitTorrent, Skype, Streaming-Lösungen
2
Q
Merkmale von PTP-Systemen
A
- Peers (“Clients”) sind meist Teil eines Overlay Netzwerks (bilden in einem anderen Netzwerk logische Verbindungen)
- Kommunizieren direkt und übernehmen Client -und Serveraufgaben
- Peers haben wechselnde Adressen im darüberliegenden Netzwerk
- Sind gleichberechtigte Partner im System
- Können ausfallen, sind nicht zuverlässig verfügbar
3
Q
Napster
A
- Kein richtiges PTP System, da Indexserver
4
Q
Gnutella 0.4
A
- Bootstrapping mit Liste stabiler peers + gwebcache (server mit liste aktuell aktiver peers)
- Ping mit ID, TTL und Hop-Count
- Join
○ Pings werden weitergeleitet, Duplikate vermieden, bei TTL=0 verworfen
○ Pongs werden zurückgeroutet, anhand es Weges des zugehörigen Pings - Suche
○ Query und QueryHit ähnlich wie Ping und Pong, Download direkt via HTTP - Lange antwortzeiten, sucherfolg mit glück
- Hat small world eigenschaften
5
Q
Gnutella 0.6
A
- Hierarchisches overlay mit ultrapeers
- Query Routing Protocol:
○ Dateiregistrierung beim Ultrapeer, Suche nur im Ultrapeer-Netzwerk
○ Dynamic Querying: 1. lokale Suche, 2. kleine Suche, 3. große Suche mit geschätztem TTL aus kleiner Suche
- Query Routing Protocol:
6
Q
Clustering-Koeffizient
A
- Kanten zwischen Nachbarn / mögliche Kanten zwischen Nachbarn
- Bedeutet wahrscheinlichkeit, dass zwei nachbarn selbst nachbarn sind
7
Q
Zufallsgraphen
A
- Haben oft viel kleineren clustering-koeffizienten als reale netze
- Kennzahlen: Knotengrad, Durchschnittliche Pfadlänge
8
Q
Small world (Graph)
A
- Kleine durchschn. Pfadlänge, hoher Clustering Koeffizient
- Gitter, Konten mit 4 Nachbarn + 1 Fernkante vernetzt
9
Q
Skalenfreie Netze
A
- Wenige stark vernetzte, viele schwach vernetzte Knoten
- Pareto-Verteilung
- Entsteht, wenn neu hinzukommende knoten sich mit einem knoten mit hohem knotengrad verbinden
- Robustheit bei zufälligen ausfällen, aber anfällig für gezielte angriffe
10
Q
DHT + Beispiele
A
Beispiele: Gnutella, CAN, CHORD, Distance Halving und Kademlia
11
Q
CAN
A
- Zustand: O(d)⁆, Routing O(dn^(1/d) )
- Konstanter Grad, polynomieller Durchmesser
- Quadrat, Schlüssel in 0..1 + 0..1, erst horizontal dann vertikal teilen
- Soft state
- Variationen:
○ Dimensionen: mehr Routingeffizienz
○ Realitäten: mehr Robustheit, da Schlüssel bei anderen Peers, und auch etwas mehr Routingeffizienz
○ Underlay-aware-routing mir RTT (roundtriptime): bessere Latenz
○ Überladen von Zonen: reduziert pfadlänge (wegen größerer gebiete) und latenz und robustheit, aber komplexer
○ Mehrere Hashfunktionen: Robustheit, Pfadlänge, Latenzoptimierung mit simultanen Anfragen möglich - Caching und Replikation möglich: Hot Spots vermeiden
12
Q
Chord
A
- Ring, 0..2^m−1
- Zustand O(log n), Routing O(log n)
- Logarithmischer Durchmesser, logarithmischer Grad
- Predecessor/Successor
- Successor-Routing O(n), Größe der Fingertabelle: O(log n)
- Stabilize: Nachfolger nach Vorgänger fragen
- Fix Fingers
- Check Predecessor
- Variationen:
○ Successor-Listen: Robustheit und dabei sogar effizient
13
Q
Overlay Prinzipielle Schranken
A
- Bei d ausgehenden kanten in höchstens h Schritten < d^(h1) Knoten erreichbar
- Tradeoff zwischen Grad und Durchmesser
14
Q
Distance Halving
A
Gradminimierte Netzwerke: Kontinuierliche Graphen: Distance Halving
- Konstanter Grad, logarithmischer Durchmesser - Routing in O(log n) Schritten, Nachbarschaftsgröße O(1)
15
Q
Kademlia
A
- UDP basiert, daher ist Zustandsgröße kein großes Problem: k-Buckets
- ID ist Bitstring (160 im Original-Paper)
- XOR als Abstandsmetrik, max. k Einträge in einem Bucket
- Nutzt fremden datenverkehr um routinginformationen zu gewinnen
- Logarithmisches Routing
- Schlüssel werden auf k Peers abgelegt für Redundanz
- Suche nach k nächsten Peers einer ID
○ K nächste peers aufstellen und alpha=3 Peers eine Find_Node anfrage schicken (Parallel)
○ Antworten in liste einsortieren und immer alpha=3 anfragen parallel verschicken an die nächsten peers der aktuellen liste
○ Alpha=1 wie chord, höher desto schneller aber auch mit mehr last - Caching als soft-state bei dem nächsten peer, der den schlüssel nicht hatte
- Join: 1. Suche nach eigener ID für nachbarn und dann Suche nach zufälligen Ids der jeweiligen Buckets zur Befüllung der Buckets und zum Bekanntmachen
- Republish alle Stunde: lokale suche und replizierung der schlüssel auf k nächste peers
16
Q
BubbleStorm
A
- Keine DHT, ermöglicht unstrukturierte Suche (Dateiname, Größe, Format …)
- Daten und Anfrage sollen sich in mindestens einem Punkt treffen
- Sucherfolgswahrdscheinlichkeit ≥1−e^(−dq/n)
- Zufälliger Graph, Knotengrad abhängig von verfügbarer Bandbreite, immer eine gerade Zahl, konstant
- Neuer knoten hängt sich zwischen zufällig ausgewählte kanten
- Wahl der kanten mit random walks
- Wenn ausreichend lang, ist der endpunkt zufällig
- Zum platzieren von kopien: bubblecast: erstellen von w kopien, 1 bei jedem besuchten knoten, verbleibende an nachbarn aufteilen
- Zufällige soft-state replikation
17
Q
NAT Eigenschaften / Techniken
A
Full cone restricted cone Hairpin-Translation Symmetrisch/Asymmetrisch UPnP/Statische Portweiterleitungen
18
Q
Restricted cone
A
Ausgehende Anfrage erlaubt nur antwort von gleicher ziel-Adresse
19
Q
Port restricted cone
A
Ausgehende Anfrage erlaubt nur antwort von gleicher ziel-adresse und port
20
Q
Relaying:
A
viel Datenverkehr, Latenz
21
Q
Hole-Punching
A
ermitteln öffentlicher und privater adressen mit rendevouz-punkt
○ Gleichzeitiger verbindungsaufbau über denselben socket (so hoffentlich selbe Portnummer wie vorher)
○ Bei tcp: min. 3 sockets mit demselben port: server, client zu rendevous, client zum peer
○ Voraussetzung: bei selbem internen ip+port auch extern selber port
22
Q
Hairpin-translation
A
○ Bei zwei peers hinter demselben nat: doppelte anwendung von NAT (ein und ausgehend)
23
Q
Symmetrischer nat
A
Unterschiedliche ports bei gleichem internen ip+port je nach externer ip
§ Lösung dort: Intelligentes raten
24
Q
Angriffsmöglichkeiten
A
- Denial of Service
○ Gegenmaßnahmen: Kryptografische Puzzles, Captchas, Syn-Cookies- Poisoning Angriffe
○ Verbreitung falscher Routinginformationen oder Daten
○ Gegenmaßnahmen: Einflussbereich einschränken, z.B. ID abhängig von IP Adresse - Fehlerhaftes Weiterleiten
○ Gegenmaßnahme: Kontrolle beim Anfragenden belassen, iterativ statt rekursiv - Eclipse-Angriffe
○ Isolierung von Peers (kooperativ)
○ Gegenmaßnahmen: feste IDs - Sybil Angriffe
○ Viele Identitäten annehmen für Mehrheits-Einflüsse
○ Gegenmaßnahmen: Zertifizierte Identitäten, Existenz-Nachweise mit Puzzles o.ä., Reputationssysteme
- Poisoning Angriffe
25
Reputationssysteme
- Symmetrisch
○ Alle teilnehmer sind gleichwertig
- Asymmetrisch
○ Besonders vertrauenswürdige instanzen
26
Auditing
- Berichte über Verhalten wird von anderen Peers kontrolliert, beispiel Speicherplatznutzung
27
Spieltheorie
- Nimmt Streng rational handelnde personen an
- Eine Strategie ist strikt dominant, wenn sie stets einen höheren Nutzen bringt
- Strategieprofil ist Nash-Gleichgewicht, wenn kein Spieler durch das Ändern seiner Strategie einen Vorteil erlangen kann
- Strategieprofil ist gegenüber einem anderen Pareto-Überlegen, wenn mind. Ein Spieler einen Vorteil hat und gleichzeitig kein anderer einen Nachteil hat.
- Stategieprofil ist pareto-optimal, wenn es kein pareto-überlegenes Strategieprofil gibt
- Gefangenendilemma - Payoff Matrix: schweigen/gestehen A/B
○ Einer verrät, beide halten dicht oder beide gestehen
- Mechanism Design: Inverse Spieltheorie, funktionierende Anreizsysteme schaffen
28
BitTorrent
kooperativer Dateidownload
- .torrent Datei
○ Datei-Metainformationen
○ Tracker-URL
○ SHA1-Hashwert aller Teile
- Tracker für zufälliges Bootstraping mit aktiven Peers -> unstrukturiertes Overlay, gibt auch eine trackerless--basierte Lösung
○ Kademlia DHT, speichern der aktiven peers als liste an schlüsselposition (datei-id)
- Initial-Seeder
- Einteilung in Pieces (256KB) und Subpieces (16KB)
- Anfragen von Subpieces:
1. Angefangenes Vervollständigen
2. Seltenes Zuerst
3. Zufällige Teile zu Beginn
4. Endspiel Modus
i. SobaldallenochfehlendenUnterteileirgendwoangefragt sind,wirdjederUnterteilbeijedemNachbarnangefragt
- Peer kann uploaden ("Kooperieren") oder nicht ("choken"): Währung
- Unchoking-Strategie soll pareto-effizient sein:
○ Belohnen von peers mit upload, die mir daten senden
§ Stabile Verbindungen
○ Ungenutzte Bandbreite für das Anweben neuer Kooperationen
○ Upload nur zu vier besten Nachbarn (höchste Datenrate) + 1 Zufällig
○ Anti-Snubbing: wenn lange kein vollständiger Teil, dann stattdessen zusätzliches Anwerben
29
Streaming
Rechtzeitige Übertragung
○ Live-Streaming
§ Aufteilung in Chunks
§ Ein Baum
§ Mehrere Bäume
§ Vermaschtes Netz wie BitTorrent mit Angebot-Nachfrage oder anderer Steuerung
○ Video on Demand: Asynchronität
§ Patches und regelmäßiger Streaming-Start
□ Patches Download auf separatem Weg
§ Intervall-Caching
□ Vorhalten der letzten x Minuten und weiterübertragung
§ Vermaschtes Netz wie Bittorrent: Angebot-Nachfrage funktioniert nicht , stattdessen Reputationssystem
30
DHT-Vergleichskriterien
Kommunikationsaufwand
für das Routing (Lookup-Pfadlänge)
für die Verwaltung der Datenstruktur (Join/Leave,
Reparaturen,. . . )
Robustheit,Zuverlässigkeit
gegen Ausfälle
gegen Angreifer
Fairness
bezüglich der Schlüsselverteilung
bezüglich der Routing-Last
Zustandsgröße
insbes. die Zahl der Verbindungen im Overlay (Grad)
