[c-lightning] Routing: bias against smaller channels

[nibnalin]

Hi,

> In code this looks like this:
> 
> https://github.com/lightningd/plugins/pull/246/commits/2dbff662f712c7883169e7557f5170e356c942e8 <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, 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. For instance, we can treat edge weights as a pythonic tuple of (hops, msat) and use the usual lexicographic comparator in one pass of dijkstra to get an equivalent route. I suspect the code I had would also produce pretty similar routes (although, I bias for smaller channels by a log(channel size) factor).

>> 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?

That sounds like a very powerful tool :) While I'm not sure about the details, another user-friendly way to support pathfinding customisations could be to allow plugin developers to implement their own edge weight functions and let c-lightning handle the actual pathfinding bulk of it. I imagine it would also be more efficient resource-wise as the plugin would only need to evaluate the edges used by pathfinding then. In practice, however, I'm not sure if it's easily possible to support customised edge weight functions via the current interface. Having a back-and-forth with plugins about every edge doesn’t sound like a fun coordination problem, anyway.

Thanks.

> On 31-May-2021, at 3:55 PM, michael at schmoock.net wrote:
> 
> 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
> -- 
> c-lightning mailing list
> c-lightning at lists.ozlabs.org
> https://lists.ozlabs.org/listinfo/c-lightning

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ozlabs.org/pipermail/c-lightning/attachments/20210531/c93afa51/attachment-0001.htm>