Important detail: On a DNF, we accept the DNF's list of best-so-far-not-visited locations, but we limit the number of forks to say 2. Thus we limit the possible damage caused by a node deliberately returning locations far away from the target.
On Thursday 07 June 2007 09:44, vive wrote: > On Wed, Jun 06, 2007 at 11:44:32PM +0100, Matthew Toseland wrote: > > On Wednesday 06 June 2007 22:19, vive wrote: > > > On Wed, Jun 06, 2007 at 09:43:52PM +0100, Matthew Toseland wrote: > > > > After a long discussion with vivee, new proposal: > > > > On a request, we should, in addition to HTL and best-so-far, track > > > > the 3 best locations of nodes we have seen, could have visited, but > > > > haven't. > > > > > > > > When we run out of HTL, this indicates that we are either a) lost in > > > > a pocket, or b) have actually reached the end of the request. We send > > > > a DataNotFound to our previous node, just as now. But the previous > > > > node can fork a request - provided that the node it would fork to is > > > > at least as close to the target than the 3rd-best not visited node. > > > > It could be one of the nodes we didn't visit, or it could be a new > > > > option because a node came out of swapping. > > > > > > Part of the idea to store the 3 best positions seen-so-far but not > > > *visited* (by the query taking greedy routing) is also to have 3 > > > chances of backtracking and continue at a good place (instead of just > > > backtracking and forking to a best-possible neighbor at a node as soon > > > as possible). > > > > > > If the backtrack does not hit a node with a neighbor closer than the > > > 3rd best position seen, then we backtrack until the query first reaches > > > any(*) of the 3 nodes that had the closest neighbors-seen-so-far. From > > > this node the query can continue to the neighbor that was not > > > previously visited (2nd-best for greedy routing, and next step should > > > have higher chances of leading to the destination). > > > > I don't see why we need this special case: We can simply fork if the fork > > is at least as closer to the target as the 3rd-best. This will normally > > result in 3 forks but it might be more or it might be less. > > What if a node that _seemed_ to be a good option has swapped position since > then? Lets say we use the rule of comparing positions against the 3rd best > seen. During backtracking we will no longer see that fork as a good one, > but we know it seemed so recently (perhaps it was even better than the path > selected, but a node could not receive traffic due to congestion or so). > That information may also be used - even if its not strictly up to date. > > One way to extend the rule of comparing positions would be to also attempt > querying in these directions that seemed good previously. But I agree on > that it's not necessary, only comparing positions may be the first way to > go and see how well it works. > > > > (*) If we take the first one encountered out of these three, then we > > > dont have to "un-backtrack" (e.g. go down the branch again that we > > > backtracked up from in the first case) if the query reaches *another* > > > dead end :-) > > > > > > > This should severely limit the amount of forking that happens after a > > > > normal completion, while still enabling us to backtrack our way out > > > > of rabbit holes. > > _______________________________________________ > Devl mailing list > Devl at freenetproject.org > http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl -------------- 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/20070608/bee16961/attachment.pgp>
