EE 122: Peer-to-Peer (P2P) NetworksHow Did it Start?ModelMain ChallengeOther ChallengesNapsterNapster: ExampleGnutellaGnutella: ExampleFastTrackOther Solutions to the Location ProblemContent Addressable Network (CAN)CAN Example: Two Dimensional SpaceSlide 14Slide 15Slide 16Slide 17Slide 18CAN: Query ExampleChordData StructureChord ExampleSlide 23Slide 24Chord ExamplesQueryDiscussionDiscussion (cont’d)Slide 29ConclusionsEE 122: Peer-to-Peer (P2P) NetworksIon StoicaNovember 27, [email protected] 2How Did it Start?A killer application: Naptser-Free music over the InternetKey idea: share the storage and bandwidth of individual (home) [email protected] 3ModelEach user stores a subset of filesEach user has access (can download) files from all users in the [email protected] 4Main ChallengeFind where a particular file is [email protected] 5Other ChallengesScale: up to hundred of thousands or millions of machines Dynamicity: machines can come and go any [email protected] 6NapsterAssume a centralized index system that maps files (songs) to machines that are aliveHow to find a file (song)-Query the index system return a machine that stores the required file•Ideally this is the closest/least-loaded machine-ftp the fileAdvantages: -Simplicity, easy to implement sophisticated search engines on top of the index systemDisadvantages:-Robustness, scalability (?)[email protected] 7Napster: ExampleABCDEFm1m2m3m4m5m6m1 Am2 Bm3 Cm4 Dm5 Em6 [email protected] 8GnutellaDistribute file locationIdea: multicast the requestHot to find a file:-Send request to all neighbors-Neighbors recursively multicast the request-Eventually a machine that has the file receives the request, and it sends back the answerAdvantages:-Totally decentralized, highly robustDisadvantages:-Not scalable; the entire network can be swamped with request (to alleviate this problem, each request has a TTL)[email protected] 9Gnutella: ExampleAssume: m1’s neighbors are m2 and m3; m3’s neighbors are m4 and m5;…[email protected] 10FastTrackUse the concept of supernodeA combination between Napster and GnutellaWhen a user joins the network it joins a supernodeA supernode acts like Napster server for all users connected to itQueries are brodcasted amongst supernodes (like Gnutella)[email protected] 11Other Solutions to the Location ProblemGoal: make sure that an item (file) identified is always foundAbstraction: a distributed hash-table data structure -insert(id, item);-item = query(id);-Note: item can be anything: a data object, document, file, pointer to a file…Proposals (also called structured p2p networks)-CAN (ACIRI/Berkeley)-Chord (MIT/Berkeley)-Pastry (Rice)-Tapestry (Berkeley)[email protected] 12Content Addressable Network (CAN)Associate to each node and item a unique id in an d-dimensional spaceProperties -Routing table size O(d)-Guarantee that a file is found in at most d*n1/d steps, where n is the total number of [email protected] 13CAN Example: Two Dimensional SpaceSpace divided between nodesAll nodes cover the entire spaceEach node covers either a square or a rectangular area of ratios 1:2 or 2:1Example: -Assume space size (8 x 8)-Node n1:(1, 2) first node that joins cover the entire space12 3 456 [email protected] 14CAN Example: Two Dimensional SpaceNode n2:(4, 2) joins space is divided between n1 and n212 3 456 [email protected] 15CAN Example: Two Dimensional SpaceNode n2:(4, 2) joins space is divided between n1 and n212 3 456 [email protected] 16CAN Example: Two Dimensional SpaceNodes n4:(5, 5) and n5:(6,6) join12 3 456 [email protected] 17CAN Example: Two Dimensional SpaceNodes: n1:(1, 2); n2:(4,2); n3:(3, 5); n4:(5,5);n5:(6,6)Items: f1:(2,3); f2:(5,1); f3:(2,1); f4:(7,5);12 3 456 [email protected] 18CAN Example: Two Dimensional SpaceEach item is stored by the node who owns its mapping in the space 12 3 456 [email protected] 19CAN: Query ExampleEach node knows its neighbors in the d-spaceForward query to the neighbor that is closest to the query idExample: assume n1 queries f412 3 456 [email protected] 20ChordAssociate to each node and item a unique id in an uni-dimensional spaceProperties -Routing table size O(log(N)) , where N is the total number of nodes-Guarantees that a file is found in O(log(N)) [email protected] 21Data StructureAssume identifier space is 0..2mEach node maintains-Finger table•Entry i in the finger table of n is the first node that succeeds or equals n + 2i-Predecessor nodeAn item identified by id is stored on the succesor node of [email protected] 22Chord ExampleAssume an identifier space 0..8Node n1:(1) joinsall entries in its finger table are initialized to itself01234567i id+2i succ0 2 11 3 12 5 1 Succ. [email protected] 23Chord ExampleNode n2:(3) joins01234567i id+2i succ0 2 21 3 12 5 1 Succ. Tablei id+2i succ0 3 11 4 12 6 1 Succ. [email protected] 24Chord ExampleNodes n3:(0), n4:(6) join 01234567i id+2i succ0 2 21 3 62 5 6 Succ. Tablei id+2i succ0 3 61 4 62 6 6 Succ. Tablei id+2i succ0 1 11 2 22 4 6 Succ. Tablei id+2i succ0 7 01 0 02 2 2 Succ. [email protected] 25Chord ExamplesNodes: n1:(1), n2(3), n3(0), n4(6)Items: f1:(7), f2:(2)01234567i id+2i succ0 2 21 3 62 5 6 Succ. Tablei id+2i succ0 3 61 4 62 6 6 Succ. Tablei id+2i succ0 1 11 2 22 4 6 Succ. Table7Items 1Items i id+2i succ0 7 01 0 02 2 2 Succ. [email protected] 26QueryUpon receiving a query for item id, node nCheck whether the item is stored at the successor node s, i.e.,-id belongs to (n, s)If not, forwards the query to the largest node in its successor table that does not exceed id01234567i id+2i succ0 2 21 3 62 5 6 Succ. Tablei id+2i succ0 3
View Full Document
Unlocking...