Specifics of peer addition in libp2p's kademlia routing table

I’m working with javascript implementation of kademlia and I looked through the outdated kademlia specs in the PRs. However, I couldn’t find if peers are stored in a least recently used ordering basis.

How are the peers stored in the routing table? If they are not stored on a least recently used basis, what changes do I need to make in order to ensure that they are?

I asked this question in the libp2p IRC channel and the answer is yes, peers get stored in the routing table on a least-recently-used basis. However, the js implementation doesn’t perform PINGs.

Hey @Mikerah, I’ve also been reading the kad spec, since I’d like to revise it soon and get it merged in. The spec doesn’t currently cover the lack of PING messages, but it’s not just the js implementation; go doesn’t do any pinging either.

The current state of things (in go, I haven’t looked closely enough at js yet) is that peers stay in their k-bucket until they disconnect entirely, at which point they’re removed. If a new peer is discovered, but the k-bucket they belong to is full, the new peer is just dropped without health-checking any existing peers.

There is a form of pruning, but that happens in the connection manager. Basically, when the DHT adds a peer to the routing table, it also tags the connection, which signals the connection manager to keep it alive if possible. If the connection limit is hit, untagged connections will be severed first, but DHT connections will eventually be cut. AFAICT, this is the only way a peer will proactively remove an entry from the routing table.

This is a significant change from Kademlia, and we have an issue in go-libp2p-kad-dht tracking this. My intuition is that this is leading to a brittle routing table with a lot of excess thrashing, but we’ll need to measure to know more.

1 Like