[c-lightning] Routing: bias against smaller channels

[michael at schmoock.net]

Hm,

I will make measurements how much the spent time in route finding is
using my modification towards trying these routes.
Im running on a Raspberry PI and still don't have a big issue with 
computational time.

Pretty sure on decent machines its faster to try short/bigger routes 
first
for all the I/O between the nodes along the routes takes more time than
pre-filtering the routes using maxhops/msatoshi iterations...

maybe we can have a quick chat this evening in the dev meeting

Michael


On 2021-05-31 11:55, ZmnSCPxj wrote:
> 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