On Thu, Sep 24, 2009 at 11:23 AM, Matthew Toseland <toad at amphibian.dyndns.org> wrote: > On Monday 21 September 2009 23:35:54 Evan Daniel wrote: >> Builds 1234-1236 included several changes to routing that we hope >> improved things. ?Specifically: >> - The "loop fix": when node A is choosing how to route a request it >> received from node B, when considering node C's FOAF locations, it >> should ignore locations among C's peers that exactly match B's >> location. ?That is, A shouldn't try to route a request back where it >> came from by an alternate route. ?Similarly, A should ignore A's own >> location, and the locations of any node A has already tried to route >> to and failed (rejectedLoop, rejectedOverload, etc). >> - FOAF tie breaking: When A is routing a request, if both B and C have >> the same minimum FOAF distance from the request location (presumably >> because they have a peer in common), A should tie break on which has >> the better immediate location. >> - A change to ULPR propagation that shouldn't have much direct impact, >> but may have had an indirect impact. >> >> This is also the first time we've made network-level changes since I >> started collecting the hourly HTL success rate data; hopefully, this >> gives me something to analyze and determine in detail whether the >> changes made an improvement. >> >> First, the caveats: ?1236 is not yet self-mandatory, so there may >> still be some upgrade disruption happening. ?This is only data from my >> node; edt has been sending me his hourly stats data as well, but I >> don't yet have any post-1236 data from him, so I haven't included any >> of it. ?There are known local changes at my node (fewer persistent >> requests queued) that correlate, because my node lost its node.db4o >> with the 1236 upgrade (though I do attempt to model local request >> count impact on success rates). ?I don't yet have enough data to know >> if there are any weekly effects (though I have attempted to account >> for time-of-day effects). ?And all I've done are regression tests; I >> haven't yet done the various non-parametric statistics tests to >> produce an actual p-value on whether the change made a difference. ?I >> strongly suspect it did, but there's too much structure to my >> residuals and too much non-normality to the data to be able to say >> that from what I've done so far. ?Network load is meaningfully lower >> on the new data as well, and I don't know how to explain that. >> >> To summarize: these results are highly preliminary. ?Do *not* draw >> conclusions from them. ?They are, however, interesting and promising. >> I'll have better data soon, that we might be able to begin drawing >> tentative conclusions from. ?But for now, I think the data are >> intriguing enough that people would enjoy seeing them. ?I would be >> *very* appreciative of comments or suggestions. >> >> Now, the request: ?I'd like more people to send me their success rate >> data! ?So far I only have one; that's rather disappointing, given how >> many people want a faster Freenet. ?It's not hard; just turn on >> loglevel normal, make sure you have plenty of space allocated to logs >> so it doesn't drop old ones, and then run "zgrep HourlyStats >> logs/freenet-*.gz > output.txt" and send me the results by email. >> There's nothing non-anonymous in there. ?You don't have to remove >> duplicates; I can handle that easily. ?There's no particular need for >> you to worry about use of your node, internet connection, uptime, etc; >> I'm trying to model that, and I should be able to basically average it >> out. ?I'd like high-uptime nodes, but it's not required. >> >> So, the preliminary results. ?All data is based on the total observed >> CHK success rate (both local and remote; the % listed in the success >> rate by htl box on the stats page). ?First, the raw success rate vs >> HTL graph: >> freenet:CHK at >> u3EvtVA0k6wVFmcji-ww0-yBdmLKmYEf~hyXD6hbF-o,mphkKgatjdGtpHjf70t7APtBy82eW-GHwPjWWnNQFW4,AAIC--8/rate_both.png >> The success rates are rather noisy, but it looks at first glance like >> the new data (magenta) shows higher success rates than the older data >> (blue). >> >> Next, I created a linear regression model that attempted to explain >> success rates based on other factors. ?I included HTL, using 4th order >> polynomial fit, since it showed a fair bit of curving; an exponential >> or power model is probably better, but nonlinear regression is more >> complicated. ?The high order polynomial should match such curves >> reasonably well. ?I included a linear fit on local CHK blocks fetched, >> on the assumption that local load probably has an impact. ?I included >> a quadratic fit on total incoming CHK requests, as an indicator of >> local / global network load. ?And lastly, I included a sinusoidal fit >> (amplitude and phase, but not frequency) to time of day, and second >> and third harmonics. ?Overall R^2 was 0.84, with high significance >> values; all parameters were significant at the 1% level (most >> dramatically better than that), with the exception of the third >> harmonic of time of day. >> >> (The model was built against the unified set of data; we'll look for >> changes resulting from the new build in the residuals, rather than in >> model coefficients.) >> >> Having explained away a large fraction of the variation in the data, >> we look at the model residuals: >> freenet:CHK at >> 9uNNkexj6-WQKqdC2pWmxqrEyJYkdnXQ-ej46c41qAc,Gsi0xqKxA2hC~3w9iwZm9S8IwcBhH4ljXH7jOAmtSpU,AAIC--8/resid_vs_htl.png >> What we see here is the portion of the success rate not explained by >> the model (the residuals). ?Positive numbers mean that the observed >> success rate was higher than predicted by the model, negative means >> lower. ?The lines shown are average residual by HTL; they present a >> slightly clearer picture of what's going on than the clouds of data >> points. ?Roughly, we see improved success rates at HTL 11-17, no >> change at 6-10 and 18, and a slight decrease at 1-5. ?This is not >> inconsistent with the hypothesis I had posed before releasing the >> builds, which was that improved routing would improve the success >> rates at all HTLs, but that there would be a secondary effect of >> improved routing meaning that more "easy" requests succeed at high >> HTL, and that therefore the remaining low-htl requests would be >> "harder", reducing the success rate. ?(I predicted we would see >> improvement at high htl, and a slight gain, no change, or slight drop >> at low htl.) >> >> Lastly, we look at a plot of model residuals vs success rate: >> freenet:CHK at >> kKiyz3eNCHAhLen8d-BQ8v0JfPJC818Yol3vKxB-phc,JgzKJzaTsqV2iNiz-5OTl~Gt4AuKR0X-NH6NBHDCzD8,AAIC--8/residuals.png >> For a multivariate regression, plotting residuals vs observed result >> is a good way to get a visual picture of whether the model is doing a >> good job. ?If the model is explaining all non-noise factors, the >> residuals should show no vertical patterning (horizontal patterning >> represents patterns in the collected data). ?We see significant >> vertical patterning, of a similar structure on both sets of data. ?The >> structure suggests that there are unexplained factors that influence >> the success rate. ?Candidates include things like whether I was >> running messaging apps (and therefore making those popular keys easy >> to find), and how long my node had been up (and thus the population of >> the recent requests cache, which I have set to a longer than default >> lifetime). ?The similarity in residual structure suggests that this >> model deficiency is probably not having a huge impact on whether our >> conclusions are valid. >> >> Looking at the model coefficients is mildly interesting. ?For example, >> the time of day factor shows a maximum impact on predicted success >> rate of +/- 1.6%. ?Success rates are good in the 2200-0200 UTC range, >> and less good in the 1200-1700 range. ?The magnitude of this effect is >> swamped by the individual data noise, but it is present. ?Other >> effects modeled (local / network load) show similar magnitude impact. >> We see a strong impact from the network load parameter (incoming chk >> request count); it accounts for a change of +/- 9%. ?This is something >> else that shows strong pre/post 1236 changes: the post-1236 data has >> less network load. ?I don't know why this would be, but we can clearly >> see it on this graph of residuals vs remote requests: >> freenet:CHK at >> VWLFEk98dqWlYJI6eDcDIvCvY7rW6Y3DKiJrmZraTbM,cvdKwGJjuaZjYtI8gGSC~o6s6Ul1PZ1Y9p9y0buL2EE,AAIC--8/resid_vs_remote.png >> >> This network load discrepancy is worth examining in more detail. >> Lower global load might well account for the entire observed effect; >> there might be no change from the new build. ?On the other hand, we >> expect improved routing to reduce global load (though I would be >> shocked if it reduced it as much as is observed). ?I don't know how to >> explain this; clearly, more modeling work is required. > > How much was network load reduced? >
I've updated the graphs. I now have more data from my node, and the data from edt's node. freenet:CHK at fSgH5IZAfhu520RxbJEcbKtsCYmJ9nXI50YGQcJgfnI,n1geI~yPHuzdn-pDKHqlP4bgD6HJnpBeRhFav9OtIMU,AAIC--8/edt_resid_by_actual.png freenet:CHK at T3Ti8c-p8F2-6m4cU4iqdcb~K-TZLRr9SRJJp4VlXBI,dkbK-85hwAFhzoKpcJmEnR8eI6mnGEPcy3UWJfhQS5Q,AAIC--8/edt_resid_by_incoming.png freenet:CHK at dd1TktpFPba0sKAlDJ3otlXUseIGDI9tGQbnIg5IggI,lt5rC6aqBeCX7I8wbwUtimtTLMexSQ0RZ6d3L7KXbC0,AAIC--8/edt_resid_by_htl.png freenet:CHK at Uc4aBfFe34hiyECwaIhu1y7xOu1hK9jyIuW14TpdFDI,pabkc8Vd0ManWTmyxlQJaZXhZBXcRri8KdZjkhVwt0g,AAIC--8/evand_resid_by_htl.png freenet:CHK at HFD2gN84QULgL~HXVJGG~kp5xwPxUQ550RQmdwlvGmo,1cDo-wd4w-kcJf-fiUrQCbByYGdyENh0~UkqwjlPSyA,AAIC--8/evand_resid_by_incoming.png freenet:CHK at f1mL6rh3qZGC4vTyyIl51ncDZVcp3X0hm8tSsOzw8VE,Uf53WdcaHsh4Z9Qsg4crrc49RaiyeJOq18mi2jInhdI,AAIC--8/evand_resid_by_actual.png I created regression models independently for the two nodes (identical explanatory variables, different coefficients). The results from the two nodes are similar, but not identical. I believe both are consistent with an improvement post-1236, though a small one. I'm somewhat perplexed by the shape of the curves in evand_resid_by_htl.png. You can get a sense of the change in network load by the resid_by_incoming graphs; the x-axis for those is total incoming accepted CHK requests during the sampling window. I'm not willing to put a precise number on it without making an attempt to correct for time of day biases, but both nodes appear to show a reduction. Evan Daniel
