js-libp2p icon indicating copy to clipboard operation
js-libp2p copied to clipboard

fix: grow routing table trie towards node kad-id

Open achingbrain opened this issue 1 year ago • 1 comments

Instead of having a balance trie, grow the routing table towards the current node's kad-id.

This gives a better knowledge of the network as we get closer to our own kad-id.

The previous behaviour can be replicated by setting prefixLength and selfPrefixLength to the same value.

Change checklist

  • [x] I have performed a self-review of my own code
  • [x] I have made corresponding changes to the documentation if necessary (this includes comments as well)
  • [x] I have added tests that prove my fix is effective or that my feature works

achingbrain avatar Oct 03 '24 11:10 achingbrain

Need to verify if this actually makes any difference.

Because we have a prefix-trie, the trie only grows deeper if the kad-ids encountered share growing prefixes. There will be plenty of peers encountered that have xor-closer kad ids to the root node but will be omitted because the shared bytes are not in the prefix.

That is, given the kad id:

000000

All of these are equally xor-distanced, but only the first would be included in the deeper section of the trie due to the shared bit being in the prefix:

011111
101111
110111
111011
111101
111110

Using a prefix is probably good enough to ensure a reasonable starting point for a query for an arbitrary kad-id, but it may not help when trying to discover more of the kad-space local to the node's peer id.

achingbrain avatar Oct 04 '24 12:10 achingbrain