Indeed, have we actually replicated the clustering effect with churn in a simulation? Ian.
On 8/14/07, Matthew Toseland <toad at amphibian.dyndns.org> wrote: > > The reasons we need periodic randomization are 1) churn results in > clustering > and 2) attacks. So it would be interesting to look at it with some churn. > > I'll have a look at the rest tomorrow. > > On Tuesday 14 August 2007 21:50, vive wrote: > > Here are some experiments on running the swapping algorithm with > periodic > > randomization of node positions. The idea is to study measures against > > position clustering, and later on what can be made to counter attacks > > against the swap algorithm. No attacks have been simulated yet, this is > the > > pure impact of randomizing positions on the swapping algorithm. > > > > The network size was fixed to 10000 nodes, HTL to 100, and the average > > degree was varied. Each run a network was initiated as the Kleinberg > model, > > measured by routing a while on it, and then positions were uniformly > > randomly assigned between 0 and 1 before staring the swapping algorithm > to > > recover the efficient routing. > > > > The major thing to study was the frequency of randomizing the position. > One > > run was evaluated for each different frequency X. Randomizing frequency > X > > was used as follows: each node randomizes its location each X'th swap > that > > goes out from that node. To avoid cyclic behaviour (at least of the > simple > > case, perhaps this needs to be extended) each nodes counter for doing > this > > is initialized independenty between 0 and X before starting the > > simulations. Lets say a node randomly initalizes its counter to y > (between > > 0 and X), then it will randomize its location on the swap > > y,y+X,y+2X,y+3X... that starts from it with a random walk (of length 6). > > This is an easy way to let a node stay with a location for a while > (unless > > swapping) and to let the neighbors route through it before randomizing > > again. X=0 corresponds to not randomizing at all. > > > > Discussing the results: > > There seems to be room for running a low-frequent randomization to begin > > with. For one case (average degree=10) it even seems to perform better > in > > some cases with randomization with a quite large period (this surely > > depends on that randomization can help the algorithm get out of some > > suboptimal configurations). This does not seem to happen for a larger > > average degree, perhaps because each randomization will have impact on > more > > links (but that is no controlled answer, just speculation at the > moment). > > > > Another note: how quickly the algorithm improves the network from the > > entirely randomized state is not of foremost interest here, the > interesting > > thing is what happens when the network is rather stable from swapping > for a > > long period. Therefore its the resulting level (on the right sides of > the > > plots) that are important, but the levels seem to have settled around > some > > performance (I will rerun the first simulation again to see how pure > > swapping without no randmization behaves in a longer run) > > > > Finally, we dont know if the observed behaviour here will be the same in > > the current Freenet topology (since the efficiency of the swapping > > algorithm depends on how much the topology deviates from the Kleinberg > > model in the first case). Therefore any implementation attempt should be > > using defensively low periods of randomization. > > > > regards, > > /Vilhelm > > _______________________________________________ > Tech mailing list > Tech at freenetproject.org > http://emu.freenetproject.org/cgi-bin/mailman/listinfo/tech > > -- Founder and CEO, Thoof Inc Email: ian at thoof.com Office: +1 512 524 8934 x 100 Cell: +1 512 422 3588 AIM: ian.clarke at mac.com Skype: sanity -------------- next part -------------- An HTML attachment was scrubbed... URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20070815/bf8103d8/attachment.html>
