Improvement to payment splitting algorithm

[t-bast]

The splitting algorithm biases too much towards good routes, regardless of capacity.
We first find routes, keep the N bests and then adjust capacity.

But it may end up using only routes with the same first hop, whereas the first link doesn't have enough capacity for the whole payment, and we discarded routes with a different first hop in the first phase.

We need to somehow incorporate in Yen's algorithm information about the amounts already used up by previous routes found.

Here is a pathological example:

      M1 channels with fee>0   +-----+   M2 channels with fee>0 
    +------------------------> | Bob | ---------------------------------------+
    |                          +-----+                                        |
    |                                                                         |
    |                                                                         |
    |                                                                         v
+--------+   N1 channels with fee=0   +-----+   N2 channels with fee=0   +-----------+
| Sender | -------------------------> | HUB | -------------------------> | Recipient |
+--------+                            +-----+                            +-----------+

If all the channels between HUB and Recipient are depleted (empty on HUB's side) the payment will fail, because the current algorithm will return only routes that go through HUB (if there are a lot of matching channels with very competitive fees there).

It's a tricky case, because the sender doesn't know the liquidity between HUB and Recipient, and if there was some liquidity available, this would be the best route (so it's correct to try it). Maybe the second payment attempt (if the first one fails) should exclude HUB?

[renepickhardt]

Sorry I missed to add this issue in my recent mail to lightning dev as I somehow overlooked this issue despite looking specifically for something like that.

The splitting algorithm biases too much towards good routes, regardless of capacity. We first find routes, keep the N bests and then adjust capacity.

Adopting the optimization problem of finding paths with liquidity given the uncertainty of liquidity in channels can easily be achieved by adding the probabilistic model for the uncertainty to the scoring function in you algorithm. This has been explained here and was included in ldk and in c-lightning who also tested the improved routing abilities of that approach. Note that the c-lightning version was a very boiled down version which is basically a one line change but according to their benchmark lead roughly a 50% faster time for payment delivery, 50% fewer attempts to send onions and 50% lower failure rate.

But it may end up using only routes with the same first hop, whereas the first link doesn't have enough capacity for the whole payment, and we discarded routes with a different first hop in the first phase.

I explain why this problem is fundamentally tricky to solve.
That is why it makes sense to additionally study the global optimization problem as described here and a good approximation to the solution can be found quickly. A java version (that can probably very easily be transferred to scala) is being worked on at lnd-manageJ and Carsten has reported a runtime of 230 ms. Also in the LDK repo I gave some pointers to libraries and stand alone implementations of that algorithm.

We need to somehow incorporate in Yen's algorithm information about the amounts already used up by previous routes found.

I don't think you will be happy on the long term to use Yen's algorithm as that is just a very poor approximation of the splitting problem which maps 1 to 1 to a min cost flow problem which as stated above is solvable and can in particular be approximated quickly and good enough for our setting in the lightning network.

It's a tricky case, because the sender doesn't know the liquidity between HUB and Recipient, and if there was some liquidity available, this would be the best route (so it's correct to try it). Maybe the second payment attempt (if the first one fails) should exclude HUB?

Of course it makes sense within a session to update the prior probabilities that encode the uncertainty about the liquidity by switching to the conditional probabilities. I explained this in a sophisticated mathematical way in the frist and more concretely in the second paper, then again [for hackers]](lightningdevkit/rust-lightning#1170 (comment)) and on the c-lightning repo in a TL;DR. Last but not least you can study the code of LDK who integrated it.

Obviously I cannot tell you what to do but after I studied these problems for three years all the solutions to this issue are available on a silver platter. I guess it will probably take you less than a day to have a prototype included into your software and benchmark it against all that you have tried so far. So I can only encourage you to give it a try. In any case feel free to ask me anything if you need help.

[renepickhardt]

While I was mainly looking for a way to reasonably plan redundant overpayments I found a rather practical way to split payments in an ad-hoc way:

https://github.com/renepickhardt/Maximum-Expected-Value-Flows-For-Redundant-Overpayments/blob/main/code/A%20Collection%20of%20Probabilistic%20Channel%20Models%20for%20Augmenting%20Maximum%20Expected%20Value%20Paths.ipynb

The actual algorithm is currently in section 2.2 of the notebook in cell 24 and can be roughly summerized via this pseudo code:

while total_ev < amount:
    candidate_path = shortest_path(G,SRC,DEST,weight="some_cost_function")
    ev, amt = candidate_path.maximize_expected_value()
    allocate_sats(candidate_path, amount)
    update_cost_function(G,candidate_path,amount)
    total_ev += ev

The nice thing of this approach is that we seperate the problem of selecting a candidate path and allocating liquidity along that path in a way that the expected delivered amount is maximized (depending on our probabilistic model for the liquidity in remote channels)

As long as we don't have redundant overpayments one has to to change the condition in the while statement with total_amount instead of total_ev