From b728216fd98a4b3996a5e51d1219c901dd09b4c2 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Sat, 27 Mar 2021 12:27:44 -0400 Subject: [PATCH] [router] Calc min-to-node fees based on min value, not est value When walking the network graph to calculate a route, we always calculate the minimum fee which is required to make one further hop. This avoids some extra hop processing at the end of each path selection loop (saving around 10% runtime in our benchmarks). However, if we use the real value which we expect to send over a channel in that calculation, we may find an alternate path to the same node which is more expensive but capacity-constrained, resulting in us considering it cheaper as the relative fee paid will be lower. Instead, we can use the `minimal_value_contribution_msat`, which is a constant through an entire path finding iteration, as the amount, preventing any basis change in the relative fee paid. --- lightning/src/routing/router.rs | 29 ++++++++++++++++------------- 1 file changed, 16 insertions(+), 13 deletions(-) diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index 706c353dc..5c7debd07 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -631,21 +631,24 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye Some(fee_msat) => { hop_use_fee_msat = fee_msat; total_fee_msat += hop_use_fee_msat; - if let Some(prev_hop_fee_msat) = compute_fees(total_fee_msat + amount_to_transfer_over_msat, - old_entry.src_lowest_inbound_fees) { - if let Some(incremented_total_fee_msat) = total_fee_msat.checked_add(prev_hop_fee_msat) { - total_fee_msat = incremented_total_fee_msat; - } - else { - // max_value means we'll always fail - // the old_entry.total_fee_msat > total_fee_msat check + // When calculating the lowest inbound fees to a node, we + // calculate fees here not based on the actual value we think + // will flow over this channel, but on the minimum value that + // we'll accept flowing over it. The minimum accepted value + // is a constant through each path collection run, ensuring + // consistent basis. Otherwise we may later find a + // different path to the source node that is more expensive, + // but which we consider to be cheaper because we are capacity + // constrained and the relative fee becomes lower. + match compute_fees(minimal_value_contribution_msat, old_entry.src_lowest_inbound_fees) + .map(|a| a.checked_add(total_fee_msat)) { + Some(Some(v)) => { + total_fee_msat = v; + }, + _ => { total_fee_msat = u64::max_value(); } - } else { - // max_value means we'll always fail - // the old_entry.total_fee_msat > total_fee_msat check - total_fee_msat = u64::max_value(); - } + }; } } } -- 2.39.5