On Tuesday 05 February 2008 19:05, Robert Hailey wrote: > > On Feb 4, 2008, at 7:24 PM, Michael Rogers wrote: > > > Matthew Toseland wrote: > >> Swapping creates this problem. Or does it? Could you perhaps do > >> some simulations of two networks of different sizes weakly linked > >> and show whether they get independant location spaces, or whether > >> swapping tries to put one of them within the global keyspace for > >> the other? > > > > Here's a quick simulation that shows that two weakly-connected > > subnets move into separate regions of the key space. Each subnet has > > an ideal Kleinberg topology and starts out uniformly distributed > > across the whole key space, and there are also a few random links > > between the subnets - this is meant to represent what would happen > > if you created a few links between two mature networks, or between a > > real network and a Sybil network. > > > > I couldn't be bothered to do a nice GUI so the output is just a > > series of histograms: on each line the key space is divided into 20 > > regions, and each column shows the number of nodes from the first > > subnet in that region. Initially there are roughly 50 nodes in each > > region, but swapping causes the subnets to segregate so that > > eventually most regions are almost exclusively occupied by one > > subnet or the other. > > > > It's kind of interesting to compare this with "white flight" in > > sociology... > > > > Cheers, > > Michael > > For a "quick simulation", I think this is an excellent demonstration! > However, I think that there are two major errors. > > First, there is an equal chance of nodes from either network swapping. > In the freenet network (since swapping is done through the network) it > is not equal (if for no other cause than the scarce links between the > two networks). More on this below.
His simulation doesn't deal with this? There are two mechanisms that would limit it: - The limit on swaps per second per link. We won't accept a swap request if we've had one within the last 900ms. However, this may be too lenient a limit, we could increase it. - Swaps are routed as random possibly looping walks. > > Second, it looks like you forgot to actually make any connections > between the two networks; without the stress points (plus the fact of > equal weighting on swaps), it is no wonder the nodes flee so quickly! > > Once I added the joins to the two networks on your sim, I noticed that > the networks would "bunchup", but not split the keyspace. However, I'm > not sure the lack-of-keyspace-split helps either side of the argument > as these swaps are are applied to stable/mature networks to begin > with. What this demonstrates is more the merging of two large networks > (e.g. freenet-china and freenet-usa finally get linked up), and that > they maintain there keyspace. Define "bunchup" ? This is IMHO a very significant result: - Link-based swap pressure causes the two networks to keep their own separate keyspaces. - Local requests will still function 99% of the time. - Exceptionally popular keys will eventually be routed to the other network, and with ULPRs will probably be propagated widely across the original network once found. - It is not a viable attack to dangle a large virtual network off a few connections. Unfortunately there are other viable attacks on swapping (read the Pitch Black paper, last year somebody appears to have deployed it with considerable success although some of our problems were certainly due to churn). - An escape-route mechanism may be interesting, however given the limited capacity it may be simplest to just rely on chance and ULPRs propagating the most sought after content? The problem with this is those few requests which cross the border will probably have low HTL when they get there, so if the content isn't popular on the other side it might not be found. So maybe we do need some sort of mechanism - but we will need a way to ration the scarce resources according to popularity. > > Speculating about the swap probability... > > ASSUMING that the keyspace would be split (i.e. as the networks grow > up together) [which I still don't think is the case], What happens as we get more and more links between the networks? Catastrophic merging? What about a few high capacity links? Etc.. more work can be done here. > then as the > probability of swapping becomes equal the two networks occupy the same > key space (as Michael's supplied simulator). However, surely as the > probability of swapping (between the two networks) approaches zero > they overlap the keyspace. Actually, it is well before zero... > logically it is that small probability of randomizing the location > after the swap (new locations entering the network at the same rate > they leave). > > I've quite enjoyed playing around with this, particularly tracking > particular nodes in the network to see if I could catch the two > networks rotating to match each other, but also varying probabilities > of swaps across the networks. -------------- 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/devl/attachments/20080205/d32c3666/attachment.pgp>
