《Lec21peer2peer.ppt》由会员分享，可在线阅读，更多相关《Lec21peer2peer.ppt（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Spring 2000Spring 2002Background Distribution Decentralized control Self-organization Symmetric communicationSpring 2000Spring 2002Examples Pioneers Napster, Gnutella, FreeNet Academic Prototypes Pastry, Chord, CAN,Spring 2000Spring 2002CS 4614Common Issues Organize, maintain overlay network node ar
2、rivals node failures Resource allocation/load balancing Resource location Locality (network proximity)Idea: generic p2p substrateSpring 2000Spring 2002CS 4615ArchitectureTCP/IPP2P SubstrateNetwork storage Event notificationInternetself-organizingoverlay networkP2p application layer?Spring 2000Spring
3、 2002CS 4616Pastry Self-organizing overlay network Consistent hashing Lookup/insert object in log16 N routing steps (expected) O(log N) per-node state Network locality heuristicsSpring 2000Spring 2002CS 4617Object DistributionConsistent hashing Karger et al. 97128 bit circular id spacenodeIds (unifo
4、rm random)objIds (uniform random)Invariant: node with numerically closest nodeId maintains objectobjidnodeids02128- 1Spring 2000Spring 2002CS 4618Object Insertion/Lookup XRoute(X)Msg with key X is routed to live node with nodeId closest to X Problem: complete routing table not feasibleO2128 - 1Sprin
5、g 2000Spring 2002CS 4619Routing Properties log16 N steps O(log N) stated46a1clocate(d46a1c)d462bad4213fd13da365a1fcd467c4d471f1Spring 2000Spring 2002Leaf SetsEach node maintains IP addresses of the nodes with the L numerically closest larger and smaller nodeIds, respectively. routing efficiency/robu
6、stness fault detection (keep-alive) application-specific local coordinationSpring 2000Spring 2002CS 46111Routing Procedureif (destination is within range of our leaf set) forward to numerically closest memberelselet l = length of shared prefix let d = value of l-th digit in Ds addressif (Rld exists)
7、 forward to Rldelse forward to a known node that (a) shares at least as long a prefix(b) is numerically closer than this nodeSpring 2000Spring 2002CS 46112RoutingIntegrity of overlay: guaranteed unless L/2 simultaneous failures of nodes with adjacent nodeIdsNumber of routing hops: No failures: log16
8、 N expected, 128/b + 1 max During failure recovery: O(N) worst case, average case much better Spring 2000Spring 2002CS 46113Node Addition d46a1cd462bad4213fd13da365a1fcd467c4d471f1addnode(d46a1c)Spring 2000Spring 2002CS 46114Node Departure (Failure)Leaf set members exchange keep-alive messages Leaf
9、set repair (eager): request set from farthest live node in set Routing table repair (lazy): get table from peers in the same row, then higher rowsSpring 2000Spring 2002CS 46115API route(M, X): route message M to node with nodeId numerically closest to X deliver(M): deliver message M to application f
10、orwarding(M, X): message M is being forwarded towards key X newLeaf(L): report change in leaf set L to application Spring 2000Spring 2002PAST: Cooperative, archival file storage and distribution Layered on top of Pastry Strong persistence High availability Scalability Reduced cost (no backup) Effici
11、ent use of pooled resourcesSpring 2000Spring 2002CS 46117PAST API Insert - store replica of a file at k diverse storage nodes Lookup - retrieve file from a nearby live storage node that holds a copy Reclaim - free storage associated with a fileFiles are immutableSpring 2000Spring 2002CS 46118PAST: F
12、ile storage fileIdInsert fileIdSpring 2000Spring 2002CS 46119PAST: File storage Storage Invariant: File “replicas” are stored on k nodes with nodeIdsclosest to fileId (k is bounded by the leaf set size)fileIdInsert fileIdk=4Spring 2000Spring 2002CS 46120PAST: File Retrieval fileIdfile located in log16 N steps (expected)usually locates replica nearest client CLookupk replicasC