[chord] Chord In PeerSim Problems

[Karrels Daniel R CPT AFIT/ENG]

Hello,

 

I am trying to build a Chord implementation for PeerSim but am having some
problems. In particular, using the pseudocode that I have found online, I am
having difficulty resolving node locations. Here is the code:

 

// ask node n to find the successor of id

 n.find_successor(id)

   if (id\in(n, successor])

     return successor;

   else

     // forward the query around the circle

     n0 = closest_preceding_node(id);

     return n0.find_successor(id);

 

 // search the local table for the highest predecessor of id

 n.closest_preceding_node(id)

   for i = m downto 1

     if (finger[i]\in(n,id))

       return finger[i];

   return n;

 

I am building the network one node at a time, but not executing any queries
until all nodes have been built (50-1000 nodes for testing).  I have not
been able to find any definitive information about how to initialize the
finger tables. Are they supposed to be nil? If so, how does one handle nil
references in find_successor() and associated methods? I have been
initializing the fingers to point to the host node ('this'), but that
doesn't seem to be correct either. In this case, searching for nodes without
a proper exploration of the identifier space causes the above
find_successor() to be an infinite loop, because 'this' is always returned.

 

To this end, I have tried implementing some more elaborate approaches to
distributing identifier information, but have had marginal success at best
(message delivery rates on the order of 66%, with terrible performance). As
knowledge of identifiers propagates, nodes will only choose to keep
information about other nodes if they are better than the current node they
have for a particular identifier range. However, if they believe they have
something better already, knowledge of the propagated node is not passed on
to other nodes, and thus is lost. I am seeing that this propagation tapers
off after a few hops, therefore resulting in finger tables still not
becoming fully updated.

 

Any ideas what I am doing wrong? Any help is greatly appreciated.

 

Daniel R. Karrels

 

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://amsterdam.lcs.mit.edu/pipermail/chord/attachments/20090210/af13fe7f/attachment.htm 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/png
Size: 171 bytes
Desc: not available
Url : http://amsterdam.lcs.mit.edu/pipermail/chord/attachments/20090210/af13fe7f/attachment.png 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/x-pkcs7-signature
Size: 6442 bytes
Desc: not available
Url : http://amsterdam.lcs.mit.edu/pipermail/chord/attachments/20090210/af13fe7f/attachment.bin