[c-lightning] Routing: bias against smaller channels

[ZmnSCPxj]

Good morning Michael,

> Hi,
>
> I'm currently thinking about the same issue while I'm polishing the
> rebalance plugin.
> My current thoughts on that: This should probably not be done by
> changing the getroute
> code but by the one that is using getroute in a way like for example:
>
> -   Start trying shorter routes first via "maxhops" parameter.
> -   In the first iteration use a lot higher "msatoshi" value than needed,
>     for example by a factor of 4 times bigger.
>
> -   When you get "route not found errors" decrease the msatoshi factor and
>     retry getroute.
>
> -   When you reached a msatoshi factor of 1 (neutral) and still run into
>     "route not found": increase the maxhops paramter by 1 and reset the
>     msatoshi factor to 4 again for the next interation.
>
> -   Repeat the loop until maxhop reached i.e. 10
>
>     Something like this. I'm still fiddling with the details.
>     Just my two Satoshi...
>
>     Michael
>

No comment on the overall "biasing" as yet, but --- note that the underlying algorithm of `getroute` is Dijkstra pathfinding algorithm, O(n log n) on length n.

With the above algorithm, the time complexity becomes O(n ^ 2 log n) i think --- you iterate from `maxhops` 1 to the final length `n`, and each `getroute` takes O(n log n).

Actually it may be worse in practice, by my memory, `maxhops` does not limit the work done, it just forces `getroute` to repeat the algorithm, though this may have changed.

In any case, I know Rusty has (had?) plans to publicly publish the routemap on-disk format, so that plugins can directly look at the on-disk routemap and implement specifially-optimized routing algorithms, what has happened to those?

Regards,
ZmnSCPxj