CS 525 Advanced Topics in Distributed Systems Spring 07Slide 2BasicsSome QuestionsSlide 5Slide 6A Brief HistoryNapster StructureNapster OperationsNapster SearchProblemsGnutellaSlide 13How do I search for my Beatles file?Slide 15Slide 16Gnutella SearchSlide 18Slide 19Avoiding excessive trafficAfter receiving QueryHit messagesDealing with FirewallsSlide 23Slide 24Ping-PongGnutella SummarySlide 27Problems (contd.)FastTrackA FastTrack-like SystemFastTrack (contd.)Wrap-up NotesSummaryDHT=Distributed Hash TableAs you leave Today’s Lecture…For this WeekendCS 525 Advanced Topics in Distributed SystemsSpring 07Indranil GuptaLecture 2Introduction to Peer to Peer SystemsJanuary 18, 2007D.S. TheoryPeer to peer systemsSensor NetworksPeer to peer systemsSensor Networks(This week and next)(Next week)D.S. Theory(Next-next week)BasicsSome 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 resources•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 WebA 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.sourceforge.netNapster 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 …..Napster 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•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 TCPNapster 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 hostProblems•Centralized server a source of congestion•Centralized server single point of failure•No security: plaintext messages and passwds•napster.com responsible for users’ copyright violation–“Indirect infringement”Gnutella•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.comGnutellaPPPPPPServents (“Peers”)PConnected in an overlay graphStore their ownfilesAlso store “peer pointers”How do I search for my Beatles file?•Gnutella routes different messages within the overlay graph•Gnutella protocol has 5 main message types–Query–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)Descriptor 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 10Incremented at each hopID of this searchtransactionNumber of bytes ofmessage following this header0 15 16 17 18 22 PayloadGnutella Message Header FormatMinimum Speed Search criteria (keywords)Query (0x80)0 1 …..Payload Format in Gnutella Query MessageGnutella SearchPPPPPPPWho has PennyLane.mp3?Query’s flooded out, ttl-restricted, forwarded only onceNum. 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 MessageGnutella SearchPPPPPPPWho has PennyLane.mp3?Successful results QueryHit’s routed on reverse pathAvoiding 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 droppedAfter 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?Dealing with FirewallsPPPPPPPRequestor sends Push to responder asking for file transferHas PennyLane.mp3But behind firewall(Why is the Push routed and not sent
View Full Document
Unlocking...