Re: DHT expiration questions

--- In [email protected], Raphael_Manfredi@... wrote:
>
> Quoting pwang708 <wang.peng@...> from ml.gnutella.dev-forum:
> :Please see my reply to the first message. The expiration time is big.
> :That is fine. But the republish time should be smaller since mojito
> :nodes assign smaller expiration time. 
> 
> As I said, your republishing period is just INSANE.  I cannot let
> gtk-gnutella match it.
> 
> What is LimeWire's expiration time?  Maybe I can adjust my republishing
> to be a little smaller than that.
> 
> Raphael
>


I uploaded a figure "Expiration time of DHT values : trade-off between
stale values and message overhead" to the folder Arne created.
http://groups.yahoo.com/group/the_gdf/files/Miscellaneous/Statistics/

An expiration time (hence the republish time) is a trade-off between
message overhead and stale DHT values in the network. When expiration
time is larger, there are more stale DHT values in the network since
more publishers left the network during this period. At the same time,
nodes save bandwidth since republishes happen less often. When the
expiration time becomes larger and larger,  however, nodes save less
and less bandwidth, since most publishers left the network. So an
expiration time largely depends on nodes' session time. The republish
time should be close to but less than the expiration time. To simply
the discussion, we assume they are the same. 

In the experiment, a limewire client joined mojito network and was
active for about 9 days. It received about 260K STORE requests in this
period. We take three fields from each request, sender (S), DHT value
(V), and the time (T) this request was received. Based on S, V, and T,
we identify initial publishes and their republishes as follows. For
the jth STORE request received, if there exists an ith STORE request,
such that S_i == S_j and V_i == V_j and T_j - T_i <= 40 minutes (note
the current republish period is 30 minutes), then j is considered a
republish of i. After processing the STORE requests, we see that about
227649 publishes did not have republishes, 9586 have 1 republishes,
1976 have 2 republishes... The data file was also uploaded to the same
place. 

The figure is based on these data. The green line shows the STORE
requests my node would received if we used different expiration time.
Assuming we need 100% STORE requests when we use 30 minutes as the
expiration time, we would saved about 5% of STORE requests when we use
1 hour as expiration time. Using 2 hours expiration time, we could
saved 7%. After that we cannot save more, since most nodes stop
republishing, and most likely left the network. 

The red line shows the fraction of possible stale values my node
stored when we use different expiration time. Note this is about the
fraction of stale values right before they expire. A published DHT
value is considered as stale, if the next scheduled republish doesn't
come. As we can see from the figure, when using 30 minutes expiration
time, 95% DHT values became stale before their expire, and more than
99% if 2 hour expiration time. 

Then what fraction of values was stale at any time? The data is not
good at answer this question, since we are trying to figure out nodes'
session time using republishes. 30 minutes is too large for this
purpose since most values became stale before that. However, this
figure still shows that DHT values expire fast due to short session
times. 

In summary, it does make sense to use short expiration time because of
the short life time of DHT values. Note, as discussed above, we cannot
save much bandwidth by using a long expiration time anyway. 

Note that this is not a rigorous study. Several factors were ignored.
E.g., republish messages could be lost, STORE requests could be
forwarded, etc. But I think the figure can help us to understand
expiration time of DHT values and the trade-off between stale values
and republish overhead. 



Now we need to figure out how to get rid of short-lived DHT values.
One simple solution is that nodes don't publish until they are online
for long time, longer than the current setting (5 minutes), e.g., half
hour. Then we may lose some data. Need to find some good Gnutella node
session time data...


Best,
Peng