Slide Number 1AcknowledgementAdministrative Administrative Administrative Administrative Plan for TodayGnutella SummaryGnutella ProblemsProblems (contd.)FastTrack (KaZaA)A FastTrack-like SystemFastTrack (contd.)Final Comments on Unstructured P2P Systems Comparative PerformanceHash Table (Phone Book)Hash FunctionsDHT=Distributed Hash TableDHTsComparative PerformanceChordBase Chord ProtocolConsistent HashingRing of PeersPeer pointers (1): successorsPeer pointers (2): finger tables (Scalable Key Location)What about the files?Mapping FilesSearchSearchSearchSummaryLecture 13Peer-to-Peer systems (Part II)CS 425/ECE 428/CSE 424Distributed Systems(Fall 2009)Acknowledgement• The slides during this semester are based on ideas and material from the following sources: – Slides prepared by Professors M. Harandi, J. Hou, I. Gupta, N. Vaidya, Y-Ch. Hu, S. Mitra. – Slides from Professor S. Gosh’s course at University o Iowa.Administrative • HW 2 – Deadline, October 6 (Tuesday), 2pm – Solutions will be released in the evening• Midterm on October 13 (Tuesday)– Exam will take place in class– You are allowed one cheat-sheet (one side only)– Exam will include all topics covered in HW1-HW2, plus P2P material (Lectures 1-13)– No TA office hours on October 12, instead the instructor willhold office hours on Monday, October 12, 3-4pm in 3104 SC• MP1 code is released on the class website– Score of MP1 will be posted on October 6, 2009 eveningAdministrative • MP2 posted October 5, 2009, on the course website, – Deadline November 6 (Friday)– Demonstrations , 4-6pm, 11/6/2009 – You will need to lease one Android/Google Developers Phone per person from the CS department (see lease instructions)!!– Start early on this MP2 – Update groups as soon as possible and let TA know by email so that she can work with TSG to update group svn – Tutorial for MP2 planned for October 28 evening if students send questions to TA by October 25. Send requests what you would like to hear in the tutorial. – During October 15-25, Thadpong Pongthawornkamol ([email protected]) will held office hours and respond to MP2 questions for Ying Huang (Ying is going to the IEEE MASS 2009 conference in China)Administrative • MP3 proposal instructions – You will need to submit a proposal for MP3 on top of your MP2 before you start MP3 on November 9, 2009– Exact Instructions for MP3 proposal format will be posted October 8, 2009 – Deadline for MP3 proposal: October 25, 2009, email proposal to TA– At least one representative of each group meets with instructor or TA during October 26-28 during their office hours ) watch for extended office hours during these days.• Instructor office hours: October 28 times 8:30-10amAdministrative • To get Google Developers Phone, you need a Lease Form – You must pick up a lease form from the instructor during October 6-9 (either in the class or during office hours) since the lease form must be signed by the instructor. – Fill out the lease form; bring the lease form to Rick van Hook/Paula Welch and pick up the phone from 1330 SC• Lease Phones: phones will be ready to pick up starting October 20, 9-4pm from room 1330 SC (purchasing , receiving and inventory control office)• Return Phones: phones need to be returned during December 14-18, 9-4pm in 1330 SCPlan for Today• Fast-Track • Summary of unstructured P2P networks• Introduction of distributed hash table conceptGnutella Summary• No index servers • Peers/servents maintain “neighbors” (membership list), this forms an overlay graph• Peers store their own files• Queries flooded out, ttl restricted• Query Replies reverse path routed• Supports file transfer through firewalls (one-way)• Periodic Ping-Pong to keep neighbor lists fresh in spite of peers joining, leaving and failing– List size specified by human user at peer : heterogeneity means some peers may have more neighbors– Gnutella found to follow power law distribution:P(#neighboring links for a node = L) ~ (k constant)kL−Gnutella Problems• Ping/Pong constitutes 50% traffic– Solution: Multiplex, cache and reduce frequency of pings/pongs• Repeated searches with same keywords– Solution: Cache Query and QueryHit messages• Modem-connected hosts do not have enough bandwidth for passing Gnutella traffic– Solution: use a central server to act as proxy for such peers– Another solution: FastTrack System (in a few slides)Problems (contd.)• Large number of freeloaders– 70% of users in 2000 were freeloaders• Flooding causes excessive traffic– Is there some way of maintaining meta-information about peers that leads to more intelligent routing? Structured Peer-to-peer systemse.g., Chord System (next lecture)FastTrack (KaZaA)• Unstructured Peer-to-Peer System • Hybrid between Gnutella and Napster• Takes advantage of “healthier” participants in the system (higher bandwidth nodes, nodes that are around most of the time, nodes that are not freeloaders, etc.)• Underlying technology in Kazaa, KazaaLite, Grokster• Proprietary protocol, but some details available• Like Gnutella, but with some peers designated as supernodesA FastTrack-like SystemPPPPPeersSSSuper-nodePSuper-nodeFastTrack (contd.)• A supernode stores a directory listing (<filename,peer pointer>), similar to Napster servers• Supernode membership changes over time• Any peer can become (and stay) a supernode, provided it has earned enough reputation– Kazaalite: participation level of a user between 0 and 1000, initially 10, then affected by length of periods of connectivity and total number of uploads from that client• A peer searches for a file by contacting a nearby supernodeFinal Comments on Unstructured P2P Systems • How does a peer join the system (bootstrap)– Send an http request to well known URL http://www.myp2pservice.com– Message routed after DNS lookup to a well known server that has partial list of recently joined peers, and uses this to initialize new peers’ neighbor table• Lookups can be speeded up by having each peer cache:– Queries and their results that it sees– All directory entries (filename, host) mappings that it sees– The files themselvesComparative PerformanceMemory LookupLatency#Messagesfor a lookupNapster O(1)@client,O(N)@serverO(1) O(1)Gnutella O(N) O(N) O(N)Hash Table (Phone Book)Hash FunctionsDHT=Distributed Hash Table• Hash table allows you to
View Full Document
Unlocking...