P2P Network Architectures - Peer-to-Peer Computing: Applications, Architecture, Protocols, and Challenges - page 34

finger table data:
(1) start: 1; interval: [1,2); succ: 0
(2) start: 2; interval: [2,4); succ: 3
(3) start: 4; interval: [4,0); succ: 6
keys stored: --

0

7

1

2

6

finger table data:
(1) start: 7; interval: [7,0); succ: 0
(2) start: 0; interval: [0,2); succ: 0
(3) start: 2; interval: [2,6); succ: 3
keys stored: 6

finger table data:
(1) start: 4; interval: [4,5); succ: 6
(2) start: 5; interval: [5,7); succ: 6
(3) start: 7; interval: [7,3); succ: 0
keys stored: 1, 2

3

5

4

FIGURE 3.4: Updated finger tables of the three nodes in the Chord ring
after node 3 leaves [Stoica et al., 2001a].

3.2.2 CAN (Content Addressable Network)
CAN (Content Addressable Network) [Ratnasamy et al., 2001] is another
prominent pioneering distributed hash table (DHT) design. Similar to Chord,
each CAN participant handles a region of the entire key-value space, called a
zone. To support e cient routing, each node also stores information about a
small number of adjacent zones in the hash table. Specifically, all the nodes
in the network are logically organized into a virtual d-dimensional Cartesian
coordinate space. For example, Figure 3.5 depicts a 6-node CAN organized
into a 2-D space. Here, node 1 handles the square zone: (2, 2), (3, 2), (3, 3),
(2, 3).
With this logical organization, for any data item V with key K, the key
K is hashed into a point in the coordinate space. The data item is then
stored at the node that handles the zone containing the point. To retrieve a
data item, the same hash function is used to locate the zone and request the
corresponding node for the item.
To support routing of requests, each node needs to determine and record
its neighbors' IP addresses. The “neighbor” notion is intuitive: two nodes
(hence two zones) are neighbors if their coordinate spans overlap along exactly
d−1 dimensions in the d-dimensional space. As can be seen in Figure 3.5,
node 1's neighbors are nodes 2, 3, 4, and 5, but not 6. Routing is then very
simple—a node just greedily forwards a message (or request) to the neighbor
with coordinates closer (in terms of Cartesian distance) to the destination
coordinates. Figure 3.5 shows how node 1 routes a message to the coordinates
(x, y) via node 4.
In general, for a d-dimensional space divided into n equal-sized zones, it
can be shown that the mean routing path length is (d/4)(n 1/d ). Furthermore,
each node in the network needs to maintain 2d neighbors. These expressions
indicate that the CAN design is highly scalable because per node state is
independent of the number of nodes in the system. Even for the path length,
the growth rate is only O(n 1/d ). Another important feature of a CAN is its