Slide 1Slide 2Slide 3A Brief HistoryNapster StructureNapster OperationsNapster SearchProblemsGnutellaSlide 10How do I search for my Beatles file?Slide 12Slide 13Gnutella SearchSlide 15Slide 16Avoiding excessive trafficAfter receiving QueryHit messagesDealing with FirewallsSlide 20Slide 21Ping-PongGnutella SummarySlide 24Problems (contd.)FastTrackA FastTrack-like SystemFastTrack (contd.)Wrap-up NotesSummaryDHT=Distributed Hash TableFor this WeekendAdministrative Announcements1Indranil Gupta (Indy)Lecture 4Peer to Peer SystemsJanuary 27, 2011All Slides © IGCS 525 Advanced Distributed SystemsSpring 20112D.S. TheoryPeer to peer systemsCloud Computing Sensor Networks34A 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.sourcefor ge.net5Napster 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 …..6Napster 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 TCP7Napster 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 host8Problems•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”9Gnutella•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.com10GnutellaPPPPPPServents (“Peers”)PConnected in an overlay graph (== each link is an implicit Internet path)Store their ownfilesAlso store “peer pointers”11How 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)12Descriptor 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 Format13 Minimum Speed Search criteria (keywords)Query (0x80)0 1 …..Payload Format in Gnutella Query Message14Gnutella SearchPPPPPPPWho has PennyLane.mp3?Query’s flooded out, ttl-restricted, forwarded only onceTTL=215Num. 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 Message16Gnutella SearchPPPPPPPWho has PennyLane.mp3?Successful results QueryHit’s routed on reverse path17Avoiding 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 dropped18After 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 message:HTTP 200 OK\r\nServer: Gnutella\r\nContent-type:application/binary\r\nContent-length: 1024 \r\n\r\n•HTTP is the file transfer protocol. Why?•Why the “range” field in the GET request?•What if responder is behind firewall that disallows incoming connections?19Dealing with FirewallsPPPPPPPRequestor sends Push to responder asking for file transferHas PennyLane.mp3But behind firewall20servent_id fileindex ip_address portPush (0x40)same as in received QueryHitAddress at whichrequestor can acceptincoming connections21•Responder establishes a TCP connection at ip_address, port specified. SendsGIV <File Index>:<Servent Identifier>/<File Name>\n\n•Requestor then sends GET to responder (as before) and file is transferred•What if requestor is behind firewall too?–Gnutella gives up–Can you think of an alternative solution?22Ping-Pong•Peers initiate Ping’s periodically•Ping’s flooded out like Query’s, Pong’s routed along reverse path like QueryHit’s•Pong replies used to update set of neighboring peers•to keep neighbor lists fresh in spite of peers joining, leaving and failingPort ip_address Num. files shared Num. KB sharedPong (0x01)Ping (0x00)no payload23Gnutella Summary•No servers •Peers/servents maintain “neighbors”, this forms an
View Full Document
Unlocking...