Consider adding a network overlay

This is a summary of some prior discussions related to network overlays.

Message stratification is an idea to help reduce overall network traffic in various scenarios. In essence, each node is assigned a persistent node ID (a large random number that survives node restarts) and then a network overlay, such as Kademlia [1], is used to efficiently route messages to relevant nodes.

For instance, once durable votes are implemented, a network overlay enables propagation of votes with far less network traffic. Durable votes would be stored on partitions of the ID key space (the possible permutations given the size of the node id, typically 160 bits). A light node would then query votes in this key space, allowing it to be connected to just a few nodes - the Kademlia distance metric ensures that any key/node can be reached within log(n) steps where n is the number of nodes. A network overlay reduces load on representative nodes since other (partial) nodes store durable votes.

[1] http://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf

What is the focus for the network overlay, is it just for durable votes or also bootstrapping, or live block/vote broadcasting?

While the current fanout of sqrt(peers) is fast and redundant to ensure delivery it results in a lot of duplicated messages, on average around 8-11 duplicates on the live network with 325 peers, and as the number of nodes increases the number of duplicate messages will also increase.

If the network overlay will not be changing live broadcasting should the fanout be reduced now that TCP is implemented and message delivery is more often guaranteed? Even reducing the fanout by 1/3 (eg 12 instead of 18 for 325 peers) would result in a 1/3 reduction in overall messages and bandwidth while still maintaining similar propagation metrics.

Another option could be to increase the fanout from the sending node for blocks by 3-4x and then reduce rebroadcasting blocks by other nodes by 1/2. This would reduce the overall network bandwidth requirements by almost half for block propagation while putting a higher bandwidth requirement on the sender which would help disincentivize spamming.

Also since the network is organized into Principle Representatives and non PR nodes, the faster blocks get to PR nodes the quicker they can be confirmed and can move on to other blocks. With that in mind, having a sender broadcast to a large portion of PR nodes would help speed up the confirmation process. PR nodes could also partially focus on sharing their votes with a predetermined amount of other PR nodes in order to keep the PR nodes relatively in sync with each other during higher load instead of relying on random peer selection.

Thoughts, comments or questions? What can help or needs to be done to analyze this further?

Yes, fanout is probably on the conservative side (at least with tcp) and there's an issue discussing that (https://github.com/nanocurrency/nano-node/issues/993)

Are they considered 2 separate/independent topics or will fanout be impacted by the network overlay? Is DHT primarily for data lookups like bootstrapping and durable vote lookup?

When fully implemented, an overlay would connect a node to a few "neighbouring" peers (with a preference for peers with long uptime), which would replace the ~sqrt(n) flooding. I suppose you could imagine a transitional phase using a kademlia-style DHT to support durables votes first, with normal fanout for other messages.

Thanks, that really helps to understand the focus and direction!

I guess the number of neighbours is less than sqrt(nbr of peers), thus, the messages will be sent to fewer peers, and hence requiring more jumps before the messages reach all peers. It seems that this will increase the time it takes for a block to get propagated and confirmed. Do you have any intuition about this?

Seems like it would depend on how many neighbors you have in the DHT, it should be much more efficient if contacts are more organized than current fanout. With 325 nodes if you have just 9-12 or maybe even fewer contacts and there is sufficient organization it should be similar to the current sqrt(325) fanout. With more organization you really only need just a few fanout to get to all nodes in 2-4 hops like it is now.

While kademlia gives clear upper bounds, the actual hop count in a given network configuration is apparently hard to analyze. There's a large body of research and I think studying those and doing simulations is going to be important (see for instance https://pdfs.semanticscholar.org/8f1c/cee9698e6aefcae07013e86fad47bea4254d.pdf regarding hop distribution)

Some (somewhat dated) research suggests even large overlays like Mainline DHT (bittorrent) can have lookup latencies as low as 2-300ms.

1 Like