Information Technology Reference
In-Depth Information
(0, 4)
6
2
(0, 3)
3
1
5
(0, 2)
4
(0, 1)
(x, y)
(0, 0)
(1, 0)
(2, 0)
(3, 0)
(4, 0)
FIGURE 3.5: An example CAN with six nodes organized into a 2-
dimensional space in which node 1 routes through 4 to reach a given point
(x, y) [Ratnasamy et al., 2001].
robustness—as there are many different paths available for any two points in
the d-dimensional space, even if some nodes' neighbors are unavailable (e.g.,
just departed or crashed), the node can route the message via some other
paths.
The process to establish a CAN is also simple and hence robust. Specifi-
cally, a node joining the CAN has to carry out the following three steps:
1. Find a node already in the CAN;
2. Find a node whose zone is to be split (so that the new node can take a
half); and
3. Notify the neighbors of the split zone to update their neighborhood
information.
The first step, i.e., the bootstrapping process, can be implemented in many
ways. One common method is to store some default or bootstrap nodes' ad-
dresses in some public domain so that the new node can easily obtain them.
For the second step, the new node just randomly selects a point in the d-
dimensional space and sends a JOIN request to the node that handles the
corresponding zone. Notice that this JOIN request is sent to the known boot-
strap node which will then route it to the appropriate node handling the
selected point. Subsequently, the selected node splits its zone in half and the
new node takes one half. The associated keys and data items are then trans-
Search WWH ::
Custom Search