use bitcoin::secp256k1::key::PublicKey;
use ln::channelmanager::ChannelDetails;
-use ln::features::{ChannelFeatures, NodeFeatures};
+use ln::features::{ChannelFeatures, InvoiceFeatures, NodeFeatures};
use ln::msgs::{DecodeError, ErrorAction, LightningError, MAX_VALUE_MSAT};
use routing::network_graph::{NetworkGraph, RoutingFees};
use util::ser::{Writeable, Readable};
pub cltv_expiry_delta: u32,
}
+/// (C-not exported)
impl Writeable for Vec<RouteHop> {
fn write<W: ::util::ser::Writer>(&self, writer: &mut W) -> Result<(), ::std::io::Error> {
(self.len() as u8).write(writer)?;
}
}
+/// (C-not exported)
impl Readable for Vec<RouteHop> {
fn read<R: ::std::io::Read>(reader: &mut R) -> Result<Vec<RouteHop>, DecodeError> {
let hops_count: u8 = Readable::read(reader)?;
return result;
}
- // If an amount transferred by the path is updated, the fees should be adjusted. Any other way
- // to change fees may result in an inconsistency. Also, it's only safe to reduce the value,
- // to not violate channel upper bounds.
+ // 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.
fn update_value_and_recompute_fees(&mut self, value_msat: u64) {
- if value_msat == self.hops.last().unwrap().route_hop.fee_msat {
- // Nothing to change.
- return;
- }
- assert!(value_msat < self.hops.last().unwrap().route_hop.fee_msat);
+ assert!(value_msat <= self.hops.last().unwrap().route_hop.fee_msat);
let mut total_fee_paid_msat = 0 as u64;
for i in (0..self.hops.len()).rev() {
// match htlc_minimum_msat logic.
let mut cur_hop_transferred_amount_msat = total_fee_paid_msat + value_msat;
if let Some(extra_fees_msat) = cur_hop.htlc_minimum_msat.checked_sub(cur_hop_transferred_amount_msat) {
+ // Note that there is a risk that *previous hops* (those closer to us, as we go
+ // payee->our_node here) would exceed their htlc_maximum_msat or available balance.
+ //
+ // This might make us end up with a broken route, although this should be super-rare
+ // in practice, both because of how healthy channels look like, and how we pick
+ // channels in add_entry.
+ // Also, this can't be exploited more heavily than *announce a free path and fail
+ // all payments*.
cur_hop_transferred_amount_msat += extra_fees_msat;
total_fee_paid_msat += extra_fees_msat;
cur_hop_fees_msat += extra_fees_msat;
/// Gets a route from us (payer) to the given target node (payee).
///
+/// If the payee provided features in their invoice, they should be provided via payee_features.
+/// Without this, MPP will only be used if the payee's features are available in the network graph.
+///
/// Extra routing hops between known nodes and the target will be used if they are included in
/// last_hops.
///
/// The fees on channels from us to next-hops are ignored (as they are assumed to all be
/// 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, first_hops: Option<&[&ChannelDetails]>,
+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 {
// TODO: Obviously *only* using total fee cost sucks. We should consider weighting by
// uptime/success in using a node in the past.
const ROUTE_CAPACITY_PROVISION_FACTOR: u64 = 3;
let recommended_value_msat = final_value_msat * ROUTE_CAPACITY_PROVISION_FACTOR as u64;
+ // Allow MPP only if we have a features set from somewhere that indicates the payee supports
+ // it. If the payee supports it they're supposed to include it in the invoice, so that should
+ // work reliably.
+ let allow_mpp = if let Some(features) = &payee_features {
+ features.supports_basic_mpp()
+ } else if let Some(node) = network.get_nodes().get(&payee) {
+ if let Some(node_info) = node.announcement_info.as_ref() {
+ node_info.features.supports_basic_mpp()
+ } else { false }
+ } else { false };
+
// Step (1).
// Prepare the data we'll use for payee-to-payer search by
// inserting first hops suggested by the caller as targets.
// the absolute liquidity contribution is lowered,
// thus increasing the number of potential channels to be selected.
- // Derive the minimal liquidity contribution with a ratio of 20 (5%, rounded up).
- let minimal_value_contribution_msat: u64 = (recommended_value_msat - already_collected_value_msat + 19) / 20;
+ // Derive the minimal liquidity contribution with a ratio of 20 (5%, rounded up)
+ // or 100% if we're not allowed to do multipath payments.
+ let minimal_value_contribution_msat: u64 = if allow_mpp {
+ (recommended_value_msat - already_collected_value_msat + 19) / 20
+ } else {
+ final_value_msat
+ };
// Verify the liquidity offered by this channel complies to the minimal contribution.
let contributes_sufficient_value = available_value_contribution_msat >= minimal_value_contribution_msat;
// as not sufficient.
// TODO: Explore simply adding fee to hit htlc_minimum_msat
if contributes_sufficient_value && amount_to_transfer_over_msat >= $directional_info.htlc_minimum_msat {
+ // Note that low contribution here (limited by available_liquidity_msat)
+ // might violate htlc_minimum_msat on the hops which are next along the
+ // payment path (upstream to the payee). To avoid that, we recompute path
+ // path fees knowing the final path contribution after constructing it.
let hm_entry = dist.entry(&$src_node_id);
let old_entry = hm_entry.or_insert_with(|| {
// If there was previously no known way to access
ordered_hops.last_mut().unwrap().hop_use_fee_msat = 0;
ordered_hops.last_mut().unwrap().route_hop.cltv_expiry_delta = final_cltv;
- let payment_path = PaymentPath {hops: ordered_hops};
+ let mut payment_path = PaymentPath {hops: ordered_hops};
+
+ // We could have possibly constructed a slightly inconsistent path: since we reduce
+ // value being transferred along the way, we could have violated htlc_minimum_msat
+ // on some channels we already passed (assuming dest->source direction). Here, we
+ // recompute the fees again, so that if that's the case, we match the currently
+ // underpaid htlc_minimum_msat with fees.
+ payment_path.update_value_and_recompute_fees(value_contribution_msat);
+
// Since a path allows to transfer as much value as
// the smallest channel it has ("bottleneck"), we should recompute
// the fees so sender HTLC don't overpay fees when traversing
}
}
+ if !allow_mpp {
+ // If we don't support MPP, no use trying to gather more value ever.
+ break 'paths_collection;
+ }
+
// Step (3).
// Stop either when recommended value is reached,
// or if during last iteration no new path was found.
// TODO: this could also be optimized by also sorting by feerate_per_sat_routed,
// so that the sender pays less fees overall. And also htlc_minimum_msat.
cur_route.sort_by_key(|path| { path.hops.iter().map(|hop| hop.channel_fees.proportional_millionths as u64).sum::<u64>() });
- let mut expensive_payment_path = cur_route.first_mut().unwrap();
+ let expensive_payment_path = cur_route.first_mut().unwrap();
// We already dropped all the small channels above, meaning all the
// remaining channels are larger than remaining overpaid_value_msat.
// Thus, this can't be negative.
// Step (8).
// Select the best route by lowest total fee.
drawn_routes.sort_by_key(|paths| paths.iter().map(|path| path.get_total_fee_paid_msat()).sum::<u64>());
- let mut selected_paths = Vec::<Vec::<RouteHop>>::new();
+ let mut selected_paths = Vec::<Vec<RouteHop>>::new();
for payment_path in drawn_routes.first().unwrap() {
selected_paths.push(payment_path.hops.iter().map(|payment_hop| payment_hop.route_hop.clone()).collect());
}
+ if let Some(features) = &payee_features {
+ for path in selected_paths.iter_mut() {
+ path.last_mut().unwrap().node_features = features.to_context();
+ }
+ }
+
let route = Route { paths: selected_paths };
log_trace!(logger, "Got route: {}", log_route!(route));
- return Ok(route);
+ Ok(route)
}
#[cfg(test)]
mod tests {
use routing::router::{get_route, RouteHint, RoutingFees};
use routing::network_graph::{NetworkGraph, NetGraphMsgHandler};
- use ln::features::{ChannelFeatures, InitFeatures, NodeFeatures};
+ use ln::features::{ChannelFeatures, InitFeatures, InvoiceFeatures, NodeFeatures};
use ln::msgs::{ErrorAction, LightningError, OptionalField, UnsignedChannelAnnouncement, ChannelAnnouncement, RoutingMessageHandler,
NodeAnnouncement, UnsignedNodeAnnouncement, ChannelUpdate, UnsignedChannelUpdate};
use ln::channelmanager;
// Simple route to 2 via 1
- if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 0, 42, Arc::clone(&logger)) {
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 0, 42, Arc::clone(&logger)) {
assert_eq!(err, "Cannot send a payment of 0 msat");
} else { panic!(); }
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths[0].len(), 2);
assert_eq!(route.paths[0][0].pubkey, nodes[1]);
is_live: true,
}];
- if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 100, 42, Arc::clone(&logger)) {
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = 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)) {
assert_eq!(err, "First hop cannot have our_node_id as a destination.");
} else { panic!(); }
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths[0].len(), 2);
}
});
// Not possible to send 199_999_999, because the minimum on channel=2 is 200_000_000.
- if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 199_999_999, 42, Arc::clone(&logger)) {
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 199_999_999, 42, Arc::clone(&logger)) {
assert_eq!(err, "Failed to find a path to the given destination");
} else { panic!(); }
});
// A payment above the minimum should pass
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 199_999_999, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 199_999_999, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths[0].len(), 2);
}
excess_data: Vec::new()
});
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 60_000, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 60_000, 42, Arc::clone(&logger)).unwrap();
// Overpay fees to hit htlc_minimum_msat.
let overpaid_fees = route.paths[0][0].fee_msat + route.paths[1][0].fee_msat;
// TODO: this could be better balanced to overpay 10k and not 15k.
excess_data: Vec::new()
});
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 60_000, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 60_000, 42, Arc::clone(&logger)).unwrap();
// Fine to overpay for htlc_minimum_msat if it allows us to save fee.
assert_eq!(route.paths.len(), 1);
assert_eq!(route.paths[0][0].short_channel_id, 12);
let fees = route.paths[0][0].fee_msat;
assert_eq!(fees, 5_000);
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 50_000, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 50_000, 42, Arc::clone(&logger)).unwrap();
// Not fine to overpay for htlc_minimum_msat if it requires paying more than fee on
// the other channel.
assert_eq!(route.paths.len(), 1);
});
// If all the channels require some features we don't understand, route should fail
- if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 100, 42, Arc::clone(&logger)) {
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 100, 42, Arc::clone(&logger)) {
assert_eq!(err, "Failed to find a path to the given destination");
} else { panic!(); }
inbound_capacity_msat: 0,
is_live: true,
}];
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
+ 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].len(), 2);
assert_eq!(route.paths[0][0].pubkey, nodes[7]);
add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[7], unknown_features.clone(), 1);
// If all nodes require some features we don't understand, route should fail
- if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 100, 42, Arc::clone(&logger)) {
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 100, 42, Arc::clone(&logger)) {
assert_eq!(err, "Failed to find a path to the given destination");
} else { panic!(); }
inbound_capacity_msat: 0,
is_live: true,
}];
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
+ 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].len(), 2);
assert_eq!(route.paths[0][0].pubkey, nodes[7]);
let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
// Route to 1 via 2 and 3 because our channel to 1 is disabled
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[0], None, &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[0], None, None, &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths[0].len(), 3);
assert_eq!(route.paths[0][0].pubkey, nodes[1]);
inbound_capacity_msat: 0,
is_live: true,
}];
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
+ 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].len(), 2);
assert_eq!(route.paths[0][0].pubkey, nodes[7]);
let mut invalid_last_hops = last_hops(&nodes);
invalid_last_hops.push(invalid_last_hop);
{
- if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, &invalid_last_hops.iter().collect::<Vec<_>>(), 100, 42, Arc::clone(&logger)) {
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, None, &invalid_last_hops.iter().collect::<Vec<_>>(), 100, 42, Arc::clone(&logger)) {
assert_eq!(err, "Last hop cannot have a payee as a source.");
} else { panic!(); }
}
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, &last_hops(&nodes).iter().collect::<Vec<_>>(), 100, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, None, &last_hops(&nodes).iter().collect::<Vec<_>>(), 100, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths[0].len(), 5);
assert_eq!(route.paths[0][0].pubkey, nodes[1]);
is_live: true,
}];
let mut last_hops = last_hops(&nodes);
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], Some(&our_chans.iter().collect::<Vec<_>>()), &last_hops.iter().collect::<Vec<_>>(), 100, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, Some(&our_chans.iter().collect::<Vec<_>>()), &last_hops.iter().collect::<Vec<_>>(), 100, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths[0].len(), 2);
assert_eq!(route.paths[0][0].pubkey, nodes[3]);
last_hops[0].fees.base_msat = 1000;
// Revert to via 6 as the fee on 8 goes up
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, &last_hops.iter().collect::<Vec<_>>(), 100, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, None, &last_hops.iter().collect::<Vec<_>>(), 100, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths[0].len(), 4);
assert_eq!(route.paths[0][0].pubkey, nodes[1]);
assert_eq!(route.paths[0][3].channel_features.le_flags(), &Vec::<u8>::new()); // We can't learn any flags from invoices, sadly
// ...but still use 8 for larger payments as 6 has a variable feerate
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, &last_hops.iter().collect::<Vec<_>>(), 2000, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, None, &last_hops.iter().collect::<Vec<_>>(), 2000, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths[0].len(), 5);
assert_eq!(route.paths[0][0].pubkey, nodes[1]);
inbound_capacity_msat: 100000,
is_live: true,
}];
- let route = get_route(&source_node_id, &NetworkGraph::new(genesis_block(Network::Testnet).header.block_hash()), &target_node_id, Some(&our_chans.iter().collect::<Vec<_>>()), &last_hops.iter().collect::<Vec<_>>(), 100, 42, Arc::new(test_utils::TestLogger::new())).unwrap();
+ 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();
assert_eq!(route.paths[0].len(), 2);
{
// Attempt to route more than available results in a failure.
- if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 250_000_001, 42, Arc::clone(&logger)) {
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 250_000_001, 42, Arc::clone(&logger)) {
assert_eq!(err, "Failed to find a sufficient route to the given destination");
} else { panic!(); }
}
{
// Now, attempt to route an exact amount we have should be fine.
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 250_000_000, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 250_000_000, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths.len(), 1);
let path = route.paths.last().unwrap();
assert_eq!(path.len(), 2);
{
// Attempt to route more than available results in a failure.
- if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 200_000_001, 42, Arc::clone(&logger)) {
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 200_000_001, 42, Arc::clone(&logger)) {
assert_eq!(err, "Failed to find a sufficient route to the given destination");
} else { panic!(); }
}
{
// Now, attempt to route an exact amount we have should be fine.
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 200_000_000, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 200_000_000, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths.len(), 1);
let path = route.paths.last().unwrap();
assert_eq!(path.len(), 2);
{
// Attempt to route more than available results in a failure.
- if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 15_001, 42, Arc::clone(&logger)) {
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 15_001, 42, Arc::clone(&logger)) {
assert_eq!(err, "Failed to find a sufficient route to the given destination");
} else { panic!(); }
}
{
// Now, attempt to route an exact amount we have should be fine.
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 15_000, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 15_000, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths.len(), 1);
let path = route.paths.last().unwrap();
assert_eq!(path.len(), 2);
{
// Attempt to route more than available results in a failure.
- if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 15_001, 42, Arc::clone(&logger)) {
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 15_001, 42, Arc::clone(&logger)) {
assert_eq!(err, "Failed to find a sufficient route to the given destination");
} else { panic!(); }
}
{
// Now, attempt to route an exact amount we have should be fine.
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 15_000, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 15_000, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths.len(), 1);
let path = route.paths.last().unwrap();
assert_eq!(path.len(), 2);
{
// Attempt to route more than available results in a failure.
- if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 10_001, 42, Arc::clone(&logger)) {
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 10_001, 42, Arc::clone(&logger)) {
assert_eq!(err, "Failed to find a sufficient route to the given destination");
} else { panic!(); }
}
{
// Now, attempt to route an exact amount we have should be fine.
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 10_000, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 10_000, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths.len(), 1);
let path = route.paths.last().unwrap();
assert_eq!(path.len(), 2);
});
{
// Attempt to route more than available results in a failure.
- if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 60_000, 42, Arc::clone(&logger)) {
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 60_000, 42, Arc::clone(&logger)) {
assert_eq!(err, "Failed to find a sufficient route to the given destination");
} else { panic!(); }
}
{
// Now, attempt to route 49 sats (just a bit below the capacity).
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 49_000, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 49_000, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths.len(), 1);
let mut total_amount_paid_msat = 0;
for path in &route.paths {
{
// Attempt to route an exact amount is also fine
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 50_000, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 50_000, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths.len(), 1);
let mut total_amount_paid_msat = 0;
for path in &route.paths {
});
{
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 50_000, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 50_000, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths.len(), 1);
let mut total_amount_paid_msat = 0;
for path in &route.paths {
{
// Attempt to route more than available results in a failure.
- if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 300_000, 42, Arc::clone(&logger)) {
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(),
+ &nodes[2], Some(InvoiceFeatures::known()), None, &Vec::new(), 300_000, 42, Arc::clone(&logger)) {
assert_eq!(err, "Failed to find a sufficient route to the given destination");
} else { panic!(); }
}
{
// Now, attempt to route 250 sats (just a bit below the capacity).
// Our algorithm should provide us with these 3 paths.
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 250_000, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 250_000, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths.len(), 3);
let mut total_amount_paid_msat = 0;
for path in &route.paths {
{
// Attempt to route an exact amount is also fine
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 290_000, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 290_000, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths.len(), 3);
let mut total_amount_paid_msat = 0;
for path in &route.paths {
{
// Attempt to route more than available results in a failure.
- if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 350_000, 42, Arc::clone(&logger)) {
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 350_000, 42, Arc::clone(&logger)) {
assert_eq!(err, "Failed to find a sufficient route to the given destination");
} else { panic!(); }
}
{
// Now, attempt to route 300 sats (exact amount we can route).
// Our algorithm should provide us with these 3 paths, 100 sats each.
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 300_000, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 300_000, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths.len(), 3);
let mut total_amount_paid_msat = 0;
{
// Now, attempt to route 180 sats.
// Our algorithm should provide us with these 2 paths.
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 180_000, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 180_000, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths.len(), 2);
let mut total_value_transferred_msat = 0;
{
// Attempt to route more than available results in a failure.
- if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 210_000, 42, Arc::clone(&logger)) {
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 210_000, 42, Arc::clone(&logger)) {
assert_eq!(err, "Failed to find a sufficient route to the given destination");
} else { panic!(); }
}
{
// Now, attempt to route 200 sats (exact amount we can route).
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 200_000, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 200_000, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths.len(), 2);
let mut total_amount_paid_msat = 0;
{
// Attempt to route more than available results in a failure.
- if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 150_000, 42, Arc::clone(&logger)) {
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 150_000, 42, Arc::clone(&logger)) {
assert_eq!(err, "Failed to find a sufficient route to the given destination");
} else { panic!(); }
}
{
// Now, attempt to route 125 sats (just a bit below the capacity of 3 channels).
// Our algorithm should provide us with these 3 paths.
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 125_000, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 125_000, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths.len(), 3);
let mut total_amount_paid_msat = 0;
for path in &route.paths {
{
// Attempt to route without the last small cheap channel
- let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 90_000, 42, Arc::clone(&logger)).unwrap();
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 90_000, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths.len(), 2);
let mut total_amount_paid_msat = 0;
for path in &route.paths {
assert_eq!(total_amount_paid_msat, 90_000);
}
}
+}
+
+#[cfg(all(test, feature = "unstable"))]
+mod benches {
+ use super::*;
+ use util::logger::{Logger, Record};
+
+ use std::fs::File;
+ use test::Bencher;
+
+ struct DummyLogger {}
+ impl Logger for DummyLogger {
+ fn log(&self, _record: &Record) {}
+ }
+ #[bench]
+ fn generate_routes(bench: &mut Bencher) {
+ let mut d = File::open("net_graph-2021-02-12.bin").expect("Please fetch https://bitcoin.ninja/ldk-net_graph-879e309c128-2020-02-12.bin and place it at lightning/net_graph-2021-02-12.bin");
+ let graph = NetworkGraph::read(&mut d).unwrap();
+
+ // First, get 100 (source, destination) pairs for which route-getting actually succeeds...
+ let mut path_endpoints = Vec::new();
+ let mut seed: usize = 0xdeadbeef;
+ 'load_endpoints: for _ in 0..100 {
+ loop {
+ seed *= 0xdeadbeef;
+ let src = graph.get_nodes().keys().skip(seed % graph.get_nodes().len()).next().unwrap();
+ seed *= 0xdeadbeef;
+ let dst = graph.get_nodes().keys().skip(seed % graph.get_nodes().len()).next().unwrap();
+ let amt = seed as u64 % 1_000_000;
+ if get_route(src, &graph, dst, None, None, &[], amt, 42, &DummyLogger{}).is_ok() {
+ path_endpoints.push((src, dst, amt));
+ continue 'load_endpoints;
+ }
+ }
+ }
+
+ // ...then benchmark finding paths between the nodes we learned.
+ let mut idx = 0;
+ bench.iter(|| {
+ let (src, dst, amt) = path_endpoints[idx % path_endpoints.len()];
+ assert!(get_route(src, &graph, dst, None, None, &[], amt, 42, &DummyLogger{}).is_ok());
+ idx += 1;
+ });
+ }
}
projects / rust-lightning / blobdiff