On Monday 20 August 2007 18:55, vive wrote: > Here are some simulations on the churn-clustering topic which we've > been discussing.. > > The simulations show that churn by shortlived nodes entering and quickly > leaving the network can add upp to the clustering in the address space. > When freenet nodes join the network they typically randomize their > positions. The simulations conver what may happen when they leave after > a relatively short while, after having participated with the swapping > algorithm - so we can think of this as even non-malicious and possibly > normal behaviour.
Great to finally have some proof of this. > > The experiments were made as follows > > 1. Create a network with Kleinberg edges, average degree=10 and HTL=100 > when routing. The positions are then shuffled and the swapping algorithm > is run until we have 90% success rate and relatively good routing > (short paths). This should represent a network when the swapping has > been running for a while, so we have quite good performance there. > > 2. For a number of steps (e.g. 10000) we introduce 5 nodes to the network > trying to fit their edges into the circle as in the original model. > These nodes randomize their initial locations. > In each step we let each node in the network initate on average 10 swap > attempts in the network (a 6-step random walk before asking the target > to swap). So if N=1000, then we try 10050 swaps in the network. > When this is done, the shortlived nodes are removed (and so are their > positions). I wonder how long 10 swap attempts take in practice. > > 3. We evaluate routing and distribution in the address range... > Some example plots are below: for N=1000 and N=5000 > > The values are chosen so that I believe the interval is short and > reasonable. Here we are able to count the number of evaluated swaps > and see what happens after then; instead of trying to simulate the > whole underlying swap/swaplock/delay mechanisms involved we study > the evolution of the system with respect to evaluated swaps. Seems sensible. > > Results (comments on the plots): > > For the 1000-node networks we can most clearly see the impact; the 5000-node > networks also seem to be on their way to prefer certain positions (the number > of introduced nodes/positions are the same here, thus we can expect it to take > more time for positions to propagate). A larger inflow (or longer time) is > needed for larger networks to degrade, that is quite natural. > > The preference for positions in certain parts of the keyspace not only seem > to depend on initial skewness when nodes randomize positions (randomizing > initial positions of nodes always leads to slight variations in densities > of positions taken on the circle, but there is no clear 1-1 relation, see > below for experiments to test this idea). > > Regarding if the /circle/ (not network) positions that are taken initially > (in 1.) by nodes affecting the outcome: experiments were also made over > initially *uniformly* distributed positions, which were then shuffled (to > have a totally uniform distribution of positions on the keyspace is done > by simply splitting the keyspace into N parts, and shuffling the positions > randomly instead of randomizing positions independently for nodes). > > More on efficiency of randomness to counter this soon... > > 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/20070820/00e6a49e/attachment.pgp>
