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). (*) 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: 187 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20070606/f231b5d6/attachment.pgp>
