On Tue, Dec 23, 2008 at 12:48:04PM +0000, Matthew Toseland wrote: > > 2. Data availability: the success rate and the number of steps in > > successful > routes (here: the roundtrip steps) that is seen in simulation. > > > > The simulation: this was made by joining both ideal (generated) social > networks as well as networks from actual datasets on social networks (the pgp > WoT). Both are navigable networks, although slighly differing. It is hoped > that this can correspond roughly to the scenario above, by joining these > networks with different numbers of random connections. > > > > Simulation: > > 0. Load the two networks, each of size 4000. All nodes are set to be pure > darknet. > > 1. Connect the networks by joining pairs of random nodes, where one node is > picked from each network. I tried this with a cut of 10,100,1000,10000 links. > > 2. Nodes randomize their positions and swap for a while to stabilize the > locations (successful swaps get more uncommon after this) to start from > a "stable" state > > 3. 1000 keys are inserted by random nodes into the network (both sink and > cache). Nodes have a store of 50 keys and a cache of 50 keys. Both are LRU as > normal. > > Actually we use pseudo-random replacement now. This probably doesn't strongly > affect the results. > > > 4. The main phase: nodes swap positions when they can, and request data for > a longer interval. (At the moment no new inserts nor churn, this can be the > next thing to simulate, but need data input, see below.) The goal is to see > what the data availability is, and how the positions have got affected after > some time. Nodes request for data via keys that have different popularity: a > standard Zipf distribution is used over the keys. The parameter is also > varied in the simulations. I have typially let the 4000 nodes do in total > 100000 requests and evaluated how that went. It could clearly be evaluated > over longer time, but how long is reasonable? > > 5. Evaluate the two measures above (variation distance always starts close > to 0 when one initially randomizes) > > > The real world case most interesting to me is that of two darknets slowly > merging. Does this result in a severe drop in performance in the short run? > Hence, an important measurement is the success rate for requests made on the > same side of the border as the data was inserted on. Is this dramatically > lower with a smaller cut? How does it compare to that darknet running on its > own?
Hi! I did some simulations of this. See the attached plots. The model here is as described previously, but it tracks data and keys with respect to which part of the network they were originally inserted. Routes where nodes query for keys that were originally inserted in the same network part are labelled "short routes", otherwise "long routes" when they search for keys inserted in the other part. The impact of this varies depending on the size of the cut and how popular certain keys are. The plots illustrate both these dependencies. The simulations show at least two things regarding to the previous fear. First, connecting two darknets loosely does not seem to break routing that much within a darknet, but shields the nodes off from data inserted in the other network. (And data is at least slowly made data available again. This is not very surprising, but here are the simulations showing some impact.) Second, real-world networks seem to be slightly better (than fair models where all nodes get the same number of connections) at making data available via long routes. This is seen by comparing the two plots where the zipf parameter is varied. The last effect is probably due to of a different degree distribution than the ideal model (then, a few high-degree nodes naturally see more queries passing through, quickly making remote data available for more nodes in their own network). Note: the simulations are still without churn and opennet. The plan is to involve these things next, but adding it is just likely to slow things down rather than changing any of the patterns qualitatively. This is why these simple simulations are justfied in the first place. Note 2: the simulations were not averaged over many runs, but the patterns clear. The result for zipfparam 1.5 in the first plot is certainly going to be averaged out (there is a good theoretical reason this may happen in some of the simulations). Cheers, /vive -------------- next part -------------- A non-text attachment was scrubbed... Name: Kleinberg_cut100_varzipf.png Type: image/png Size: 58357 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20090105/bba6db60/attachment.png> -------------- next part -------------- A non-text attachment was scrubbed... Name: PGPWoT_cut100_varzipf.png Type: image/png Size: 63553 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20090105/bba6db60/attachment-0001.png> -------------- next part -------------- A non-text attachment was scrubbed... Name: Kleinberg_zipf1_varcut.png Type: image/png Size: 59732 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20090105/bba6db60/attachment-0002.png> -------------- next part -------------- A non-text attachment was scrubbed... Name: PGPWoT_zipf1_varcut.png Type: image/png Size: 64405 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20090105/bba6db60/attachment-0003.png> -------------- next part -------------- A non-text attachment was scrubbed... Name: not available Type: application/pgp-signature Size: 195 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20090105/bba6db60/attachment.pgp>
