Code for sub second runtime of piecewise linarization to quickly approximate the minimum convex cost flow problem (makes fast multi part payments with large amounts possible)

Summary:

The Lightning Network has found a quick way to approximate the slow minimum convex cost flow computation. This is necessary for optimally reliable and cheap payment flows. The proposed solution happens via piecewise linearization of the min cost flow problem on the uncertainty network which we face in order to compute the optimal split and planning of large amount multi part payments. The notion of "optimal" is obviously subjective with respect to the chosen cost function. As known we suggest to include the negative logarithm of success probabilities based on the likelihood that enough liquidity is available on a channel as a dominant feature of the used cost function.One of the largest criticisms and concerns of the approach to use minimum cost flows for payment delivery back in July/August last year was that the min cost flow approach would be impractical due to run time constrains. However, with the now published code it's possible to compute a reasonable looking approximation to the optimal solution in a sub-second run time on the complete public channel graph of the Lightning Network. The currently widely deployed Dijkstra search to generate a single candidate path takes roughly 100ms of runtime while the runtime of the piecewise linearized problem the min cost flow approach is now competitive from a runtime perspective. The flow computation is still a bit slower than Dijkstra in both theory and practice. However, the piecewise linearized min cost flow has the huge advantage that it generates several candidate paths for a solid approximation of the optimal MPP split. The iPython notebook which was shared contains about 1 page to explain how to conduct a piecewise linear approximation. The quality of the approximation is not the major goal here as the focus is to demonstrate the run time of the approach and the principle of how to achieve this runtime. Thus, the piecewise linear approximation is done very roughly in the published code. This result is of particular interest for LSPs. If an LSP has to schedule x payments per second, it can just do one flow computation with several sink nodes and plan all of those payments with a single min cost flow computation. This globally optimizes the potentially heavy load that LSPs might have even if all payments were so small that no splitting was necessary.

Updated on: 2023-06-03T07:52:59.983367+00:00