Joost Jager [ARCHIVE] on Nostr: 📅 Original date posted:2021-11-15 📝 Original message: Hi Rene, > First I am ...
📅 Original date posted:2021-11-15
📝 Original message:
Hi Rene,
> First I am happy that you also agree that reliability can and should be
> expressed as a probability as discussed in [0].
>
Probability based routing is not new to me. I've implemented a form of that
in lnd in march 2019: https://github.com/lightningnetwork/lnd/pull/2802,
followed by several rounds of refinement.
> The problem that you address is that of feature engineering[1]. Which
> consists of two (or even more) steps:
>
> 1.) Feature selection: That means in payment delivery we will compute a
> min cost flow [2] with a chosen cost function (historically people used
> dijkstra seach for single paths with the cost function representing the
> weights on the edges of the graph -which is what most folks currently still
> do). While [2] and I personally agree with you that the cost function
> should be a combination the two features fees and reliability (as in
> successprobability) Matt Corallo righfully pointed out [3] that other
> features might be chosen in the future to deliver more optimal results. For
> example implementations currently often use CLTV as a feature (which I
> honestly find horrible) and I am currently investigating if one could add
> latency of channels or - for known IP addresses - either the geo distance
> or IP distance.
>
I am aware that there are more candidate features, but my question is
specifically about the ones that I mentioned.
2.) Combining features: This is the question that you are asking. Often
> people use a linear weighted sum to combine features. This is what often
> happens implicitly in neural networks. While this is often good enough and
> while it is often practical to either learn the weights or give users a
> choice there are many situation where the weighted linear sum does not work
> well with the selected features. An example for the weighted sum is the
> risk-factor in c-lightning that could have been used to decide if one
> wanted the dijkstra seach to either optimize for CLTV delta or for paid
> routing fees. Also in our paper [2] in which we discuss the same two
> features that you mentioned we explain how a linear sum of two features can
> be optimal due to the lagrangian bounding principle. However in practice
> (of machine learning) it has been shown that using the harmonic mean [4]
> between features often works very well without the necessity to learn a
> weight / parameter. This has for example been done when c-lightnign
> recently switched to probabilistic path finding [5]. In this thread you
> find a long discussion and evaluation how the harmonic mean outperformed
> the linear sum.
>
Obviously features can be combined in a multitude of ways, but I am looking
for something that is anchored to some kind of understandable starting
point. What I did in lnd is to work with so called 'payment attempt cost'.
A virtual satoshi amount that represents the cost of a failed attempt. If
you put a high price on failed attempts, pathfinding will tend towards more
reliable routes even if they require a higher fee. To me, the idea of
putting a (virtual) cost on a payment attempt is tangible and ideally the
math should follow from that. I don't want zero parameters, because I think
that ultimately the fee/reliability trade-off is up to the user to decide
on.
Joost
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20211115/0be67f54/attachment.html>;
📝 Original message:
Hi Rene,
> First I am happy that you also agree that reliability can and should be
> expressed as a probability as discussed in [0].
>
Probability based routing is not new to me. I've implemented a form of that
in lnd in march 2019: https://github.com/lightningnetwork/lnd/pull/2802,
followed by several rounds of refinement.
> The problem that you address is that of feature engineering[1]. Which
> consists of two (or even more) steps:
>
> 1.) Feature selection: That means in payment delivery we will compute a
> min cost flow [2] with a chosen cost function (historically people used
> dijkstra seach for single paths with the cost function representing the
> weights on the edges of the graph -which is what most folks currently still
> do). While [2] and I personally agree with you that the cost function
> should be a combination the two features fees and reliability (as in
> successprobability) Matt Corallo righfully pointed out [3] that other
> features might be chosen in the future to deliver more optimal results. For
> example implementations currently often use CLTV as a feature (which I
> honestly find horrible) and I am currently investigating if one could add
> latency of channels or - for known IP addresses - either the geo distance
> or IP distance.
>
I am aware that there are more candidate features, but my question is
specifically about the ones that I mentioned.
2.) Combining features: This is the question that you are asking. Often
> people use a linear weighted sum to combine features. This is what often
> happens implicitly in neural networks. While this is often good enough and
> while it is often practical to either learn the weights or give users a
> choice there are many situation where the weighted linear sum does not work
> well with the selected features. An example for the weighted sum is the
> risk-factor in c-lightning that could have been used to decide if one
> wanted the dijkstra seach to either optimize for CLTV delta or for paid
> routing fees. Also in our paper [2] in which we discuss the same two
> features that you mentioned we explain how a linear sum of two features can
> be optimal due to the lagrangian bounding principle. However in practice
> (of machine learning) it has been shown that using the harmonic mean [4]
> between features often works very well without the necessity to learn a
> weight / parameter. This has for example been done when c-lightnign
> recently switched to probabilistic path finding [5]. In this thread you
> find a long discussion and evaluation how the harmonic mean outperformed
> the linear sum.
>
Obviously features can be combined in a multitude of ways, but I am looking
for something that is anchored to some kind of understandable starting
point. What I did in lnd is to work with so called 'payment attempt cost'.
A virtual satoshi amount that represents the cost of a failed attempt. If
you put a high price on failed attempts, pathfinding will tend towards more
reliable routes even if they require a higher fee. To me, the idea of
putting a (virtual) cost on a payment attempt is tangible and ideally the
math should follow from that. I don't want zero parameters, because I think
that ultimately the fee/reliability trade-off is up to the user to decide
on.
Joost
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20211115/0be67f54/attachment.html>;