From 16a6e9c5c8f694750e87c3f4ea0acb6d74ca8b44 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Fri, 26 Mar 2021 22:31:57 -0400 Subject: [PATCH] [router] Avoid re-selecting the same path over and over again If we walk the network graph and find a route that meets are payment amount and has a liquidiy limit far in excess of our payment amount, we may select the same path several times in the main path-gathering loop. Instead, if the path we selected was not limited by the available liquidity, we set the middle hop in the path's liquidity available to zero, disabling that channel in future path finding steps. --- lightning/src/routing/router.rs | 17 ++++++++++++++++- 1 file changed, 16 insertions(+), 1 deletion(-) diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index 0163ae515..bf7c29487 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -894,7 +894,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // on some channels we already passed (assuming dest->source direction). Here, we // recompute the fees again, so that if that's the case, we match the currently // underpaid htlc_minimum_msat with fees. - payment_path.update_value_and_recompute_fees(value_contribution_msat); + payment_path.update_value_and_recompute_fees(cmp::min(value_contribution_msat, final_value_msat)); // Since a path allows to transfer as much value as // the smallest channel it has ("bottleneck"), we should recompute @@ -905,6 +905,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // might have been computed considering a larger value. // Remember that we used these channels so that we don't rely // on the same liquidity in future paths. + let mut prevented_redundant_path_selection = false; for payment_hop in payment_path.hops.iter() { let channel_liquidity_available_msat = bookkeeped_channels_liquidity_available_msat.get_mut(&payment_hop.route_hop.short_channel_id).unwrap(); let mut spent_on_hop_msat = value_contribution_msat; @@ -915,8 +916,22 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // trying to avoid cases when a hop is not usable due to the fee situation. break 'path_construction; } + if spent_on_hop_msat == *channel_liquidity_available_msat { + // If this path used all of this channel's available liquidity, we know + // this path will not be selected again in the next loop iteration. + prevented_redundant_path_selection = true; + } *channel_liquidity_available_msat -= spent_on_hop_msat; } + if !prevented_redundant_path_selection { + // If we weren't capped by hitting a liquidity limit on a channel in the path, + // we'll probably end up picking the same path again on the next iteration. + // Decrease the available liquidity of a hop in the middle of the path. + let victim_liquidity = bookkeeped_channels_liquidity_available_msat.get_mut( + &payment_path.hops[(payment_path.hops.len() - 1) / 2].route_hop.short_channel_id).unwrap(); + *victim_liquidity = 0; + } + // Track the total amount all our collected paths allow to send so that we: // - know when to stop looking for more paths // - know which of the hops are useless considering how much more sats we need -- 2.39.5