Information Technology Reference
In-Depth Information
0
7
1
6
2
3
5
4
FIGURE 3.1: An example Chord identifier-ring with three nodes currently
in the network [Stoica et al., 2001a].
1≤i≤m. Furthermore, the i-th entry also includes a half-open interval,
starting from s until but not including the identifier of the next finger. The
interval of each entry is very useful because it indicates the range of identifiers
that particular finger handles (e.g., responsible for storing the data items
within the range of identifiers). Most importantly, the i-th entry also contains
the identifier q of the successor node (i.e., q = successor(s)). Figure 3.2 shows
the finger tables of the three nodes in the Chord ring example with m = 3.
To illustrate the data item search process [Balakrishnan et al., 2003] (e.g.,
a file search in a file sharing system, or a tracker search in a video streaming
system), suppose node 3 needs to retrieve a data item with identifier 1. Check-
ing node 3's finger table, 1 is within the interval [7, 3) and the corresponding
successor node is 0. Thus, node 3 contacts node 0 to check the latter's finger
table in order to locate identifier 1. Eventually, node 0 finds that identifier 1
is handled by node 1, and reports this back to node 3.
Chord can also handle peer dynamics in a robust manner. Specifically,
Chord can maintain the following two invariants:
1. Each node's successor (i.e., the first finger) is correctly maintained.
2. For every data item identifier k, it is handled by node with identifier
successor(k).
When a new peer n joins the Chord network, the following three tasks are
carried out:
Search WWH ::
Custom Search