Slide 1Slide 2BasicsWhy Study Peer to peer systems?Some QuestionsSlide 6Slide 7A Brief HistoryNapster StructureNapster OperationsNapster SearchProblemsGnutellaSlide 14How do I search for my Beatles file?Slide 16Slide 17Gnutella SearchSlide 19Slide 20Avoiding excessive trafficAfter receiving QueryHit messagesDealing with FirewallsSlide 24Slide 25Ping-PongGnutella SummarySlide 28Problems (contd.)FastTrackA FastTrack-like SystemFastTrack (contd.)Wrap-up NotesSummaryDHT=Distributed Hash TableFor this Weekend1Indranil Gupta (Indy)Lecture 4Peer to Peer SystemsJanuary 28, 2010All Slides © IGCS 525 Advanced Distributed SystemsSpring 20102D.S. TheoryPeer to peer systemsCloud Computing Sensor Networks3Sensor Networks(This week and next)D.S. Theory(Next week)Basics(Next week)Peer to peer systemsCloud Computing4Why Study Peer to peer systems?•To understand how they work•To build your own peer to peer system•To understand the techniques and principles within them•To modify, adapt, reuse these techniques and principles in other related areas–Cloud computing–Sensor networks•To grow the body of knowledge about distributed systems5Some Questions•Why do people get together?–to share information –to share and exchange resources they have•books, class notes, experiences, videos, music cd’s•How can computers help people –find information–find resources–exchange and share resources6•Existing technologies: The Web!–Search engines–Forums: chat rooms, blogs, ebay–Online business•But, the web is heavy weight if you want specific resources: say a Beatles’ song “PennyLane”•A google search will give you their bio, lyrics, chords, articles on them, and then perhaps the mp3•But you want only the song, nothing else!•If you can find a peer who wouldn’t mind exchanging her Beatles mp3 songs for your UIUC Homeocoming videos, that would be great! –Napster: a solution light weight that was lighter than the Web78A Brief History•[6/99] Shawn Fanning (freshman Northeastern U.) releases Napster online music service•[12/99] RIAA sues Napster, asking $100K per download•[3/00] 25% UWisc traffic Napster, many universities ban it•[00] 60M users•[2/01] US Federal Appeals Court: users violating copyright laws, Napster is abetting this•[9/01] Napster decides to run paid service, pay % to songwriters and music companies•[Today] Napster protocol is open, people free to develop opennap clients and servers http://opennap.sou r c e f orge.ne t9Napster StructureSSSPPPPPPClient machines (“Peers”)napster.com ServersStore their ownfilesStore a directory, i.e., filenames with peer pointers Filename Info aboutPennyLane.mp3 Beatles, @ 128.84.92.23:1006 …..10Napster OperationsClient•Connect to a Napster server•Upload list of music files that you want to share–Server maintains list of <filename, ip_address, portnum> tuples. Server stores no files.•Search–Send server keywords to search with–(Server searches its list with the keywords)–Server returns a list of hosts - <ip_address, portnum> tuples - to client–Client pings each host in the list to find transfer rates –Client fetches file from best host•All communication uses TCP11Napster SearchSSSPPPPPPPeersnapster.com ServersStore their ownfilesStore peer pointers for all files3. Response1. Query2. All servers search their lists (ternary tree algo.)4. ping candidates5. download from best host12Problems•Centralized server a source of congestion•Centralized server single point of failure•No security: plaintext messages and passwds•napster.com declared to be responsible for users’ copyright violation–“Indirect infringement”13Gnutella•Eliminate the servers•Client machines search and retrieve amongst themselves•Clients act as servers too, called servents•[3/00] release by AOL, immediately withdrawn, but 88K users by 3/03•Original design underwent several modificationshttp://www.limewire.com14GnutellaPPPPPPServents (“Peers”)PConnected in an overlay graph (== each link is an implicit Internet path)Store their ownfilesAlso store “peer pointers”15How do I search for my Beatles file?•Gnutella routes different messages within the overlay graph•Gnutella protocol has 5 main message types–Query (search)–QueryHit (response to query)–Ping (to probe network for other peers)–Pong (reply to ping, contains address of another peer)–Push (used to initiate file transfer)•We’ll go into the message structure and protocol now(note: all fields except IP address are in little-endian format)16Descriptor ID Payload descriptor TTL Hops Payload lengthDescriptor HeaderType of payload0x00 Ping0x01 Pong0x40 Push0x80 Query0x81 QueryhitDecremented at each hop,Message dropped when ttl=0ttl_initial usually 7 to 10Incremented at each hopID of this searchtransactionNumber of bytes ofmessage following this header0 15 16 17 18 22 PayloadGnutella Message Header Format17 Minimum Speed Search criteria (keywords)Query (0x80)0 1 …..Payload Format in Gnutella Query Message18Gnutella SearchPPPPPPPWho has PennyLane.mp3?Query’s flooded out, ttl-restricted, forwarded only onceTTL=219Num. hits port ip_address speed (fileindex,filename,fsize) servent_id0 1 3 7 11 n n+16QueryHit (0x81) : successful result to a queryResultsUnique identifier of responder;a function of its IP addressInfo aboutresponderPayload Format in Gnutella Query Reply Message20Gnutella SearchPPPPPPPWho has PennyLane.mp3?Successful results QueryHit’s routed on reverse path21Avoiding excessive trafficTo avoid duplicate transmissions, each peer maintains a list of recently received messages•Query forwarded to all neighbors except peer from which received•Each Query (identified by DescriptorID) forwarded only once •QueryHit routed back only to peer from which Query received with same DescriptorID•Duplicates with same DescriptorID and Payload descriptor (msg type) are dropped•QueryHit with DescriptorID for which Query not seen is dropped22After receiving QueryHit messages•Requestor chooses “best” QueryHit responder–Initiates HTTP request directly to responder’s ip+portGET /get/<File Index>/<File Name>/HTTP/1.0\r\nConnection: Keep-Alive\r\nRange: bytes=0-\r\nUser-Agent: Gnutella\r\n\r\n•Responder then replies with file packets following this
View Full Document
Unlocking...