<p>In fact, finding a route in LND can be described as the process of finding the &quot;shortest path&quot; on a weighted graph. In LND, the weight of each channel is composed of three parts, fee, CLTV_DELTA and the probability. You'll understand the first two factors if you are familiar with the Lightning Network, and the last factor is the probability that this channel can afford the payments from a local perspective.</p>
<p>If a route fails, then the node with insufficient capacity will actively include this information in the return message, which can only be unlocked and seen by the payer. For example,  Then the payer will reduce the probability of this channel in the local view and find the route again (you can treat it as setting the weight of this edge to very large).</p>
<p>You can find detailed information <a href="https://github.com/lightningnetwork/lnd/issues/4864" rel="nofollow noreferrer">here</a>.</p>

CC BY-SA 4.0
2020-12-21T07:49:08.567Z
2020-12-26T07:35:18.200Z
2020-12-26T07:35:18.200Z
sphpmp
<p>So I went ahead and looked at the LND implementation here: <a href="https://github.com/lightningnetwork/lnd/blob/master/routing/pathfind.go" rel="nofollow noreferrer">https://github.com/lightningnetwork/lnd/blob/master/routing/pathfind.go</a> and this is the comment block above the function findPath:</p>

<blockquote>
  <p>findPath attempts to find a path from the source node within the ChannelGraph to the target node that's capable of supporting a payment of <code>amt</code> value. The current approach implemented is modified version of Dijkstra's algorithm to find a single shortest path between the source node and the destination. The distance metric used for edges is related to the time-lock+fee costs along a particular edge. If a path is found, this function returns a slice of ChannelHop structs which encoded the chosen path from the target to the source. The search is performed backwards from
  destination node back to source. This is to properly accumulate fees that need to be paid along the path and accurately check the amount to forward at every node against the available bandwidth.</p>
</blockquote>

<p>If this is the case then I don't think your scenario would play out. It appears LND wouldn't return the path A --> B --> C --> D because it does not have sufficient balance/bandwidth.</p>

CC BY-SA 4.0
2019-10-27T15:04:23.167Z
Yeah, that is the general aim of `findPath`, but as long as `bandwidthHints` is not set, it has no "available bandwidth". `bandwidthHints` usually is only set for the outgoing channel of A. I also extended my problem description.
If it actually sets bandwidth hints from e. g. failed routes, that would exactly be what I am interested in!
wtho
CC BY-SA 4.0
2019-10-27T17:25:43.757Z
The distribution of the balance in a channel is not public information, so lnd wouldn't know that the funds are all on the side of C in `B->C` before attempting to route the payment through the channel.
Murch
CC BY-SA 4.0
2019-10-23T15:24:41.243Z
2019-10-23T15:24:41.243Z
Matthew Cruz
<p>Suppose LND node <code>A</code> wants to send a payment to another node <code>D</code>. The <code>pathfind</code> algorithm based on Dijkstra found a route through <code>B</code> and <code>C</code> and initiates the payment. It fails, as <code>B -&gt; C</code> does not have sufficient balance/bandwidth.</p>
<p>Will LND just fail the payment or try another time with a different route? How does it remember the failed route?</p>
<p>Follow-up question: Can node <code>A</code> figure out which edge failed?</p>
<hr />
<p><strong>Edit</strong>:
To be more clear, in my example, all channels have 0.5 BTC as capacity, and all of them have an equal balance distribution of this capacity (0.25, 0.25), except for <code>B -&gt; C</code>, which has (0, 0.5), so <code>B</code> currently cannot send any payments to <code>C</code>.</p>
<p>The balance state (here: (0, 0.5)) is private, but the capacity of all channels is public.</p>
<p>As the routing computation is done in <code>A</code> (source routing), the algorithm initially has no knowledge of the balances. If <code>A</code> just wants to send 0.001 BTC, the routing algorithm will find the route, but it cannot reach the target.</p>

<lightning-network><lightning-network-daemon><lightning-routing>
How does LND make sure that it does not reuse the same route for a retry after the first payment failed?
wtho
# How does LND make sure that it does not reuse the same route for a retry after the first payment failed?

(Asked by: username_0 on 2019-10-18)

Suppose LND node `A` wants to send a payment to another node `D`. The `pathfind` algorithm based on Dijkstra found a route through `B` and `C` and initiates the payment. It fails, as `B -> C` does not have sufficient balance/bandwidth.

Will LND just fail the payment or try another time with a different route? How does it remember the failed route?

Follow-up question: Can node `A` figure out which edge failed?

---

**Edit**:
To be more clear, in my example, all channels have 0.5 BTC as capacity, and all of them have an equal balance distribution of this capacity (0.25, 0.25), except for `B -> C`, which has (0, 0.5), so `B` currently cannot send any payments to `C`.

The balance state (here: (0, 0.5)) is private, but the capacity of all channels is public.

As the routing computation is done in `A` (source routing), the algorithm initially has no knowledge of the balances. If `A` just wants to send 0.001 BTC, the routing algorithm will find the route, but it cannot reach the target.

**Tags:** lightning-network, lightning-network-daemon, lightning-routing


---

## 2 answers

### Answer by username_1 on 2020-12-21. Score: 1

In fact, finding a route in LND can be described as the process of finding the "shortest path" on a weighted graph. In LND, the weight of each channel is composed of three parts, fee, CLTV\_DELTA and the probability. You'll understand the first two factors if you are familiar with the Lightning Network, and the last factor is the probability that this channel can afford the payments from a local perspective.

If a route fails, then the node with insufficient capacity will actively include this information in the return message, which can only be unlocked and seen by the payer. For example, Then the payer will reduce the probability of this channel in the local view and find the route again (you can treat it as setting the weight of this edge to very large).

You can find detailed information [here](https://github.com/lightningnetwork/lnd/issues/4864).


---

### Answer by username_2 on 2019-10-23. Score: 0

So I went ahead and looked at the LND implementation here: <https://github.com/lightningnetwork/lnd/blob/master/routing/pathfind.go> and this is the comment block above the function findPath:

> findPath attempts to find a path from the source node within the ChannelGraph to the target node that's capable of supporting a payment of `amt` value. The current approach implemented is modified version of Dijkstra's algorithm to find a single shortest path between the source node and the destination. The distance metric used for edges is related to the time-lock+fee costs along a particular edge. If a path is found, this function returns a slice of ChannelHop structs which encoded the chosen path from the target to the source. The search is performed backwards from
> destination node back to source. This is to properly accumulate fees that need to be paid along the path and accurately check the amount to forward at every node against the available bandwidth.

If this is the case then I don't think your scenario would play out. It appears LND wouldn't return the path A --> B --> C --> D because it does not have sufficient balance/bandwidth.

> **Comments:**
> **username_0**: Yeah, that is the general aim of `findPath`, but as long as `bandwidthHints` is not set, it has no "available bandwidth". `bandwidthHints` usually is only set for the outgoing channel of A. I also extended my problem description. If it actually sets bandwidth hints from e. g. failed routes, that would exactly be what I am interested in!  
> **username_3**: The distribution of the balance in a channel is not public information, so lnd wouldn't know that the funds are all on the side of C in `B->C` before attempting to route the payment through the channel.  

---

