Problem with the calculation of the finger table

[areiter]

I think there is a problem with the calculation of the finger table. If creating less than explorer.min-peers nodes, everything works as expected and the finger table only contains the first finger, linking to its successor.

Increasing the nodes yields a problem. Take a look at the following finger tables: https://gist.github.com/areiter/3818428f92d99a9e3d6b

It seems like, the calculation of the IDs of the fingers is only based on the local peer ID, and does not take the IDs of other peers into account. This works fine as long as the IDs start at zero and are increased by one for each peer. In the case of a hash value, with a few nodes in the large ID space, the fingers should consider the IDs of the other nodes: successor(successor(...n)) and so on.

Any ideas on that? Thanks

[daviddias]

explorer.min-peers is a way to make sure we don't start calculating the finger table until we have an interesting number of peers.

The calculation of fingers happens in two phases

1. Finding the ideal fingers, that is, in a DHT filled with every ID, what would be the ideal finger for that row
2. Finding the successors for the ideal fingers, which means, finding the peer that is responsible for that ID in the DHT

I noticed now that I didn't have the latest signalling server pushed, with configurable Finger table. Take a look at:

• https://github.com/diasdavid/webrtc-explorer-signalling-server/blob/master/config/default.json#L13-L19

That array represents the rows on the finger table that should be filled.

Thank you for noticing this and apologies for the confusion.

[areiter]

I think your point 1 is exactly what I'm unsure about. What is the added value that is provided by calculating the finger table based on an imaginary DHT filled with every possible node ID. Node IDs have 48bit, so there are 2^48 unique node IDs available, this is quite a huge number. So, I propose that in practice you will never make advantages out of the finger table, and will always send requests to your direct successors. In my opinion a better solution would be to calculate the finger table based on the actual connected nodes (on the structure of your actual network). The signalling server, which is currently doing the finger updates anyhow knows all the nodes. What do you think?

[daviddias]

What is the added value that is provided by calculating the finger table based on an imaginary DHT filled with every possible node ID. Node IDs have 48bit, so there are 2^48 unique node IDs available, this is quite a huge number.

The calculation is not done by bruteforcing, you calculate for each row, an ideal Node and for that ideal Node, you calculate the sucessor. This is described in the Chord paper[1], see Table 1 and Figure 3 for example. Let m know if you have any questions.

[1] - http://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf

[areiter]

You're right, according to the paper it is implemented correctly, but from a practical point-of-view it seems a bit inefficient. All of the ideal fingers will refer to the same actual node, because node IDs are spread through the whole ID space.

However, my initial concern was that the finger calculation is not implemented correctly because the routing was not working all the time on my side. In my initial tests I spawned 10 nodes in a short period of time. After that, the routing information is broken. I wrongly suspected the finger calculation, but I think I have found the real reason for that (at least it's working now :smile: ). It's located in the fingerUpdate function. The channelManager operates asynchronously, once a peer connection is ready the finger table entry is populated. If multiple finger updates (with the same rowIndex) arrive in a short period of time, the callbacks of the channelManager.connect might not be in the same order, and the finger table on the client diverges from the calculated finger table on the signalling server.

I made a quick fix by introducing a ready flag and writing the finger entry to the finger table immediatly. I guess the channelTo method will also need an adaption in the long run.

   self.fingerUpdate = function(data) {
        console.log('finger-update', data);
        // 1. Check if needs to perform a new connect or just update an entry on the table
        // 2. Connect if necessary
        // 3. Once connected, update the finger tableA

        if (table[data.rowIndex] &&
                table[data.rowIndex].fingerId === data.fingerId) {
            console.log('already had establish this channel with: ', data.fingerId);
            return;
        }

        if(!table[data.rowIndex]) {
            table[data.rowIndex] = {};
        }
        if(table[data.rowIndex].channel) {
            table[data.rowIndex].channel.destroy();
        }
        table[data.rowIndex].fingerId = data.fingerId;
        table[data.rowIndex].ready = false;

        channelManager.connect(data.fingerId, function(err, channel) {
            console.log('finger table row update: ',   data.rowIndex, data.fingerId);

            if(table[data.rowIndex].fingerId !==  data.fingerId){
                console.log('Finger %s at index %d changed while connection was established, closing channel', data.fingerId, data.rowIndex);
                channel.destroy();
                return;
            }

            if(!table[data.rowIndex]) {
                table[data.rowIndex] = {};
            }
            if(table[data.rowIndex].channel) {
                table[data.rowIndex].channel.destroy();
            }
            table[data.rowIndex].fingerId = data.fingerId;
            table[data.rowIndex].channel = channel;
            table[data.rowIndex].ready = true;
        });

    };