Correctly implement kademlia bootstrapping algorithm

[Stebalien]

We currently bootstrap:

1. A random key.
2. Our own key.

However, this doesn't keep the entire routing table full. The correct algorithm is to:

1. Keep track of the last time we've searched for a key in each of the k buckets.
2. If we don't search for a key in a single bucket for an hour, pick a random key in that bucket and search for it.

See the end of section 2.3 in the paper.

[Stebalien]

@aarshkshah1992 want to try this one?

[aarshkshah1992]

@Stebalien Perfect. Let me take a look at the relevant paper section/code & come up with something.
Can you assign it to me ?

[aarshkshah1992]

@Stebalien

Currently, for bootstrapping, we query for self & a random nodeID once every 5 minutes(by default).

If I understand your comment/the code & this section in the paper correctly, we will now:

1. Query for self only once when bootstrap is initiated & not every 5 minutes
2. Query only once for a random id in each of the k-buckets created because of 1).... except for the nearest(last bucket in the routing table) k-bucket. Look at the following line in the paper:

Finally, u refreshes all k-buckets further away than it's closet neighbour

3. Keep track of which k-buckets get queried by hooking onto the 'dht.findPeerSingle' call
4. Query for a random nodeID in a k-bucket that does not get queried for more than an hour in 3)

Wdyt ?

[aarshkshah1992]

@Stebalien

So the k-bucket now looks like

type Bucket struct {
......

lastQueriedAtLk sync.RWMutex  
lastQueriedAt time.Time // set to the current time when a new bucket is created
}

func (b *Bucket) lastQueriedAt() time.Time {
    
}

func(b *Bucket) resetLastQueriedAt(newTime) {

}

We add a function to the routing table

func(r *RoutingTable) genRandPeerID(bucketID) peer.ID {
   if (bucketID == len(r.buckets) - 1) {
       Generated a peerID where ATLEAST bucketID bits match the host
   } else {
       Generate a peerID where EXACTLY bucketID bits match the host
   }
}

DHT.Bootstrap now has a dedicated go-routine that periodically scans the routing table to identify buckets that haven't been queried since an hour -> does a random walk for them -> resets the timer.

Two important questions are :

1. What should be the scan interval ? Should we do it say every 30 minutes ?
2. Is hooking onto dht.findPeerSingle a reasonable way to identify the peers that get queried so we can reset the timer for their buckets ?

[Stebalien]

Exactly.

However, in the periodic query, I'd keep the self query. That is, every hour, query self to determine the nearest bucket (there may be a closer bucket that we're simply not aware of), then proceed normally.

What should be the scan interval ? Should we do it say every 30 minutes ?

30m sounds fine. That gives us the hour delay.

Is hooking onto dht.findPeerSingle a reasonable way to identify the peers that get queried so we can reset the timer for their buckets ?

Yes.

---

I apologize for the insane delay. I was stalling trying to avoid context switching away from some other tasks till they were done. Thanks for the frequent reminders and please continue to bug me if I do this again.

[aarshkshah1992]

@Stebalien This issue can now be closed.