Content addressable network

Content addressable network

The Content Addressable Network (CAN) is a distributed, decentralized P2P infrastructure that provides hash table functionality on an Internet-like scale. CAN was one of the original four distributed hash table proposals, introduced concurrently with Chord, Pastry, and Tapestry.

Contents

Overview

Like other distributed hash tables, CAN is designed to be scalable, fault tolerant, and self-organizing. The architectural design is a virtual multi-dimensional Cartesian coordinate space, a type of overlay network, on a multi-torus. This d-dimensional coordinate space is a virtual logical address, completely independent of the physical location and physical connectivity of the nodes. Points within the space are identified with coordinates. The entire coordinate space is dynamically partitioned among all the nodes in the system such that every node possesses at least one distinct zone within the overall space.[1]

Routing

A CAN node maintains a routing table that holds the IP address and virtual coordinate zone of each of its neighbors. A node routes a message towards a destination point in the coordinate space. The node first determines which neighboring zone is closest to the destination point, and then looks up that zone's node's IP address via the routing table.[1]

Node joining

To join a CAN, a joining node must:

  1. Find a node already in the overlay network.
  2. Identify a zone that can be split
  3. Update the routing tables of nodes neighboring the newly split zone.[1]

To find a node already in the overlay network, bootstrapping nodes may be used to inform the joining node of IP addresses of nodes currently in the overlay network.[1]

After the joining node receives an IP address of a node already in the CAN, it can attempt to identify a zone for itself. The joining node randomly picks a point in the coordinate space and sends a join request, directed to the random point, to one of the received IP addresses. The nodes already in the overlay network route the join request to the correct device via their zone-to-IP routing tables. Once the node managing the destination point's zone receives the join request, it may honor the join request by splitting its zone in half, allocating itself the first half, and allocating the joining node the second half. If it does not honor the join request, the joining node keeps picking random points in the coordinate space and sending join requests directed to these random points until it successfully joins the network.[1]

After the zone split and allocation is complete, the neighboring nodes are updated with the coordinates of the two new zones and the corresponding IP addresses. Routing tables are updated and updates are propagated across the network.[1]

Node departing

To handle a node departing, the CAN must i) identify a node is departing, ii) have the departing node's zone merged or taken-over by a neighboring node, and iii) update the routing tables across the network.[1]

Detecting a node's departure can be done, for instance, via heartbeat messages that periodically broadcast routing table information between neighbors. After a predetermined period of silence from a neighbor, that neighboring node is determined as failed and is considered a departing node.[1] Alternatively, a node that is willingly departing may broadcast such a notice to its neighbors.

After a departing node is identified, its zone must be either merged or taken-over. First the departed node's zone is analyzed to determine whether a neighboring node's zone can merge with the departed node's zone to form a valid zone. For example, a zone in a 2d coordinate space must be either a square or rectangle and cannot be L-shaped. The validation test may cycle through all neighboring zones to determine if a successful merge can occur. If one of the potential merges is deemed a valid merge, the zones are then merged. If none of the potential merges are deemed valid, then the neighboring node with the smallest zone takes over control of the departing node's zone.[1] After a take-over, the take-over node may periodically attempt to merge its additionally controlled zones with respective neighboring zones.

If the merge is successful, routing tables of neighboring zones' nodes are updated to reflect the merge. The network will see the subsection of the overlay network as one, single zone after a merge and treat all routing processing with this mindset. To effectuate a take-over, the take-over node updates neighboring zones' nodes' routing tables, so that requests to either zone resolve to the take-over node. And, as such, the network still sees the subsection of the overlay network as two separate zones and treats all routing processing with this mindset.

Developers

Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker

See also

References

  1. ^ a b c d e f g h i Ratnasamy et al. (2001). A Scalable Content-Addressable Network. In Proceedings of ACM SIGCOMM 2001. http://berkeley.intel-research.net/sylvia/cans.pdf. Retrieved 2008-12-22. 

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Content-addressable memory — (CAM) is a special type of computer memory used in certain very high speed searching applications. It is also known as associative memory, associative storage, or associative array, although the last term is more often used for a programming data …   Wikipedia

  • Content addressable memory — Mémoire adressable par contenu Pour les articles homonymes, voir CAM. La mémoire adressable par contenu (CAM, en anglais Content Addressable Memory) est un type de mémoire informatique spécial utilisé dans certaines applications de recherche à… …   Wikipédia en Français

  • Content-Addressable Storage — Content Addressed Storage (CAS) ist ein spezielles Speicherverfahren auf Festplatten, das einen direkten Zugriff auf einzelne Objekte ermöglicht und gleichzeitig die Unveränderbarkeit der gespeicherten Information sicherstellt. Mit dem Content… …   Deutsch Wikipedia

  • Content processor — Content processors are sometimes confused with network processors that inspect the packet payload of an IP packet travelling through a computer network. These components allow for the design and deployment of next generation networking systems… …   Wikipedia

  • Network Search Engine — Computer networks are connected together to form larger networks such as campus networks, corporate networks, or the Internet. Routers are network devices that may be used to connect these networks (e.g., a home network connected to the network… …   Wikipedia

  • Recurrent neural network — A recurrent neural network (RNN) is a class of neural network where connections between units form a directed cycle. This creates an internal state of the network which allows it to exhibit dynamic temporal behavior.Recurrent neural networks must …   Wikipedia

  • Artificial Neural Network — Réseau de neurones Pour les articles homonymes, voir Réseau. Vue simplifiée d un réseau artificiel de neurones Un réseau de neurones artificiel est un modèle de c …   Wikipédia en Français

  • Neuronal network — Réseau de neurones Pour les articles homonymes, voir Réseau. Neurosciences …   Wikipédia en Français

  • IBM Systems Network Architecture — Systems Network Architecture (SNA) is IBM s proprietary networking architecture created in 1974. It is a complete protocol stack for interconnecting computers and their resources. SNA describes the protocol and is, in itself, not actually a… …   Wikipedia

  • Distributed hash table — A distributed hash table (DHT) is a class of a decentralized distributed system that provides a lookup service similar to a hash table; (key, value) pairs are stored in a DHT, and any participating node can efficiently retrieve the value… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”