SkipNet: A Scaleable Overlay Network With Practical Locality PropertiesPhilosophy of SkipNetAdded FunctionalityWhy not a DHT?Structure of SkipNet: Perfect Skip ListsStructure of SkipNet: Probabilistic Skip ListStructure of SkipNet: Perfect Lexicographic Address SpaceStructure of SkipNet: Lexicographic Address Space (2)Numeric Space vs. Lexicographic SpaceStructure of SkipNet: Lexicographic SearchingStructure of SkipNet: Node JoinStructure of SkipNet: Node DepartureUseful Properties: LocalityUseful Properties: Constrained Load BalancingUseful Properties: Fault ToleranceUseful Properties: Range QueriesResults: MethodologyResults: Basic Routing CostsResults: Locality of PlacementResults: Fault ToleranceResults: CLBAdditional Optimizations: Efficient RoutingAdditional Optimizations: Virtual NodesDesign AlternativesDiscussion QuestionsSkipNet: A Scaleable Overlay Network With Practical Locality PropertiesPresented by Rachel RubinCS294-4: Peer-to-Peer SystemsBy Nicholas Harvey, Michael Jones, Stephan Saroiu, Marvin Theimer and Alec WolmanP2P Systems 2003 ©2003 Rachel Rubin/UC Berkeley SkipNet:2Philosophy of SkipNet•General purpose, scalable, fault tolerant overlay that allows for explicit control over content availability and placement•Preserve useful content and path locality•Enable load balancing over subset of nodes•Provide resiliency against common internet failuresP2P Systems 2003 ©2003 Rachel Rubin/UC Berkeley SkipNet:3Added Functionality•SkipNet adds content locality–Explicitly place data on specific overlay nodes or across nodes within an organization•Adds path locality–Guarantee that message traffic is routed between two overlay nodes within the same organization stays within it–Important for availability and security•This provides advantages for availability, performance, manageability and security•Provides node and data managementP2P Systems 2003 ©2003 Rachel Rubin/UC Berkeley SkipNet:4Why not a DHT?•Controlling Data Location is not the goal of a DHT•DHT’s provide load balancing at the price of where data is stored–May be stored far away–May be stored out of the domain•Destroy Locality•Discard useful application-specific information•But what are the benefits of a DHT?P2P Systems 2003 ©2003 Rachel Rubin/UC Berkeley SkipNet:5Structure of SkipNet: Perfect Skip Lists•Dictionary-like structure stored in memory•Sorted linked list with pointers•Height of the i’th node is the exponent of the largest power-of-two that divides i•The pointers have length of 2h•Searches in O(log N)Perfect Skip List 1 2 3 4 5 6 7 8 9 10 0 1 0 2 0 1 0 3 0 1P2P Systems 2003 ©2003 Rachel Rubin/UC Berkeley SkipNet:6Structure of SkipNet: Probabilistic Skip List•Each node chooses a height with a probability of choosing height h is 1/2h•Maintains O(log N)Probabilistic Skip ListP2P Systems 2003 ©2003 Rachel Rubin/UC Berkeley SkipNet:7Structure of SkipNet: Perfect Lexicographic Address Space•Maintain a sorted list of all data records as well as “skip” pointers•Doubly-linked ring•Each node stores2*log N pointersP2P Systems 2003 ©2003 Rachel Rubin/UC Berkeley SkipNet:8Structure of SkipNet: Lexicographic Address Space (2)•The pointers maintained at each level if a nodes routing table are “rings”•Each level skips over 2h nodes•Routing possible in O(log N)•Ring membership determined by their unique random ID number – probabilistic optimization•Duplicate pointer elimination from the rou\ting table improves performance by around 20%P2P Systems 2003 ©2003 Rachel Rubin/UC Berkeley SkipNet:9Numeric Space vs. Lexicographic Space•Node names and content identifier strings are mapped into the Lexicographic space–Distributed generalization of Skip Lists–Support content placement and path localities•Hashes of node names and content identifiers are mapped into the numeric space–Supports DHT functionality–Routing between overlay nodes–Allows the functionality of ChordP2P Systems 2003 ©2003 Rachel Rubin/UC Berkeley SkipNet:10Structure of SkipNet: Lexicographic Searching•Follow the pointers that route closest to the intended destination•Route along the highest-level pointer that doesn’t point past the destination•Terminate when the message arrives at the node closest to the lexicographic nameP2P Systems 2003 ©2003 Rachel Rubin/UC Berkeley SkipNet:11Structure of SkipNet: Node Join•Find the top-level ring that corresponds to the random ID by searching through rings•Join the top-level ring and the the next lower ring, etc. until the zero-level ring–Nodes do not acknowledge the newcomer until this is completeP2P Systems 2003 ©2003 Rachel Rubin/UC Berkeley SkipNet:12Structure of SkipNet: Node Departure•Can route correctly as long as the bottom level ring is maintained•Repair upper-level rings lazily•Each node maintains a leaf-set that points to additional nodes along the bottom ringP2P Systems 2003 ©2003 Rachel Rubin/UC Berkeley SkipNet:13Useful Properties: Locality•Incorporating a peer’s address into a content name guarantees the content will be hosted there–Naming is not arbitrary•Routing locality can be guaranteed if you use naming prefixesP2P Systems 2003 ©2003 Rachel Rubin/UC Berkeley SkipNet:14Useful Properties: Constrained Load Balancing•Dividing a data object’s name into two parts–Specifies the set of nodes over which DHT leaf balancing should be performed–Input to the DHT hash function•Searches for the name prefix in lexicographic space•Switches to numeric space to search for the hash of the name suffix•Limitations–Can be performed over any naming subtree, not over an arbitrary subset of the nodes–Domain of load-balancing is encoded in the name, so transparent remapping is impossibleP2P Systems 2003 ©2003 Rachel Rubin/UC Berkeley SkipNet:15Useful Properties: Fault Tolerance•Generally node failures in overlay systems are not independent–Nodes belonging to the same organization tend to fail together•Independent failures–Maintain level zero–Lazy stabilization•Organization Boundaries–Since you preserve locality, this results in partitions instead of scattered link failures–Partitions remerged via the leaf setsP2P Systems 2003 ©2003 Rachel Rubin/UC Berkeley SkipNet:16Useful Properties: Range Queries•Inherits the functionality and flexibility in supporting
View Full Document
Unlocking...