1 files changed, 47 insertions, 29 deletions

diff --git a/p2p/discv5/table.go b/p2p/discv5/table.go
index 5c8c50706..2cf05009c 100644
--- a/p2p/discv5/table.go
+++ b/p2p/discv5/table.go
@@ -25,6 +25,7 @@ package discv5
 import (
 	"crypto/rand"
 	"encoding/binary"
+	"fmt"
 	"net"
 	"sort"
 
@@ -64,42 +65,54 @@ func newTable(ourID NodeID, ourAddr *net.UDPAddr) *Table {
 	return tab
 }
 
-func (tab *Table) chooseBucketFillTarget() common.Hash {
-	bucketCount := nBuckets
-	for bucketCount > 0 && len(tab.buckets[nBuckets-bucketCount].entries) == 0 {
-		bucketCount--
+const printTable = false
+
+// chooseBucketRefreshTarget selects random refresh targets to keep all Kademlia
+// buckets filled with live connections and keep the network topology healthy.
+// This requires selecting addresses closer to our own with a higher probability
+// in order to refresh closer buckets too.
+//
+// This algorithm approximates the distance distribution of existing nodes in the
+// table by selecting a random node from the table and selecting a target address
+// with a distance less than twice of that of the selected node.
+// This algorithm will be improved later to specifically target the least recently
+// used buckets.
+func (tab *Table) chooseBucketRefreshTarget() common.Hash {
+	entries := 0
+	if printTable {
+		fmt.Println()
 	}
-	var bucket int
-	for {
-		// select a target hash that could go into a certain randomly selected bucket
-		// buckets are chosen with an even chance out of the existing ones that contain
-		// less that bucketSize entries, plus a potential new one beyond these
-		bucket = nBuckets - 1 - int(randUint(uint32(bucketCount+1)))
-		if bucket == bucketCount || len(tab.buckets[bucket].entries) < bucketSize {
-			break
+	for i, b := range tab.buckets {
+		entries += len(b.entries)
+		if printTable {
+			for _, e := range b.entries {
+				fmt.Println(i, e.state, e.addr().String(), e.ID.String(), e.sha.Hex())
+			}
 		}
 	}
 
-	// calculate target that has the desired log distance from our own address hash
-	target := tab.self.sha.Bytes()
-	prefix := binary.BigEndian.Uint64(target[0:8])
-	shift := uint(nBuckets - 1 - bucket)
-	if bucket != bucketCount {
-		shift++
+	prefix := binary.BigEndian.Uint64(tab.self.sha[0:8])
+	dist := ^uint64(0)
+	entry := int(randUint(uint32(entries + 1)))
+	for _, b := range tab.buckets {
+		if entry < len(b.entries) {
+			n := b.entries[entry]
+			dist = binary.BigEndian.Uint64(n.sha[0:8]) ^ prefix
+			break
+		}
+		entry -= len(b.entries)
 	}
-	var b [8]byte
-	rand.Read(b[:])
-	rnd := binary.BigEndian.Uint64(b[:])
-	rndMask := (^uint64(0)) >> shift
-	addrMask := ^rndMask
-	xorMask := uint64(0)
-	if bucket != bucketCount {
-		xorMask = rndMask + 1
+
+	ddist := ^uint64(0)
+	if dist+dist > dist {
+		ddist = dist
 	}
-	prefix = (prefix&addrMask ^ xorMask) | (rnd & rndMask)
-	binary.BigEndian.PutUint64(target[0:8], prefix)
+	targetPrefix := prefix ^ randUint64n(ddist)
+
+	var target common.Hash
+	binary.BigEndian.PutUint64(target[0:8], targetPrefix)
 	rand.Read(target[8:])
-	return common.BytesToHash(target)
+	return target
 }
 
 // readRandomNodes fills the given slice with random nodes from the
@@ -175,6 +188,10 @@ func (tab *Table) closest(target common.Hash, nresults int) *nodesByDistance {
 // bucket has space available, adding the node succeeds immediately.
 // Otherwise, the node is added to the replacement cache for the bucket.
 func (tab *Table) add(n *Node) (contested *Node) {
+	//fmt.Println("add", n.addr().String(), n.ID.String(), n.sha.Hex())
+	if n.ID == tab.self.ID {
+		return
+	}
 	b := tab.buckets[logdist(tab.self.sha, n.sha)]
 	switch {
 	case b.bump(n):
@@ -228,6 +245,7 @@ outer:
 // delete removes an entry from the node table (used to evacuate
 // failed/non-bonded discovery peers).
 func (tab *Table) delete(node *Node) {
+	//fmt.Println("delete", node.addr().String(), node.ID.String(), node.sha.Hex())
 	bucket := tab.buckets[logdist(tab.self.sha, node.sha)]
 	for i := range bucket.entries {
 		if bucket.entries[i].ID == node.ID {