1 Peer-to-Peer Technologischer Überblick - KOM

Transcrição

Peer-to-Peer
Technologischer Überblick
Dr.-Ing. Nicolas C. Liebau, KOM, TU Darmstadt
Dr.-Ing. Nicolas C. Liebau
[email protected]
Tel.+49 6151 165240
KOM - Multimedia Communications Lab
Prof. Dr.-Ing. Ralf Steinmetz (Director)
Dept. of Electrical Engineering and Information Technology
Dept. of Computer Science (adjunct Professor)
TUD – Technische Universität Darmstadt
Merckstr. 25, D-64283 Darmstadt, Germany
Tel.+49 6151 166150, Fax. +49 6151 166152
www.KOM.tu-darmstadt.de
18.02.2009
© author(s) of these slides 2008 including research results of the research network KOM and TU Darmstadt otherwise as specified at the respective slide
Observations
Content Owners
Distribution of digital content over the Internet
Media industry fighting it since 1999
February 2001 – Napster has 50 million reg. User
2.79 billion music-downloads
February 2006 – Episode of TV-series “Lost”
downloaded 500.000 times via BitTorrent-network
P2P Traffic in the Internet
60% – 80% P2P file sharing traffic on backbones
Internet Protocol Breakdown 1993 - 2006
KOM – Multimedia Communications Lab
Source: CacheLogic Research
2
1
Bekannte Anwendungsgebiete
Dateitauschbörsen (Filesharing)
eMule, KaZaA, BitTorrent, DC++, …
Kommerzielle Verteilung digitaler Medien
Download, Video on Demand (VoD) Streaming,
Live Streaming
Mercora (Audio), In2movies, Octoshape, Zattoo, ….
VoIP
Skype
Persistente Datenhaltung
OceanStore
3
4
Inhalt
Definition
Overlay-Netzwerke
Gnutella
Chord
Kademlia
Globase.KOM
Verteilung digitaler Medien
Swarming mit BitTorrent
Network Coding
Life Streaming
VoD Streaming
Forschungsthemen und industrielles Umfeld
2
Peer-to-Peer Technologie
Definition & Overlay-Netzwerke
[email protected]
Tel.+49 6151 165240
Tel.+49 6151 166150, Fax. +49 6151 166152
18.02.2009
P2P - Definition
Charakteristika
Peers bilden ein Overlay-Netzwerk
Peers bieten und konsumieren Dienste und Ressourcen
Peers besitzen signifikante Autonomie
Es ist ein selbstorganisierendes System
Dienste können zwischen allen teilnehmenden Peers ausgetauscht werden
Keine zentrale Kontrolle & keine Nutzung zentraler Dienste
Ebenfalls wichtig
Peers sind heterogen
Zuverlässige, dauerhafte Verbindungen der Peers können nicht vorausgesetzt
werden
Z.B. Unterstützung Einwahl-Nutzern mit variablen IP-Adressen
Z.B. hinter Firewall
P2P-Systeme operieren außerhalb des DNS-Systems
6
3
Overlay Netzwerk Schicht
Dienst B
Dienst A
Dienst C
Peers
identifiziert
Peers
identified
by PeerID
durch PeerID
Overlay Netzwerk
TCP/IP
TCP/IP
Network
Relay Network
HTTP
Firewall + NAT
TCP/IP
TCP/IP
Network
Network
TCP
TCP/IP
TCP/IP
Network
Network
UnderlayNetzwerk
Picture adapted from Traversat, et.al Project JXTA virtual network
7
Übersicht P2P-Overlays
Unstrukturierte P2P-Overlays
Strukturierte P2P
Zentrales P2P
Reines P2P
Hybrides P2P
DHT-basiert
1. Besitzt alle Eigenschaften von P2P
2. Zentrale Stelle
notwendig um Dienste
zu leisten
3. Zentrale Stelle ist Art
Index/GruppenDatenbank
1.
1. Besitzt alle Eigenschaften von P2P
2. Jeder Knoten kann
entfernt werden ohne
Funktions-verlust
3. Æ dynamisch zentrale
Stellen
1.
Beispiel: Napster
2.
3.
Besitzt alle Eigenschaften von P2P
Jeder Knoten kann
entfernt werden ohne
Funktions-verlust
Æ keine zentrale
Stelle
Beispiele:
Gnutella 0.4, Freenet
1. Generation
Beispiele:
Gnutella 0.6, Fasttrack,
eDonkey
2. Generation
Besitzt alle Eigenschaften von P2P
2.
Any terminal entity
can be removed
without loss of
functionality
3.
Æ keine zentrale
Stelle
4.
Verbindungen im
Overlay sind “fest”
Beispiele: Chord, CAN
3. Generation
nach R.Schollmeier and J.Eberspächer, TU München
8
4
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 weitergeleitet
Antworten können verschiedenste Form haben
Dateinamen
Werbenachrichten
URLs
“Anonymes“ Suchen
9
Gnutella Protokoll [1]
Gnutella Deskriptoren regeln Kommunikation
Deskriptoren
Ping :
Pong :
Query :
Netz aktiv erforschen
Antwort auf Ping
Eigentliche Suchanfrage
(TTL limitiert Reichweite)
Query hit :
Positivantwort auf Suchanfrage
Push Request : Initiiert das Senden (Firewall)
Reichweite
Bei TTL 7 erreichen die Suchanfragen ca. 10 000 Hosts
KOM – Multimedia Communications Lab 10
5
Gnutella 0.6
Hybrides P2P Overlay Netzwerk
Gnutella 0.6 ist ein typisches P2P System der 2. Generation
von R.Schollmeier and J.Eberspächer, TU München
Chord
Benutzt SHA-1 zum Abbilden von IP-Adressen/Objektname
auf 160 Bit ID
Grundlegende Ring Topologie mod 2n
709
Successor/
660-709
Predecessor
Link zum Ring-Successor
2011
1009-1622
2207
1623-2011
2012-2207
2682
Circular Key Space
659
612-659
Erweiterte Topologie
1622
1008
710-1008
611
3486-4095
0-611
2208-2682
2906
3485
2683-2906
2907-3485
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
709
660-709
1622
1008
2011
1009-1622
710-1008
1623-2011
2207
2012-2207
2682
2208-2682
659
612-659
611
3486-4095
0-611
3485
2907-3485
2906
2683-2906
6
Chord: Inhaltsadressierung
Lookup
Enthält Hash-Wert des gesuchten Inhalts
In jedem Schritt wird die Distanz zum Ziel halbiert
Finger werden benutzt um
Ziel schneller zu finden.
Ohne Finger: Keine
Abkürzung, im Kreis laufen
Konten 1008 sucht
Element 3000
1622
1008
709
1009-1622
710-1008
2011
2207
1623-2011
660-709
2012-2207
1
2682
3
659
612-659
611
3486-…
0-611
Verantwortlich
für 1008 + 1024
3485
2
2208-2682
2906
2683-2906
2907-3485
Verantwortlich
für 2207 + 512
Verantwortlich
für 3000
Verantwortliches
Peer gefunden
Kademlia: Systembeschreibung
Knoten sind Blätter in einem binären Baum
Position 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 enthalten
Mindestens 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)
7
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 im
1-(*) 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
3
2
Globase.KOM: Scenario
Čevapčići…
Location-based Search
Suche nach Inhalten
in einem definierten
geographischem
Gebiet
ED
OS
L
C
8
Globase.KOM: Overview
Globase.KOM
(Geographical LOcationBAsed SEarch):
Welt unterteilt in
nicht überscheidende, rechteckige
Zonen
Zweischichtiges Overlay:
Hierarchischer Superpeers- Baum
Unstrukturiertes P2P-Network für
verbundene Peer
Fehlerbehebungs- und Such- effizienz
Æ Zwischen-verbindungen:
Lernen von erhaltenen Nachrichten
*Assumption: peer knows its Galileo/GPS coordinates
Query-Beispiel: Gebietssuche
A
B
B
G
F
E
D
C
J
F
G
H
I
K
J
H
E
K
D
C
I
A
SEARCH QUERY
Schritte zur Durchführung einer Bereichssuche:
Query beginnt auf Knoten J
Antworten von Knoten A, B, C, E, und F
9
Zusammenfassung Overlay-Netzwerke
Strukturierte Overlays
Für Systeme die Primärschlüssel-Abfragen benötigen
Vollständige Suchergebnisse
Eventuell nicht 100% aktuell
Unstrukturierte Overlays
Besser geeignet für komplexere Abfragen
Aktuelle Ergebnisse
Eventuell nicht vollständig
Aktuell Forschungsfragen
Routing-Optimierung
Netzpartitionierung und -zusammenführung
Adaption an das Underlay (Lokationsbewußtsein)
Umgang mit „Churn“
Verteilung digitaler Medien –
Schwarm-Effekt & Streaming
[email protected]
Tel.+49 6151 165240
Tel.+49 6151 166150, Fax. +49 6151 166152
18.02.2009
10
Verteilung digitaler Inhalte mit P2P
Quellserver
(Content provider)
Content Provider möchte Ubuntu Linux (1 GB) verteilen
Dateien
Multimedia Daten:
Audio (3 MB+)
Video (650 MB+)
Software Updates (100 MB+)
Neue OS Releases (1,5 GB+)
1000+ clients
Ziel des Content Providers: Kosten minimieren
Umgebung: Quellserverbetriebskosten hängen von Ausgangsbbandbreite ab
Einsparung: Nutzen P2P-basiertes Content-Delivery-System
Kooperatives Dateitauschen (wie BitTorrent):
Idealer BitTorrent-Betrieb
von www.wtata.com
BitTorrent zu Beginn
11
BitTorrent: Schnelle Verteilung mit Anreizen
Prozess
1. Große Datei wird in “Chunks” aufgeteilt
4 5
2. Peers, die an der gleichen Datei
interessiert sind, “selbstorganisieren”
sich in einem “torrent”
Torrent of Bits
3. Peers tauschen untereinander “Chunks”
der Datei aus
Anreizmechanismus für Upload

