[freenet-dev] Getting stuck down rabbit holes

[Matthew Toseland]

Recent probe data suggests a theory:

Parts of the network are "rabbit holes" or "dungeons", i.e. sub-networks which 
are only weakly connected to the larger network. These cover a small chunk of 
the keyspace, say 0.36-0.41 (roughly, in the trace I had). A request for 0.5 
got stuck down the rabbit hole. The gateway node at 0.436 was backed off; if 
the request had been able to reach that node, it would have been able to get 
much closer to where it should be. So the request bounced around in the 
dungeon, and eventually DNFed.

What we need is some backtracking. At the moment backtracking only occurs when 
we actually run out of nodes in a pocket i.e. when it is really small. We 
track the best location seen so far on the request (not including dead ends 
i.e. RNFs), and whenever this improves we reset the HTL back to the maximum 
(10); otherwise it is decremented.

It wasn't always this way. What we did at the beginning of 0.7 was 
this: Limit the number of linear hops (HTL) to 10. Only route to a node 
closer to the target than we are (actually I think it was only route to a 
node closer than the best-so-far). The problem with this approach is we'd 
tend to dance around at the beginning, looking for a route, wasting all our 
HTL. So we changed it to the above algorithm. Which does have the advantage 
that we won't run out of hops if we are actually getting closer to the 
target, and we'll have a few hops left over after we reach the best node to 
look around in case there have been short range network changes. The problem 
is, it gets stuck down rabbit holes, because there is essentially no 
backtracking (unless the network is really small).

Both approaches are wrong. But we can have the best of both worlds:
- The first time on a new node, we always route to the closest node to the 
target, even if it is further away from the target than the best-so-far and 
than this node is. Because the following hop will often be better.
- When we go say 4 hops without advancing (without best-so-far improving), 
backtrack to the previous node with something like a DNF.
- This may include the new best-so-far location if any.
- After a DNF, we will try other nodes, but only if they are closer to the 
target than the node which is rerouting is (or the previous best-so-far if 
this node was the best-so-far when first entered).
- A normal completion will not cause very much backtracking, because we keep 
the new best-so-far, and many nodes we would visit we have already visited 
(because of the triangles property, and this does seem to happen in 
practice). Having said that, there will be some forking on the way back.

"Fork if closer than this node" is better than "fork if closer than the best 
so far" in simulations on a related project, although there are some 
differences.

Note that dungeons are IMHO inevitable on a true darknet. Also, this should 
not generally increase the linear path length along which data is returned. 
We can probably afford the extra hops since we're not sending data down them. 
One worry is that inserts would send data to all the nodes; we should 
probably limit this. We might also want to have a total nodes visited count, 
with a maximum.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://emu.freenetproject.org/pipermail/devl/attachments/20070606/a29dd3f7/attachment.pgp