Re: [Sipdht-devel] CHORD Fingers

[Enrico M. <enr...@te...>]

Mosiuoa Tsietsi wrote:
> I have been testing out the sipdht-0.0.2 release.  Its working fine, but I have a query about the finger table entries that are generated when I simlulate nodes joining the overlay (DHT).  The DHT surely is based on CHORD since it uses finger tables (and draft-bryan-sipping-p2p-02 uses CHORD as example).

Actually the DHT implemented so far is not properly chord, since the
finger table management is simplified.  In fact it is populated using
only the information retrieved from the successor: basically, when the
DHT is stabilized, finger `i', which, for i > 0, should be the
responsible for the right-open interval [n + 2^(i-1), n + 2^1[, will be
populated by the closer _known_ node to the start of the interval.

This method, which actually isn't documented :-(, permits a drastical
reduction in the number of messages exchanged during the stabilization
procedure.  On the other hand, the number of iterations for get/put
seems to increase in the worst case from log2N to log4N.

> Say three nodes (127.0.1.1, 127.0.1.2 and 127.0.1.3) join the overlay (in that order).    And say [2] bootstraps through [1] and [3] through [2].  Using the sipdhtq command for displaying finger tables of the nodes with hash cardinality of 8, I get for [1]:
> 
> Finger 0: (0x2) : sip:2@127.0.1.1

Right.

> Finger 1: (0x3) : sip:2@127.0.1.1

The interval is [2, 3[ and the node closest to 2 is 1; since 1 is the
actual node, it can be replaced by its successor.

> Finger 2: (0x5) : sip:2@127.0.1.1

The interval is [3, 5[ and the node closest to 3 is 2.

If the cardinality had been 16, the 4th finger, responsible of [5, 9[
would have been 3.

If it is not clear, try to give a look to the sipdht_fit_finger function
defined in dht_util.c (its description is in dht_util.h).

> .......
> 
> Finger 0 gives the immediate successor of the node in the circular space, which I understand.  [2] is the immediate successor for [1], ok.  But I don't understand the i^th   entries for the finger tables of [1].  Using the formula s = successor(n + 2^i-1  ) formula, I should get for [1]:
> 
> Finger 0: (0x2) : sip:2@127.0.1.1
> Finger 1: (0x3) : sip:3@127.0.1.1
> Finger 2: (0x5) : sip:1@127.0.1.1
> .......
> 
> Please help me out if I got my understanding of CHORD mixed up, or I'm failing to interpret the output correctly.

None of the above.

> Again, if I use cardinality of 8, I also thought it would only give three lines of output (m=3 for three bit identifiers if there are 8 nodes: 0-7) for each node's finger tables.

It is.  Do not confuse hash cardinality (defined as SIPDHT_MAX_N in
dht.h) with sipdhtq -N parameter which is used only for output formatting.

Enrico