“P2P” in the InternetNapsterSlide 4Slide 5GnutellaSlide 7Slide 8Slide 9So FarStorage Management Systems challengesRouting challangesWe are going to look atWhat is PAST ?How it worksPAST NodesPAST operationsInsertionInsert contdPowerPoint PresentationLookup & ReclaimPastry: Peer-to-peer routingPastry:How it works?Pastry: Node ID spacePastry:Node ID spacePastry: Node State (1)Pastry: Node State (2)Example: NodeId=10233102, b=2, nodeId is 16 bit. All numbers in base 4.Pastry: Routing RequestsSlide 30Pastry:Node AdditionSlide 32Pastry: Node Failures, RecoverySecurityMore on SecurityStorage ManagementCauses for storage imbalance & solutionsReplica diversionPolicies for accepting a replicaFile diversionMaintaining replicasMaintaining replicas contdCachingCaching contdEvaluationKey ResultsCFS:IntroductionSlide 48CFS: Layer functionalitiesSlide 50CFS: PropertiesChordChord detailsFinger i points to successor of n+2iChord: Node join/failureChord: Server selectionCFS: Node Id AuthenticationCFS: Dhash LayerCFS: ReplicationCFS: CachingCFS: ImplementationCFS: Experimental resultsSlide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Future ResearchConclusionspeer-to-peer file systemsPresented by: Serge Kreiker“P2P” in the InternetNapster: A peer-to-peer file sharing applicationallow Internet users to exchange files directlysimple idea … hugely successfulfastest growing Web application50 Million+ users in January 2001shut down in February 2001similar systems/startups followed in rapid successionNapster,Gnutella, FreenetNapsterCentral Napster server(xyz.mp3, 128.1.2.3)128.1.2.3NapsterCentral Napster serverxyz.mp3 ?128.1.2.3128.1.2.3NapsterCentral Napster server128.1.2.3xyz.mp3 ?GnutellaGnutellaxyz.mp3 ?GnutellaGnutellaxyz.mp3So FarCentralized : Napster - Table size – O(n)- Number of hops – O(1)Flooded queries: Gnutella- Table size – O(1)- Number of hops – O(n)Storage Management Systems challengesDistributedNodes have identical capabilities and responsibilities anonymityStorage management : spread storage burden evenlyTolerate unreliable participantsRobustness : surviving massive failures Resilience to DoS attacks, censorship, other node failures.Cache management :cache additional copies of popular filesRouting challangesEfficiency : O(log(N)) messages per lookupN is the total number of serversScalability : O(log(N)) state per nodeRobustness : surviving massive failuresWe are going to look at PAST (Rice and Microsoft Research, routing substrate - Pastry)CFS (MIT, routing substrate - Chord)What is PAST ?Archival storage and content distribution utilityNot a general purpose file systemStores multiple replicas of filesCaches additional copies of popular files in the local file systemHow it worksBuilt over a self-organizing, Internet-based overlay networkBased on Pastry routing schemeOffers persistent storage services for replicated read-only filesOwners can insert/reclaim filesClients just lookupPAST NodesThe collection of PAST nodes form an overlay networkMinimally, a PAST node is an access pointOptionally, it contributes to storage and participate in the routingPAST operationsfileId = Insert(name, owner-credentials, k, file);file = Lookup(fileId);Reclaim(fileId, owner-credentials);InsertionfileId computed as the secure hash of name, owner’s public key, saltStores the file on the k nodes whose nodeIds are numerically closest to the 128 msb of fileIdHow to map Key IDs to Node IDs? Use PastryInsert contdThe required storage is debited against the owner’s storage quotaA file certificate is returnedSigned with owner’s private keyContains: fileId, hash of content, replication factor + othersThe file & certificate are routed via PastryEach node of the k replica storing nodes attach a store receiptAck sent back after all k-nodes have accepted the fileInsert file with fileId=117, k=41241151202001.Node 200 insert file 117source1222. 122 is one of the 4 closest nodes to 117, 125 was reached first Because it is the nearest node to 200.dest3. 122 returns store receiptLookup & ReclaimLookup: Pastry locates a “near” node that has a copy and retrieves itReclaim: weak consistencyAfter it, a lookup is no longer guaranteed to retrieve the fileBut, it does not guarantee that the file is no longer availablePastry: Peer-to-peer routingProvide generic, scalable indexing, data location and routing Inspiration from Plaxton’s algorithm (used in web content distribution eg. Akamai) and Landmark hierarchy routingGoals Efficiency Scalability Fault Resilience Self-organization (completely decentralized)Pastry:How it works?Each node has Unique nodeId.Each Message has a key.Both are uniformly distributed and lie in the same namespacePastry node routes the message to the node with the closest nodeId to the key.Number of routing steps is O(log N).Pastry takes into account network locality.PAST – uses fileID as key, and stores the file in k closest nodes.Pastry: Node ID spaceEach node is assigned a 128-bit node identifier - nodeId.nodeId is assigned randomly when joining the system. (e.g. using SHA-1 hash of its IP or nodes public Key) Nodes with adjacent nodeId’s are diverse in geography, ownership, network attachment, etc.nodeId and keys are in base 2b. b is configuration param with typical value 4.Pastry:Node ID space128 bits (=> max. 2128 nodes)Node id = L levelsb = 128/L bits per level NodeId = sequence of L, base 2b (b-bit) digits 01 L–1 … …b bitsCircular Namespace112128|02128 - 1Pastry: Node State (1)Each node maintains: routing table-R, neighborhood set-M, leaf set-L.Routing table is organized into log2bN rows with 2b-1 entry each.Each entry n contains the IP address of a close node which ID matches in the first n digits, differs in digit (n+1) Choice of b - tradeoff between size of routing table and length of route.Pastry: Node State (2)Neighborhood set - nodeId’s , IP addresses of M nearby nodes based on proximity in nodeId spaceLeaf set – set of L nodes withclosest nodeId to current node.L - divided into 2 : L /2 closest larger, L /2 closest smaller.values for L and M are 2bExample: NodeId=10233102, b=2, nodeId is 16 bit. All numbers in base 4.Pastry: Routing