}
/// A channel descriptor which provides a last-hop route to get_route
-#[derive(Clone)]
-pub struct RouteHint {
+#[derive(Eq, PartialEq, Debug, Clone)]
+pub struct RouteHintHop {
/// The node_id of the non-target end of the route
pub src_node_id: PublicKey,
/// The short_channel_id of this channel
/// These fee values are useful to choose hops as we traverse the graph "payee-to-payer".
#[derive(Clone)]
struct PathBuildingHop<'a> {
- // The RouteHint fields which will eventually be used if this hop is used in a final Route.
+ // The RouteHintHop fields which will eventually be used if this hop is used in a final Route.
// Note that node_features is calculated separately after our initial graph walk.
pubkey: PublicKey,
short_channel_id: u64,
// If the amount transferred by the path is updated, the fees should be adjusted. Any other way
// to change fees may result in an inconsistency.
//
- // Sometimes we call this function right after constructing a path which has inconsistent
- // (in terms of reaching htlc_minimum_msat), so that this function puts the fees in order.
- // In that case we call it on the "same" amount we initially allocated for this path, and which
- // could have been reduced on the way. In that case, there is also a risk of exceeding
- // available_liquidity inside this function, because the function is unaware of this bound.
- // In our specific recomputation cases where we never increase the value the risk is pretty low.
- // This function, however, does not support arbitrarily increasing the value being transferred,
- // and the exception will be triggered.
+ // Sometimes we call this function right after constructing a path which is inconsistent in
+ // that it the value being transferred has decreased while we were doing path finding, leading
+ // to the fees being paid not lining up with the actual limits.
+ //
+ // Note that this function is not aware of the available_liquidity limit, and thus does not
+ // support increasing the value being transferred.
fn update_value_and_recompute_fees(&mut self, value_msat: u64) {
assert!(value_msat <= self.hops.last().unwrap().0.fee_msat);
/// equal), however the enabled/disabled bit on such channels as well as the
/// htlc_minimum_msat/htlc_maximum_msat *are* checked as they may change based on the receiving node.
pub fn get_route<L: Deref>(our_node_id: &PublicKey, network: &NetworkGraph, payee: &PublicKey, payee_features: Option<InvoiceFeatures>, first_hops: Option<&[&ChannelDetails]>,
- last_hops: &[&RouteHint], final_value_msat: u64, final_cltv: u32, logger: L) -> Result<Route, LightningError> where L::Target: Logger {
+ last_hops: &[&RouteHintHop], final_value_msat: u64, final_cltv: u32, logger: L) -> Result<Route, LightningError> where L::Target: Logger {
// TODO: Obviously *only* using total fee cost sucks. We should consider weighting by
// uptime/success in using a node in the past.
if *payee == *our_node_id {
let empty_channel_features = ChannelFeatures::empty();
- let mut targets = BinaryHeap::new(); //TODO: Do we care about switching to eg Fibbonaci heap?
+ // The main heap containing all candidate next-hops sorted by their score (max(A* fee,
+ // htlc_minimum)). Ideally this would be a heap which allowed cheap score reduction instead of
+ // adding duplicate entries when we find a better path to a given node.
+ let mut targets = BinaryHeap::new();
+
+ // Map from node_id to information about the best current path to that node, including feerate
+ // information.
let mut dist = HashMap::with_capacity(network.get_nodes().len());
// During routing, if we ignore a path due to an htlc_minimum_msat limit, we set this,
let mut spent_on_hop_msat = value_contribution_msat;
let next_hops_fee_msat = payment_hop.next_hops_fee_msat;
spent_on_hop_msat += next_hops_fee_msat;
- if *channel_liquidity_available_msat < spent_on_hop_msat {
- // This should not happen because we do recompute fees right before,
- // 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.
#[cfg(test)]
mod tests {
- use routing::router::{get_route, RouteHint, RoutingFees};
+ use routing::router::{get_route, RouteHintHop, RoutingFees};
use routing::network_graph::{NetworkGraph, NetGraphMsgHandler};
+ use chain::transaction::OutPoint;
use ln::features::{ChannelFeatures, InitFeatures, InvoiceFeatures, NodeFeatures};
use ln::msgs::{ErrorAction, LightningError, OptionalField, UnsignedChannelAnnouncement, ChannelAnnouncement, RoutingMessageHandler,
NodeAnnouncement, UnsignedNodeAnnouncement, ChannelUpdate, UnsignedChannelUpdate};
let our_chans = vec![channelmanager::ChannelDetails {
channel_id: [0; 32],
+ funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
short_channel_id: Some(2),
remote_network_id: our_id,
counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
user_id: 0,
outbound_capacity_msat: 100000,
inbound_capacity_msat: 100000,
- is_live: true,
+ is_outbound: true, is_funding_locked: true,
+ is_live: true, is_public: true,
counterparty_forwarding_info: None,
}];
// If we specify a channel to node7, that overrides our local channel view and that gets used
let our_chans = vec![channelmanager::ChannelDetails {
channel_id: [0; 32],
+ funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
short_channel_id: Some(42),
remote_network_id: nodes[7].clone(),
counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
user_id: 0,
outbound_capacity_msat: 250_000_000,
inbound_capacity_msat: 0,
- is_live: true,
+ is_outbound: true, is_funding_locked: true,
+ is_live: true, is_public: true,
counterparty_forwarding_info: None,
}];
let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
// If we specify a channel to node7, that overrides our local channel view and that gets used
let our_chans = vec![channelmanager::ChannelDetails {
channel_id: [0; 32],
+ funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
short_channel_id: Some(42),
remote_network_id: nodes[7].clone(),
counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
user_id: 0,
outbound_capacity_msat: 250_000_000,
inbound_capacity_msat: 0,
- is_live: true,
+ is_outbound: true, is_funding_locked: true,
+ is_live: true, is_public: true,
counterparty_forwarding_info: None,
}];
let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
// If we specify a channel to node7, that overrides our local channel view and that gets used
let our_chans = vec![channelmanager::ChannelDetails {
channel_id: [0; 32],
+ funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
short_channel_id: Some(42),
remote_network_id: nodes[7].clone(),
counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
user_id: 0,
outbound_capacity_msat: 250_000_000,
inbound_capacity_msat: 0,
- is_live: true,
+ is_outbound: true, is_funding_locked: true,
+ is_live: true, is_public: true,
counterparty_forwarding_info: None,
}];
let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(13));
}
- fn last_hops(nodes: &Vec<PublicKey>) -> Vec<RouteHint> {
+ fn last_hops(nodes: &Vec<PublicKey>) -> Vec<RouteHintHop> {
let zero_fees = RoutingFees {
base_msat: 0,
proportional_millionths: 0,
};
- vec!(RouteHint {
+ vec!(RouteHintHop {
src_node_id: nodes[3].clone(),
short_channel_id: 8,
fees: zero_fees,
cltv_expiry_delta: (8 << 8) | 1,
htlc_minimum_msat: None,
htlc_maximum_msat: None,
- }, RouteHint {
+ }, RouteHintHop {
src_node_id: nodes[4].clone(),
short_channel_id: 9,
fees: RoutingFees {
cltv_expiry_delta: (9 << 8) | 1,
htlc_minimum_msat: None,
htlc_maximum_msat: None,
- }, RouteHint {
+ }, RouteHintHop {
src_node_id: nodes[5].clone(),
short_channel_id: 10,
fees: zero_fees,
// Simple test across 2, 3, 5, and 4 via a last_hop channel
// First check that lst hop can't have its source as the payee.
- let invalid_last_hop = RouteHint {
+ let invalid_last_hop = RouteHintHop {
src_node_id: nodes[6],
short_channel_id: 8,
fees: RoutingFees {
// Simple test with outbound channel to 4 to test that last_hops and first_hops connect
let our_chans = vec![channelmanager::ChannelDetails {
channel_id: [0; 32],
+ funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
short_channel_id: Some(42),
remote_network_id: nodes[3].clone(),
counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
user_id: 0,
outbound_capacity_msat: 250_000_000,
inbound_capacity_msat: 0,
- is_live: true,
+ is_outbound: true, is_funding_locked: true,
+ is_live: true, is_public: true,
counterparty_forwarding_info: None,
}];
let mut last_hops = last_hops(&nodes);
let target_node_id = PublicKey::from_secret_key(&Secp256k1::new(), &SecretKey::from_slice(&hex::decode(format!("{:02}", 43).repeat(32)).unwrap()[..]).unwrap());
// If we specify a channel to a middle hop, that overrides our local channel view and that gets used
- let last_hops = vec![RouteHint {
+ let last_hops = vec![RouteHintHop {
src_node_id: middle_node_id,
short_channel_id: 8,
fees: RoutingFees {
}];
let our_chans = vec![channelmanager::ChannelDetails {
channel_id: [0; 32],
+ funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
short_channel_id: Some(42),
remote_network_id: middle_node_id,
counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
user_id: 0,
outbound_capacity_msat: 100000,
inbound_capacity_msat: 100000,
- is_live: true,
+ is_outbound: true, is_funding_locked: true,
+ is_live: true, is_public: true,
counterparty_forwarding_info: None,
}];
let route = get_route(&source_node_id, &NetworkGraph::new(genesis_block(Network::Testnet).header.block_hash()), &target_node_id, None, Some(&our_chans.iter().collect::<Vec<_>>()), &last_hops.iter().collect::<Vec<_>>(), 100, 42, Arc::new(test_utils::TestLogger::new())).unwrap();
// Now, limit the first_hop by the outbound_capacity_msat of 200_000 sats.
let our_chans = vec![channelmanager::ChannelDetails {
channel_id: [0; 32],
+ funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
short_channel_id: Some(42),
remote_network_id: nodes[0].clone(),
counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
user_id: 0,
outbound_capacity_msat: 200_000_000,
inbound_capacity_msat: 0,
- is_live: true,
+ is_outbound: true, is_funding_locked: true,
+ is_live: true, is_public: true,
counterparty_forwarding_info: None,
}];
});
#[cfg(require_route_graph_test)]
return Ok(res.expect("Didn't have route graph and was configured to require it"));
- res
+ #[cfg(not(require_route_graph_test))]
+ return res;
}
pub(super) fn random_init_seed() -> u64 {
use super::*;
use util::logger::{Logger, Record};
- use std::fs::File;
use test::Bencher;
struct DummyLogger {}