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. 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). 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. 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: N1000_initial.jpg Type: image/jpeg Size: 21997 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20070820/5a94ba5f/attachment.jpg> -------------- next part -------------- A non-text attachment was scrubbed... Name: N1000_inflow.jpg Type: image/jpeg Size: 24762 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20070820/5a94ba5f/attachment-0001.jpg> -------------- next part -------------- A non-text attachment was scrubbed... Name: N1000_after.jpg Type: image/jpeg Size: 25856 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20070820/5a94ba5f/attachment-0002.jpg> -------------- next part -------------- A non-text attachment was scrubbed... Name: N1000_shuffled_initial.jpg Type: image/jpeg Size: 20036 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20070820/5a94ba5f/attachment-0003.jpg> -------------- next part -------------- A non-text attachment was scrubbed... Name: N1000_shuffled_inflow.jpg Type: image/jpeg Size: 24560 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20070820/5a94ba5f/attachment-0004.jpg> -------------- next part -------------- A non-text attachment was scrubbed... Name: N1000_shuffled_after.jpg Type: image/jpeg Size: 25994 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20070820/5a94ba5f/attachment-0005.jpg>
