View
215
Download
0
Category
Preview:
Citation preview
1
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
Tel.+49 6151 166150, Fax. +49 6151 166152 www.KOM.tu-darmstadt.de
© author(s) of these slides 2008 including research results of the research network KOM and TU Darmstadt otherwise as specified at the respective slide
Dr.-Ing. Nicolas C. Liebau
Nicolas.Liebau@KOM.tu-darmstadt.de Tel.+49 6151 165240
18.02.2009
Peer-to-PeerTechnologischer Überblick
Dr.-Ing. Nicolas C. Liebau, KOM, TU Darmstadt
KOM – Multimedia Communications Lab 2
Observations
Content OwnersDistribution of digital content over the InternetMedia industry fighting it since 1999
February 2001 – Napster has 50 million reg. User2.79 billion music-downloads
February 2006 – Episode of TV-series “Lost”downloaded 500.000 times via BitTorrent-network
P2P Traffic in the Internet60% – 80% P2P file sharing traffic on backbones
Internet Protocol Breakdown 1993 - 2006
Source: CacheLogic Research
2
KOM – Multimedia Communications Lab 3
Bekannte Anwendungsgebiete
Dateitauschbörsen (Filesharing)eMule, KaZaA, BitTorrent, DC++, …
Kommerzielle Verteilung digitaler MedienDownload, Video on Demand (VoD) Streaming, Live StreamingMercora (Audio), In2movies, Octoshape, Zattoo, ….
VoIPSkype
Persistente DatenhaltungOceanStore
KOM – Multimedia Communications Lab 4
Inhalt
Definition
Overlay-NetzwerkeGnutellaChordKademliaGlobase.KOM
Verteilung digitaler MedienSwarming mit BitTorrentNetwork CodingLife StreamingVoD Streaming
Forschungsthemen und industrielles Umfeld
3
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
Tel.+49 6151 166150, Fax. +49 6151 166152 www.KOM.tu-darmstadt.de
© author(s) of these slides 2008 including research results of the research network KOM and TU Darmstadt otherwise as specified at the respective slide
Dr.-Ing. Nicolas C. Liebau
Nicolas.Liebau@KOM.tu-darmstadt.de Tel.+49 6151 165240
18.02.2009
Peer-to-Peer TechnologieDefinition & Overlay-Netzwerke
KOM – Multimedia Communications Lab 6
P2P - Definition
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
Tel.+49 6151 166150, Fax. +49 6151 166152 www.KOM.tu-darmstadt.de
© author(s) of these slides 2008 including research results of the research network KOM and TU Darmstadt otherwise as specified at the respective slide
Dr.-Ing. Nicolas C. Liebau
Nicolas.Liebau@KOM.tu-darmstadt.de Tel.+49 6151 165240
18.02.2009
Peer-to-Peer TechnologieVerteilung digitaler Medien –Schwarm-Effekt & Streaming
11
KOM – Multimedia Communications Lab 26
DateienMultimedia Daten:
Audio (3 MB+)Video (650 MB+)
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
of file creationlength: file sizename: file namepiece length: chunk sizepieces: SHA1 hash key
of each chunk
Seed = Quelle
Wie BitTorrent funktioniert: Publishing
13
KOM – Multimedia Communications Lab 30
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
Detailablauf abhängig von verwendetem Codec
Standard: H.264Chunk basiertZ.B. Octoshape, emundoo
Layered Video Codecs
Quelle: Goolge Earth
KOM – Multimedia Communications Lab 35
P2P Live Streaming
ForschungsfragenAufbau des Streaming-Baums
Unterstützung heterogener PeersAufbau eines „Meshs“ zur Unterstützung mit „nicht vollständigen“ Streams
Unterhaltung des Streaming-BaumsUmgang mit ausfallenden Knoten
Mesh oder Multibaum besser als einfacher BaumAbspielstrategien
Delay-erhaltendDelay bleibt konstant, Paketverluste geduldet
QualitäterhaltendKeine Paketverluste, Abspiel wird verzögert
Welche ergibt höhere QoE?Anreize zur Kooperation
16
KOM – Multimedia Communications Lab 36
P2P VoD Streaming
Kooperation mit vorangegangenen Nutzern
Datei in Teile unterteilt
Rechtzeitiges herunterladen des benötigten Dateiteils
Ähnlich BitTorrentZ.B. NextShare, emundoo
Eventuell Unterstützung durch Server (Quelle)
Quelle: Goolge Earth
KOM – Multimedia Communications Lab 37
Aktuelle Fragestellungen bei P2P Streaming
Minimieren der Wartezeiten bis zum Anspielen
Auch bei Vorspulen, etc.
Minimieren von Caching
TeilgrößeAbhängig von Verteilung
Je kleiner, je größerer Verwaltungsaufwand
Abhängig von CodierungJe kleiner je eher passend zu Key Frames
ReplikationsmechanismusWelche Teile, welche AnzahlAuf welchen Knoten Zusätzlich zur Entlastung der Quellserver
Anreize zur KooperationNicht-monetäre Anreizsysteme
Peer-assisted CDNsHybride P2P-Systeme mit Servern für
Erhöhung der ZuverlässigkeitGerade bei kleinen Schwärmen
NAT-Durchdringung
17
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
Tel.+49 6151 166150, Fax. +49 6151 166152 www.KOM.tu-darmstadt.de
© author(s) of these slides 2008 including research results of the research network KOM and TU Darmstadt otherwise as specified at the respective slide
Dr.-Ing. Nicolas C. Liebau
Nicolas.Liebau@KOM.tu-darmstadt.de Tel.+49 6151 165240
18.02.2009
Peer-to-Peer TechnologieForschungsthemen und industrielles Umfeld
KOM – Multimedia Communications Lab 39
Aktuelle Forschungsthemen
MedienverteilungsstrategienBitTorrent, etc.AnreizmechanismenVertrauen und Reputation
Streaming (VoD oder live)
Overlay-NetzwerkeOverlay-Konstruktion
Overlay-Partitionierung und FusionierungLokationsbewusste Konstruktion
Hierarchische Overlay-NetzwerkeIngenieursmethodiken
P2P-Information-Retrieval Komplexe Suchanfragen in P2P-Systemen Semantische Overlay-Netzwerke und semantisches “Query-Routing” in P2P-Systemen
DatenmanagementPlatzierung, Replikation, Deskriptoren, …
Sicherheit
Dienste und Applikationen
“Mobile Peer-to-Peer”
18
KOM – Multimedia Communications Lab 40
Zukünftige P2P Forschungsthemen
SicherheitMitgliedschafts- & Zugangskontrolle
Virtuelle P2P-Umgebungen
Selbst-XSelbstkonfiguration von Overlays, Mechanismen für Dienste und AnwendungenSelbstheilungSelbstorganisation
Netzwerkeffizienz von P2P-SystemenAus Blickwinkel eines ISPs Einsparung von Transitverkehr
Kontrolle von P2P-Systemen aus dem NetzwerkKommunikation zwischen Overlay und Underlay um Effizienz zu erhöhenQualitätsgarantien (QoS) für P2P-Dienste
Hybride P2P-Architekturen
P2P- Rahmenwerke (ähnlich GRID ???)
KOM – Multimedia Communications Lab 41
Music Media Purchasing Trending
0%
10%
20%
30%
40%
50%
2000 2002 2004 2006 2008 2010
Year
Res
pond
ing
[%]
OnlineCDsBoth
Observations
19
KOM – Multimedia Communications Lab 42
China Mobile
Vodafone Group
China Unicom
Telecom Italia
China Telecom
France Telecom
Deutsche Telekom
NTT
Cable & Wireless
SBC Communications
BT Group
0 20 40 60 80 100
Development of the Telephony Industry
ObservationsTelephony service becoming a free commodityTelephony companies willloose more revenuesHow to pay their employees?
ConsequencesNew business models required!
Coupling telephony with other servicesIP-TVTriple Play
Merge of traditional telephony business with
broadcasting businessMedia distribution
Percentage voice telephony of total revenues
KOM – Multimedia Communications Lab 43
P2P based Content Distribution Market
TV/Video Audio
Games
Solution Provider
Stre
amin
g
Download
Streaming
Download
Softw
are
Publishing
B2B
C2CApplications/Games/Publishing
20
KOM – Multimedia Communications Lab 44
Fragen …
Recommended