1Indranil GuptaLecture 9Peer-to-peer systemsComputer Science 425Distributed SystemsComputer Science 425Distributed SystemsPeer to peer systems(Next few lectures)D.S. Theory2 Angles of Distributed SystemsSome Questions• Why do people get together?– to share information – to share and exchange resources they have• books, class notes, experiences, 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 songs for your Miles Davis recordings, that would be great! – Napster: a light weight solution (lighter than the Web)A 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.net• [Today] eDonkey, BitTorrent, …2Napster 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 (names only, not the files themselves!)– Server maintains list of <filename, ip_address, portnum> tuples• Search from a client:– Send server keywords to search with– (Server searches its directory with the keywords)– Server returns a list of matching 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 abetting 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 modifications; we’ll look at the initial versionhttp://www.limewire.comGnutellaPPPPPPServents (“Peers”)PConnected in an overlay graphStore their ownfilesAlso store “peer pointers”a peer pointer3How 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 22PayloadGnutella 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 onceTTL=2TTL=1Num. hits port ip_address speed (fileindex,filename,fsize) servent_id0 1 3 7 11 n n+16QueryHit (0x80) : 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 path4Avoiding excessive trafficTo avoid duplicate transmissions, each peer maintains a list of recently received messages• Query forwarded to all neighbors except peer from which received (and this is remembered)• 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-\filesize\nUser-Agent: Gnutella\r\n\r\n• Responder then replies with file packets following the msg: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 directly?)servent_id fileindex ip_address portPush (0x40)same as in received QueryHitAddress at whichrequestor can acceptincoming connections• Responder establishes a TCP connection at ip_address,port specified. SendsGIV <File Index>:<Servent Identifier>/<File Name>\n\n• Requestor then sends GET to
View Full Document
Unlocking...