CharakteristikaPeers bilden ein Overlay-NetzwerkPeers bieten und konsumieren Dienste und RessourcenPeers besitzen signifikante AutonomieEs ist ein selbstorganisierendes SystemDienste können zwischen allen teilnehmenden Peers ausgetauscht werden
Keine zentrale Kontrolle & keine Nutzung zentraler Dienste
Ebenfalls wichtigPeers sind heterogenZuverlässige, dauerhafte Verbindungen der Peers können nicht vorausgesetzt werden
Z.B. Unterstützung Einwahl-Nutzern mit variablen IP-AdressenZ.B. hinter FirewallP2P-Systeme operieren außerhalb des DNS-Systems
4
KOM – Multimedia Communications Lab 7
Overlay Netzwerk Schicht
Picture adapted from Traversat, et.al Project JXTA virtual network
TCP/IPNetwork
TCP/IPNetwork
Firewall + NAT
TCP/IPNetwork
TCP/IPNetwork
TCP/IPNetwork
TCP/IPNetwork
HTTP TCP
Peers identified by PeerID
Dienst ADienst B
Dienst C
Relay
Overlay Netzwerk
Underlay-Netzwerk
Peers identifiziert durch PeerID
KOM – Multimedia Communications Lab 8
DHT-basiertReines P2P Hybrides P2PZentrales P2P
1. Besitzt alle Eigen-schaften von P2P
2. Any terminal entitycan be removedwithout loss of functionality
3. keine zentrale Stelle
4. Verbindungen im Overlay sind “fest”
Beispiele: Chord, CAN
1. Besitzt alle Eigen-schaften von P2P
2. Jeder Knoten kann entfernt werden ohne Funktions-verlust
3. dynamisch zentrale Stellen
Beispiele: Gnutella 0.6, Fasttrack, eDonkey
1. Besitzt alle Eigen-schaften von P2P
2. Jeder Knoten kann entfernt werden ohne Funktions-verlust
3. keine zentrale Stelle
Beispiele: Gnutella 0.4, Freenet
1. Besitzt alle Eigen-schaften von P2P
2. Zentrale Stelle notwendig um Dienste zu leisten
3. Zentrale Stelle ist Art Index/Gruppen-Datenbank
Beispiel: Napster
Strukturierte P2PUnstrukturierte P2P-Overlays
1. Generation 2. Generation 3. Generation
nach R.Schollmeier and J.Eberspächer, TU München
Übersicht P2P-Overlays
5
KOM – Multimedia Communications Lab 9
Gnutella v0.4
Ein Netzwerk zum Suchen und Entdecken
Gedacht für Mensch und nicht Maschine
Total dezentral Nicht wirklich zu stoppen
Freie Interpretation der Anfrage Suchanfrage wird unverändert weitergeleitetAntworten können verschiedenste Form haben
DateinamenWerbenachrichtenURLs
“Anonymes“ Suchen
KOM – Multimedia Communications Lab 10
Gnutella Protokoll [1]
Gnutella Deskriptoren regeln Kommunikation
DeskriptorenPing : Netz aktiv erforschenPong : Antwort auf PingQuery : Eigentliche Suchanfrage
(TTL limitiert Reichweite)Query hit : Positivantwort auf SuchanfragePush Request : Initiiert das Senden (Firewall)
ReichweiteBei TTL 7 erreichen die Suchanfragen ca. 10 000 Hosts
6
KOM – Multimedia Communications Lab 13
Gnutella 0.6Hybrides P2P Overlay Netzwerk
Gnutella 0.6 ist ein typisches P2P System der 2. Generationvon R.Schollmeier and J.Eberspächer, TU München
KOM – Multimedia Communications Lab 14
Chord
Benutzt SHA-1 zum Abbilden von IP-Adressen/Objektnameauf 160 Bit ID
Grundlegende Ring Topologie mod 2n Successor/ Predecessor
Circular Key Space
Link zum Ring-Successor
22072012-2207
29062683-29063485
2907-3485
20111623-2011
16221009-16221008
710-1008709660-709
659612-659
26822208-2682
6113486-40950-611Erweiterte Topologie
K-ter Finger zu Peer n ist Abkürzung, die auf den Peer zeigt verantwortlich für Objekt ID (n + 2k)O(log(N)) Finger führen zu lookup-Operation mit O(log(N))
Finger zeigen auf Peers mit ObjektIDs, exponentiell ansteigend. Hier: 709 + 2k
= …, 965, 1221, 1733, 2757
22072012-2207
29062683-29063485
2907-3485
20111623-2011
16221009-16221008
710-1008709660-709
659612-659
26822208-2682
6113486-40950-611
7
KOM – Multimedia Communications Lab 15
Chord: Inhaltsadressierung
LookupEnthält Hash-Wert des gesuchten InhaltsIn jedem Schritt wird die Distanz zum Ziel halbiert
Konten 1008 sucht Element 3000
Finger werden benutzt um Ziel schneller zu finden. Ohne Finger: Keine Abkürzung, im Kreis laufen
Verantwortliches Peer gefunden
22072012-2207
29062683-29063485
2907-3485
20111623-2011
16221009-16221008
710-1008709660-709
659612-659
26822208-2682
6113486-…0-611
2
Verantwortlich für 1008 + 1024
31
Verantwortlichfür 2207 + 512
Verantwortlich für 3000
KOM – Multimedia Communications Lab 17
Kademlia: Systembeschreibung
Knoten sind Blätter in einem binären BaumPosition wird durch kürzesten eindeutigen Prefix der Node ID bestimmt
Für jeden Knoten (z.B. Knoten „001“)Teile den Binären Baum in eine Serie aufeinander-folgender niedrigerer Unterbäume die diesen Knoten nicht enthaltenMindestens ein Kontaktknoten benötigt zu jedem Unterbaum
Große Unterbäume bieten viele Alternativen für Nachbarn
Bucket 0:distance [20, 21)
Bucket 1: distance [21, 22)
Bucket n:distance [2n, 2n+1)
...
8
KOM – Multimedia Communications Lab 18
Kademlia: Lookup-Operation
Jeder Hop leitet das Queries an alle kleineren Unterbäume um das Ziel herum weiter
Beispiele: Knoten „001“ routet nach “101”Knoten „001“ benötig einen Kontakt im1-(*) Unterbaum (z.B. „110“)Knoten „110“benötig einen Kontakt im 10-(*) Unterbaum (z.B. „100“Knoten „100“ leitet das Query zum Ziel „101“
1 23
KOM – Multimedia Communications Lab 21
Globase.KOM: Scenario
Čevapčići…
Location-based Search
Suche nach Inhaltenin einem definierten geographischem Gebiet CL
OSED
9
KOM – Multimedia Communications Lab 22
Globase.KOM: Overview
Globase.KOM(Geographical LOcation-BAsed SEarch):
Welt unterteilt in nicht überscheidende, rechteckige ZonenZweischichtiges Overlay:
Hierarchischer Superpeers- BaumUnstrukturiertes P2P-Network für verbundene Peer
Fehlerbehebungs- und Such- effizienzZwischen-verbindungen:
Lernen von erhaltenen Nachrichten
*Assumption: peer knows its Galileo/GPS coordinates
KOM – Multimedia Communications Lab 23
Query-Beispiel: Gebietssuche
Schritte zur Durchführung einer Bereichssuche:Query beginnt auf Knoten JAntworten von Knoten A, B, C, E, und F
A
B C D E
F G H I JK
A
B
C
D
E
G
H
I
J
K
F
SEARCH QUERY
10
KOM – Multimedia Communications Lab 24
Zusammenfassung Overlay-Netzwerke
Strukturierte OverlaysFür Systeme die Primärschlüssel-Abfragen benötigenVollständige SuchergebnisseEventuell nicht 100% aktuell
Unstrukturierte OverlaysBesser geeignet für komplexere AbfragenAktuelle ErgebnisseEventuell nicht vollständig
Aktuell ForschungsfragenRouting-OptimierungNetzpartitionierung und -zusammenführungAdaption an das Underlay (Lokationsbewußtsein)Umgang mit „Churn“
KOM - Multimedia Communications LabProf. Dr.-Ing. Ralf Steinmetz (Director)
Dept. of Electrical Engineering and Information TechnologyDept. of Computer Science (adjunct Professor)
TUD – Technische Universität Darmstadt Merckstr. 25, D-64283 Darmstadt, Germany
Software Updates (100 MB+)Neue OS Releases (1,5 GB+)
Verteilung digitaler Inhalte mit P2P
Quellserver(Content provider)
1000+ clients
Ziel des Content Providers: Kosten minimieren
Umgebung: Quellserverbetriebskosten hängen von Ausgangsbbandbreite abEinsparung: Nutzen P2P-basiertes Content-Delivery-System
Content Provider möchte Ubuntu Linux (1 GB) verteilen
KOM – Multimedia Communications Lab 27
Kooperatives Dateitauschen (wie BitTorrent):
BitTorrent zu Beginn Idealer BitTorrent-Betrieb
von
ww
w.w
tata
.com
12
KOM – Multimedia Communications Lab 28
BitTorrent: Schnelle Verteilung mit Anreizen
Prozess1. Große Datei wird in “Chunks” aufgeteilt
2. Peers, die an der gleichen Datei interessiert sind, “selbstorganisieren”sich in einem “torrent”
3. Peers tauschen untereinander “Chunks”der Datei aus
Anreizmechanismus für Uploadtit-for-tat
BewertungLeichtgewichtig und effizientSkaliert gut bei „Flash Crowd“
4 5
Torrent of Bits
...
KOM – Multimedia Communications Lab 29
Der “Publisher”Erstellen Metadatei “foo.torrent”Veröffentlichen auf WebseiteStarten des TrackersStarten eines BT-Clients alsinitiale Quelle (initial seed)
3 4 5...
Tracker siteWeb site
foo.torrent
Hier bin ich!
peer list
foo.torrent announce: tracker URL for bootstrapcreation date: epoch time
Der DownloaderDownload der Metadatei foo.torrentStart eines BT-Clients, verbindenzum TrackerBeziehe Peer-Liste vom TrackerBeziehe erstes Chunk von anderenPeers (seeds)
3 4 5...
Tracker siteWeb site
foo.torrent
foo.torrent
peer list
downloadI am here!
peer list
seed
Wie BitTorrent funktioniert: Downloading
KOM – Multimedia Communications Lab 31
Der DownloaderDownload der Metadatei foo.torrentStart eines BT-Clients, verbindenzum TrackerBeziehe Peer-Liste vom TrackerBeziehe erstes Chunk von anderenPeers (seeds)Tausche Chunks der Datei mitanderen PeersDownload vollständig: werde eineneue Quelle (seed)
3 4 5...
Tracker siteWeb site
foo.torrent
foo.torrent
peer list
seed
foo.torrent
Wie BitTorrent funktioniert: Downloading
14
KOM – Multimedia Communications Lab 32
3 4 5...
The downloaderDownload der Metadatei foo.torrentStart eines BT-Clients, verbindenzum TrackerBeziehe Peer-Liste vom TrackerBeziehe erstes Chunk von anderenPeers (seeds)Tausche Chunks der Datei mitanderen PeersDownload vollständig: werde eineneue Quelle (seed)Initiale Quelle verlässt dasNetzwerk
3 4 5...
Tracker siteWeb site
foo.torrent
foo.torrent
peer list
seed
foo.torrent
seed
Zukünftige LeistungsfähigkeitHängt vom Hinzukommen und
Verlassen von neuen Downloadernund Quellen ab
Wie BitTorrent funktioniert: Downloading
KOM – Multimedia Communications Lab 33
Streaming
Traditionelle CDNRegionale Datenzentren
Live StreamingVerteilen an DatenzentrenVerteilen an Endknoten
VoD StreamingUpload in alle DatenzentrenDownload-Anforderung wird an lokales Datenzentrum geleitet
NachteileHohe Verkehr
In DatenzentrenHohe operative Kosten
Quelle: Goolge Earth
15
KOM – Multimedia Communications Lab 34
P2P Live Streaming
Kooperation der EndknotenLeiten (Teil des) Streams an weitere Endknoten weiter
Herausforderung:Kleine Upload-Bandbreite der PeersServer können unterstützen
Aufbau eines Multicast-Streaming-Baums auf Anwendungsebene
