[chord] Chord queries relating to Initialisation and Join
Aisling O' Driscoll
odriscoll.aisling at gmail.com
Thu May 20 11:56:49 EDT 2010
Hi,
I'd really appreciate any help/advice anyone could give on the below as I'm
quite stuck.
Many thanks in advance.
---------- Forwarded message ----------
From: Aisling O' Driscoll <odriscoll.aisling at gmail.com>
Date: Wed, May 19, 2010 at 7:30 PM
Subject: Chord queries relating to Initialisation and Join
To: chord at amsterdam.lcs.mit.edu
Hi,
I am currently implementing chord in opnet and would greatly appreciate if
two main points could be clarified to ensure my implementation is correct.
I have read differing accounts as to the order in which the steps should
occur for a node join so if the logic of the following sequence could be
verified that would be great:
1. I assume a chord ring is already formed.
2. Node n wishes to join the ring.
3. Node n contacts a known node in the chord ring (node q) and queries
q for its successor. Node p replies that its successor is node s.
4. Node n sets its successor = s and its predecessor = nil.
5. Node n then begins to build its finger table by getting node q to
do lookups for each of its finger table entries (according to
the algorithm
as specified in the paper, n – 2^i-1).
6. Does node n then trigger the stabilize function or do I set a timer
for node n and wait for stabilize to occur at the next interval? If it is
triggered, then node n will inform node s of its existence so that it can
update its predecessor pointer.
7. Node p, who was previously the predecessor of node s, then sends
it’s periodic notify message querying node s’ predecessor. When node s
replies saying its predecessor is node n, node p updates its
successor and
notifies node n that it is its new predecessor.
8. Am I correct in saying that *only now* does node n copy the keys
it’s responsible for i.e. only after all the above steps have
occurred? And
if so, does the predecessor node p initiate this transfer upon
learning that
it has a new successor just after it sends the notify message?
9. Furthermore when does the predecessor node p update its finger
tables to reflect node s? Is it immediately, when it learns that it has a
new successor and immediately recalculates every entry in its
finger table
or is it done gradually according to the fix_fingers algorithm?
10. Finally I have read differing accounts as to how other nodes in
the ring update their finger table entries. I think according to
the default
Chord algorithm this is done lazily i.e. every node periodically does a
lookup on a random finger table entry i.e. fix_fingers. Therefore it will
take O(log N) intervals to update the entire table. I have read others
accounts such as the attached that claim all nodes whose finger tables
previously referred to node s must be updated. They reference the Chord
SIGCOMM paper so I am unsure which approach to take? Also, if a proactive
approach is taken how does joining node n know which nodes should be
updated?
My seconds question relates to how nodes join when the network is first
initialised (as opposed to later on when the Chord ring is functioning – as
per above).
1. So node n joins the network. It is the first node in the Chord ring.
It sets successor = n and predecessor = nil. It creates every entry in its
finger table so that every entry finger_table [i] = n. It is now the
bootstrap node for the network.
2. Now node m joins the network. This is where I’m confused. Node m
contacts node n (its equivalent of a bootstrap node). It queries its
successor. Node n will reference its finger table and deduce that node n
itself is the successor for joining node m. Node m will then query node n
for its finger table entries but based on the previous step all the answers
will be set to that of node n. So both nodes will now have finger tables
only containing entries for node n. Is this correct behaviour? And if so how
will these nodes ever have build correct finger table entries?
Many thanks in advance.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://amsterdam.lcs.mit.edu/pipermail/chord/attachments/20100520/c18f827e/attachment.htm
More information about the chord
mailing list