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.
