[router] Avoid re-processing peers when a score component decreases
authorMatt Corallo <git@bluematt.me>
Sat, 27 Mar 2021 16:49:42 +0000 (12:49 -0400)
committerMatt Corallo <git@bluematt.me>
Wed, 7 Apr 2021 01:41:45 +0000 (21:41 -0400)
commit0d7c316259b383ab5f374af619ab440ef93dd03b
tree125401e4e4dd2e8d2771361dbc92dc04da8fb7e2
parentc2cd8d4855c608132f9fe9bab41bb41aba7a5d74
[router] Avoid re-processing peers when a score component decreases

While walking the graph doing Dijkstra's, we may decrease the
amount being sent along one path, and not others, based on the
htlc_minimum_msat value. This may result in a lower relative fees
on that path in comparison to others. In the extreme, this may
result in finding a second path to a node with a lower fee than the
first path found (normally impossible in a Dijkstra's
implementation, as we walk next hops in fee-order).

In such a case, we end up with parts of our state invalid as
further hops beyond that node have been filled in using the
original total fee information.

Instead, we simply track which nodes have been processed and ignore
and further updates to them (as it implies we've reduced the amount
we're sending to find a lower absolute fee, but a higher relative
fee, which isn't a better route).

We check that we are in exactly this case in test builds with new
in-line assertions. Note that these assertions successfully detect
the bug in the previous commit.

Sadly this requires an extra HashMap lookup every time we pop an
element off of our heap, though we can skip a number of heap pushes
during the channel walking.
lightning/src/routing/router.rs