Remove pathfinding probability floor

[joostjager]

Currently in pathfinding there is a minimum route success probability below which a route isn't considered. The current default min_probability is set at 1%.

The original goal of this limit is to make sure that the payment lifecycle terminates. Otherwise it would always run until the timeout. Even if there is just a single route that failed, it would be retried over an over regardless of how unlikely it is that the next attempt will be different. Temporary channel failures do resolve, so it wouldn't be entirely useless. But in the vast majority of cases, it would result in bad ux with negligible benefit.

There are however issues with the minimum probability limit:

• If there are many different routes to a destination and/or the minimum probability is low and/or the failure half life time is short, the success probabilities of a route after failure may have recovered enough already to be retried within the same payment lifecycle. In that case, the endless loop isn't prevented. It is not clear to a user of lnd how to set the parameters such that this doesn't happen, and it is probably impossible to set it to be always correct anyway.
• The probability estimation algorithm is non-trivial. For example, it factors in the history of other channels of a node too. The resulting probabilities are a rough educated guess and probably far from the true probability. Useful for guiding pathfinding, but not necessarily reliable enough to be used in the definition of a stopping criterium. What can happen is that a payment is failed early, even though there are still promising but mis-estimated routes left. Some operators intentionally set the min probability setting to a much lower value than 1%, to be sure that the set of options is fully exhausted.
• A payment may fail without a single attempt being made if there are no routes that reach min_probability. I think a user would expect at least something to happen, regardless of whether there were recent failures on that route.

Overall it seems that min_probability isn't the best solution. In this issue I'd like to propose the following alternative:

• Remove min_probability.
• Track on a per-payment basis the set of channels that have failed and exclude those from pathfinding.
• Stop when no routes can be found anymore.

This probably leads to more attempts being made before stopping, but not as many as when min_probability is set to a tiny value (effectively disabling the stopping condition).

The change would also take down a hurdle for removing the "second chance logic" #6883 (comment), which has benefits of its own.

[lightninglabs-deploy]

Consolidating related issue here. The following has been closed as a duplicate:

• [router] Validate invalid combinations of routerrpc settings #6553 — Reports that certain combinations of routerrpc settings cause pathfinding to search endlessly, consuming all available memory. Specific problematic config: minrtprob=0.4, apriorihopprob=0.5, aprioriweight=0. The min route probability of 40% combined with a priori weight of 0 causes no routes to be found, leading to infinite search. Requests validation of invalid setting combinations. Originally reported via Loop out causing OOM kill in LND lightninglabs/loop#491.