[c-lightning] Routing: bias against smaller channels
ZmnSCPxj at protonmail.com
Mon May 31 19:55:23 AEST 2021
Good morning Michael,
> 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...
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?
More information about the c-lightning