[feature]: Proposal for a different cutoff between InboundFee and OutboundFee in pathfinding

[feelancer21]

Is your feature request related to a problem? Please describe.

I am picking up a topic that I already mentioned in #8940. In the course of #6934, a split for the total channel fees was implemented. The current cutoff results in not always finding the optimal route as mentioned here.
#6934 (review)

Here is another example from the perspective of a sender A, who can send a payment to D either through B or C.
A-[out fee 0 msat | in fee -100 msat]-B-[out 150 msat | in fee 0]-D
and
A-[out fee 0 msat | in fee 0 msat]-C-[out 100 msat | in fee 0]-D

Since the out_fee in the outgoing channels of a source is always counted as 0, the incoming fee on this channel is completely absorbed by the current cutoff, and both source channels are considered with a weight of 0 in the pathfinding (ignoring the timelock penalty). The optimal solution is determined based on the second channel, and the result is the more expensive second route (about 50ppm). This is even though the success probability of the second route could be lower.
However, if a fee_limit of 75ppm is set, the first route will be found at least after the fix of #8940.

Describe the solution you'd like

In my opinion, this behavior can be addressed if we do not base the calculation on the total channel fee, but measure the distance from the fromVertex to the target without considering the outbound fee of the fromVertex. Instead calculating thefee with

lnd/routing/pathfind.go

Lines 805 to 809 in b7c59b3

	signedFee := inboundFee + outboundFee
	fee := lnwire.MilliSatoshi(0)
	if signedFee > 0 {
	fee = lnwire.MilliSatoshi(signedFee)
	}

it should be calculated with fee := toNodeDist.outboundFee + inboundFee, which cannot become negative due to the construction of the inboundFee. The outbound fee of the source would be disregarded, which is unproblematic since it is currently counted as 0. Moreover, the individual fee components would add up to the totalFee again after merging #8941.

In the end, the proposal is nothing more than shifting the measurement point of the distance from the point between the involved edges to the middle of the outgoing edge of the fromVertex. Intuitively, I would even argue that we find the optimal solution in this way without transforming the graph into a line graph.

I am looking forward to your assessment or if I am missing something. The shift seems to be too simple to be true. ;)

[bitromortac]

I am looking forward to your assessment or if I am missing something. The shift seems to be too simple to be true. ;)

Yes, unfortunately I think that doesn't solve it, during implementation/review of #6934 this approach was tried but not documented. Here's an example graph that would lead to non-optimal outcomes with the suggested approach.

Take the following graph with outbound and inbound fees as indicated on the edges:

flowchart LR

S -->|out: 0, in: -4| A
A -->|out: 9, in: -11| B
A -->|out: 0, in: -6| C
B -->|out: 8, in: 0| T
C -->|out: 10, in: 0| T

Loading

The top route (SABT) has fees or weight of 5=8-8+9-4, the lower, optimal, route (SACT) has weight of 4=10-6+0+0, keeping in mind that the inbound discount is capped by the next hop's outbound fee, so the total node fee is not allowed to become negative.

I'll show the current approach, the suggested approach and the line-graph approach as examples.

Capped total channel fees

This is the currently implemented approach: taking the weight as the edge's inbound fee plus its outbound fee, capped from below by zero. Dijkstra's algorithm would work like this:

• explore T

  • B: accumulated weight = 0 (prev accWeight) + 0 (inFee) + 8 (outFee) = 8
  • C: accWeight = 0 + 0 + 10 = 10
  • the queue looks like this (notation: Node: accWeight (prevOutFee))
    • B: 8 (8)
    • C: 10 (10)

• explore B

  • A: accumulated weight = 8 - 8 (capped inFee) + 9 = 9
  • queue:
    • A 9 (9)
    • C 10 (10)

• explore A

  • S: accumulated weight = 9 + 0 + 0 (capped channel fee) = 9
  • queue:
    • S 9 (0): the current algo ends here with a non-optimal route
    • C 10 (10)

Inbound fee and previous outbound fee

• explore T
  • B: accumulated weight = 0 (prev accWeight) + 0 (inFee) + 0 (prev outFee) = 0
  • C: accWeight = 0 + 0 + 0 = 0
  • queue:
    • B: 0 (8)
    • C: 0 (10)

