Content Addressable Network

Content Addressable Network (CAN for short) is one of the structured peer-to-peer networks, which are also known as Distributed Hash Table . Basically, CAN is an implementation of these distributed hash tables. The advantages of such structured networks include efficient and targeted searches. If the content you are looking for exists on the internet, it is guaranteed to be found.

Basic design

Exemplary distribution of the value ranges among the nodes A - D

CAN represents a logical overlay network which does not have to correspond to the physical network. The logical structure forms a d-dimensional torus in which key-value pairs (K, V) are stored in the points of the coordinate system. A hash function known to all nodes is used to determine the point. The coordinate space of the torus is shared by all nodes that are present at the CAN in so-called zones . Accordingly, a node has the key-value pairs whose point coordinates are in the zone of the node. Because the nodes only know the addresses and value ranges of their direct neighbors, a request must be routed through the network to search for content that is not in the immediate vicinity or in their own zone.

Routing

In order to direct a search query through the network, it is forwarded to the neighbor who has the shortest Euclidean distance to the destination. It is important to know who the neighbors are. In a d-dimensional coordinate system, two nodes are neighbors if their coordinates of the zones overlap in d - 1 dimensions. It is therefore possible for a node to have several neighbors and thus several routes to its destination. That makes this implementation very robust. This means that if a node fails, the request is forwarded to the next best neighbor. The same also applies if several nodes fail. If all direct neighbors fail , the node uses a ring search . This ring search is stateless, controlled flooding via unicast in the CAN mesh network. This is to find a node that is closer to the destination than the searching node to forward the request.

average path length: ; where , ${\ displaystyle \ left ({\ frac {d} {4}} \ right) \ cdot \ left (n ^ {\ frac {1} {d}} \ right)}$ ${\ displaystyle n = {\ text {Number of nodes}}}$ ${\ displaystyle d = {\ text {NumberDimension}}}$
increasing path length when adding a node: ${\ displaystyle O \ left (n ^ {\ frac {1} {d}} \ right)}$

Structure of the CAN structure

Add a node:

Finding a node already in the CAN
Finding a node that divides its zone
Notify neighboring nodes of new neighbors

Remove a node:

Joining the zones; Update of the routing tables

Failure of nodes:

Takeover message

Find a node

In order to join the CAN, the node that wants to join must find a bootstrap node that is already in the CAN. This is done using a bootstrap algorithm as described in P.Francis: Yoid: Extending the Internet Multicast Architecture . This gives the node an IP of such a bootstrap node, which has an IP address list of nodes located in the CAN and returns it. With this list the new node can now start to find a zone.

Find the zone

With the IP list mentioned under Finding a Node , the new node has its entry points into the CAN. Then the new node selects a random point in the coordinate system and sends a JOIN request with the coordinates of the point as the target. This request is now distributed via the CAN nodes and the routing algorithm to the node with the point in its zone. This node divides its own zone. This division is realized by a special axis sequence. First a zone is divided along the X dimension, then in the Y dimension. This is also important for the subsequent reconnection of zones. After the division, the respective key-value pairs are transferred to the new node.

Insert into routing

After the split, the new node learns the IP addresses of the immediate neighbors from the previous owner of the zone. After the two nodes know their new neighbors, they must be informed about the split. An UPDATE message is immediately sent to the surrounding neighbors so that they can update their own routing tables. The addition of a node obviously only affects a small proportion of all nodes in the CAN, i.e. H. only those nodes that have the shared zone as a direct neighbor. This is advantageous, for example, if a large number of nodes have to be managed. It is crucial that the number of neighbors of a node depends only on the dimension and not on the total number of all nodes.

Affected nodes by adding a node: ${\ displaystyle O ({\ text {NumberDimensions}})}$

Leaving the CAN

If a node wants to leave the CAN, there are two options. First, the node transfers its zone to one of its neighbors (free choice). If this results in a valid zone (distribution equilibrium - the zones are all approximately the same), the key-value pairs are transmitted and the node can leave the CAN. Second, the node does not find a suitable neighbor and passes its zone on to the neighbor with the currently smallest zone. This neighbor then has to manage two zones for a short time. If several such cases occur simultaneously, the range of values can be fragmented. To avoid this, there is a background algorithm - Background Zone Reassignment - which redistributes the zones in the background. When leaving the CAN, it is important that the nodes leave the network gracefully . This means that you first have to transfer your zone including key-value pairs to a neighboring node.

