Finding an alternate route in case of an 'insufficient amount' somewhere in the path

[pm47]

Consider this setup:

A 2-----0 B 2-----0 C 0-----2 D 
                    2         0
                    |         |
                    |         |
                    0         2
                    E 2-----0 F

If A wants to pay D 1 BTC, a simple Dijsktra will return the route A-B-C-D, but only the route A-B-C-E-F-D would work. I believe this kind of scenario could be pretty common until we use dual-funded channels, and assuming that typical_htlc_amount << typical_channel_capacity might not be enough.

We don't currently advertise the amount a node is willing to forward to an outgoing channel. This could have been done by adding a field in the channel_update message, and would have allowed us to easily filter out channels a priori when calculating a route, but IIRC we discarded this possibility for privacy reasons.

The other way I think could be to filter out channels a posteriori by adding a specific error code in BOLT 4, but there isn't any. Is that on purpose?

[Roasbeef]

IIRC we discarded this possibility for privacy reasons.

IMO the impact to network wide bandwidth implications of such a change are a far greater deterrent.

If A wants to pay D 1 BTC, a simple Dijsktra will return the route A-B-C-D, but only the route A-B-C-E-F-D would work.

The solution here is to use a proper path finding algorithm, such as Yen's Algorithm. All route selection should be multi-path, falling back to lower ranked routes in the case of payment failure occurring when attempting to use a higher ranked path.

I believe this kind of scenario could be pretty common until we use dual-funded channels

Such conditions can still arise regardless of if channels are dual-funded or not (also remember we have the push amount currently).

[pm47]

The solution here is to use a proper path finding algorithm, such as Yen's Algorithm. All route selection should be multi-path, falling back to lower ranked routes in the case of payment failure occurring when attempting to use a higher ranked path.

Yes, that's what I meant by filtering out channels a posteriori, I am fine with that. I didn't know this particular algorithm though, thanks for the link!

Reading the spec more carefully, I think the error code I was looking for is temporary_channel_failure (channel capacity reached). There is no need to be more specific, so this is an non-issue!

Cheers, Pierre

[akumaigorodski]

FWIW my current plan is precisely to return up to 8 shortest paths to a client. I'm using a modified AllDirectedPaths from jgrapht: https://github.com/btcontract/lncloud/blob/master/src/main/java/com/btcontract/lncloud/CachedAllDirectedPaths.java It's performance is comparable to a single path Dijsktra plus it caches data such that any subsequent call for the same target from any destination saves a lot of computation.