The accumulated weights are 0 for both, so the order by which nodes are explored
is non-deterministic.

1. explore B first

• A: 0 (prev accWeight) - 8 (capped inFee) + 8 (prev outFee) = 0
• queue:
  • A 0 (9)
  • C 0 (10)

Both nodes in the queue have the same accumulated weight.

1.1. explore A first

• S: 0 - 4 + 9 = 5

• queue:

  • C 0 (10)
  • S 5 (0)

• explore C

  • A: 0 - 6 + 10 = 4
  • queue:
    • A 4 (0)
    • S 5 (0)

• explore A

  • S: 4 + 0 + 0 = 4: new best: optimal route

1.2. explore C first

• A: 0 - 6 + 10 = 4 -> worse than before, keep A 0 (9)

• queue:

  • A 0 (9)

• explore A

  • S: 0 - 4 + 9 = 5 -> algo stops here, S found, non-optimal

2. explore C first

• A: 0 - 6 + 10 = 4

• queue:

  • B 0 (8)
  • A 4 (0)

• explore B

  • A: 0 - 8 + 8 = 0: new best
  • queue:
    • A 0 (9) -> ends up at S with non-optimal route as before

So in some cases optimal routes are found, sometimes not. Perhaps one could apply the next outbound fee as a tie-breaker and maybe there are other edge cases, but I think the next approach is the exact one.

Inbound fee and previous outbound fee with line graph

