How DHT Nodes Refresh Buckets and Prune Dead Nodes

BitTorrent’s Distributed Hash Table (DHT), based on the Kademlia protocol, allows peer-to-peer file sharing without relying on centralized trackers by organizing connected nodes into routing table buckets. To maintain network efficiency and avoid routing requests to unresponsive peers, a DHT node continuously monitors the health of its routing table through scheduled bucket refreshes, proactive find_node queries, direct keep-alive pings, and replacement caches. This automated maintenance cycle identifies inactive nodes, removes them from the routing table, and promotes verified live peers.

The Structure of K-Buckets

A DHT routing table organizes contacts into lists called \(k\)-buckets, where each bucket holds up to \(k\) nodes (typically \(k = 8\)). Buckets are categorized by the XOR metric distance between the local node’s ID and the remote node’s ID. Because peer churn in torrent networks is high, keeping these buckets populated strictly with responsive nodes is critical for fast query resolution.

Node State Classification

Mainline DHT categorizes known nodes into three distinct states based on responsiveness:

• Good: The node has successfully responded to a query within the last 15 minutes, or it has responded to a query and sent a query of its own within the last 15 minutes.
• Questionable: The node has not responded to any queries or sent messages for over 15 minutes.
• Bad: The node has failed to respond to multiple consecutive queries or ping attempts.

Periodic Bucket Refreshing

If a node has not performed a lookup in a specific bucket’s ID range for a set period (typically 15 minutes), that bucket becomes stale. To refresh it:

1. Generate a Target ID: The node selects a random target ID that falls within the numerical range of the stale bucket.
2. Execute find_node: The node initiates a find_node query targeting that random ID, sending requests to the closest known nodes in that bucket.
3. Process Responses: As neighboring nodes return lists of active nodes closer to the target, the querying node receives fresh peer contacts to insert into its routing table.

Probing and Eviction Policy

Kademlia favors long-lived nodes over newly discovered ones because statistically, nodes that have been online for a long time are more likely to remain online. When a bucket is full and a new candidate node is discovered, the node does not simply overwrite an existing entry:

1. Ping the Least Recently Seen Node: The local node sends a ping query to the oldest (least recently active) node at the head of the bucket.
2. Retain Active Nodes: If the questioned node responds, it is moved to the tail of the bucket (marked as most recently active), and the new candidate is discarded or moved to a secondary replacement cache.
3. Prune Dead Nodes: If the questioned node fails to respond within a timeout window (often after two failed attempts), it is declared Bad. The dead node is immediately evicted from the bucket, and the new candidate node is inserted in its place.

The Replacement Cache

To avoid empty slots when dead nodes are pruned, modern DHT implementations maintain a replacement cache for each bucket. When new node announcements arrive for an already full bucket, valid candidates are queued in this cache. Once a dead node is pruned during a keep-alive probe or routing failure, the local node instantly pulls a verified replacement from the cache without needing to execute a new network lookup.