From 5b36449c5950a78ae1857985c8ce309cdf091cc9 Mon Sep 17 00:00:00 2001 From: Jeffrey Czyz Date: Mon, 21 Mar 2022 19:11:48 -0500 Subject: [PATCH] Add a base penalty to ProbabilisticScorer ProbabilisticScorer tends to prefer longer routes to shorter ones. Make the default scoring behavior include a customizable base penalty to avoid longer routes. --- lightning/src/routing/scoring.rs | 64 ++++++++++++++++++++++---------- 1 file changed, 45 insertions(+), 19 deletions(-) diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs index 2ccfba08d..22d7012c3 100644 --- a/lightning/src/routing/scoring.rs +++ b/lightning/src/routing/scoring.rs @@ -516,17 +516,22 @@ pub struct ProbabilisticScorerUsingTime, T: Time } /// Parameters for configuring [`ProbabilisticScorer`]. +/// +/// Used to configure a base penalty and a liquidity penalty, the sum of which is the channel +/// penalty (i.e., the amount in msats willing to be paid to avoid routing through the channel). #[derive(Clone, Copy)] pub struct ProbabilisticScoringParameters { - /// A multiplier used to determine the amount in msats willing to be paid to avoid routing - /// through a channel, as per multiplying by the negative `log10` of the channel's success - /// probability for a payment. + /// A fixed penalty in msats to apply to each channel. /// - /// The success probability is determined by the effective channel capacity, the payment amount, - /// and knowledge learned from prior successful and unsuccessful payments. The lower bound of - /// the success probability is 0.01, effectively limiting the penalty to the range - /// `0..=2*liquidity_penalty_multiplier_msat`. The knowledge learned is decayed over time based - /// on [`liquidity_offset_half_life`]. + /// Default value: 500 msat + pub base_penalty_msat: u64, + + /// A multiplier used in conjunction with the negative `log10` of the channel's success + /// probability for a payment to determine the liquidity penalty. + /// + /// The penalty is based in part by the knowledge learned from prior successful and unsuccessful + /// payments. This knowledge is decayed over time based on [`liquidity_offset_half_life`]. The + /// penalty is effectively limited to `2 * liquidity_penalty_multiplier_msat`. /// /// Default value: 10,000 msat /// @@ -549,11 +554,6 @@ pub struct ProbabilisticScoringParameters { pub liquidity_offset_half_life: Duration, } -impl_writeable_tlv_based!(ProbabilisticScoringParameters, { - (0, liquidity_penalty_multiplier_msat, required), - (2, liquidity_offset_half_life, required), -}); - /// Accounting for channel liquidity balance uncertainty. /// /// Direction is defined in terms of [`NodeId`] partial ordering, where the source node is the @@ -602,6 +602,7 @@ impl, T: Time> ProbabilisticScorerUsingTime Self { Self { + base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 10_000, liquidity_offset_half_life: Duration::from_secs(3600), } @@ -757,6 +758,7 @@ impl, T: Time> Score for ProbabilisticScorerUsin .unwrap_or(&ChannelLiquidity::new()) .as_directed(source, target, capacity_msat, liquidity_offset_half_life) .penalty_msat(amount_msat, liquidity_penalty_multiplier_msat) + .saturating_add(self.params.base_penalty_msat) } fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) { @@ -1734,7 +1736,7 @@ mod tests { fn increased_penalty_nearing_liquidity_upper_bound() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters { - liquidity_penalty_multiplier_msat: 1_000, ..Default::default() + base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, ..Default::default() }; let scorer = ProbabilisticScorer::new(params, &network_graph); let source = source_node_id(); @@ -1759,7 +1761,7 @@ mod tests { let last_updated = SinceEpoch::now(); let network_graph = network_graph(); let params = ProbabilisticScoringParameters { - liquidity_penalty_multiplier_msat: 1_000, ..Default::default() + base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, ..Default::default() }; let scorer = ProbabilisticScorer::new(params, &network_graph) .with_channel(42, @@ -1779,7 +1781,7 @@ mod tests { fn does_not_further_penalize_own_channel() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters { - liquidity_penalty_multiplier_msat: 1_000, ..Default::default() + base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, ..Default::default() }; let mut scorer = ProbabilisticScorer::new(params, &network_graph); let sender = sender_node_id(); @@ -1800,7 +1802,7 @@ mod tests { fn sets_liquidity_lower_bound_on_downstream_failure() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters { - liquidity_penalty_multiplier_msat: 1_000, ..Default::default() + base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, ..Default::default() }; let mut scorer = ProbabilisticScorer::new(params, &network_graph); let source = source_node_id(); @@ -1822,7 +1824,7 @@ mod tests { fn sets_liquidity_upper_bound_on_failure() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters { - liquidity_penalty_multiplier_msat: 1_000, ..Default::default() + base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, ..Default::default() }; let mut scorer = ProbabilisticScorer::new(params, &network_graph); let source = source_node_id(); @@ -1844,7 +1846,7 @@ mod tests { fn reduces_liquidity_upper_bound_along_path_on_success() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters { - liquidity_penalty_multiplier_msat: 1_000, ..Default::default() + base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, ..Default::default() }; let mut scorer = ProbabilisticScorer::new(params, &network_graph); let sender = sender_node_id(); @@ -1868,6 +1870,7 @@ mod tests { fn decays_liquidity_bounds_over_time() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters { + base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, liquidity_offset_half_life: Duration::from_secs(10), }; @@ -1919,6 +1922,7 @@ mod tests { fn decays_liquidity_bounds_without_shift_overflow() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters { + base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, liquidity_offset_half_life: Duration::from_secs(10), }; @@ -1943,6 +1947,7 @@ mod tests { fn restricts_liquidity_bounds_after_decay() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters { + base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, liquidity_offset_half_life: Duration::from_secs(10), }; @@ -1980,6 +1985,7 @@ mod tests { fn restores_persisted_liquidity_bounds() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters { + base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, liquidity_offset_half_life: Duration::from_secs(10), }; @@ -2009,6 +2015,7 @@ mod tests { fn decays_persisted_liquidity_bounds() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters { + base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, liquidity_offset_half_life: Duration::from_secs(10), }; @@ -2035,4 +2042,23 @@ mod tests { SinceEpoch::advance(Duration::from_secs(10)); assert_eq!(deserialized_scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 371); } + + #[test] + fn adds_base_penalty_to_liquidity_penalty() { + let network_graph = network_graph(); + let source = source_node_id(); + let target = target_node_id(); + + let params = ProbabilisticScoringParameters { + base_penalty_msat: 0, ..Default::default() + }; + let scorer = ProbabilisticScorer::new(params, &network_graph); + assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 585); + + let params = ProbabilisticScoringParameters { + base_penalty_msat: 500, ..Default::default() + }; + let scorer = ProbabilisticScorer::new(params, &network_graph); + assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 1085); + } } -- 2.39.5