cjdelisle/cjdns — pull request #505 by Arceliar (2014-04-15 18:59:18+00:00)
Title: Patch from Testing (2/2): linkey

The second of the two patch sets from my testing branch.

This is less of a direct performance patch and more of a "moral" patch. It changes the interface used to update reach in the NodeStore.

1. Instead of updating reach for a node, we update reach for a path.
2. Instead of supplying a new reach value, we supply a time (in milliseconds) that a response took, or signal a timeout. The details of how this affects reach (and ideally, the fact that reach exists at all) remain hidden within the NodeStore.

In addition, the way reach gets updated on a response is slightly changed. We iterate over the nodes (that we know of) along the path, from beginning to end. If the new reach is both higher than the current reach for that node, and along the best path for that node, then we update the reach. At the end of the line, if we're on the best path for the final node, we update reach regardless of if it is higher or lower. This is meant to prevent nodes from updating the reach along the wrong path, and to handle potential bestParent updates for intermediate nodes (which could potentially be missed by not iterating this way).

Note to self: A lot of the internals of this are made more complicated (and arguably wrong) by the fact that reach is stored per node. Reach (or equivalently, latency) is really a property of a link, not a node. In principle, we should probably be storing it per link (or our best estimate, based on the difference in response time between adjacent nodes), so that we can update and calculate expected reach for every possible path. The node would then just store the best path and reach for easy lookup. Start working on this.