pay needs to hand failures back to gossipd for re-routing

[rustyrussell]

lightningd/pay.c:115: /* FIXME: check for routing failure / perm fail. */

[ZmnSCPxj]

Okay, I have been looking through gossip/routing.c. It seems the core algorithm generates from 0 to 20 routes, one of each length. Currently we just select the best route.

One thing we can do would be to sort the routes, then send them all in sorted order to lightningd in gossip_getroute_reply. We could provide just the top 5 routes, for example.

---

A worry I have is that the algo always considers just one route for each length. Consider the network A -> B -> C -> D <-> A. If A wants to pay C, it might get two routes: A -> B -> C and A -> D -> B, but the latter would fail. However if D has lower fees and delays, the algo will never consider the route through B.

But then maybe that would be an Eldritch condition, and in practice, perhaps will happen rarely enough...

[ZmnSCPxj]

Although.... the issue does say to hand back failures. So maybe add a gossip_increaseroutecost_req and reply, which accepts a route and increases a cost multiplier for those channels. This cost multiplier should decay slowly over time back to the normal case, since channels may eventually balance more favorably over time. This also handles the diamomd case in my previous comment.

---

So our pay_command structure should keep track of the number of retries and the most recent failed route. If a route fails, we increase its cost, increment retries counter, then ask for a new route; if new route is same as the previous failing route we immediately treat is as failure and do not bother to try it again (channels are unlikely to balance in the time frames involved), increasing its cost further and then requesting yet another route.

[ZmnSCPxj]

Looking at the lightningd/pay.c code, it seems we have two paths to go through for failure. If the faliure is local, we immediately call json_pay_failed. Otherwise we extract the failure code from the failing hout and then call json_pay_failed. I think the "report route failure to gossipd" should be in json_pay_failed instead of payment_failed.

---

Plan:

1. Add a double cost_multiplier to struct node_connection. In bfg_one_edge, multiply fee by this cost_multiplier field. Initialize cost_multiplier to 1.0.
2. Add a gossip_inform_failed_route message which accepts a variadic array of struct route_hop, from lightningd to gossipd. The handler for this message searches for each struct node_connection via get_connection_by_scid and get_channel_direction, then adds a small constant to the cost_multiplier.
3. Keep the array of struct route_hop in the struct pay_command (modulo @rustyrussell 's plan to get rid of it in favor of wallet_payment), stealing it into the pay_command. Modify json_pay_success to accept a struct pay_command and tal_free the route. Modify json_pay_failed to send gossip_inform_failed_route to gossipd with the route and tal_free it afterwards.

Notice that the above plan does not look at failcode, even though the comment check_for_routing_failure(i, sender, failure_code) suggests that we should. The thing is that even permanent failures we cannot be certain which channel/node actually failed on a long route. So the best we can do is simply to weaken all channels along the route indiscriminately.

[rustyrussell]

BOLT 7 says how to handle failures. The simplest is to remove the channel from consideration until the next channel_update.

We could get more sophisticated with differentiating errors (specifically CAPACITY_EXCEEDED) but this is the minimal viable fix.

Note this also fixes #611 though the preference there would be to look at adjacent channel capacity directly...

[ZmnSCPxj]

I cannot find anything in BOLT 7 about how to handle routing failure, so I will have to defer to you there.

Reading through the code further I realize now that routing failure returns enough information to identify which node reported the error. So I suppose it is possible to identify also the specific channel that failed to forward. In BOLT4 it also indicates a short algorithm for how to treat failures. Since that algorithm mostly talks about removing channels from consideration, it is probably best to implement it in gossipd, and to add a message:

gossip_routing_failure,N
gossip_routing_failure,,erring_node,struct pubkey
gossip_routing_failure,,erring_channel,struct short_channel_id
gossip_routing_failure,,failcode,enum onion_type

There is an active field in struct node_connection which seems to be intended for this routing-failure, so I suppose the simplest handling for gossip_routing_failure would be to set this field to false. The channel_update handler seems to already set this.