[freenet-dev] Getting stuck down rabbit holes

[vive]

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 : http://emu.freenetproject.org/pipermail/devl/attachments/20070606/f231b5d6/attachment.pgp