+/// A [`Router`] implemented using [`find_route`].
+pub struct DefaultRouter<G: Deref<Target = NetworkGraph<L>>, L: Deref, S: Deref> where
+ L::Target: Logger,
+ S::Target: for <'a> LockableScore<'a>,
+{
+ network_graph: G,
+ logger: L,
+ random_seed_bytes: Mutex<[u8; 32]>,
+ scorer: S
+}
+
+impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, S: Deref> DefaultRouter<G, L, S> where
+ L::Target: Logger,
+ S::Target: for <'a> LockableScore<'a>,
+{
+ /// Creates a new router.
+ pub fn new(network_graph: G, logger: L, random_seed_bytes: [u8; 32], scorer: S) -> Self {
+ let random_seed_bytes = Mutex::new(random_seed_bytes);
+ Self { network_graph, logger, random_seed_bytes, scorer }
+ }
+}
+
+impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, S: Deref> Router for DefaultRouter<G, L, S> where
+ L::Target: Logger,
+ S::Target: for <'a> LockableScore<'a>,
+{
+ fn find_route(
+ &self, payer: &PublicKey, params: &RouteParameters, first_hops: Option<&[&ChannelDetails]>,
+ inflight_htlcs: &InFlightHtlcs
+ ) -> Result<Route, LightningError> {
+ let random_seed_bytes = {
+ let mut locked_random_seed_bytes = self.random_seed_bytes.lock().unwrap();
+ *locked_random_seed_bytes = Sha256::hash(&*locked_random_seed_bytes).into_inner();
+ *locked_random_seed_bytes
+ };
+
+ find_route(
+ payer, params, &self.network_graph, first_hops, &*self.logger,
+ &ScorerAccountingForInFlightHtlcs::new(self.scorer.lock(), inflight_htlcs),
+ &random_seed_bytes
+ )
+ }
+
+ fn notify_payment_path_failed(&self, path: &[&RouteHop], short_channel_id: u64) {
+ self.scorer.lock().payment_path_failed(path, short_channel_id);
+ }
+
+ fn notify_payment_path_successful(&self, path: &[&RouteHop]) {
+ self.scorer.lock().payment_path_successful(path);
+ }
+
+ fn notify_payment_probe_successful(&self, path: &[&RouteHop]) {
+ self.scorer.lock().probe_successful(path);
+ }
+
+ fn notify_payment_probe_failed(&self, path: &[&RouteHop], short_channel_id: u64) {
+ self.scorer.lock().probe_failed(path, short_channel_id);
+ }
+}
+
+/// A trait defining behavior for routing a payment.
+pub trait Router {
+ /// Finds a [`Route`] between `payer` and `payee` for a payment with the given values.
+ fn find_route(
+ &self, payer: &PublicKey, route_params: &RouteParameters,
+ first_hops: Option<&[&ChannelDetails]>, inflight_htlcs: &InFlightHtlcs
+ ) -> Result<Route, LightningError>;
+ /// Finds a [`Route`] between `payer` and `payee` for a payment with the given values. Includes
+ /// `PaymentHash` and `PaymentId` to be able to correlate the request with a specific payment.
+ fn find_route_with_id(
+ &self, payer: &PublicKey, route_params: &RouteParameters,
+ first_hops: Option<&[&ChannelDetails]>, inflight_htlcs: &InFlightHtlcs,
+ _payment_hash: PaymentHash, _payment_id: PaymentId
+ ) -> Result<Route, LightningError> {
+ self.find_route(payer, route_params, first_hops, inflight_htlcs)
+ }
+ /// Lets the router know that payment through a specific path has failed.
+ fn notify_payment_path_failed(&self, path: &[&RouteHop], short_channel_id: u64);
+ /// Lets the router know that payment through a specific path was successful.
+ fn notify_payment_path_successful(&self, path: &[&RouteHop]);
+ /// Lets the router know that a payment probe was successful.
+ fn notify_payment_probe_successful(&self, path: &[&RouteHop]);
+ /// Lets the router know that a payment probe failed.
+ fn notify_payment_probe_failed(&self, path: &[&RouteHop], short_channel_id: u64);
+}
+
+/// [`Score`] implementation that factors in in-flight HTLC liquidity.
+///
+/// Useful for custom [`Router`] implementations to wrap their [`Score`] on-the-fly when calling
+/// [`find_route`].
+///
+/// [`Score`]: crate::routing::scoring::Score
+pub struct ScorerAccountingForInFlightHtlcs<'a, S: Score> {
+ scorer: S,
+ // Maps a channel's short channel id and its direction to the liquidity used up.
+ inflight_htlcs: &'a InFlightHtlcs,
+}
+
+impl<'a, S: Score> ScorerAccountingForInFlightHtlcs<'a, S> {
+ /// Initialize a new `ScorerAccountingForInFlightHtlcs`.
+ pub fn new(scorer: S, inflight_htlcs: &'a InFlightHtlcs) -> Self {
+ ScorerAccountingForInFlightHtlcs {
+ scorer,
+ inflight_htlcs
+ }
+ }
+}
+
+#[cfg(c_bindings)]
+impl<'a, S: Score> Writeable for ScorerAccountingForInFlightHtlcs<'a, S> {
+ fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> { self.scorer.write(writer) }
+}
+
+impl<'a, S: Score> Score for ScorerAccountingForInFlightHtlcs<'a, S> {
+ fn channel_penalty_msat(&self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage) -> u64 {
+ if let Some(used_liquidity) = self.inflight_htlcs.used_liquidity_msat(
+ source, target, short_channel_id
+ ) {
+ let usage = ChannelUsage {
+ inflight_htlc_msat: usage.inflight_htlc_msat + used_liquidity,
+ ..usage
+ };
+
+ self.scorer.channel_penalty_msat(short_channel_id, source, target, usage)
+ } else {
+ self.scorer.channel_penalty_msat(short_channel_id, source, target, usage)
+ }
+ }
+
+ fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
+ self.scorer.payment_path_failed(path, short_channel_id)
+ }
+
+ fn payment_path_successful(&mut self, path: &[&RouteHop]) {
+ self.scorer.payment_path_successful(path)
+ }
+
+ fn probe_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
+ self.scorer.probe_failed(path, short_channel_id)
+ }
+
+ fn probe_successful(&mut self, path: &[&RouteHop]) {
+ self.scorer.probe_successful(path)
+ }
+}
+
+/// A data structure for tracking in-flight HTLCs. May be used during pathfinding to account for
+/// in-use channel liquidity.
+#[derive(Clone)]
+pub struct InFlightHtlcs(
+ // A map with liquidity value (in msat) keyed by a short channel id and the direction the HTLC
+ // is traveling in. The direction boolean is determined by checking if the HTLC source's public
+ // key is less than its destination. See `InFlightHtlcs::used_liquidity_msat` for more
+ // details.
+ HashMap<(u64, bool), u64>
+);
+
+impl InFlightHtlcs {
+ /// Constructs an empty `InFlightHtlcs`.
+ pub fn new() -> Self { InFlightHtlcs(HashMap::new()) }
+
+ /// Takes in a path with payer's node id and adds the path's details to `InFlightHtlcs`.
+ pub fn process_path(&mut self, path: &[RouteHop], payer_node_id: PublicKey) {
+ if path.is_empty() { return };
+ // total_inflight_map needs to be direction-sensitive when keeping track of the HTLC value
+ // that is held up. However, the `hops` array, which is a path returned by `find_route` in
+ // the router excludes the payer node. In the following lines, the payer's information is
+ // hardcoded with an inflight value of 0 so that we can correctly represent the first hop
+ // in our sliding window of two.
+ let reversed_hops_with_payer = path.iter().rev().skip(1)
+ .map(|hop| hop.pubkey)
+ .chain(core::iter::once(payer_node_id));
+ let mut cumulative_msat = 0;
+
+ // Taking the reversed vector from above, we zip it with just the reversed hops list to
+ // work "backwards" of the given path, since the last hop's `fee_msat` actually represents
+ // the total amount sent.
+ for (next_hop, prev_hop) in path.iter().rev().zip(reversed_hops_with_payer) {
+ cumulative_msat += next_hop.fee_msat;
+ self.0
+ .entry((next_hop.short_channel_id, NodeId::from_pubkey(&prev_hop) < NodeId::from_pubkey(&next_hop.pubkey)))
+ .and_modify(|used_liquidity_msat| *used_liquidity_msat += cumulative_msat)
+ .or_insert(cumulative_msat);
+ }
+ }
+
+ /// Returns liquidity in msat given the public key of the HTLC source, target, and short channel
+ /// id.
+ pub fn used_liquidity_msat(&self, source: &NodeId, target: &NodeId, channel_scid: u64) -> Option<u64> {
+ self.0.get(&(channel_scid, source < target)).map(|v| *v)
+ }
+}
+
+impl Writeable for InFlightHtlcs {
+ fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> { self.0.write(writer) }
+}
+
+impl Readable for InFlightHtlcs {
+ fn read<R: io::Read>(reader: &mut R) -> Result<Self, DecodeError> {
+ let infight_map: HashMap<(u64, bool), u64> = Readable::read(reader)?;
+ Ok(Self(infight_map))
+ }
+}
+