CS 268 Lecture 22 Peer to Peer Networks Ion Stoica April 10 2001 How Did it Start A killer application Naptser Free music over the Internet Key idea share the storage and bandwidth of individual home users Internet istoica cs berkeley edu 2 Model Each user stores a subset of files Each user has access can download files from all users in the system istoica cs berkeley edu 3 Main Challenge Find where a particular file is stored Note problem similar to finding a particular page in web caching see last lecture what are the differences E F D E A C B istoica cs berkeley edu 4 Other Challenges Scale up to hundred of thousands or millions of machines Dynamicity machines can come and go any time istoica cs berkeley edu 5 Napster Assume a centralized index system that maps files songs to machines that are alive How 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 file Advantages Simplicity easy to implement sophisticated search engines on top of the index system Disadvantages Robustness scalability istoica cs berkeley edu 6 Napster Example m5 E m6 F E E E m5 m1 m2 m3 m4 m5 m6 m4 C A m1 D A B C D E F B m3 m2 istoica cs berkeley edu 7 Gnutella Distribute file location Idea multicast the request Hot 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 answer Advantages Totally decentralized highly robust Disadvantages Not scalable the entire network can be swamped with request to alleviate this problem each request has a TTL istoica cs berkeley edu 8 Gnutella Example Assume m1 s neighbors are m2 and m3 m3 s neighbors are m4 and m5 m5 E m6 F E E D E m4 E E C A m1 B m3 m2 istoica cs berkeley edu 9 Freenet Addition goals to file location Provide publisher anonymity security Resistant to attacks a third party shouldn t be able to deny the access to a particular file data item object even if it compromises a large fraction of machines Architecture Each file is identified by a unique identifier Each machine stores a set of files and maintains a routing table to route the individual requests istoica cs berkeley edu 10 Data Structure Each node maintains a common stack Forwarding istoica cs berkeley edu file Each message contains the file id it is referring to If file id stored locally then stop If not search for the closest id in the stack and forward the message to the corresponding next hop id next hop id file identifier next hop another node that store the file id file file identified by id being stored on the local node 11 Query API file query id Upon receiving a query for document id Check whether the queried file is stored locally If yes return it If not forward the query message Notes Each query is associated a TTL that is decremented each time the query message is forwarded to obscure distance to originator TTL can be initiated to a random value within some bounds When TTL 1 the query is forwarded with a finite probability Each node maintains the state for all outstanding queries that have traversed it help to avoid cycles When file is returned it is cached along the reverse path istoica cs berkeley edu 12 Query Example query 10 n2 n1 4 n1 f4 12 n2 f12 5 n3 1 9 n3 f9 4 4 2 n3 3 n1 f3 14 n4 f14 5 n3 3 n4 14 n5 f14 13 n2 f13 3 n6 n5 5 4 n1 f4 10 n5 f10 8 n6 Note doesn t show file caching on the reverse path istoica cs berkeley edu 13 Insert API insert id file Two steps Search for the file to be inserted If found report collision if number of nodes exhausted report failure If not found insert the file istoica cs berkeley edu 14 Insert Searching like query but nodes maintain state after a collision is detected and the reply is sent back to the originator Insertion Follow the forward path insert the file at all nodes along the path A node probabilistically replace the originator with itself obscure the true originator istoica cs berkeley edu 15 Insert Example Assume query returned failure along gray path insert f10 insert 10 f10 n1 4 n1 f4 12 n2 f12 5 n3 n2 9 n3 f9 n4 n3 3 n1 f3 14 n4 f14 5 n3 14 n5 f14 13 n2 f13 3 n6 istoica cs berkeley edu n5 4 n1 f4 11 n5 f11 8 n6 16 Insert Example insert 10 f10 n1 10 n1 f10 4 n1 f4 12 n2 n2 orig n1 9 n3 f9 n4 n3 3 n1 f3 14 n4 f14 5 n3 14 n5 f14 13 n2 f13 3 n6 istoica cs berkeley edu n5 4 n1 f4 11 n5 f11 8 n6 17 Insert Example n2 replaces the originator n1 with itself insert 10 f10 n1 10 n1 f10 4 n1 f4 12 n2 n2 10 n1 f10 9 n3 f9 n4 orig n2 n3 10 n2 10 3 n1 f3 14 n4 14 n5 f14 13 n2 f13 3 n6 istoica cs berkeley edu n5 4 n1 f4 11 n5 f11 8 n6 18 Insert Example n2 replaces the originator n1 with itself Insert 10 f10 n1 10 n1 f10 4 n1 f4 12 n2 n2 10 n1 f10 9 n3 f9 n4 n3 10 n2 10 3 n1 f3 14 n4 10 n2 f10 14 n5 f14 13 n2 istoica cs berkeley edu n5 10 n4 f10 4 n1 f4 11 n5 19 Freenet Properties Newly queried inserted files are stored on nodes with similar ids New nodes can announce themselves by inserting files Attempts to supplant or discover existing files will just spread the files istoica cs berkeley edu 20 Freenet Summary Advantages Provides publisher anonymity Totally decentralize architecture robust and scalable Resistant against malicious file deletion Disadvantages Does not always guarantee that a file is found even if the file is in the network istoica cs berkeley edu 21 Other Solutions to the Location Problem Goal make sure that an item file identified is always found Abstraction 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 CAN ACIRI Berkeley Chord MIT Berkeley Pastry Rice Tapestry Berkeley istoica cs berkeley edu 22 Content Addressable Network CAN Associate to each node and item a unique id in an d dimensional space Properties Routing table size O d Guarantees that a file is found in at most d n1 d steps where n is the total number of nodes istoica cs berkeley edu 23 CAN Example Two Dimensional Space Space divided between nodes All nodes cover the entire space Each node covers either a square or a rectangular area of ratios 1 …
View Full Document
Unlocking...