CS 414 - Spring 2011 CS 414 – Multimedia Systems Design Lecture 36 – Introduction to P2P and P2P Streaming Klara NahrstedtAdministrative MP3 preview is on April 27 Sign-up sheet for APRIL 27 demonstration will be provided in class on April 27 Preview demonstrations on April 27, 7-9pm in 216 SC CS 414 - Spring 2011Administration Final MP3 delivery on April 29 Demonstration time slots on April 29 will be allocated on Thursday, April 28 (TA will email to each group) Two demonstration intervals students not in Google competition – demos 2-4pm in 216 SC, students in Google competition – demos 5-7pm in 216 SC Pizza and Google Prizes Announcement at 7:15pm, April 29 (room 3403 SC) Homework 2 will be out on Wednesday, April 27 Deadline, May 4, 11:59pm – submission via compass CS 414 - Spring 2011Why P2P? People like to get together Share things Share information How can I find others to share? How can I find what they are sharing? CS 414 - Spring 2011Why P2P? WWW to share? Not everyone can set up and maintain a website Might not have a good enough search engine rank Sharing on a social network? Only possible if you created the content People have to find you, instead of the content CS 414 - Spring 2011Napster Created in 1999 to share music CS 414 - Spring 2011 Napster’s servers •Store file directory (Filename/location) Clients/peers •Store filesNapster, operation CS 414 - Spring 2011 1. Query (keyword) 2. Servers search using ternary tree 3. Response 4. Ping candidates 5. DownloadNapster’s drawbacks Asymmetric operation – servers vs. client peers Scalability and congestion issues Single point of failure Napster responsible for abetting users’ copyright violation CS 414 - Spring 2011Contemporary P2P systems Symmetric operation – all nodes (peers) have the same functionality System naturally scales with new peers Basic operations Insert file Search file Delete file Maintain an overlay network CS 414 - Spring 2011 (physical network)Contemporary P2P Systems (Classification) Usually classified depending on how peers connect to each-other – i.e., how the overlay network is created and maintained Unstructured – no particular connection pattern (e.g., randomly connected) Gnutella Fast Track Skype BitTorrent, etc. CS 414 - Spring 2011Contemporary P2P Systems (Classification) Structured – defines a distributed data structure (e.g., distributed hash table) Chord Pastry CAN Etc. CS 414 - Spring 2011Gnutella CS 414 - Spring 2011 Servents (peers) Peer pointer Peers store: •Their files •Peer pointersGnutella, searching CS 414 - Spring 2011 Query message: <id, QUERY, ttl, hops, payload length, min speed, keywords> Query hit message: <id, QUERY HIT, ttl, hops, payload length, num hits, port, ip, speed, (fileindex, filename, filesize), servent id> “jazz”?? 1. Flood query ( ) 2. Ignore repeated messages 3. Answer if local match 4. Query hit sent using reverse path ( ) 5. Establish connection and fetch file ( ) “jazz”Gnutella, maintaining the overlay CS 414 - Spring 2011 V X A Ping: <id, PING, ttl, hops, payload length (zero)> Pong: <id, PONG, ttl, hops, payload length, port, ip, num. files, num. KBs> Neighbor list: •“A” “V” “X” 1. Periodically flood ping ( ) 2. Pong sent using reverse path( ) 3. Update neighbor list with received pongs • Why periodically?Gnutella, maintaining the overlay CS 414 - Spring 2011 V X Peers can leave or fail at any time. Neighbor list: •“A” •“V” •“X”Gnutella: some issues Ping/Pong constitutes 50% of traffic Flooding causes excessive traffic Repeated searches with same keywords Large number of freeloaders (70% of users in 2000) CS 414 - Spring 2011DHTs (Distributed Hash Tables) Hash table allows these operations on object identified by key: Insert Lookup Delete Distributed Hash Table – same but in a distributed setting (object could be files) CS 414 - Spring 2011DHT performance comparison Memory Lookup latency lookup overhead Napster O(1) at client; O(N) at server O(1) O(1) Gnutella O(N) O(N) O(N) Chord (DHT) O(log(N)) O(log(N)) O(log(N)) CS 414 - Spring 2011Streaming from servers Bandwidth at video service and number of servers have to grow with demand Flash crowds have to be taken into account CS 414 - Spring 2011 … … clients Video service serversP2P Streaming Use the participating node’s bandwidth More nodes watching stream = more shared bandwidth App-level multicast How? CS 414 - Spring 2011 Live stream source (could be a member of the p2p network) P2P network Peers watching streamP2P Streaming Common arrangements to multicast the stream Single Tree Multiple Tree Mesh-based All nodes are usually interested in the stream They all have to deal with node dynamism (join/leave/fail/capacity-changes) CS 414 - Spring 2011Streaming in a single tree CS 414 - Spring 2011 Source Frames coder 3 2 1 packets 3 2 1 3 2 1 (using RTP/UDP)Single Tree Peers interested in the stream organize themselves into a tree CS 414 - Spring 2011 … … … Source Nodes send as many copies of a data packet as they have childrenJoining the tree Find a node with spare capacity, then make it parent If contacted node lacks capacity, pick child Random child Round robin Child closest in physical network to joining node CS 414 - Spring 2011 “Parent?” “Try one of my children”Leaving the tree or failing Orphan nodes need a new parent Policies for new parent Children pick source Subtree nodes pick source Children pick grandfather Subtree nodes pick grandfather …then repeat join procedure CS 414 - Spring 2011 Orphan children after parent leaves Ex-parent grandfatherSingle tree issues Leaves do not use their outgoing bandwidth Packets are lost while recovering after a parent leaves/fails Finding unsaturated peer could take a while Tree connections could be rearranged for better transfer CS 414 - Spring 2011Multiple Trees Challenge: a peer must be internal node in only one tree, leaf in the rest CS 414 - Spring 2011 1 2 2 3 1 3 3 1 2 Source Are nodes 1, 2, 3 receiving the same data multiple times?Multiple Description
View Full Document
Unlocking...