X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Fscorer.rs;h=8b5fae70abdbffa34e6a365f312eb654f5165d84;hb=e3bdfa0585b9900cd732d568169a3778005be523;hp=e3f5c8679b68d6b57ca418b70befdc0ff34e35d7;hpb=2d102a3065d7a438d5c88fffcad36545a0822bfa;p=rust-lightning diff --git a/lightning/src/routing/scorer.rs b/lightning/src/routing/scorer.rs index e3f5c867..8b5fae70 100644 --- a/lightning/src/routing/scorer.rs +++ b/lightning/src/routing/scorer.rs @@ -19,7 +19,7 @@ //! # //! # use lightning::routing::network_graph::NetworkGraph; //! # use lightning::routing::router::{RouteParameters, find_route}; -//! # use lightning::routing::scorer::Scorer; +//! # use lightning::routing::scorer::{Scorer, ScoringParameters}; //! # use lightning::util::logger::{Logger, Record}; //! # use secp256k1::key::PublicKey; //! # @@ -30,52 +30,293 @@ //! # fn find_scored_route(payer: PublicKey, params: RouteParameters, network_graph: NetworkGraph) { //! # let logger = FakeLogger {}; //! # -//! // Use the default channel penalty. +//! // Use the default channel penalties. //! let scorer = Scorer::default(); //! -//! // Or use a custom channel penalty. -//! let scorer = Scorer::new(1_000); +//! // Or use custom channel penalties. +//! let scorer = Scorer::new(ScoringParameters { +//! base_penalty_msat: 1000, +//! failure_penalty_msat: 2 * 1024 * 1000, +//! ..ScoringParameters::default() +//! }); //! //! let route = find_route(&payer, ¶ms, &network_graph, None, &logger, &scorer); //! # } //! ``` //! +//! # Note +//! +//! If persisting [`Scorer`], it must be restored using the same [`Time`] parameterization. Using a +//! different type results in undefined behavior. Specifically, persisting when built with feature +//! `no-std` and restoring without it, or vice versa, uses different types and thus is undefined. +//! //! [`find_route`]: crate::routing::router::find_route use routing; +use ln::msgs::DecodeError; use routing::network_graph::NodeId; +use routing::router::RouteHop; +use util::ser::{Readable, Writeable, Writer}; + +use prelude::*; +use core::ops::Sub; +use core::time::Duration; +use io::{self, Read}; /// [`routing::Score`] implementation that provides reasonable default behavior. /// /// Used to apply a fixed penalty to each channel, thus avoiding long paths when shorter paths with -/// slightly higher fees are available. +/// slightly higher fees are available. Will further penalize channels that fail to relay payments. /// /// See [module-level documentation] for usage. /// /// [module-level documentation]: crate::routing::scorer -pub struct Scorer { - base_penalty_msat: u64, +pub type Scorer = ScorerUsingTime::; + +/// Time used by [`Scorer`]. +#[cfg(not(feature = "no-std"))] +pub type DefaultTime = std::time::Instant; + +/// Time used by [`Scorer`]. +#[cfg(feature = "no-std")] +pub type DefaultTime = Eternity; + +/// [`routing::Score`] implementation parameterized by [`Time`]. +/// +/// See [`Scorer`] for details. +/// +/// # Note +/// +/// Mixing [`Time`] types between serialization and deserialization results in undefined behavior. +pub struct ScorerUsingTime { + params: ScoringParameters, + // TODO: Remove entries of closed channels. + channel_failures: HashMap>, +} + +/// Parameters for configuring [`Scorer`]. +pub struct ScoringParameters { + /// A fixed penalty in msats to apply to each channel. + pub base_penalty_msat: u64, + + /// A penalty in msats to apply to a channel upon failing to relay a payment. + /// + /// This accumulates for each failure but may be reduced over time based on + /// [`failure_penalty_half_life`]. + /// + /// [`failure_penalty_half_life`]: Self::failure_penalty_half_life + pub failure_penalty_msat: u64, + + /// The time required to elapse before any accumulated [`failure_penalty_msat`] penalties are + /// cut in half. + /// + /// # Note + /// + /// When time is an [`Eternity`], as is default when enabling feature `no-std`, it will never + /// elapse. Therefore, this penalty will never decay. + /// + /// [`failure_penalty_msat`]: Self::failure_penalty_msat + pub failure_penalty_half_life: Duration, +} + +impl_writeable_tlv_based!(ScoringParameters, { + (0, base_penalty_msat, required), + (2, failure_penalty_msat, required), + (4, failure_penalty_half_life, required), +}); + +/// Accounting for penalties against a channel for failing to relay any payments. +/// +/// Penalties decay over time, though accumulate as more failures occur. +struct ChannelFailure { + /// Accumulated penalty in msats for the channel as of `last_failed`. + undecayed_penalty_msat: u64, + + /// Last time the channel failed. Used to decay `undecayed_penalty_msat`. + last_failed: T, } -impl Scorer { - /// Creates a new scorer using `base_penalty_msat` as the channel penalty. - pub fn new(base_penalty_msat: u64) -> Self { - Self { base_penalty_msat } +/// A measurement of time. +pub trait Time: Sub where Self: Sized { + /// Returns an instance corresponding to the current moment. + fn now() -> Self; + + /// Returns the amount of time elapsed since `self` was created. + fn elapsed(&self) -> Duration; + + /// Returns the amount of time passed since the beginning of [`Time`]. + /// + /// Used during (de-)serialization. + fn duration_since_epoch() -> Duration; +} + +impl ScorerUsingTime { + /// Creates a new scorer using the given scoring parameters. + pub fn new(params: ScoringParameters) -> Self { + Self { + params, + channel_failures: HashMap::new(), + } + } + + /// Creates a new scorer using `penalty_msat` as a fixed channel penalty. + #[cfg(any(test, feature = "fuzztarget", feature = "_test_utils"))] + pub fn with_fixed_penalty(penalty_msat: u64) -> Self { + Self::new(ScoringParameters { + base_penalty_msat: penalty_msat, + failure_penalty_msat: 0, + failure_penalty_half_life: Duration::from_secs(0), + }) + } +} + +impl ChannelFailure { + fn new(failure_penalty_msat: u64) -> Self { + Self { + undecayed_penalty_msat: failure_penalty_msat, + last_failed: T::now(), + } + } + + fn add_penalty(&mut self, failure_penalty_msat: u64, half_life: Duration) { + self.undecayed_penalty_msat = self.decayed_penalty_msat(half_life) + failure_penalty_msat; + self.last_failed = T::now(); + } + + fn decayed_penalty_msat(&self, half_life: Duration) -> u64 { + let decays = self.last_failed.elapsed().as_secs().checked_div(half_life.as_secs()); + match decays { + Some(decays) => self.undecayed_penalty_msat >> decays, + None => 0, + } + } +} + +impl Default for ScorerUsingTime { + fn default() -> Self { + Self::new(ScoringParameters::default()) } } -impl Default for Scorer { - /// Creates a new scorer using 500 msat as the channel penalty. +impl Default for ScoringParameters { fn default() -> Self { - Scorer::new(500) + Self { + base_penalty_msat: 500, + failure_penalty_msat: 1024 * 1000, + failure_penalty_half_life: Duration::from_secs(3600), + } } } -impl routing::Score for Scorer { +impl routing::Score for ScorerUsingTime { fn channel_penalty_msat( - &self, _short_channel_id: u64, _source: &NodeId, _target: &NodeId + &self, short_channel_id: u64, _source: &NodeId, _target: &NodeId ) -> u64 { - self.base_penalty_msat + let failure_penalty_msat = self.channel_failures + .get(&short_channel_id) + .map_or(0, |value| value.decayed_penalty_msat(self.params.failure_penalty_half_life)); + + self.params.base_penalty_msat + failure_penalty_msat + } + + fn payment_path_failed(&mut self, _path: &[&RouteHop], short_channel_id: u64) { + let failure_penalty_msat = self.params.failure_penalty_msat; + let half_life = self.params.failure_penalty_half_life; + self.channel_failures + .entry(short_channel_id) + .and_modify(|failure| failure.add_penalty(failure_penalty_msat, half_life)) + .or_insert_with(|| ChannelFailure::new(failure_penalty_msat)); + } +} + +#[cfg(not(feature = "no-std"))] +impl Time for std::time::Instant { + fn now() -> Self { + std::time::Instant::now() + } + + fn duration_since_epoch() -> Duration { + use std::time::SystemTime; + SystemTime::now().duration_since(SystemTime::UNIX_EPOCH).unwrap() + } + + fn elapsed(&self) -> Duration { + std::time::Instant::elapsed(self) + } +} + +/// A state in which time has no meaning. +pub struct Eternity; + +impl Time for Eternity { + fn now() -> Self { + Self + } + + fn duration_since_epoch() -> Duration { + Duration::from_secs(0) + } + + fn elapsed(&self) -> Duration { + Duration::from_secs(0) + } +} + +impl Sub for Eternity { + type Output = Self; + + fn sub(self, _other: Duration) -> Self { + self + } +} + +impl Writeable for ScorerUsingTime { + #[inline] + fn write(&self, w: &mut W) -> Result<(), io::Error> { + self.params.write(w)?; + self.channel_failures.write(w)?; + write_tlv_fields!(w, {}); + Ok(()) + } +} + +impl Readable for ScorerUsingTime { + #[inline] + fn read(r: &mut R) -> Result { + let res = Ok(Self { + params: Readable::read(r)?, + channel_failures: Readable::read(r)?, + }); + read_tlv_fields!(r, {}); + res + } +} + +impl Writeable for ChannelFailure { + #[inline] + fn write(&self, w: &mut W) -> Result<(), io::Error> { + let duration_since_epoch = T::duration_since_epoch() - self.last_failed.elapsed(); + write_tlv_fields!(w, { + (0, self.undecayed_penalty_msat, required), + (2, duration_since_epoch, required), + }); + Ok(()) + } +} + +impl Readable for ChannelFailure { + #[inline] + fn read(r: &mut R) -> Result { + let mut undecayed_penalty_msat = 0; + let mut duration_since_epoch = Duration::from_secs(0); + read_tlv_fields!(r, { + (0, undecayed_penalty_msat, required), + (2, duration_since_epoch, required), + }); + Ok(Self { + undecayed_penalty_msat, + last_failed: T::now() - (T::duration_since_epoch() - duration_since_epoch), + }) } }