[chord] a quest about chord

[Aisling O' Driscoll]

Hi Mouse,



Hope I’m not too late in replying. You're correct, this isn’t very clearly
specified by the paper and it is assumed a stable ring already exists when a
node joins. It is fairly well described in the paper “Bootstrapping Chord in
AdHoc Networks: Not Going Anywhere for a While” though which you might find
helpful. It also took me a while to figure it out so here’s my
understanding:



Basically the first node to join (lets say N10) joins and sets it successor
to itself (N10) and its predecessor to nil. Lets say, two more nodes
subsequently join (N5 and N20).



·        N10 then periodically stabilises – As it successor is itself and
its predecessor is nil nothing happens.

·        N5 next stabilizes with N10. N10 returns a predecessor of NIL. N5
leaves its successor as N10 and sends N10 a notify message so that N10
updates its predecessor to N5.

·        N20 next stabilizes with N10. N10 returns a predecessor of N5. N20
updates its successor to N5 and sends N5 a notify message. N5 updates it
predecessor to N20.

·        N10 next stabilizes. As its successor is itself it checks its
predecessor to see if it’s not nil. Since its predecessor is N5 it sets it
successor to N5 and sends a stabilize message. N5 returns a predecessor of
N20. N10 sets its successor to N20 and sends a notify message to N20. N20
updates its predecessor to N10.



At this point the network is fully bootstrapped. This actually takes a long
time to occur and Cramer showed in his paper that to bootstrap a Chord
network involves linear time complexity O(n) e.g. if the stabilization
interval is 30s and there’s 40 nodes then it takes 120 seconds to fully
bootstrap.



Hope this helps.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://amsterdam.lcs.mit.edu/pipermail/chord/attachments/20100628/9a60c4d9/attachment.htm