Consider existing in-flight HTLCs when routing

[TheBlueMatt]

lnd has a very long-standing bug where if you go to send a payment and it decides to split the payment, it may try to send both over the same channel, even if the channel does not have sufficient capacity to handle both parts. Instead, one part will be sent, and the other part will fail, leaving the payment to wait until the MPP times out. This is worse when paying an LDK client because of #1050. However, even on the sending side I believe we actually have the same bug. We should check for this and figure out how to handle this.

[jkczyz]

However, even on the sending side I believe we actually have the same bug. We should check for this and figure out how to handle this.

Is bookkept_channels_liquidity_available_msat (renamed in #1456 ) suppose to handles this?

rust-lightning/lightning/src/routing/router.rs

Line 823 in 342698f

let mut bookkept_channels_liquidity_available_msat = HashMap::with_capacity(network_nodes.len());

(cc: @jurvis)

[TheBlueMatt]

Yes, that handles it in the first route fetch, but we don't do any kind of bookkeeping across path retries. I'll be honest I'm not 100% sure what I was referring to here, but I think it was on retry, or certainly that would make sense.

[jkczyz]

@jurvis and I were chatting about this recently. IIUC, the problem can be more generally stated as accounting for known in-flight HTLCs across all our outstanding payments. Either way, the question may be how to keep track of this and what that means for the find_route / Router API.

One idea would be to track these in-flight HTLCs either separately or as part of the NetworkGraph. Perhaps the EventHandler implementation for NetworkGraph could manage this accounting. Thoughts?

[jkczyz]

One idea would be to track these in-flight HTLCs either separately or as part of the NetworkGraph. Perhaps the EventHandler implementation for NetworkGraph could manage this accounting. Thoughts?

Ah, but that would only be helpful for removing HTLCs which are no longer in flight. Adding them would require a mutable NetworkGraph. So maybe an auxiliary data structure would be needed.

Edit: Hmmm... such a data structure would need to be mutated when actually sending the payment (i.e., in ChannelManager). The coordination seems complicated. 🙁

[TheBlueMatt]

Yea it's really not clear to me what the right answer is here, I think naively the simplest approach is to store extra information in the InvoicePayer that can then be passed to find_route, some kind of in-flight tracking struct which can be efficiently queried for channel balance information.

[tnull]

I think an issue I encountered in #1526 is somewhat related: when calculating the minimum per-path value contribution, it would be nice to do this dynamically, i.e., allow a lower contribution for subsequent paths, if we have collected paths that contribute a good amount already. However, this is currently hard to do with the current logic in get_route, since at the time of collecting/checking paths we're not aware which other paths will end up in the final route. If we as of this issue would find a way to reliably track the state of all the MPP arms during routing, it may be worth having another look at this.

[tnull]

Closing as addressed in #1643.