Algorithm
The algorithm implemented is inspired by the one described in draft-bryan-sipping-p2p-02, which in turn defines the Chord protocol using SIP as a transport for message exchanges. However, since the current version of the Internet Draft is not meant for real use (it's too long to explain why; if you are really interested, ask the P2P SIP community), it tries to address some of the open issues in a way that is not described elsewhere.
Finger Table
SIPDHT nodes maintain a finger table that is quite different from that that would be maintained by Chord nodes. The main differences are the following:
- finger numbering starts from 0 instead of 1. This is just a dumb choice, made by an old fashioned C programmer;
- each node is authoritative on the inteval [IDpred, ID), where ID is the identifier of the node and IDpred is the identifier of the node's predecessor (i.e. a node is not authoritative on his identifier, but he is on his predecessor's);
- the URL in the ith entry identifies the
(known) node which occupies the nearest position on the ring before the start of the
interval. Algebrically, such a node is the one for which the following function returns the
smallest value:
d(x) = |ID + 2i - IDx|MOD 2N,
where ID is the local identifier, IDx is the identifier of the node x and N is the number of fingers (i.e. the number of bits of the values returned by the hash function).
Search
Since SIPDHT finger table differs from Chord's one, also the search algorithm needs to be revised. However, the concept is pretty the same:
search(KEY)
if KEY in [IDpred, ID) then local_search(KEY)
for i in [0, N - 1)
if KEY in [ID, ID + 2i) then
forward_request(fingeri)
forward_request(fingerN - 1)
Maintainance
The greatest gain induced by the changes made in respect of Chord consists in the reduction of message exhcanges needed for maintaining the finger table updated. Indeed, while Chord nodes have to perform a query for each entry of the finger table for every stabilization phase, SIPDHT nodes can populate their finger table using only the information retrieved from their successor.
The information useful for populating the finger table are the URL of active nodes, which one by one are inserted in the entry where they fit best (if any). Thus, since the accuracy of the finger table depends on the number of active nodes known, each node can decide the balance of message exchanges and search efficency. Obviously, the choice made by a single node has impact on the whole DHT.
Performance
SIPDHT performance can be tuned in terms of number of message exchanges and, in the best case (i.e. when logN messages are exchanged for each stabilization phase), each operation is one message more expensive than the analogous Chord one. This seems to be due to the fact that each search must reach the predecessor of the authoritative node before being served.
NOTE: these consideretions are empirical.
