On Thursday 24 January 2008 19:42, Michael Rogers wrote: > Matthew Toseland wrote: > > Not in terms of predecessor samples afaics. The only new information we get is > > how many requests have survived this far. And beyond a certain distance that > > presumably just complicates the underlying signal (proportion of requests > > likely to come to me if X is the originator) ??? > > Good point! > > I guess the only remaining issue is branching - when we get a DNF/RNF > from a peer, do we (1) always return a DNF/RNF without trying any more > peers, or (2) toss the coin again before trying each peer?
Two different failure modes. RNF means we ran out of nodes, DNF means we ran out of HTL (randomly chose to end the request). > > It seems like (1) might be prone to getting stuck in rabbit holes, but It might yes, and that's something we need to deal with. The current algorithm is vulnerable to such problems. Per node failure tables would probably be a good solution: When we get a DNF, we don't route to that node the next time; if we're on a good network topology this won't matter very much, we'll get to the same cluster in the end, but on a bad topology, it will mean we avoid the whole subnetwork. > (2) might visit too many nodes. In fact I'm sure it will - once we send > a request to a peer it doesn't (and shouldn't) know whether it's the > first node ever to see that request. So the expected size of each branch > is equal to the expected size of the entire tree. I think that means the > expected size of the tree is infinite, which would make sense - the > depth of the tree is exponentially distributed, so the size of the tree > is Pareto distributed, and Pareto distributions can have finite or > infinite means depending on the parameters. So can we adjust the > parameters (depth and/or branching factor) to get a finite mean? Right, always retrying on a DNF, or even randomly retrying on a DNF, means we'll visit a ridiculous number of nodes. > > The size of the tree will be finite if each node has less than one child > on average, excluding loops. So if we try each peer with decreasing > probability, in such a way that the average number of peers tried > (excluding loops) is less than 1, then the number of nodes visited > should be finite. Hmmmm.... > > For example, we could try the first peer with probability 1-pDrop, the > second with probability pDrop*(1-pDrop), the third with probability > pDrop^2*(1-pDrop), etc, unless we get a RejectedLoop in which case we > move on without changing the probability. Firstly, why is this useful? Can't we just kill the request on getting a DNF, and route differently next time? Secondly, lets look at this... When we receive a request, we have a pDrop chance of killing it at that point. If we don't, we route it. If a node gives us RejectedLoop, we move on; if a node gives us a RejectedOverload, we evaluate pDrop again (we don't want to keep searching for a non-overloaded node forever, do we?). If we get a RouteNotFound, we evaluate pDrop again and continue. If we get a DataNotFound, we drop the request unless random(1.0) < pDrop. We move on to the next node, and if that also gives us a DataNotFound, we do the same. So the probability of trying at least one peer is 1-pDrop, the probability of trying at least two peers is pDrop*(1-pDrop), a third is pDrop^2*(1-pDrop) ... (if we assume that almost all requests we do give DNFs). > > Cheers, > Michael -------------- 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/20080124/dd3e4117/attachment.pgp>
