Re: Shortlived nodes: the route to position clustering?

Not sure I understand your graphs. What is N1000_initial vs 
N1000_shuffled_initial? If it's an idealised kleinberg, it should be flat, 
no?

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.
> 
> 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
>

_______________________________________________
Tech mailing list
[email protected]
http://emu.freenetproject.org/cgi-bin/mailman/listinfo/tech

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQBGyfSKA9rUluQ9pFARAnpPAKCE3/alP744/DanHo+AMSoj6CadnACgqJok
tA0AIY5gKibrWTMFD0QChYA=
=aCJD
-----END PGP SIGNATURE-----