[10:57] <vivee> i've just been running some simulations to tradeoff closeness vs link delay, showing that nuder certain distrbutions of link delay it can actually improve GR :-)
[10:57] <vivee> the next step is to try fitting this to real numbers on link delays
[11:02] <CIA-33> toad * r14555 /trunk/freenet/src/freenet/node/RequestHandler.java: Re-enable request bytes logging. Was broken by refactoring in 14087. This may account for the recent problems with bandwidth usage/load...
[11:02] <toad_> vivee: under certain distributions what can improve what?
[11:06] <CIA-33> toad * r14556 /trunk/freenet/src/freenet/node/RequestHandler.java: Missed the vital part of the last commit. :)
[11:08] <vivee> toad_: greedy routing that adapts to request delays can make requests go faster than using strict greedy routing.
[11:08] <CIA-33> toad * r14557 /trunk/freenet/src/freenet/node/RequestHandler.java: Same problem with status
[11:09] <vivee> it's similar to what Ian did previously on "Next Generation Routnig"
[11:10] <toad_> hmmm
[11:10] <toad_> what's the basic principle?
[11:14] <toad_> I mean, in the simulation, what's your routing algorithm?
[11:14] <toad_> exactly how do you adapt to delays?
[11:15] <toad_> I can well believe that our implementation of NGR was rubbish for reasons other than it being theoretically intractable ... there could very well be something there which we missed because of all the alchemy and guesswork
[11:16] <vivee> well... the actual implementation is still somewhat from what I really hope for. :) the basic principle is to monitor delay to route to certain *distance*
[11:16] <vivee> this delay is monitored by overhearing forwarded requests as well as looking at locally initiated requests
[11:17] <vivee> and monitoring delay times is done by keeping a moving average, subtracting the delay to closests neighbors
[11:17] <toad_> this is delay for successful requests? unsuccessful requests? both?
[11:17] <vivee> snice we can only directly observe delay to *local* neighbors this quantity + expected from that neighbor is what I try to minimize
[11:18] <vivee> so minimizing expected time instead of the number of hops
[11:18] <vivee> however i still think the approach can be a little improved, by making some trick mathematically with the Kleinberg model (I have yet to experiment with that, the problem is to initialise one or two constants)
[11:18] <toad_> you try to minimise expected delay from neighbour plus what? average for that distance?
[11:18] <vivee> successful requests
[11:19] <vivee> yes
[11:19] <vivee> one extension to do is to monitor routing times sent over *individual* neighbors
[11:19] <toad_> hmmmmmmmm
[11:20] <vivee> you say that NGR didnt work ok?
[11:20] <toad_> well...
[11:20] <toad_> it was all alchemy, there's a thousand reasons for it not working
[11:20] <vivee> this is NGR running on the Kleinberg model, where we know greedy routing should work quite well..
[11:20] <toad_> right
[11:20] <vivee> so we just modify the greedy to minimize time to target instead of steps to target
[11:20] <vivee> (easily said)
[11:20] <vivee> approximately
[11:20] <toad_> yeah but then we have to calculate the time to target :)
[11:21] <vivee> of course, and this is what we do estimate
[11:21] <toad_> and we do want to route by location at some level, rather than purely by time ...
[11:21] <toad_> don't we?
[11:21] <vivee> yes! that is the tradeoff i'm talking about
[11:21] <toad_> maybe we could bias locations by performance somehow
[11:21] <toad_> in the swapping level
[11:22] <vivee> yes... the scheme should consist of 1) bias by time and 2) bias by location
[11:22] <vivee> it is 2) that is a little bit tricky, also compilcated by nodes swapping around
[11:23] <vivee> if links vary a lot then the scheme for biasing by time only will improve quite good
[11:23] <vivee> if the links vary less then the second bias also becomes important..
[11:27] <toad_> hmmm
[11:27] <toad_> whereas on NGR we tried to bias by time only
[11:27] <toad_> and we ended up always routing wherever was temporarily non-overloaded
[11:27] <vivee> yes, i understood that
[11:28] <vivee> then you didnt have the fitting to kleinberg model..
[11:28] <vivee> it's no guarantee it will fit well with the darknet topology though, but the now coming opennet seems promsing..
[11:29] <vivee> i quickly got a bunch of opennet peers yesterday after having connected to you..
[11:29] <vivee> talking about the periodic randomizing of the location, i think there may be an answer in an ideal kleinberg model (since i've made some experimence of number of swaps to convergence tehre)
[11:30] <CIA-33> toad * r14558 /trunk/freenet/src/freenet/node/RequestHandler.java: Report status
[11:30] <CIA-33> toad * r14559 /trunk/freenet/src/freenet/node/RequestSender.java: Minor sync bug
[11:30] <vivee> it depends on 1) how frequently nodes attempt swaps and 2) maximum fraction of nodes we want to have "unfitted to location" at any given momenet
[11:31] <toad_> hmmm
[11:31] <toad_> we can define that, or there is some theoretical reason for a particular value?
[11:31] <vivee> (and the network size, the number of swaps to fit well grows with network size, but we can put an upper bound on the network size in the foreseeable future at some 10000 perhaps for a while?)
[11:32] <toad_> 10k for a while, but it may grow fast e.g. at a slashdotting
[11:32] <toad_> of course usually it shrinks back down agai
[11:32] <toad_> n
[11:32] <vivee> you mean how to define the fraction of nodes that we allow to be unfitted at a moment? by experiment.. but its good to use this defensively and say e.g. max 5%
[11:33] <vivee> what is the scheme of initializing swaps?
[11:33] <toad_> hmmm?
[11:33] <vivee> how often?
[11:33] <toad_> very often
[11:33] <vivee> :)
[11:33] <toad_> every 2 seconds we check whether we are locked (i.e. currently doing a swap), and if not we send one
[11:34] <vivee> no explicit timer value then?
[11:34] <vivee> ah ko!
[11:34] <vivee> ok
[11:35] <toad_> if a swap comes in less than 900ms after the previous swap from that node, we reject it
[11:35] <vivee> cool
[11:35] <vivee> from that *neighbor* or from that *node*?
[11:35] <toad_> and obviously we only lock if we're one of the endpoints - we can have swaps going through us as well
[11:35] <toad_> from that peer
[11:35] <toad_> neighbour
[11:36] <toad_> it's an attempt at limiting the amount of influence a bad guy can have to some factor times the number of links he has
[11:36] <vivee> ah good, that is what i hoped it was :)
[11:37] <vivee> did you read my thesis paper anything? i had some experiments on e.g. with 10000 nodes in the ideal model.
[11:38] <toad_> which paper?
[11:38] <vivee> i sent you it a while ago to try explaining the metropolis hastnigs thingy
[11:38] <toad_> probably not...
[11:38] <toad_> http://www.dtek.chalmers.se/~vive/soc1.pdf∞ ?
[11:39] <vivee> no
[11:39] <vivee> http://www.math.chalmers.se/~ossa/vilhelm_thesis.pdf∞
[11:39] <vivee> check page numbered 9
[11:39] <vivee> (pg 14 in the document)
[11:40] <vivee> number 9, number 9, number 9, thats a weird beatles song?
[11:40] <vivee> n/m
[11:40] <vivee> there at the upper plot you have a network with 10000 nodes, and you see how effective the swapping is
[11:41] <toad_> ooooh
[11:41] <vivee> (this is quite ideal, without delays or limits/locks or so, so we definitely want to multiply this)
[11:41] <toad_> is there any indication as to the O() of the algorithm - how many swaps per node to stabilise?
[11:42] <vivee> it seems to be quadratic to reach a really good result :(
[11:42] <vivee> but the three different schemes i tried to seem to peform better
[11:43] <vivee> anyway, that is another question for later on perhaps
[11:43] <toad_> O(n) per node or O(n^2) per node?
[11:43] <toad_> I know oskar's original algorithm is something like that
[11:43] <toad_> well, i do need to read that paper and we need to talk about implementing new swapping algorithms
[11:44] <vivee> O(N) per node
[11:44] <toad_> well that's not utterly totally horrible, it _might_ be feasible even for big networks depending on churn etc
[11:44] <toad_> probably churn is too high for it to be acceptable though
[11:45] <vivee> yes, but dont make it a max priority. for smaller networks we can still expect to have uniform random swap selection to work fine (when we scale to 100000 nodes we may wish for other things :)
[11:45] <toad_> ok
[11:45] <toad_> then i suggest you post to the list, and file a bug
[11:45] <vivee> post what?
[11:46] <toad_> your paper with a brief explanation that you have found several better swapping algorithms
[11:46] <vivee> the results are too abstract for freenet though, the results may be different for 1) more churn 2) overloaded nodes 3) delay on links 4) so and so on..
[11:47] <vivee> i'm rather restrictive in drawnig conclusions except for in the ideal model
[11:47] <vivee> but anyway, i will do that - when i have decided how to pubilsh it in a more digestable form
[11:47] <toad_> :)
[11:47] <toad_> ok
[11:47] <toad_> yeah we need a lot more simulations :)
[11:48] <toad_> well... yes and no
[11:48] <toad_> I doubt very much that a swapping algo which is good in theory will be bad in practice because of overload
[11:48] <toad_> because of bad topology is quite possible
[11:49] <toad_> but if it does basically the same as the current algo only faster it's not likely to be worse re overload
[11:49] <vivee> me neither, but i'm still conservative about it until there is somewhat more fniegrained simulations :)
[11:49] <vivee> at least i need to simulate them in a decentralized way, if you would read the paper you would see how ideal it is
[11:50] <vivee> that is a requirement before putting out anything in a decentralized system
[11:50] <toad_> yeah, i might find time to read the paper...
[11:51] <toad_> "simulate them in a decentralized way" ?
[11:51] <vivee> what was shown by the simulations is that it's, well, theoretically possible when there is a good mechanism of connecting two peers that fit for swapping
[11:51] <vivee> when a network is a lot of disorganized this mechanism can only be an approximation of the best swaps
[11:51] <toad_> ahhh
[11:51] <vivee> however, i built the swaps with randomness in to compensate for that, and i was quite generous with the randomness,so...
[11:51] <toad_> so it will work less well on networks which had poor topology in the first place?
[11:52] <vivee> well, they should, as you say work *at least* as well as the uniformly random swap selection :)
[11:52] <toad_> well, the work on load is more urgent, but there should be some permanent, easily accessible record on the lists or the bug tracker in case you disappear
[11:52] <vivee> but an established freenet with nodes periocally randomizing positions can be expected to lie somewhere ni between very disordered and fitted to kleinberg
[11:53] <vivee> ok, i see what you mean
[11:54] <vivee> its in your brain now (probably overloaded from all the other hacking you do on freenet) at least :) -- but ok, i'll try to file it down before my SoC time goes out
[11:54] <toad_> :)
[11:54] <toad_> my brain is interested but things tend to get crowded out yeah :)
[11:54] <toad_> i'll stash this convo somewhere and try to find time to read the paper