[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)

[René Pickhardt]

Good morning ZmnSCPxj,

Maybe I oversee something - in that case sorry for spamming the list - but
I don't understand how you could know the distance from yourself if you
don't know the entire topology? (unless u use it on the pruned view as you
suggested)

On the other hand querying for a certain depth would be possible with the
suggested `query ask egonetwork` in case for depth 3 one would have to peer
with the nodes from the friend of a friend network.

Best Rene


ZmnSCPxj <ZmnSCPxj at protonmail.com> schrieb am Fr., 29. März 2019, 09:47:

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20190329/54ccc4a4/attachment.html>