Re: DHT expiration questions

Given the lack of response, and because I need to move forward, I have
decided to use the following settings for gtk-gnutella:

* Republish interval: 12 hours
* Expiration interval: 13 hours
* Replication interval: 1 hour (standard Kademlia)

I have chosen an expiration interval greater than the republish
interval to let the source republish before the data leaves the network.

I have kept the standard 1 hour replication interval because
Kademlia's choice of k=20 normally ensures that at least one of the k
targets will be alive the next hour.  However, I did not keep
Kademlia's default 24 hours republishing interval because I believe it
is too large -- not that many hosts stay alive more than half a day.

For push-proxies ("PROX") values, the above settings are superseded as
follows:

* Republish interval: 2 hours
* Expiration interval: 3 hours

The expiration interval will be further modified as follows: if the
key falls within the node's k-ball, then no adjustment is necessary. 
If not, the adjustment will be exponential to the distance the key has
with our k-ball frontier:

Assuming the k-ball's frontier is F (meaning the furthest node among
our k-closest neighbours has F leading bits in common with our KUID),
and given X the amount of common leading bits the key of the value to
store has with our KUID, then the expiration interval will be divided
by 1.5^(F-X)

For instance, if F=14, and X=10 (we necessarily have X < F or the key
would fall into our k-ball), we have 1.5^(14-10) = 5.0625. The
expiration interval for a PROX would become 3/5.0625 = 35.5 minutes,
whilst an ALOC would be 13/5.0625 = 2 hours and 34 minutes.

Decimating using an exponential of 2 seemed too harsh: a node's
ability to act as a cache for highly requested values must not be made
useless by expiring cached values too soon.  However, cached values
will never be replicated.

To avoid replicating things over and over again, GTKG will further
adopt the following policy:

* Never replicate something not stored by the creator directly.
* Never replicate keys not falling in our k-ball (we were necessarily
a caching node at the time of the publication).
* Once a value has expired (according to the rules aforementioned),
GTKG will remember about that expiration and will not accept
replication from peers in the k-ball. Only the creator will be able to
publish the value back again.

Finally, GTKG will return the following additional store status:

#define STORE_SC_EXPIRED        14U /**< Value has already expired */

when a peer tries to replicate a value which GTKG has already expired.

Raphael