small lecturenumber - hepage : Distributed Hash Tablessmall lecturenumber - hepage : Desirable Propertiessmall lecturenumber - hepage : Chordsmall lecturenumber - hepage : CANsmall lecturenumber - hepage : Address construction in CANsmall lecturenumber - hepage : Examplesmall lecturenumber - hepage : Routing in CANsmall lecturenumber - hepage : Routing in CANsmall lecturenumber - hepage : Node joiningsmall lecturenumber - hepage : Node joining - bootstrappingsmall lecturenumber - hepage : Node joining - finding a zone to sharesmall lecturenumber - hepage : Node joining - updating neighborssmall lecturenumber - hepage : Examplesmall lecturenumber - hepage : Clean exitsmall lecturenumber - hepage : Handling Failuresmall lecturenumber - hepage : Latencysmall lecturenumber - hepage : Improvements: multiple coordinate spacessmall lecturenumber - hepage : Improved routing metricssmall lecturenumber - hepage : Overloading zonessmall lecturenumber - hepage : CAN summarysmall lecturenumber - hepage : Coralsmall lecturenumber - hepage : Coral in a Nutshell, pt 1small lecturenumber - hepage : Coral in a Nutshell, pt 2small lecturenumber - hepage : Coral DNSsmall lecturenumber - hepage : Coral HTTP proxysmall lecturenumber - hepage : Coral Architecturesmall lecturenumber - hepage : Routing and DSHTssmall lecturenumber - hepage : Sloppy Storagesmall lecturenumber - hepage : Sloppy Storagesmall lecturenumber - hepage : Sloppy Storagesmall lecturenumber - hepage : Semantic Overlay Networkssmall lecturenumber - hepage : Examplesmall lecturenumber - hepage : Classifying Nodessmall lecturenumber - hepage : Deciding which SONs to joinsmall lecturenumber - hepage : Querying in a SONsmall lecturenumber - hepage : Discussionsmall lecturenumber - hepage : SummaryDistributed Software DevelopmentMore DHTsChris BrooksDepartment of Computer ScienceUniversity of San FranciscoDepartment of Computer Science — University of San Francisco – p. 1/??16-2: Distributed Hash Tables•On Tuesday, we talked about Distributed Hash Tables◦Used Chord as an example•Able to act as a distributed storage and indexing mechanism•Maps “keys” (hashes of data) to “values” (coordinates in aspace of nodes.)•Each node is responsible for a set of the keyspace.Department of Computer Science — University of San Francisco – p. 2/??16-3: Desirable Properties•Desirable properties of DHTs include:◦Always able to find data stored in the network◦Able to support entry and exit of nodes◦Able to tolerate node failure◦Efficient routing of queriesDepartment of Computer Science — University of San Francisco – p. 3/??16-4: Chord•Recall that Chord uses a 1-D ring to structure the network.•Nodes keep a finger table that tells them the successors atvarious points in the network.•Routing requires O(logn) messages.•Can tolerate failures through replication of data.Department of Computer Science — University of San Francisco – p. 4/??16-5: CAN•CAN stands for Content Addressable Network•Developed at Berkeley at the same time as Chord wasdeveloped at MIT.•Also provides hash-table like functionality.◦get, store, deleteDepartment of Computer Science — University of San Francisco – p. 5/??16-6: Address construction in CAN•CAN uses a d-dimensional torus as its address space.◦Vector of d dimensions where each dimension “wrapsaround”•Each node is responsible for a zone in this space.•The hash function maps data into a point in this space.Department of Computer Science — University of San Francisco – p. 6/??16-7: Example0 ,01,10,11,01234 5•An example CAN in a 2-Dspace.•Node 1 is responsible fordata in the range ( (0-0.25),(0.5-1) )•Node 4 is responsible fordata in the range ( (0.5-1),(0.5-1) )Department of Computer Science — University of San Francisco – p. 7/??16-8: Routing in CAN•Each node keeps track of the IP address and zone of itsneighbors.•A neighbor is a node whose zone overlaps a node in n − 1dimensions, and abuts it in the nth dimension.•In our example, 2,3, and 4 are neighbors of 1.◦Remember that the space is really a torus.•Routing is done by greedy search.•Always forward the message to the neighbor who is closest tothe data, using standard Euclidean distance. (ties brokenrandomly)Department of Computer Science — University of San Francisco – p. 8/??16-9: Routing in CAN•In a d-dimensional space of n evenly-sized zones,◦Routing requiresd4(n1d) hops.◦Each node stores info about 2d neighbors.•By increasing d, we can reduce the length of routes•Cost: additional storage at each node.•We get resistance to failure when routing for free◦If we are trying to route through a non-responsive node, justchoose the “next-best” path.Department of Computer Science — University of San Francisco – p. 9/??16-10: Node joining•New nodes are added to the system by choosing an existingzone and subdividing it.•First, the new node must find an existing bootstrap node.•Then it must find its coordinates within CAN•Finally, it must update its neighbors’ routing tables.Department of Computer Science — University of San Francisco – p. 10/??16-11: Node joining - bootstrapping•It is assumed that the IP address of at least one current CANnode is known to the joining node.•The designers use DNS to map a CAN hostname to one ormore CAN nodes.•This bootstrap node can provide the IP addresses of othernodes in the network that can be used as entry points.Department of Computer Science — University of San Francisco – p. 11/??16-12: Node joining - finding a zone to share•The newly-joining node next randomly selects a point P in thecoordinate space.•It sends a JOIN message to that coordinate.•This message is routed as all other CAN messages.•When it reaches the node responsible for P , that node returnsa reply to the newly-joining node.•The node responsible for P then divides its zone in half andassigns half to the newly-joining node.Department of Computer Science — University of San Francisco – p. 12/??16-13: Node joining - updating neighbors•Once the zone has been partitioned, all neighbors need toupdate their routing tables.•New node gets the routing table from the node whose zone itsplit.•Adds node whose zone it split, and removes all non-neighbors.•Split node removes non-neighbors as well.•Both nodes send update messages to all affected nodes.Department of Computer Science — University of San Francisco – p.
View Full Document
Unlocking...