_ Git - rust-lightning/blob - lightning/src/routing/scorer.rs

   1 // This file is Copyright its original authors, visible in version control
   2 // history.
   3 //
   4 // This file is licensed under the Apache License, Version 2.0 <LICENSE-APACHE
   5 // or http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   6 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your option.
   7 // You may not use this file except in accordance with one or both of these
   8 // licenses.
   9
  10 //! Utilities for scoring payment channels.
  11 //!
  12 //! [`Scorer`] may be given to [`find_route`] to score payment channels during path finding when a
  13 //! custom [`routing::Score`] implementation is not needed.
  14 //!
  15 //! # Example
  16 //!
  17 //! ```
  18 //! # extern crate secp256k1;
  19 //! #
  20 //! # use lightning::routing::network_graph::NetworkGraph;
  21 //! # use lightning::routing::router::{RouteParameters, find_route};
  22 //! # use lightning::routing::scorer::{Scorer, ScoringParameters};
  23 //! # use lightning::util::logger::{Logger, Record};
  24 //! # use secp256k1::key::PublicKey;
  25 //! #
  26 //! # struct FakeLogger {};
  27 //! # impl Logger for FakeLogger {
  28 //! #     fn log(&self, record: &Record) { unimplemented!() }
  29 //! # }
  30 //! # fn find_scored_route(payer: PublicKey, params: RouteParameters, network_graph: NetworkGraph) {
  31 //! # let logger = FakeLogger {};
  32 //! #
  33 //! // Use the default channel penalties.
  34 //! let scorer = Scorer::default();
  35 //!
  36 //! // Or use custom channel penalties.
  37 //! let scorer = Scorer::new(ScoringParameters {
  38 //!     base_penalty_msat: 1000, ..ScoringParameters::default()
  39 //! });
  40 //!
  41 //! let route = find_route(&payer, &params, &network_graph, None, &logger, &scorer);
  42 //! # }
  43 //! ```
  44 //!
  45 //! [`find_route`]: crate::routing::router::find_route
  46
  47 use routing;
  48
  49 use routing::network_graph::NodeId;
  50 use routing::router::RouteHop;
  51
  52 use prelude::*;
  53 #[cfg(not(feature = "no-std"))]
  54 use core::time::Duration;
  55 #[cfg(not(feature = "no-std"))]
  56 use std::time::SystemTime;
  57
  58 /// [`routing::Score`] implementation that provides reasonable default behavior.
  59 ///
  60 /// Used to apply a fixed penalty to each channel, thus avoiding long paths when shorter paths with
  61 /// slightly higher fees are available. May also further penalize failed channels.
  62 ///
  63 /// See [module-level documentation] for usage.
  64 ///
  65 /// [module-level documentation]: crate::routing::scorer
  66 pub struct Scorer {
  67         params: ScoringParameters,
  68         #[cfg(not(feature = "no-std"))]
  69         channel_failures: HashMap<u64, (u64, SystemTime)>,
  70         #[cfg(feature = "no-std")]
  71         channel_failures: HashMap<u64, u64>,
  72 }
  73
  74 /// Parameters for configuring [`Scorer`].
  75 pub struct ScoringParameters {
  76         /// A fixed penalty in msats to apply to each channel.
  77         pub base_penalty_msat: u64,
  78
  79         /// A penalty in msats to apply to a channel upon failure.
  80         ///
  81         /// This may be reduced over time based on [`failure_penalty_decay_interval`].
  82         ///
  83         /// [`failure_penalty_decay_interval`]: Self::failure_penalty_decay_interval
  84         pub failure_penalty_msat: u64,
  85
  86         /// The time needed before any accumulated channel failure penalties are cut in half.
  87         #[cfg(not(feature = "no-std"))]
  88         pub failure_penalty_decay_interval: Duration,
  89 }
  90
  91 impl Scorer {
  92         /// Creates a new scorer using the given scoring parameters.
  93         pub fn new(params: ScoringParameters) -> Self {
  94                 Self {
  95                         params,
  96                         channel_failures: HashMap::new(),
  97                 }
  98         }
  99
 100         /// Creates a new scorer using `penalty_msat` as a fixed channel penalty.
 101         pub fn with_fixed_penalty(penalty_msat: u64) -> Self {
 102                 Self::new(ScoringParameters {
 103                         base_penalty_msat: penalty_msat,
 104                         failure_penalty_msat: 0,
 105                         #[cfg(not(feature = "no-std"))]
 106                         failure_penalty_decay_interval: Duration::from_secs(0),
 107                 })
 108         }
 109
 110         #[cfg(not(feature = "no-std"))]
 111         fn decay_from(&self, penalty_msat: u64, last_failure: &SystemTime) -> u64 {
 112                 decay_from(penalty_msat, last_failure, self.params.failure_penalty_decay_interval)
 113         }
 114 }
 115
 116 impl Default for Scorer {
 117         fn default() -> Self {
 118                 Scorer::new(ScoringParameters::default())
 119         }
 120 }
 121
 122 impl Default for ScoringParameters {
 123         fn default() -> Self {
 124                 Self {
 125                         base_penalty_msat: 500,
 126                         failure_penalty_msat: 1024,
 127                         #[cfg(not(feature = "no-std"))]
 128                         failure_penalty_decay_interval: Duration::from_secs(3600),
 129                 }
 130         }
 131 }
 132
 133 impl routing::Score for Scorer {
 134         fn channel_penalty_msat(
 135                 &self, short_channel_id: u64, _source: &NodeId, _target: &NodeId
 136         ) -> u64 {
 137                 #[cfg(not(feature = "no-std"))]
 138                 let failure_penalty_msat = match self.channel_failures.get(&short_channel_id) {
 139                         Some((penalty_msat, last_failure)) => self.decay_from(*penalty_msat, last_failure),
 140                         None => 0,
 141                 };
 142                 #[cfg(feature = "no-std")]
 143                 let failure_penalty_msat =
 144                         self.channel_failures.get(&short_channel_id).copied().unwrap_or(0);
 145
 146                 self.params.base_penalty_msat + failure_penalty_msat
 147         }
 148
 149         fn payment_path_failed(&mut self, _path: &Vec<RouteHop>, short_channel_id: u64) {
 150                 let failure_penalty_msat = self.params.failure_penalty_msat;
 151                 #[cfg(not(feature = "no-std"))]
 152                 {
 153                         let decay_interval = self.params.failure_penalty_decay_interval;
 154                         self.channel_failures
 155                                 .entry(short_channel_id)
 156                                 .and_modify(|(penalty_msat, last_failure)| {
 157                                         let decayed_penalty = decay_from(*penalty_msat, last_failure, decay_interval);
 158                                         *penalty_msat = decayed_penalty + failure_penalty_msat;
 159                                         *last_failure = SystemTime::now();
 160                                 })
 161                                 .or_insert_with(|| (failure_penalty_msat, SystemTime::now()));
 162                 }
 163                 #[cfg(feature = "no-std")]
 164                 self.channel_failures
 165                         .entry(short_channel_id)
 166                         .and_modify(|penalty_msat| *penalty_msat += failure_penalty_msat)
 167                         .or_insert(failure_penalty_msat);
 168         }
 169 }
 170
 171 #[cfg(not(feature = "no-std"))]
 172 fn decay_from(penalty_msat: u64, last_failure: &SystemTime, decay_interval: Duration) -> u64 {
 173         let decays = last_failure.elapsed().map_or(0, |elapsed| {
 174                 elapsed.as_secs() / decay_interval.as_secs()
 175         });
 176         penalty_msat >> decays
 177 }