Balanced Kademlia

[Eknir]

User story

Story

As a node operator, I want to evenly spread the connections that I make each bin, such that I minimize the expected hop count for any random request (given a fixed amount of connections)

Acceptance criteria

• The average hopcount is reduced (compared to the current implementation)

Background

Old Swarm

Work on this was done in old Swarm (this PR as a reference).

Metabins

@metacertain has done research on this and he proposes to implement this concept with metabins. Each normal Kademlia bin contains a metabin, that on it's turn can contain 2 additional metabins or an array of peers. A metabin contains a value R which stands for the required number of peers in that bin and it is defined as the binSize (for the top metabin) or 1/2*R of the parent. When a metabin splits in two children metabins, the address space of the parent metabin is equally divided to the two children.
With this structure in place in both the connected peers and known peers, it becomes possible to implement the balanced kademlia logic, needed to fulfill the acceptance criteria of this issue.

Tasks

Task	Assignee	Done (1), or 0

[Eknir]

@metacertain, are you going to work on this?

[metacertain]

@Eknir yes!

[Eknir]

This issue is still in progress @metacertain . could you please update the status, connect it to a PR (if it exists) and put it back into the backlog if you are not currently working on it?
Thanks!

[metacertain]

Status - this is in progress still, experiencing performance problems for now, so it's under development