[Lightning-dev] Routemap scaling (was: Just in Time Routing (JIT-Routing) and a channel rebalancing heuristic as an add on for improved routing success in BOLT 1.0)

[ZmnSCPxj]

Good morning Rene,


Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Friday, March 29, 2019 1:54 PM, René Pickhardt <r.pickhardt at googlemail.com> wrote:

> Dear ZmnSCPxj and fellow lightning developers,
>
> I want to point out two things and make a suggestion for a new gossip message. 
>
> > A good pruning heuristic is "channel capacity", which can be checked onchain (the value of the UTXO backing the channel is the channel capacity).
> > It is good to keep channels with large capacity in the routemap, because such large channels are more likely to successfully route a payment than smaller channels.
> > So it is reasonable to delete channels with low capacity when the routemap memory is becoming close to full.
>
> Intuitively (without simulation). I encourage to make that process not deerministic but rather probabilistic. It would be good if everyone had a different set of channels. (which is somewhat achieved with everyone keeping their local view) 

At a software engineer point-of-view, probabilistic can be difficult to test.
This can be made deterministic by including an RNG seed in the input to this code.

However, let me propose instead, in combination with your later thought:

>
> > Nodes still need to track their direct channels (so they are implicitly always in the routemap).
>
> I strongly advice that the local view should be extended. Every node should always track their friends of a friend network.

Perhaps the pruning rule can be modified to include *distance from self* in addition to channel capacity.
The nearer the channel is, the more likely it is retained.
The further, the less likely.
The larger the channel is, the more likely it is retained.
The smaller, the less likely.

The capacity divided by the distance can be used as a sorting key, and if pruning is needed, the smallest "score" is pruned until the routemap fits.

This will lead to everyone having a different set of channels, while being likely to track their friend-of-friend network compared to more distant nodes.

Of course, the pruning itself would affect the distance of the channel to the "self" node.
So determinism may be difficult to achieve here anyway.

Regards,
ZmnSCPxj