Reliability of the CAN

Of course, the CAN must also be protected against network errors and failures from other nodes. This protection is shown in a kind of takeover procedure . Under normal circumstances, each node regularly sends update messages to its neighbors to show that it is still active and available. The lack of an update signals an error in a node. This implicit signaling leads to an immediate takeover of the neighboring nodes. Otherwise the key-value pairs of the zone would be lost. Each neighbor executes this algorithm independently of the other neighbors and starts a takeover timer in proportion to its own zone size. If this timer has expired, the node sends a TAKEOVER message to all neighbors of the lost node. If a node receives such a message, it compares the zone size contained in the message with its own. If this is smaller than his own, he stops the takeover procedure. Otherwise it replies with its own TAKEOVER message. This is the most effective way to find an active, neighboring node with the currently smallest zone, which takes over the zone of the faulty node. In this case, too, it can happen that a node has to manage several zones at the same time. The background zone reassignment algorithm also applies here .

Extensions in the design

If you look at the basic design of the CAN, it quickly becomes clear that the freedom of the overlay network does not necessarily have to be an advantage over the physical network. The reason for this is the possibility that the physical nodes are on different continents and therefore also behind several IP hops. From this one can conclude that despite a neighborhood relationship at the overlay level, very large delays can occur at the physical level.

Average search delay: ${\ displaystyle \ operatorname {avg} ({\ text {NumberOfCANHops}}) \ cdot \ operatorname {avg} ({\ text {LatencyPerHop}})}$

There are two approaches to reducing this latency:

Reduction of the path length
Reduction of the latency on the hops

Multidimensional viewing

One possibility to reduce the path length is to increase the dimensions of the coordinate system. At the same time, this reduces the overall delay, because each node has more neighbors with increasing dimensions. Failure safety is also increased because a node has several alternatives available in the event of a failure of a direct neighbor. Conversely, this also means that the routing tables are slightly larger. Thus one can adapt the formula from routing for the scaling of the path length and say that an additional dependence on the number of dimensions applies for this approach.

Scaling the path length: ${\ displaystyle O \ left (d \ cdot n ^ {\ frac {1} {n}} \ right)}$

Realities

If the dimensions of the coordinate space are not limited, the number of coordinate spaces per node is also unlimited. This means that each node is assigned several coordinate spaces and thus also several zones that are independent of one another. These different coordinate spaces are called realities . With a number of r realities, a node is assigned to r coordinate spaces and has r neighborhood lists, i.e. one list per coordinate space. The advantage of the whole is the increased data availability due to the replication of the hash tables in every reality. There are thus even more paths through the CAN to the destination. This shortens the average path length because, in the event of a packet forwarding, the node first checks in each reality which neighboring node is closest to the destination.

Multiple hash functions

Another approach to reducing path lengths and increasing availability would be to use multiple hash functions on the same key. If one uses a number of k hash functions, one single key of a key-value pair can be stored in k points of the coordinate system. This means that the key is also distributed across different nodes, resulting in a higher level of data replication and a reduction in the average path length and latency. It should be noted that this increases the size of the key-value database, since each node has to manage a larger number of keys and the traffic for queries increases by a factor of k .

In A Scalable Content-Addressable Network , further approaches to the points mentioned above are mentioned and carried out. In addition, a tabular comparison of all implementations of the design extensions is listed.

Individual evidence

↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker: A Scalable Content-Addressable Network. Aug. 2001, SIGCOM'01.
↑ ^a ^b D. Korzun, A. Gurtov: Structured Peer-to-Peer Systems: Fundamentals of Hierarchical Organization, routing, scaling, and Security. Springer Science + Business Media, New York 2013.
↑ ^a ^b Konrad Miller: Lecture Distributed Operating Systems , July 2009.
↑ P. Francis: Yoid: Extending the Internet multicast architecture. YOID website , Unpublished Paper Apr. 2000.

[Quelle1-1] ↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker: A Scalable Content-Addressable Network. Aug. 2001, SIGCOM'01.

[Quelle2-2] D. Korzun, A. Gurtov: Structured Peer-to-Peer Systems: Fundamentals of Hierarchical Organization, routing, scaling, and Security. Springer Science + Business Media, New York 2013.

[Quelle3-3] Konrad Miller: Lecture Distributed Operating Systems , July 2009.

[Quelle4-4] P. Francis: Yoid: Extending the Internet multicast architecture. YOID website , Unpublished Paper Apr. 2000.