Information Technology Reference
In-Depth Information
ferred to the new node. Finally, the neighborhood information of the affected
nodes is updated.
(0, 4)
6
2
(0, 3)
3
1
7
5
(0, 2)
4
(0, 1)
(0, 0)
(1, 0)
(2, 0)
(3, 0)
(4, 0)
FIGURE 3.6: The updated situation of the CAN after node 7 joins [Rat-
nasamy et al., 2001].
Figure 3.6 shows the situation after node 7 joins the example CAN. No-
tice that the members of node 7's neighbor set 1, 2, 4, 5 will update their
corresponding neighborhood information.
3.2.3 Other Structured Approaches
Let us first briefly examine two other well-known pioneering DHT ap-
proaches: Pastry [Rowstron and Druschel, 2001a] and Tapestry [Zhao et al.,
2004]. In the Pastry approach, each node identifier is a 128-bit number picked
from a circular key space also. Each peer keeps a routing table having log b N
rows (here, b is some system-specific integer value). In each row, there are
nodes with identifiers matching one prefix more than those of the previous row.
Consequently, routing works by matching the identifier in the local routing
table for the longest shared prefix with the key. In terms of time-complexity,
Pastry DHT systems route a message within O(log b N ) hops. Tapestry is sim-
ilar in design as Pastry. Specifically, each node keeps connecting to a set of
peers that share common prefixes with its identifier. A Tapestry DHT can
also route a message in O(log b N ) steps.
Fu et al. [Fu et al., 2008] proposed an internetworking approach for con-
necting different DHT networks together, as shown in Figure 3.7. This is an
important idea because we can expect a variety of DHTs are being used in
Search WWH ::




Custom Search