Transforming the problem to a line graph (https://en.wikipedia.org/wiki/Line_graph) solves the problem for this example graph. The new pivots of exploration are the middle points between two nodes, which helps to keep track of weights without overriding information (a solution found by Joost Jager).

• explore T
  • B: 0 (prev accWeight) + 0 (inFee) + 0 (prev outFee) = 0
  • C: 0 + 0 + 0 = 0
  • queue with new notation NodeTuple accWeight (prev outFee)
    • (B,T): 0 (8)
    • (C,T): 0 (10)

Again, we have same weights, any tuple could get picked.

1. explore (B,T) first

• A: 0 - 8 (capped inFee) + 8 (prev outFee) = 0
• queue:
  • (A,B) 0 (9)
  • (C,T) 0 (10)

Both nodes in the queue both have again the same weight.

1.1. explore (A,B) first

• S: 0 - 4 + 9 = 5

• queue:

  • (C,T) 0 (10): (S,A) is not first yet, keep exploring
  • (S,A) 5 (0)

• explore (C,T)

  • A: 0 + 10 - 6 = 4
  • queue:
    • (A,C) 4 (0)
    • (S,A) 5 (0)

• explore (A,C)

  • S: 4 + 0 + 0 = 4: override last best
  • queue:
    • (S,A) 4 (0): optimal route found

1.2. explore (C,T) first

• A: 0 - 6 + 10 = 4

  • queue:
    • (A,B) 0 (9)
    • (A,C) 4 (0)

• explore (A,B)

  • S: 0 - 4 + 9 = 5
    -queue:
    - (A,C) 4 (0): optimal route found
    - (S,A) 5 (0)

• explore (A,C)

  • S: 4 + 0 + 0 = 4: new best
    -queue:
    - (S,A) 4 (0): optimal route found

2. explore (C,T) first

• A: 0 -6 + 10 = 4

  • queue:
    • (B,T) 0 (8)
    • (A,C) 4 (0)

• explore (B,T)

  • A: 0 - 8 + 8 = 0
  • queue:
    • (A,B) 0 (9)
    • (A,C) 4 (0)

• explore (A,B)

  • S: 0 - 4 + 9 = 5
  • queue:
    • (A,C) 4 (0)
    • (S,A) 5 (0)

• explore (A,C)

  • S: 4 + 0 + 0 = 4, new best
  • queue:
    • (S,A) 4 (0): optimal route

Next steps

So the suggestion to use the inbound fee plus the previous outbound fee makes the algo correct (at least for this toy graph) if the heap/queue is used with a node pair tuple, which is the case with 54c4988. I'm going to explore this change and check it's execution time behavior. The exit condition can be changed by adding a fake hop (0,S) we are really looking for, I think.

[feelancer21]

First of all, thank you very much for the detailed answer and the very interesting example. I already thought that the dependencies between inbound and outbound go much deeper, but haven't seen it yet.

To summarize it for me: 1.1. vs. 1.2. is about the decision of A 0 (9) vs A 4 (0). However, the optimal solution depends on the inbound discount on S. If it had been -6 or lower, A 0 (9) would have been the right choice.

I suppose you can also construct cases where it is better to choose a higher distance with a higher outbound fee, which is later improved by discounts. So the classic reason why Dijsktra does not find the optimal solution with negative weights

[feelancer21]

explore A

• S: accumulated weight = 9 - 4 + 0 = 5

• queue:

  • S 5 (0): the current algo ends here with a non-optimal route
  • C 10 (10)

Not sure if I have really understood the current approach. I had expected accumulated weight = 9 + max(- 4 + 0; 0) = 9 because of the checkt of the signedFee

Edit:
If I'm not wrong about the previous one and the conversion to the line graph is more extensive than you thought, then I would like to suggest that at least the senders can benefit better from the inbound discounts of their direct peers.

You could set tempWeight = totalFee + sumTimeLockPenalty directly in the case fromVertex == source. Here, sumTimeLockPenalty is the sum of the timeLockPenalty, which would have to be kept separately in nodeWithDist. Then the distance would be correct again, at least in the last iteration, and the chance of finding the optimum path would increase.

[bitromortac]

Not sure if I have really understood the current approach. I had expected accumulated weight = 9 + max(- 4 + 0; 0) = 9 because of the checkt of the signedFee

Ah yes, thank you for the correction, updated (it doesn't change the outcome)!

If I'm not wrong about the previous one and the conversion to the line graph is more extensive than you thought, then I would like to suggest that at least the senders can benefit better from the inbound discounts of their direct peers.

Changing to that approach could make sense, as it is closer to the optimal solution 👍, but I think it's worth to explore the behavior of the line-graph approach first.

[bitromortac]

I did a bit more research on this, the line graph approach fixes all known non-optimal test cases, see https://github.com/bitromortac/lnd/commits/2410-line-graph.

Unfortunately, when benchmarking the line-graph approach (see https://github.com/bitromortac/lnd/commits/2410-line-graph/), I saw quite long pathfinding run times when computing paths to random nodes (typically they took several seconds): Pathfinding perf metrics: nodes=48450, edges=8368338, time=1m0.60802918s.

The number of explored nodes isn't surprising as the line graph has the original graph's number of edges. I was wondering about the large number of edges explored, but it makes sense since when converting an LN graph to the line graph representation (via networkx) this leads to:

LN graph: 15932 nodes and 52414 edges
Line graph: 52414 nodes and 13609686 edges (!)

The run time complexity of the current implementation looks to be linear in the number of edges explored (with 8 µs per explored edge, which is rather slow), which is why I think we'd need significant improvements in the current edge traversal first in order to be able to make up for a factor of ~250 in computational time when using the line graph. Maybe it's possible to skip some edge evaluations if no inbound discounts were involved.

I also tried the suggested approach (using the inbound fee + previous outbound fee), but it fails to compute an optimal path in the following case:
S - A -[out 100 msat]- B -[out 0 msat]- R (total fee 100 msat)
and
S - A -[out 0 msat]- C -[out 1 msat]- R (total fee 1 msat),
because when exploring the B route first, we would find a distance to A of 0 msat and a distance of 1 msat to A via C, which is why we would discard the path A-C-R, overpaying 99 msat in this case (I think this is similar to this example #8945 (comment), but it demonstrates that the weight measure already fails for outbound fees only).

[feelancer21]

Hey, thanks for the analysis. It's crazy to see these numbers.
I don't think it makes sense to think about optimizations, since the number of edges in the line graph probably grows quadratically to the number of vertices in the node graph. I don't think it's worth spending more time on further optimizations. As soon as you work with tight feel limits, you can still get very close to the optimal solution.

Additional thought: In my opinion, the line graph is also only helpful with floored inbound fees as we currently use them. For inbound fees without a floor (i.e. negative fordward fees), we can probably also work with a node graph, as we would then have no dependency of the inbound fees on the previous outbound fees. I like the idea of negative fees more and more ;).