On Mon, Aug 20, 2007 at 01:19:29PM +0100, Michael Rogers wrote: > vive wrote: > > That doesn't follow just because its probabilistic. This depends on > > simulations mostly not using the deterministic component of the > > Kleinberg model: the nearest-neighbor connections, which is unreasonable > > to assume for Freenet. So the greedy routing isn't able to strictly > > approach its target, having to deal with dead ends. > > Agreed, we will always be dealing with an approximation. The question > is, if we use the current locations to calculate the connection > probabilities when replacing a node, will the resulting graph be a > better or worse approximation?
Routing for certain parts of the keyspace will work less good, yes. Routing between specific nodes still works quite well (so far as I've seen). > Here's a thought experiment: take a Kleinberg network and shuffle the > locations. Then replace the nodes one by one with new nodes, using the > current locations to calculate the connection probabilities. When all > the nodes have been replaced, don't you have a Kleinberg network again? I claim you don't. It will be more alike a random graph. But indeed, if you think so then try to simulate it. :) This does not work because (IMHO) you confuse location on the circle with location in the network. Kleinbergs model gives efficient greedy routing since there is a good balance between #connections going to different parts of the graph. But something similar that is exactly how I've been doing it: for a number of steps add a small fraction of nodes. These new nodes randomize their positions after getting links according to distribution on the "original" locations in the topology. Then all nodes in the network swap for a while, and then these new nodes leave again. The topology is still the same, but the positions taken by nodes left in the network may have changed since nodes that leave bring out some of the positions.. This scenario corresponds roughly to many nodes that are alive in the network and a small flow through of positions by nodes joining but decide to leave for good. Some results soon... > > You're right, we can use the inversely proportional distribution to add > > the edges. But lets say we have shuffled the positions randomly. Do you > > think this will help us to get a navigable network when we have added > > enough of nodes? I claim this is not the same thing. > > I see your point: if we use the shuffled locations it's equivalent to > choosing the neighbours uniformly at random, which will make the network > less navigable using the old locations. But at the same time, we're > adding links that will be navigable using the new locations. Eventually > the old network will be entirely replaced and the old locations will > become irrelevant - the network will become navigable again through > churn, even without swapping. No, I dont think it will become navigable easy enough. My point with the experiment was: even if we dont shuffle positions then it will still degrade the network if too many nodes are added. > > To clarify what I mean, I performed some experiments on this in the > > "ideal model", no position randomizing. Edges were selected as in the > > Kleinberg model, evaluation was over 100000 routes with HTL=100. > > > > 1) Starting with 1000 nodes, average degree=10 > > Result: N=1000,succrate=0.996,avglen=8.261 > > > > 2) Starting with 1000 nodes, average degree=10. Then we add 1000 nodes to > > random places on the circle (growing it to 2000 positions) with avgdeg=10 > > Result: N=2000,succrate=0.557,avglen=13.455 > > > > 3) Starting with 2000 nodes, average degree=10 > > Result: N=2000,succrate=0.993,avglen=10.103 > > Those are interesting results, but a single influx of 1000 nodes is not > the same as continuously replacing nodes. There are disproportionately > many connections between the older nodes, because their connection > probabilites were calculated when the network was smaller. However, if > you replace nodes one at a time so the size of the network stays > constant, the new node's connection probabilities will be identical to > those of the node it replaces, so it seems to me that you won't deviate > from the model, you'll just move from one instantiation of the model to > another. Yes, if you dont shuffle anything and just replace nodes then you will move between instantiations if you use the original positions. This is not the same as adding edges based on the current /positions/ that nodes take after randomizing and swapping on the circle. > > to be in the /whole/ network is a different thing than joining nodes later > > on > > and adding these /as/ the Kleinberg model. > > But when you construct a Kleinberg network you *don't* consider the > links in the whole network. That's why I keep talking about > independence. It's not like preferential attachment, where the location > of new links depends on the location of existing links; each link is > created independently, so it doesn't matter what order you create them in. I understand what you mean, but to let nodes use other node locations on the /circle/ to base their decisions on who in the /network/ to link to, then the other node locations need to reflect the network. This is not preserved when randomizing, and swapping can only bring it back to an approximation. If you dont agree on this yet then try to check Oskars paper instead of debating this with me, and you'll see this difference there. > I agree that the Kleinberg model doesn't apply to growing graphs, but > churn isn't the same as growth. Agreed on that, this is why the simulation strategy (above) should be able to say something about the effect on churn.. regards, Vilhelm -------------- 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/20070820/da1e78a3/attachment.pgp>
