Thus, the resource lookup comes down to lookup for the node s closest to the resource key. DHT systems provide efficient node lookup and routing messages between nodes.
Even in very large systems, every DHT node should be able to route messages to any other node recursive routing , or find the node responsible for any resource lookup - iterative routing in a small number of steps. Although being founded on a common concept, individual distributed hash table designs are based on different overlay network geometries: tree [ 27 , 30 , 36 ], hypercube [ 28 ], ring [ 33 ], XOR metric [ 22 ].
The overlay network is a virtual network formed by the connections between DHT nodes, and the geometry determines the connection graph structure - constraints defining between which pairs of nodes connections may be established. One of the most crucial characteristics of DHT systems is static resilience - the ability of the system to deliver messages in the presence of node failures, with the recovery mechanisms switched off. A node failure might be caused by a node leaving the system without proper communicating that fact, not allowing its neighbors to reestablish connections, a network connection being broken, a node being overloaded and not processing messages, or due to existence of malicious nodes not processing requests according to the protocol.
However, it also directly translates to the behavior of the system under churn the process of nodes joining and leaving the system - connecting to and disconnecting from the DHT [ 29 ] - efficiency, ability to deliver messages, lookup accuracy, data availability and many other.
It usually takes some time for the recovery and replication processes to react to topology changes, so maintaining a high level of static resilience is very important, especially in very dynamic systems, where the changes take place constantly. Moreover, static resilience also indirectly affects the efficiency of the system maintenance and recovery mechanisms.
A different approach for analyzing resilience of DHT systems, presented in [ 15 ], discusses fault-tolerance in the worst-case joins and leaves scenario. In [ 11 ], the authors discuss the influence of the geometry of distributed hash tables on their static resilience and average path length. Different geometries provide different degrees of flexibility in route selection the number of nodes to which messages may be routed in each routing step.
The authors prove that the flexibility in next hop selection is a crucial factor influencing the static resilience of the system. The flexibility determines how many other options remain for the next hop preserving routing convergence to the destination , when the best next hop is down for any reason. If there are few of them or none in some cases , the routing is very likely to fail very often under high failure rates.
Certain DHT architectures support the use of sequential neighbors sets - usually, sequential neighbors are some number of successors and the same number of predecessors of a node on a logical one-dimensional ring which requires single global ordering of the nodes.
Some DHTs naturally support the existence of sequential neighbors [ 33 ], and other do not [ 22 , 27 , 28 ]. Due to many advantages of maintaining such sets, the DHT designs, not supporting this concept naturally, are often modified to include the support for sequential neighbors [ 30 ]. As presented in [ 11 ] and [ 37 ], introducing sequential neighbors sets dramatically increases the degree of flexibility in route next hop selection, making such systems highly resistant to node failures and targeted node attacks.
These factors indirectly influence many other DHT characteristics, making them extremely important for large-scale DHT systems. Although such a one-dimensional model yields a high level of resilience to node failures, it may lead to path length increases in the presence of failures of many nodes. As the number of failed nodes increases, next hops are more often found only in the sequential neighbors sets, and at one extreme routing using only sequential neighbors , the expected path length is proportional to the number of the nodes in the system.
The use of a multidimensional routing metric may significantly decrease the expected path length when routing using only the closest neighbors sets. However, by using a multidimensional metric, the system loses the properties connected with the existence of sequential neighbors - ensuring that a certain number of closest nodes would match any potential direction.
This paper presents the architecture of a distributed hash table called HyCube. The presented model is based on a hierarchical hypercube geometry a multiple-level nested hypercube, where vertices are lower-level hypercubes and employs a variable modified by nodes on the route multi-dimensional metric adopting the Steinhaus transform [ 21 ].
Novel routing, lookup and search algorithms are discussed, as well as routing table nodes selection algorithms, and maintenance and recovery procedures.
HyCube is scalable, efficient and significantly outperforms existing solutions in respect of resilience, routing and lookup efficiency under dynamically changing conditions, despite not using the sequential neighbors concept.
A preliminary conception of the described DHT was presented at a conference and published in the conference proceedings [ 24 ]. This paper presents the complete design of HyCube , including numerous enhancements, supported by results obtained during extensive simulations. The rest of this paper is organized as follows. Section 2 presents the related work. Section 3 introduces the routing architecture of HyCube.
Section 4 describes the simulation methodology used for obtaining the experimental results presented in the paper. Sections 5 and 6 contain a study leading to improvement of the routing performance and resilience. The evaluation of the presented routing architecture is presented in Section 7.
The routing table node selection mechanisms used in HyCube are discussed in Section 8. Section 9 describes algorithms used for locating nodes in the system - lookup and search. Self-organization and recovery algorithms are discussed in Section Section 11 concludes.
This section briefly describes the most significant existing DHT architectures in the descriptions below, N denotes the number of the nodes in the system. Chord [ 33 ] is a DHT, in which nodes are logically located on a ring with 2 m possible positions identifiers. Routing in Chord is based on passing messages to nodes being closer on the ring to the destination node than the current node. The routing tables are built in a way allowing decreasing the distance left to the destination at least by half in each routing step.
The expected path length in Chord is log2 N. The ring topology naturally supports the sequential neighbors sets, mentioned in Section 1 , which makes it very resistant to node failures. CAN Content-Addressable Network [ 28 ] is an example of a distributed hash table built on a hypercube geometry.
The CAN nodes are located in a d -dimensional hypercube which in fact is treated as a d -dimensional torus - a ring in each dimension. The hypercube is partitioned into so-called zones each node in the system has a zone assigned to it , and messages are routed between the zones - in every routing step, a message may be sent to a zone adjacent to the current zone.
The routing flexibility is, however, limited in such a geometry, and the sequential neighbors sets cannot be used to increase the node failure resilience. There have been several works regarding improvements of efficiency of CAN network.
One of the approaches, described in [ 25 ] introduces shortcut zones and additional routing table nodes, corresponding to these zones. In [ 35 ], another approach is presented, where the hypercube is split into zones at multiple levels. The lowest-level zones correspond to the CAN zones, and zones at higher levels are so-called expressway zones - routing using these zones allows messages to be routed further than with the use of the regular CAN neighbors.
In both solutions, introducing additional zones, decreased the average path length between nodes to O log N. Plaxton mesh [ 27 ] is a distributed hash table based on the tree geometry. In Plaxton mesh , identifiers of nodes consist of m d -bit groups.
Every node maintains a routing table with multiple levels. For a given node A , the routing table level i represents node s , which share first i initial groups of bits of the identifier with A , and the routing table slot at j -th position stores a node sharing i initial identifier groups with A and having the next group of bits equal to j.
Thus, in every routing step, the routing algorithm is able to pass a message to a node, which shares a longer prefix with the destination node in terms of bit groups than the current node if such a node exists. As there is no flexibility in the next hop selection in each routing step, the message may be routed to exactly one node in the routing table , the level of static resilience of the system in its pure form is very low.
Pastry [ 30 ] uses a routing algorithm based on the Plaxton mesh , but, in Pastry , the distance between pairs of nodes is defined as the distance on a ring.
If a node sharing a longer prefix with the destination node is not found in a certain routing step, the message is routed to a node sharing the same prefix length as with the current node in terms of the number of bit groups , but being closer to the destination in terms of the metric ring. In addition to the routing table, every node maintains a set of closest nodes in either direction on the ring - the leaf set.
A set built in this way is, in fact, the sequential neighbors set, which ensures that, with high probability, any message can be routed by any node, decreasing the distance left to the destination, even if the corresponding routing table slot is empty. Main differences concern methods of ensuring locality, replication, as well as joining, leaving, and recovery algorithms. An example of such a design is Viceroy [ 18 ]. In Viceroy , every node is assigned one of m levels, and a unique ID - a real number from 0 inclusive to 1 exclusive.
The nodes also connect to their successor and predecessor on their level-ring, as well as the successor and predecessor on the ring formed by all nodes at all levels. Routing proceeds in three phases. In the first phase, a message is sent up to the top level. When the lowest level level m is reached, the search is performed using the ring and level-ring links until the destination is reached. The expected number of steps is O log N.
Kademlia [ 22 ] is a distributed hash table protocol which bases its search algorithm on the so-called XOR metric. Every node in the system maintains references to neighbors in structures called k -buckets.
With the use of the XOR metric and k -buckets, the lookup procedure quickly converges to the lookup key. The resources in Kademlia are stored in k nodes closest to the resource key, so a node performing a lookup for a resource searches for k closest nodes to the resource key.
Kademlia ensures its static resilience by the increased number of stored references to other nodes multiple references in k-buckets , and sending lookup messages to multiple nodes in parallel. The Kademlia protocol gained a great popularity and is nowadays the most popular DHT used in variety of applications.
An interesting family of distributed hash tables are the systems based on degree-optimal graphs. The problem of degree-optimal graphs is formulated in [ 17 ].
Koorde [ 12 ] is a distributed hash table based on Chord and de Bruijn graphs [ 2 ]. Another DHT based on the de Bruijn graphs, D2B [ 10 ], for a d -dimensional de Bruijn graph achieves the average path length O log d N and the expected number of references stored in the routing table O d.
The graph structure is based on a dynamic decomposition of the space into cells and assigning the cells to nodes. The structure ensures the path length of O log d N , where d is the node degree constant. The path lengths in these systems are therefore asymptotically even better than in Plaxton mesh.
Moreover, fault tolerance of the constant-degree DHTs in their pure form is very limited. Symphony [ 19 ] is another interesting distributed hash table protocol based on a ring topology, which models the small-world phenomenon [ 13 ] and creates links between nodes in a probabilistic way.
An extensive study regarding randomization in the construction of the connection graphs is presented in [ 20 ]. Although the research is constantly being conducted in the topic of distributed hash tables, majority of the currently used DHT systems and applications are based on the architectures already mentioned in this section. The recent research focuses mainly on extending DHT overlays with specific features, such as Sybil attack resistance [ 16 ], resource discovery for grid computing [ 4 , 26 , 31 , 34 ], as well as adapting DHTs to particular environments or applications [ 1 ], [ 9 ].
The architecture is conceptionally similar to the solutions based on the tree geometry Plaxton mesh , Pastry , Tapestry , however, extending the hierarchical geometry with a possibility of employing a multidimensional routing metric, which, together with the use of the variable Steinhaus metric, yields significant improvement in the resilience and performance of the system in the presence of node failures.
This section presents the routing architecture of HyCube - a distributed hash table system based on a hierarchical hypercube geometry. Sections 3. Section 3. The routing geometry of HyCube is a combination of the tree geometry and the hypercube geometry. It is similar to Plaxton mesh [ 27 ], but nodes are logically located in vertices of a d -dimensional hierarchical hypercube.
A hierarchical hypercube is a hypercube whose vertices are also lower level hypercubes. Vertices of the hypercubes at the lowest level are positions which may be assigned to nodes. Figure 1 presents the structure of an exemplary hierarchical hypercube with 3 dimensions and 2 hierarchy levels. Node IDs are determined by their positions - the identifier of a node is a string of d -bit groups determining positions of the node in hypercubes at individual levels starting with the hypercube at the highest level.
The position in a hypercube at a particular level is a number built of bits corresponding to the positions of the node in the hypercube in individual dimensions. The hierarchical hypercube and the tree geometries are isomorphic. However, the geometry of HyCube has a dual nature. Visualizing the structure as a hierarchical hypercube gives an idea of the non-hierarchical, spatial arrangement of nodes in a d -dimensional space - the numbers formed from bits corresponding to individual dimensions relate to the coordinates of the node in these dimensions in the system of coordinates with the center in point 0.
However, the geometry of HyCube should be seen as a d -dimensional torus with the perimeter equal to 2 l in each dimension the set of coordinates in each dimension is treated as on a ring.
This fact is important in determining distances between nodes - in every dimension the distance is determined like on a ring - the shorter of the distances in either direction.
In HyCube , the default number of dimensions is 4 and the number of levels is 32, resulting in a bit address space which allows avoiding conflicts of identifiers in majority of applications. The primary routing table has the same structure as in Plaxton mesh. It has l levels the number of hierarchy levels , and, at each level, there are 2 d slots d - the number of dimensions.
For clarity, groups of bits are represented by quaternary digits base-4 numeral system. The digits in bold represent the sub-hypercube addresses corresponding to routing table slots at individual levels. The underlined digits represent the hypercubes corresponding to the routing table slots matching the hypercubes of node X at individual levels. The secondary routing table of a node X contains nodes from adjacent hypercubes to the hypercube of node X in each dimension, in both directions, at each level.
An adjacent hypercube at any level is the one whose coordinate in one dimension is greater or smaller by 1 than the coordinate of the same level hypercube of X modulo 2 l , and coordinates in all other dimensions are equal to those of X. The secondary routing table does not contain nodes in slots at the highest level, as hypercubes corresponding to them are covered by the primary routing table.
Also, one of the adjacent hypercubes at each level in each dimension is covered by a primary routing table slot. The secondary routing table increases the level of flexibility in the next hop selection. With the use of the primary routing table, routing a message between nodes sharing a short ID prefix would require many steps of traversing the tree. For clarity, in this example, the IDs are represented as binary numbers.
Addresses of adjacent hypercubes corresponding to the routing table slots are marked in bold, and bits of addresses of adjacent hypercubes corresponding to the particular dimension are underlined - the numbers built of these bits are larger by 1 or smaller by 1 than the numbers formed of the corresponding bits of X. All other hypercube address bits the remaining dimensions are equal to the corresponding ones of X.
In addition to the routing tables described above, nodes maintain sets of closest to them according to the chosen metric nodes existing in the system - called neighborhood sets. Based on the same principle as sequential neighbors sets, the closest neighbors sets are expected to increase the probability of delivering messages in the presence of node failures. For sequential neighbors, the path length is proportional to N. Assuming the same probability of dropping a message by a single node along the path, the overall probability of dropping the message is smaller when the number of routing steps is smaller.
The neighborhood sets have also very good properties for supporting joining and leaving procedures, as well as maintenance and recovery algorithms.
Moreover, their existence is crucial for searching closest nodes for a given key discussed in detail in Section 9 , as well as for replicating resources. The default size of the neighborhood set is Let us consider routing a message from node X to node Y. Every node R along the route first checks if there is a reference to the destination node in its neighborhood set, in which case, the message is sent directly to that node.
Otherwise, the routing tables are searched for an appropriate next hop - the node that shares at least one d -bit group longer prefix of ID with Y than with R or shares the same number of d -bit groups of the ID but is closer to Y than R in terms of the chosen routing metric. The routing metric of HyCube is discussed in Section 5. For the time being, let us assume that routing converges according to the Euclidean metric.
The detailed algorithm is presented below:. Initially, the routing algorithm finds the slot in the primary routing table that corresponds to nodes sharing at least one group of d bits longer prefix of ID with Y than with the current node R. In a hierarchical hypercube, this slot corresponds to a hypercube in which the destination node is located, at a lower level than the lowest-level hypercube containing both, the current and the destination node. If this slot is not empty, the message is routed to the node found in the slot - increasing the common prefix length with the destination node Y by at least one d -bit group.
If no node is found in the appropriate primary routing table slot, nodes sharing the same prefix length with Y as with R in terms of the number of bit groups , but closer to Y in terms of the chosen metric, are also considered - both routing tables and the neighborhood set are checked.
From the set of nodes found, the node sharing the longest prefix of the ID with Y number of d -bit groups is chosen, and, if there are more than one such nodes, the node closest to Y according to the routing metric is chosen for the next hop. The primary routing table supports routing based on extending the ID prefix in terms of d -bit groups - tree-based routing Plaxton mesh , and the secondary routing table supports finding a closer node in any dimension - such nodes are likely to be closer to the destination node also in terms of the Euclidean metric.
Both routing tables and the neighborhood set are used for determining the best possible next hop, to which the message is routed. In cases when the acknowledgment mechanism is implemented at the application level beyond the scope of HyCube , the native HyCube mechanism may be switched off.
HyCube also implements message duplicate detection. In case of receiving a message duplicate, the duplicate is dropped. Message duplicates may be received as a result of incorrect routing or network problems, or an ACK message not being delivered. Duplicates are detected based on the header of the message. The address node identifiers space should be large enough to prevent potential conflicts of identifiers existence of two nodes with the same ID. The size of the address space in HyCube equals:.
However, the number or dimensions and levels of the hierarchical hypercube influences the system characteristics. Adding additional levels of hierarchy causes the address space to increase, but it also proportionally increases the number of routing table slots that nodes maintain. Moreover, the pessimistic route length would also increase, as in the pessimistic scenario, routing steps correspond to individual routing table levels.
Nevertheless, the expected route length remains at the same level, because, on average, similar number of routing table slots would be populated with high probability the lower-level slots are empty. Increasing the number of dimensions, on the other hand, has a very strong impact on routing characteristics. Although the routing tables grow sharply with the increase of the number of dimensions, the routing algorithm is more specific in selecting next hops - in each routing step, the common prefix with the destination node ID is increased by a larger number of bits, maintaining the same pessimistic path length and decreasing the average path length.
As the base of the logarithm Eq. However, the maintenance cost is significant, as the primary routing table size grows exponentially with the number of dimensions:. At one extreme, when the number of dimensions is equal to the number of identifier bits 1 level of hierarchy , every node would maintain references to all other nodes in the system, and the routing table slots would correspond to all possible values of node identifiers.
In the final part of a route, when the message is already relatively close to the destination node, the routing algorithm may omit some nodes that are close to the destination, but do not share the same long or longer prefix of ID with the destination node than with the current node. This phenomenon becomes more significant when a multidimensional metric is used. That is why, like in [ 30 ], HyCube uses a heuristic switching to routing based only on the distance left, when a message is already in vicinity of the destination.
Nodes should therefore be able to determine how close the message is to the destination in relation to the density of nodes in the space. If this condition is satisfied, all further nodes on the route are chosen based only on their distance to the destination node - they might not share the same long or longer prefix of the identifier. All nodes from both routing tables and the neighborhood set are checked and the closest node is chosen for the next hop.
The prefix mismatch heuristic may be also enabled, when no next hop is found with routing based on extending the common prefix length with the destination node. This behavior may be configured by changing a system parameter value.
In many cases, the number of neighborhood set nodes matching the destination is much larger if the selection is based only on the distance. Obeying the prefix condition is a much stronger constraint on the next hops, and may cause more failed paths, especially in the presence of many node failures. Thus, although the path length might increase, by default, HyCube switches to routing based only on the distance left whenever no next hop is found.
To maintain routing convergence, the prefix mismatch heuristic is followed by all subsequent nodes along the path. The value should be large enough to ensure high probability of message delivery. The simulation scenario consists of the following steps. First, a given number of nodes with random identifiers are initialized, and each node joins the system by connecting to a randomly chosen node already connected to the DHT.
When the DHT system is initialized, for varying numbers of failed nodes and for different system variants algorithms used, parameter values , a given number of test messages are sent between random pairs of nodes remaining in the system. A node failure means removing the node from the network and waiting for other nodes to remove the reference from their routing tables the mechanism described in Section 8.
During the simulation, the simulator registers the number of messages successfully delivered to the destination, the number of failed routes, and calculates the average route length. While simulating different network variants comparisons , for all simulations run in a batch, the same sets of generated nodes IDs are used.
They are connected to the system in the same sequence, using the same bootstrap nodes. Moreover, in order to eliminate differences in the results caused by different random simulation runs and to allow proper comparison of the simulated algorithms, the sets of nodes removed from the system node failures , as well as the pairs of nodes between which test messages are sent, are generated once and are used for all simulations in the batch.
When all DHT variants are simulated following the same scenario, it is possible to conduct a detailed comparative study of individual algorithms and parameter values. In DHT systems, distances between pairs of nodes are defined by a certain metric, and the routing converges according to this metric. The choice of the metric has a great impact on the average route length and the probability of message delivery. Choosing a one-dimensional metric allows the use of sequential neighbors, which has proved to greatly improve the static resilience.
However, the use of sequential neighbors may cause a significant increase in path lengths in the case of node failures, when many routing table slots are empty, and a large number of nodes along the paths are found in the sequential neighbors sets.
In comparison with sequential neighbors, the use of a multidimensional metric significantly decreases the expected path length when routing using only neighborhood sets. This fact becomes very important when considering network properties under churn or in the presence of node failures. However, by using a multidimensional metric, the network loses some properties connected with the existence of sequential neighbors.
In a multi-dimensional space, it is not trivial to ensure uniform distribution of the closest neighbors set, ensuring that a certain subset of these nodes would match any potential direction. For a ring topology sequential neighbors , there are only two possible directions, while for any number of dimensions larger than one, the number of possible directions is infinite.
As the neighborhood set nodes play a crucial role in maintaining high static resilience, the metric should provide the highest possible level of flexibility in next hop selection within the neighborhood set, which would directly translate to the overall resilience of the system.
Let us consider routing using only neighborhood sets and assume that in each step, next hops are chosen only by the distance left to the destination without ensuring the prefix condition. When a node chooses the next hop for a message, only a subset of the neighborhood set is closer to the destination node than the current node.
It is crucial that the number of such nodes be as large as possible, so even in the case of many node failures, the message would not be dropped. The expected ratio of the number of matching nodes to the number of all nodes in the neighborhood set may be interpreted as the probability that a message may be routed to a single node in the neighborhood set.
The following sections present a study maximizing this probability. L 1 defines the distance as a sum of distances in individual dimensions absolute values of differences of coordinates.
In a 3-dimensional space, these points are located on an octahedron, and for spaces having larger numbers of dimensions, the equal-distance points are located on a cross-polytope hyperoctahedron having its center in the point corresponding to the node ID, and vertices located on lines parallel to the coordinate axes, passing through point X.
The distance between two points is defined as the maximum of the distances in individual dimensions. In a 2-dimensional space, points being in equal distances to a certain point X are located on edges of a square with the center in the point corresponding to the X and edges parallel to the coordinate axes Fig. For larger numbers of dimensions, equal-distance points are located on a cube 3 dimensions or a d -dimensional hypercube.
L 2 Euclidean metric defines distance in a way that is the most natural and intuitive, corresponding to the way of measuring distances in everyday life. Equal-distance points are located on a circle in 2-dimensional space, a sphere 3 dimensions or a d -sphere d -dimensions. It is the ratio of the number of points possible nodes positions that are in the distance r from the current node and are closer to the destination than d , to the number of all points being at the distance r from the current node.
Because coordinates of nodes are integer numbers, nodes may take only certain positions in the space. However, such accurate calculations would obscure the picture. For simplicity, instead of the number of positions, let us consider lengths of curves, areas of the surfaces and their equivalents for higher dimensional spaces, which is a good approximation, because normally we are not interested in numbers of nodes within exact distances, but rather in a more general estimation in a certain distance range.
Figure 4 presents an exemplary visualization for a 2-dimensional space. If r is the distance to a certain node R being considered as the next hop, R is closer to the destination than the current node only if it is located on the dotted part of the circle of radius r around the current node.
The probability that a node in the neighborhood set is closer to the destination for 2, 3 and 4 dimensions equals formulas derived by the author :. Matching nodes for next hop selection L 2 - Euclidean metric.
The calculated probability values are visualized in Fig. The closer the message is to the destination node, the fewer appropriate nodes in the neighborhood set. The phenomenon becomes more significant as the number of dimensions increases. This fact has a great impact on static resilience - fewer node failures may cause the message to be dropped in the final parts of routing paths. L 2 Euclidean is the only metric from Minkowski distances preserving distances between nodes after space rotation.
For instance, if these metrics are used, depending on the direction of the vector from the current node to the destination, the expected numbers of nodes in the neighborhood set to which the message may be routed are different. The bigger squares represent the points being in the same distance from the destination node as the current node, and the smaller squares represent the points located in the distance from the current node, in which a certain node R , being considered as the next hop, is located.
The message may be routed to R , decreasing the distance left to the destination, only if it is located on the fragment of the smaller square that is inside the bigger square. It can be seen that the expected number of matching nodes closer to the destination than the current node strongly depends on the direction.
For higher dimensional spaces, this becomes an even more serious problem, as there might be very few or no nodes matching certain directions. Due to this fact, only L 2 metric will be considered in the further discussion. Matching nodes for next hop selection L 1 metric. In [ 6 ] and [ 7 ], the authors present the Steinhaus transform.
The terminology comes from the fact that this distance was used in biological problems for the study of biotopes [ 21 ]. Applying a metric with the Steinhaus transform to every route, setting the value of a to the ID of the source node, causes the next hops to be chosen in such a way that they are closer to the destination node and more distant from the source node.
Such an approach increases the expected number of neighborhood set nodes to which messages may be routed in each routing step - although some closer nodes according to metric D might be considered more distant when the Steinhaus transform is applied, it allows sending messages using more roundabout routes, while still being convergent to the destination node. One important remark should be made regarding the Steinhaus transform. The use of the Steinhaus transform yields very good routing parameters and very high static resilience for networks containing relatively few nodes.
However, for networks containing much more nodes denser , in final parts of routes, the addend D x , a of the denominator in Eq. Thus, the more nodes in the network, the lesser is the influence of the Steinhaus transform on the static resilience. However, a certain modification can be introduced - a variable metric adopting the Steinhaus transform, where point a would be changed by intermediate nodes along routes. The value of a would initially be set to the source node ID, and subsequent nodes, before choosing the next hops, would check whether they are closer in terms of the Euclidean metric to the destination than the current point a.
In such a case, point a would be updated - would be given the value of the current node. Such a way of changing point a ensures that the routing is convergent to the destination there will be no cycles on routes and yields a very high level of flexibility in the next hop selection along the whole route, regardless of the network size. It is easy to notice that whenever the Steinhaus point has the value of the current node ID, messages may be passed to any other node, decreasing the Steinhaus distance left to the destination.
With great probability the node closest to the destination in terms of the Euclidean metric is chosen. It may however not be a node that is closer Euclidean to the destination. Nevertheless, in such a case, the subsequent next hop selections would be more restrictive and converge to the destination faster. The routing algorithm simulated did enforce the common ID prefix length condition.
For comparison, if messages were routed using sequential neighbors in one-dimensional space ring geometry , the line would remain approximately at the level 0.
With the variable Steinhaus metric, the level of flexibility is higher than for sequential neighbors. Any message would be dropped only if all the matching nodes failed, and the probability of such a case is significantly reduced with the use of the variable metric. Figures 9 and 10 visualize the influence of applying the Steinhaus transform on the next hop selection. The destination node is represented by the blue point, the current node is represented by the black point, and the red point is the current point a.
The green part denotes the points that are closer to the destination node than the current node, according to Steinhaus metric. It can be seen that the expected number of nodes in the neighborhood set to which the message may be routed is much larger than with the use of the Euclidean metric, and in case when the message was previously routed to a more distant node, the next hop selection is more restrictive.
Visualization of the influence of applying the Steinhaus transform on the next hop selection. The green part denotes the points that are closer to the destination than the current node, according to Steinhaus metric.
Visualization of the influence of applying the Steinhaus transform on the next hop selection in the case when the message was previously routed to a more distant node. It should be noted that whenever the Steinhaus point is equal to any of the node IDs between which the distance is measured, the distance value equals 1, regardless of the second argument value:. When calculating distances from multiple nodes to the destination node, if the Steinhaus point is given the value of the destination node ID, it is impossible to differentiate the nodes, as all the distances are then equal to 1.
The routing algorithm is not exposed to such a situation - the Steinhaus point value would be equal to the destination point only when the destination is already reached. However, any other algorithm using Steinhaus distances, modifying the Steinhaus point, should take that fact into account e. Figure 11 presents simulation results of static resilience and path length increase in the presence of varying numbers of node failures for Euclidean metric, Steinhaus metric, variable Steinhaus metric, and 1-dimensional metric using sequential neighbors - with the use of closest neighbors sets only, without enforcing the prefix condition the routing converges only in respect to the routing metric.
The figure clearly shows the advantage of adopting the Steinhaus transform. In particular, using the variable Steinhaus metric yields significant decrease of failed paths rate. Routing with the use of sequential neighbors yields very poor performance and resilience due to the fact that the average number of hops path length , in this case, is proportional to the number of nodes in the system.
For larger systems, the results become much worse. Thus, sequential neighbors should not be used for routing on their own without any shortcut routing table support. The variable Steinhaus metric still has the best characteristics, although a longer average path length is achieved, compared to the sequential neighbors variant. However, for larger numbers of node failures, this increase is caused mainly by nonexistence of direct short paths between pairs of nodes and forcing the messages to be routed using more roundabout paths for other metrics, many of these messages would be simply dropped.
Because using the variable Steinhaus metric increases the average path length, especially for higher node failure rates, another simulation was performed to test the behavior of the system with the Steinhaus transform enabled only for the final routing steps, when the prefix mismatch heuristic is already applied. Theoretically, such a modification could decrease the path length, preventing messages from being routed to more distant areas according to the Euclidean metric in initial steps, when the average hop distances are much larger.
The use of the Steinhaus transform is the most important when the message is already in the proximity of the destination node, and the probability of finding the next hop in the neighborhood set drops sharply with the use of the Euclidean metric.
If the Steinhaus transform is used only when the prefix mismatch heuristic is applied, it would be enabled when the message gets close to the destination, or when no next hop is found which would also enable the prefix mismatch heuristic, allowing the Steinhaus transform to be used.
Figure 13 presents the simulation results - a comparison of the system with the variable Steinhaus metric used in every next hop selection with the variant enabling the variable Steinhaus metric only when the prefix mismatch heuristic is already applied. The obtained results prove that, indeed, the proposed modification decreases the average path length.
However, despite a significant decrease of the average path length, the modification did not cause any static resilience decrease. The final steps of routing with the use of a metric with the Steinhaus transform applied may cause a message to be sent to a node that is more distant from the destination than it would be if the Steinhaus transform was not applied. Therefore, when, at some point, a node on a route cannot find the next hop in its routing tables and neighborhood set, it is possible that the route is ended in a point node that is not the closest one to the destination in terms of the Euclidean metric.
For some applications, if the destination node itself cannot be reached, it is crucial to reach the closest possible node. Thus, HyCube introduces one more modification - when a message cannot be routed by a node, the node tries to route it again, based only on the Euclidean distance left to the destination.
All consecutive next hops after that should be chosen in the same way. Such an approach will cause that, in the case the message is dropped, a relatively close node to the destination is reached.
Furthermore, as it can be seen in Fig. There is, however, one drawback of such an approach - the failed path lengths undelivered messages may possibly increase due to re-routing with another metric after the next hop is not found. Nevertheless, messages usually get relatively close to the destination node, and, in most cases, only a small number of additional hops if any are performed.
This section presents several modifications of the routing algorithm, which lead to the increase of the level of static resilience. The enhancements include ensuring uniform distribution of neighborhood set nodes, hypercube-aware next hop selection and preventing storing the same node in routing table slots corresponding to overlapping hypercubes.
The neighborhood set should provide possibility to route messages regardless of the direction in which the destination node is located. Therefore, it is important that nodes in neighborhood sets be uniformly distributed in terms of directions. There might be a scenario where some nodes would have more closest neighbors in one direction and no or very few neighbors in other directions.
In such a case, the nodes would not be able to route messages in all directions using neighborhood sets. The issue becomes more important in the presence of node failures, when the number of matching next hops should be as large as possible.
When using sequential neighbors concept, the problem might be solved by splitting the set into two equal size sets - successors and predecessors. In this case, half of the closest nodes matches any message destination successors or predecessors depending on the direction on the ring. In a multi-dimensional space, however, it is not trivial to ensure uniform distribution of the closest neighbors set, ensuring that certain subset of these nodes would match any potential direction message destination.
Uniform distribution of nodes in terms of directions may be defined in a variety of ways, and many different algorithms may be employed to maximize this uniformity.
Both, proximity and even distribution, should be considered, because ensuring uniform distribution of nodes in respect of directions may cause some more distant nodes to be included in neighborhood sets and pass over some closer nodes.
The key is to maintain the good properties of neighborhood sets as being the closest existing nodes , and to make these good properties valid regardless of the direction. HyCube adopts a simple technique for ensuring uniform distribution of neighborhood set nodes in respect of directions. You are commenting using your Twitter account. You are commenting using your Facebook account. Notify me of new comments via email. Notify me of new posts via email. Skip to content. So what happens when a node fails and its underlying data are lost.
So it is a matter of separation of concern. Like this: Like Loading Next Post Instance-based vs Name-based Clustering.
Subjectivity aside, leave a reply Cancel reply Enter your comment here Fill in your details below or click an icon to log in:. Email required Address never made public. Name required. Follow Following. Sign me up. Already have a WordPress. Log in now. Post was not sent - check your email addresses!
0コメント