Commit message · Lagrang3askrene: add constant probability cost per hop
Added an homogeneous and constant cost to every hop in the MCF solver.
test_real_data shows a slight decrease of paths lengths by looking at
the path length histograms
SLOW_MACHINE=0
histogram before {2: 1, 3: 8, 4: 34, 5: 77, 6: 45, 7: 23, 8: 4}
histogram after {2: 2, 3: 59, 4: 110, 5: 5, 6: 5}
SLOW_MACHINE=1
histograms before {2: 1, 3: 3, 4: 11, 5: 15, 6: 6, 7: 6, 8: 3}
histogram after {2: 2, 3: 16, 4: 18, 5: 1, 6: 5}
the most frequent path length moves from 5 to 4 and there aren't more
than 6 hops in any given path.
Another consequence of the additional per hop cost is a slight reduction
in the number paths (or payment parts) per route query. Even though our linear
approximation gives equal cost to 3 paths of length 1 than to 1 path of
length 3.
in test_real_data this is shown by the expected_first_success (the
number of success computations in the first loop) and
expected_total_paths (the total number of parts for those successes,
also the sum of values in the histogram).
For SLOW_MACHINE=0 we get a mean parts per payment of
expected_total_paths / expected_first_success = 192 / 95 = 2.02
that becomes
expected_total_paths / expected_first_success = 181 / 95 = 1.90
For SLOW_MACHINE=1 we get a mean parts per payment of
expected_total_paths / expected_first_success = 45 / 24 = 1.87
that becomes
expected_total_paths / expected_first_success = 42 / 24 = 1.75
Changelog-Changed: askrene-getroutes: penalizes every extra hop in every route with an homogeneous and constant probability of failure of 1%, as a consequence askrene will slightly prefer smaller routes and fewer payment parts.
Signed-off-by: Lagrang3 <lagrang3@protonmail.com>
68/100 · AdequateMessage clarity
✓ Descriptive subject✓ Names a concrete action or component✓ Provides detailed explanatory context