Calculate a new penalty based on historical channel liquidity range
authorMatt Corallo <git@bluematt.me>
Thu, 21 Jul 2022 02:08:28 +0000 (02:08 +0000)
committerMatt Corallo <git@bluematt.me>
Thu, 6 Oct 2022 21:10:23 +0000 (21:10 +0000)
commit6852ea974178c60211a37d4558c14678889a2932
tree474ee506ecbdf579382178934123b00847ec3e12
parentc5eab6e11f050c7f049b3bfaac35d35bcf5b751a
Calculate a new penalty based on historical channel liquidity range

Our current `ProbabilisticScorer` attempts to build a model of the
current liquidity across the payment channel network. This works
fine to ignore channels we *just* tried to pay through, but it
fails to remember patterns over longer time horizons.

Specifically, there are *many* channels within the network that are
very often either fully saturated in one direction, or are
regularly rebalanced and rarely saturated. While our model may
discover that, when it decays its offsets or if there is a
temporary change in liquidity, it effectively forgets the "normal"
state of the channel.

This causes substantially suboptimal routing in practice, and
avoiding discarding older knowledge when new datapoints come in is
a potential solution to this.

Here, we implement one such design, using the decaying buckets
added in the previous commit to calculate a probability of payment
success based on a weighted average of recent liquidity estimates
for a channel.

For each min/max liquidity bucket pair (where the min liquidity is
less than the max liquidity), we can calculate the probability that
a payment succeeds using our traditional `amount / capacity`
formula. From there, we weigh the probability by the number of
points in each bucket pair, calculating a total probability for the
payment, and assigning a penalty using the same log-probability
calculation used for the non-historical penalties.
lightning/src/routing/scoring.rs