On Wednesday 06 June 2007 22:19, vive wrote: > On Wed, Jun 06, 2007 at 09:43:52PM +0100, Matthew Toseland wrote: > > X-Spam-Checker-Version: SpamAssassin 3.1.7-deb (2006-10-05) on > > emu.dh.bytemark.co.uk > > X-Spam-Level: > > X-Spam-Status: No, score=-106.9 required=5.0 tests=AWL,BAYES_00, > > FORGED_RCVD_HELO,USER_IN_WHITELIST autolearn=ham version=3.1.7-deb > > From: Matthew Toseland <toad at amphibian.dyndns.org> > > To: Discussion of development issues <devl at freenetproject.org> > > Date: Wed, 6 Jun 2007 21:43:52 +0100 > > Subject: Re: [freenet-dev] Getting stuck down rabbit holes > > > > 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. > > (*) 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. > > /vive -------------- 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/20070606/780901af/attachment.pgp>
