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 -------------- next part -------------- A non-text attachment was scrubbed... Name: not available Type: application/pgp-signature Size: 189 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20070815/e44899c3/attachment.pgp>