tit-for-tat
Bewertung
...

Leichtgewichtig und effizient
Skaliert gut bei „Flash Crowd“
Wie BitTorrent funktioniert: Publishing
Seed = Quelle
...
foo.torrent
3 4 5
Hier bin ich!
foo.torrent
peer list
Tracker site
announce: tracker URL
for bootstrap
creation date: epoch time
of file creation
length: file size
name: file name
piece length: chunk size
pieces: SHA1 hash key
of each chunk
Web site
Der “Publisher”
Erstellen Metadatei “foo.torrent”
Veröffentlichen auf Webseite
Starten des Trackers
Starten eines BT-Clients als
initiale Quelle (initial seed)
12
Wie BitTorrent funktioniert: Downloading
seed
...
3 4 5
foo.torrent
peer list
Tracker site
Der Downloader
Download der Metadatei foo.torrent
Start eines BT-Clients, verbinden
zum Tracker
Beziehe Peer-Liste vom Tracker
Beziehe erstes Chunk von anderen
Peers (seeds)
Web site
peer list
download
I am here!
foo.torrent
seed
...
3 4 5
foo.torrent
peer list
Tracker site
foo.torrent
Web site
Der Downloader
zum Tracker
Peers (seeds)
Tausche Chunks der Datei mit
anderen Peers
Download vollständig: werde eine
neue Quelle (seed)
foo.torrent
13
seed
Zukünftige Leistungsfähigkeit
... 3 4 5
Hängt vom Hinzukommen
und
Verlassen von neuen Downloadern
und Quellen ab
foo.torrent
peer list
Tracker site
Web site
foo.torrent
foo.torrent
The downloader
zum Tracker
Peers (seeds)
Tausche Chunks der Datei mit
anderen Peers
Download vollständig: werde eine
neue Quelle (seed)
Initiale Quelle verlässt das
Netzwerk
seed
...
3 4 5
Streaming
Traditionelle CDN
Regionale Datenzentren
Live Streaming
Verteilen an Datenzentren
Verteilen an Endknoten
VoD Streaming
Upload in alle Datenzentren
Download-Anforderung wird an lokales Datenzentrum geleitet
Nachteile
Hohe Verkehr
In Datenzentren
Hohe operative Kosten
Quelle: Goolge Earth
14
P2P Live Streaming
Kooperation der Endknoten
Leiten (Teil des) Streams an weitere
Endknoten weiter
Herausforderung:
Kleine Upload-Bandbreite der Peers
Server können unterstützen
Aufbau eines Multicast-StreamingBaums auf Anwendungsebene
Detailablauf abhängig von verwendetem
Codec
Standard: H.264
Chunk basiert
Z.B. Octoshape, emundoo
Layered Video Codecs
P2P Live Streaming
Forschungsfragen
Aufbau des Streaming-Baums
Unterstützung heterogener Peers
Aufbau eines „Meshs“ zur Unterstützung mit „nicht vollständigen“ Streams
Unterhaltung des Streaming-Baums
Umgang mit ausfallenden Knoten
Mesh oder Multibaum besser als einfacher Baum
Abspielstrategien
Delay-erhaltend
Delay bleibt konstant, Paketverluste geduldet
Qualitäterhaltend
Keine Paketverluste, Abspiel wird verzögert
Welche ergibt höhere QoE?
Anreize zur Kooperation
15
P2P VoD Streaming
Kooperation mit vorangegangenen
Nutzern
Datei in Teile unterteilt
Rechtzeitiges herunterladen des
benötigten Dateiteils
Ähnlich BitTorrent
Z.B. NextShare, emundoo
Eventuell Unterstützung durch Server
(Quelle)
Aktuelle Fragestellungen bei P2P Streaming
Minimieren der Wartezeiten bis zum
Anspielen
Auch bei Vorspulen, etc.
Minimieren von Caching
Teilgröße
Abhängig von Verteilung
Je kleiner, je größerer
Verwaltungsaufwand
Abhängig von Codierung
Je kleiner je eher passend zu Key
Frames
Replikationsmechanismus
Welche Teile, welche Anzahl
Auf welchen Knoten
Zusätzlich zur Entlastung der
Quellserver
Anreize zur Kooperation
Nicht-monetäre Anreizsysteme
Peer-assisted CDNs
Hybride P2P-Systeme mit Servern für
Erhöhung der Zuverlässigkeit
Gerade bei kleinen Schwärmen
NAT-Durchdringung
16
Forschungsthemen und industrielles Umfeld
[email protected]
Tel.+49 6151 165240
Tel.+49 6151 166150, Fax. +49 6151 166152
18.02.2009
Aktuelle Forschungsthemen
Medienverteilungsstrategien
BitTorrent, etc.
Anreizmechanismen
Vertrauen und Reputation
Streaming (VoD oder live)
Overlay-Netzwerke
Overlay-Konstruktion
Overlay-Partitionierung und
Fusionierung
Lokationsbewusste Konstruktion
Hierarchische Overlay-Netzwerke
Ingenieursmethodiken
P2P-Information-Retrieval
Komplexe Suchanfragen in P2PSystemen
Semantische Overlay-Netzwerke und
semantisches “Query-Routing” in P2PSystemen
Datenmanagement
Platzierung, Replikation, Deskriptoren,
…
Sicherheit
Dienste und Applikationen
“Mobile Peer-to-Peer”
17
Zukünftige P2P Forschungsthemen
Sicherheit
Mitgliedschafts- & Zugangskontrolle
Virtuelle P2P-Umgebungen
Selbst-X
Selbstkonfiguration von Overlays, Mechanismen für Dienste und Anwendungen
Selbstheilung
Selbstorganisation
Netzwerkeffizienz von P2P-Systemen
Aus Blickwinkel eines ISPs Æ Einsparung von Transitverkehr
Kontrolle von P2P-Systemen aus dem Netzwerk
Kommunikation zwischen Overlay und Underlay um Effizienz zu erhöhen
Qualitätsgarantien (QoS) für P2P-Dienste
Hybride P2P-Architekturen
P2P- Rahmenwerke (ähnlich GRID ???)
Observations
Music Media Purchasing Trending
Responding [%]
50%
40%
Online
30%
CDs
20%
Both
10%
0%
2000
2002
2004
2006
2008
2010
Year
18
Development of the Telephony Industry
Percentage voice telephony
of total revenues
0
20
40
Observations
60
80
100
China Mobile
Vodafone Group
China Unicom
Telecom Italia
Telephony service becoming a free
commodity
Telephony companies will
loose more revenues
How to pay their employees?
Consequences
New business models required!
Coupling telephony with other services
China Telecom
France Telecom
IP-TV
Triple Play
Deutsche Telekom
Merge of traditional telephony
business with
NTT
Cable & Wireless
broadcasting business
Media distribution
SBC Communications
BT Group
P2P based Content Distribution Market
TV/Video
Download
Audio
Software
Streaming
Streaming
Download
B2B
G
am
es
Applications/Games/
Publishing
Publishing
C2C
Solution Provider
19
Fragen …
20