Here are some experiments on running the swapping algorithm with periodic randomization of node positions. The idea is to study measures against position clustering, and later on what can be made to counter attacks against the swap algorithm. No attacks have been simulated yet, this is the pure impact of randomizing positions on the swapping algorithm.
The network size was fixed to 10000 nodes, HTL to 100, and the average degree was varied. Each run a network was initiated as the Kleinberg model, measured by routing a while on it, and then positions were uniformly randomly assigned between 0 and 1 before staring the swapping algorithm to recover the efficient routing. The major thing to study was the frequency of randomizing the position. One run was evaluated for each different frequency X. Randomizing frequency X was used as follows: each node randomizes its location each X'th swap that goes out from that node. To avoid cyclic behaviour (at least of the simple case, perhaps this needs to be extended) each nodes counter for doing this is initialized independenty between 0 and X before starting the simulations. Lets say a node randomly initalizes its counter to y (between 0 and X), then it will randomize its location on the swap y,y+X,y+2X,y+3X... that starts from it with a random walk (of length 6). This is an easy way to let a node stay with a location for a while (unless swapping) and to let the neighbors route through it before randomizing again. X=0 corresponds to not randomizing at all. Discussing the results: There seems to be room for running a low-frequent randomization to begin with. For one case (average degree=10) it even seems to perform better in some cases with randomization with a quite large period (this surely depends on that randomization can help the algorithm get out of some suboptimal configurations). This does not seem to happen for a larger average degree, perhaps because each randomization will have impact on more links (but that is no controlled answer, just speculation at the moment). Another note: how quickly the algorithm improves the network from the entirely randomized state is not of foremost interest here, the interesting thing is what happens when the network is rather stable from swapping for a long period. Therefore its the resulting level (on the right sides of the plots) that are important, but the levels seem to have settled around some performance (I will rerun the first simulation again to see how pure swapping without no randmization behaves in a longer run) Finally, we dont know if the observed behaviour here will be the same in the current Freenet topology (since the efficiency of the swapping algorithm depends on how much the topology deviates from the Kleinberg model in the first case). Therefore any implementation attempt should be using defensively low periods of randomization. regards, /Vilhelm -------------- next part -------------- A non-text attachment was scrubbed... Name: D10_pathlens.jpg Type: image/jpeg Size: 29790 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20070814/7b793913/attachment.jpg> -------------- next part -------------- A non-text attachment was scrubbed... Name: D10_succrate.jpg Type: image/jpeg Size: 30552 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20070814/7b793913/attachment-0001.jpg> -------------- next part -------------- A non-text attachment was scrubbed... Name: D20_pathlens.jpg Type: image/jpeg Size: 30032 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20070814/7b793913/attachment-0002.jpg> -------------- next part -------------- A non-text attachment was scrubbed... Name: D20_succrate.jpg Type: image/jpeg Size: 30457 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20070814/7b793913/attachment-0003.jpg> -------------- next part -------------- A non-text attachment was scrubbed... Name: not available Type: application/pgp-signature Size: 187 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20070814/7b793913/attachment.pgp>
