Attached is a probe trace to support the below conclusions.
On Wednesday 06 June 2007 19:11, Matthew Toseland wrote: > 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: trace.txt.zip Type: application/x-zip Size: 2442 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20070607/5cd21153/attachment.bin> -------------- 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/20070607/5cd21153/attachment.pgp>
