[c-lightning] Routing: bias against smaller channels

[ZmnSCPxj]

> Hi,
>
> > In code this looks like this:
> >
> > https://github.com/lightningd/plugins/pull/246/commits/2dbff662f712c7883169e7557f5170e356c942e8
>
> Interesting! So if I understand this routine correctly, this finds a path with the least number of hops, and in the subset of paths of that length, a path with high msat (likely just the one with the highest msat in practice).
>
> I suppose it's not surprising that pathfinding's O(maxhop*(N log)) isn't the bottleneck for most practical usage,

Yes.

However it does somewhat assume that the published network will not grow in the future.
If it **does** grow, then the n * n log n will be significant.

> but to add to ZmnSCPxj's comment, if I'm not mistaken, I think we can redefine the edge weights in the graph and run the equivalent of your subroutine in a single pass of dijkstra.

Correct, but that is the sticking point in the reluctance to modify `getroute`!

For example, we have a `riskfactor` argument to `getroute`.
This translates the CLTV-delta cost on each hop into an `msatoshi` cost that is then added to the fee to that hop, to generate the cost ("edge weight") of that hop.

If we add another conversion factor from channel size (or log(channel size) --- and what would the base of the log be as well?) then that adds more parameters to pass to `getroute`.

Personally I do not really have an intuitive grasp of the existing `riskfactor` argument to `getroute`, and have to look up the table in the docs all the time.
I imagine that if we add another parameter to factor in the channel size, the same effect will apply (i.e. it is difficult to intuitively understand the parameter that converts channel size to the edge weight).

That is why there is an idea to just expose the routemap directly, so that plugins can provide their own exact pathfinding algorithm.

--

Another idea would be to pass in a "function" to the `getroute` method.

Basically, `getroute` would be given two optional arguments, `costfunctionmethod` and `costfunctionargs`.
The first would be a string, the second would be a generic JSON object.

* A plugin that wants to provide its own edge weight computation to `getroute` would first implement its own unique cost function as an ordinary plugin command.
* Then it would pass in the name of that command as the `costfunctionmethod` to `getroute`.
* `getroute` would then invoke the given method with the channel details (i.e. similar to an object in `listchannels` output?), which should return a `{"cost": 42.0}` object.
  * `getroute` would then cache the cost for every channel it has to open, in order to reduce the RPC-call overhead.
* Optionally, if the function requires additional arguments, the plugin could add `costfunctionargs`, and any object keys in that object will be added to the arguments to the given `costfunctionmethod`.

Basically the above just uses the command name as a function address, and implements a closure by explicitly passing in additional arguments to the function.

What is more, as I noted in my presentation in Berlin in 2019, Dijkstra, A\*, and Greedy Best First Search are really a continuum of related algorithms.
The core of this family of algorithms is that they have **two** cost functions, `G()` and `H()`.
They form the "cumulative" cost function `F() = G() + H()`.

`G()` is the "actual distance from current node to next node".
`H()` is the "estimated distance from next node to destination" i.e. the "heuristic".

In Dijkstra at one end, `H()` always returns 0.
At the other end, Greedy Best First Search, `G()` always returns 0.

In between them, A\* has non-zero `H()` (biased to underestimate; if it overestimates, it starts to move towards Greedy Best First) and non-zero `G()`.

We can instead have a `getroutealgo` command that accepts two functions, `G()` and `H()` using the above technique ("pass in the method name and any extra method args, i.e. closure"), which would also allow plugins to experiment with using A* and Greedy Best First by simply playing around with the cost functions.

Then we could also have a `payalgo` command that accepts a `getroute`-like replacement function, using the closure technique, so that plugins can experiment with various routing functions without having to reimplement the complicated `pay` logic.

--

The difficulty here is that `getroute` is really implemented over in `gossipd`, and the interfaces to the plugins are over in the main daemon `lightningd`.
So we may very well need to expose the on-disk routemap format to `lightningd` at least so that `getroute` is instead implemented there, where it can poke at the plugin RPC interface.

Thoughts, Rusty?

Regards,
ZmnSCPxj