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 >
_______________________________________________ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
