X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=45dab242675c498e8003c5cdafe373c0f4569d40;hb=a3c2dfdcbc71b6eb28a2d84da7d6a0dee1e0fd98;hp=ad0f63f136eaac1392404bb52ddaac82ab8874d9;hpb=1aaf5fc5d01837b6c31a3f03cca5f7f811759207;p=rust-lightning diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index ad0f63f1..45dab242 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -423,7 +423,7 @@ impl<'a> CandidateRouteHop<'a> { /// so that we can choose cheaper paths (as per Dijkstra's algorithm). /// Fee values should be updated only in the context of the whole path, see update_value_and_recompute_fees. /// These fee values are useful to choose hops as we traverse the graph "payee-to-payer". -#[derive(Clone, Debug)] +#[derive(Clone)] struct PathBuildingHop<'a> { // Note that this should be dropped in favor of loading it from CandidateRouteHop, but doing so // is a larger refactor and will require careful performance analysis. @@ -463,6 +463,22 @@ struct PathBuildingHop<'a> { value_contribution_msat: u64, } +impl<'a> core::fmt::Debug for PathBuildingHop<'a> { + fn fmt(&self, f: &mut core::fmt::Formatter) -> Result<(), core::fmt::Error> { + f.debug_struct("PathBuildingHop") + .field("node_id", &self.node_id) + .field("short_channel_id", &self.candidate.short_channel_id()) + .field("total_fee_msat", &self.total_fee_msat) + .field("next_hops_fee_msat", &self.next_hops_fee_msat) + .field("hop_use_fee_msat", &self.hop_use_fee_msat) + .field("total_fee_msat - (next_hops_fee_msat + hop_use_fee_msat)", &(&self.total_fee_msat - (&self.next_hops_fee_msat + &self.hop_use_fee_msat))) + .field("path_penalty_msat", &self.path_penalty_msat) + .field("path_htlc_minimum_msat", &self.path_htlc_minimum_msat) + .field("cltv_expiry_delta", &self.candidate.cltv_expiry_delta()) + .finish() + } +} + // Instantiated with a list of hops with correct data in them collected during path finding, // an instance of this struct should be further modified only via given methods. #[derive(Clone)] @@ -1299,8 +1315,8 @@ where L::Target: Logger { ordered_hops.last_mut().unwrap().0.fee_msat = value_contribution_msat; ordered_hops.last_mut().unwrap().0.hop_use_fee_msat = 0; - log_trace!(logger, "Found a path back to us from the target with {} hops contributing up to {} msat: {:?}", - ordered_hops.len(), value_contribution_msat, ordered_hops); + log_trace!(logger, "Found a path back to us from the target with {} hops contributing up to {} msat: \n {:#?}", + ordered_hops.len(), value_contribution_msat, ordered_hops.iter().map(|h| &(h.0)).collect::>()); let mut payment_path = PaymentPath {hops: ordered_hops}; @@ -1522,7 +1538,7 @@ where L::Target: Logger { #[cfg(test)] mod tests { - use routing::scoring::Score; + use routing::scoring::{ProbabilisticScorer, ProbabilisticScoringParameters, Score}; use routing::network_graph::{NetworkGraph, NetGraphMsgHandler, NodeId}; use routing::router::{get_route, PaymentParameters, Route, RouteHint, RouteHintHop, RouteHop, RoutingFees}; use chain::transaction::OutPoint; @@ -1997,7 +2013,7 @@ mod tests { let (secp_ctx, network_graph, _, _, logger) = build_graph(); let (_, our_id, _, nodes) = get_nodes(&secp_ctx); let payment_params = PaymentParameters::from_node_id(nodes[2]); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); // Simple route to 2 via 1 @@ -2028,7 +2044,7 @@ mod tests { let (secp_ctx, network_graph, _, _, logger) = build_graph(); let (_, our_id, _, nodes) = get_nodes(&secp_ctx); let payment_params = PaymentParameters::from_node_id(nodes[2]); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); // Simple route to 2 via 1 @@ -2047,7 +2063,7 @@ mod tests { let (secp_ctx, network_graph, net_graph_msg_handler, _, logger) = build_graph(); let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx); let payment_params = PaymentParameters::from_node_id(nodes[2]); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); // Simple route to 2 via 1 @@ -2172,7 +2188,7 @@ mod tests { let (secp_ctx, network_graph, net_graph_msg_handler, _, logger) = build_graph(); let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx); let payment_params = PaymentParameters::from_node_id(nodes[2]).with_features(InvoiceFeatures::known()); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); // A route to node#2 via two paths. // One path allows transferring 35-40 sats, another one also allows 35-40 sats. @@ -2308,7 +2324,7 @@ mod tests { let (secp_ctx, network_graph, net_graph_msg_handler, _, logger) = build_graph(); let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx); let payment_params = PaymentParameters::from_node_id(nodes[2]); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); // // Disable channels 4 and 12 by flags=2 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[1], UnsignedChannelUpdate { @@ -2366,7 +2382,7 @@ mod tests { let (secp_ctx, network_graph, net_graph_msg_handler, _, logger) = build_graph(); let (_, our_id, privkeys, nodes) = get_nodes(&secp_ctx); let payment_params = PaymentParameters::from_node_id(nodes[2]); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); // Disable nodes 1, 2, and 8 by requiring unknown feature bits let unknown_features = NodeFeatures::known().set_unknown_feature_required(); @@ -2407,7 +2423,7 @@ mod tests { fn our_chans_test() { let (secp_ctx, network_graph, _, _, logger) = build_graph(); let (_, our_id, _, nodes) = get_nodes(&secp_ctx); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); // Route to 1 via 2 and 3 because our channel to 1 is disabled let payment_params = PaymentParameters::from_node_id(nodes[0]); @@ -2536,7 +2552,7 @@ mod tests { fn partial_route_hint_test() { let (secp_ctx, network_graph, _, _, logger) = build_graph(); let (_, our_id, _, nodes) = get_nodes(&secp_ctx); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); // Simple test across 2, 3, 5, and 4 via a last_hop channel // Tests the behaviour when the RouteHint contains a suboptimal hop. @@ -2635,7 +2651,7 @@ mod tests { let (secp_ctx, network_graph, _, _, logger) = build_graph(); let (_, our_id, _, nodes) = get_nodes(&secp_ctx); let payment_params = PaymentParameters::from_node_id(nodes[6]).with_route_hints(empty_last_hop(&nodes)); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); // Test handling of an empty RouteHint passed in Invoice. @@ -2717,7 +2733,7 @@ mod tests { let (secp_ctx, network_graph, net_graph_msg_handler, _, logger) = build_graph(); let (_, our_id, privkeys, nodes) = get_nodes(&secp_ctx); let payment_params = PaymentParameters::from_node_id(nodes[6]).with_route_hints(multi_hint_last_hops(&nodes)); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); // Test through channels 2, 3, 5, 8. // Test shows that multiple hop hints are considered. @@ -2823,7 +2839,7 @@ mod tests { let (secp_ctx, network_graph, _, _, logger) = build_graph(); let (_, our_id, _, nodes) = get_nodes(&secp_ctx); let payment_params = PaymentParameters::from_node_id(nodes[6]).with_route_hints(last_hops_with_public_channel(&nodes)); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); // This test shows that public routes can be present in the invoice // which would be handled in the same manner. @@ -2872,7 +2888,7 @@ mod tests { fn our_chans_last_hop_connect_test() { let (secp_ctx, network_graph, _, _, logger) = build_graph(); let (_, our_id, _, nodes) = get_nodes(&secp_ctx); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); // Simple test with outbound channel to 4 to test that last_hops and first_hops connect let our_chans = vec![get_channel_details(Some(42), nodes[3].clone(), InitFeatures::from_le_bytes(vec![0b11]), 250_000_000)]; @@ -2993,7 +3009,7 @@ mod tests { }]); let payment_params = PaymentParameters::from_node_id(target_node_id).with_route_hints(vec![last_hops]); let our_chans = vec![get_channel_details(Some(42), middle_node_id, InitFeatures::from_le_bytes(vec![0b11]), outbound_capacity_msat)]; - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); get_route(&source_node_id, &payment_params, &NetworkGraph::new(genesis_block(Network::Testnet).header.block_hash()), Some(&our_chans.iter().collect::>()), route_val, 42, &test_utils::TestLogger::new(), &scorer) } @@ -3047,7 +3063,7 @@ mod tests { let (secp_ctx, network_graph, mut net_graph_msg_handler, chain_monitor, logger) = build_graph(); let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); let payment_params = PaymentParameters::from_node_id(nodes[2]).with_features(InvoiceFeatures::known()); // We will use a simple single-path route from @@ -3319,7 +3335,7 @@ mod tests { // one of the latter hops is limited. let (secp_ctx, network_graph, net_graph_msg_handler, _, logger) = build_graph(); let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); let payment_params = PaymentParameters::from_node_id(nodes[3]).with_features(InvoiceFeatures::known()); // Path via {node7, node2, node4} is channels {12, 13, 6, 11}. @@ -3442,7 +3458,7 @@ mod tests { fn ignore_fee_first_hop_test() { let (secp_ctx, network_graph, net_graph_msg_handler, _, logger) = build_graph(); let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); let payment_params = PaymentParameters::from_node_id(nodes[2]); // Path via node0 is channels {1, 3}. Limit them to 100 and 50 sats (total limit 50). @@ -3488,7 +3504,7 @@ mod tests { fn simple_mpp_route_test() { let (secp_ctx, network_graph, net_graph_msg_handler, _, logger) = build_graph(); let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); let payment_params = PaymentParameters::from_node_id(nodes[2]).with_features(InvoiceFeatures::known()); // We need a route consisting of 3 paths: @@ -3619,7 +3635,7 @@ mod tests { fn long_mpp_route_test() { let (secp_ctx, network_graph, net_graph_msg_handler, _, logger) = build_graph(); let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); let payment_params = PaymentParameters::from_node_id(nodes[3]).with_features(InvoiceFeatures::known()); // We need a route consisting of 3 paths: @@ -3781,7 +3797,7 @@ mod tests { fn mpp_cheaper_route_test() { let (secp_ctx, network_graph, net_graph_msg_handler, _, logger) = build_graph(); let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); let payment_params = PaymentParameters::from_node_id(nodes[3]).with_features(InvoiceFeatures::known()); // This test checks that if we have two cheaper paths and one more expensive path, @@ -3948,7 +3964,7 @@ mod tests { // if the fee is not properly accounted for, the behavior is different. let (secp_ctx, network_graph, net_graph_msg_handler, _, logger) = build_graph(); let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); let payment_params = PaymentParameters::from_node_id(nodes[3]).with_features(InvoiceFeatures::known()); // We need a route consisting of 2 paths: @@ -4127,7 +4143,7 @@ mod tests { // This bug appeared in production in some specific channel configurations. let (secp_ctx, network_graph, net_graph_msg_handler, _, logger) = build_graph(); let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); let payment_params = PaymentParameters::from_node_id(PublicKey::from_slice(&[02; 33]).unwrap()).with_features(InvoiceFeatures::known()) .with_route_hints(vec![RouteHint(vec![RouteHintHop { src_node_id: nodes[2], @@ -4215,7 +4231,7 @@ mod tests { // path finding we realize that we found more capacity than we need. let (secp_ctx, network_graph, net_graph_msg_handler, _, logger) = build_graph(); let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); let payment_params = PaymentParameters::from_node_id(nodes[2]).with_features(InvoiceFeatures::known()); // We need a route consisting of 3 paths: @@ -4372,7 +4388,7 @@ mod tests { let network_graph = Arc::new(NetworkGraph::new(genesis_block(Network::Testnet).header.block_hash())); let net_graph_msg_handler = NetGraphMsgHandler::new(Arc::clone(&network_graph), None, Arc::clone(&logger)); let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); let payment_params = PaymentParameters::from_node_id(nodes[6]); add_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, &privkeys[1], ChannelFeatures::from_le_bytes(id_to_feature_flags(6)), 6); @@ -4501,7 +4517,7 @@ mod tests { // we calculated fees on a higher value, resulting in us ignoring such paths. let (secp_ctx, network_graph, net_graph_msg_handler, _, logger) = build_graph(); let (our_privkey, our_id, _, nodes) = get_nodes(&secp_ctx); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); let payment_params = PaymentParameters::from_node_id(nodes[2]); // We modify the graph to set the htlc_maximum of channel 2 to below the value we wish to @@ -4563,7 +4579,7 @@ mod tests { // resulting in us thinking there is no possible path, even if other paths exist. let (secp_ctx, network_graph, net_graph_msg_handler, _, logger) = build_graph(); let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); let payment_params = PaymentParameters::from_node_id(nodes[2]).with_features(InvoiceFeatures::known()); // We modify the graph to set the htlc_minimum of channel 2 and 4 as needed - channel 2 @@ -4630,7 +4646,7 @@ mod tests { let (_, our_id, _, nodes) = get_nodes(&secp_ctx); let logger = Arc::new(test_utils::TestLogger::new()); let network_graph = NetworkGraph::new(genesis_block(Network::Testnet).header.block_hash()); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); let payment_params = PaymentParameters::from_node_id(nodes[0]).with_features(InvoiceFeatures::known()); { @@ -4671,7 +4687,7 @@ mod tests { let payment_params = PaymentParameters::from_node_id(nodes[6]).with_route_hints(last_hops(&nodes)); // Without penalizing each hop 100 msats, a longer path with lower fees is chosen. - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); let route = get_route( &our_id, &payment_params, &network_graph, None, 100, 42, Arc::clone(&logger), &scorer @@ -4684,7 +4700,7 @@ mod tests { // Applying a 100 msat penalty to each hop results in taking channels 7 and 10 to nodes[6] // from nodes[2] rather than channel 6, 11, and 8, even though the longer path is cheaper. - let scorer = test_utils::TestScorer::with_fixed_penalty(100); + let scorer = test_utils::TestScorer::with_penalty(100); let route = get_route( &our_id, &payment_params, &network_graph, None, 100, 42, Arc::clone(&logger), &scorer @@ -4738,7 +4754,7 @@ mod tests { let payment_params = PaymentParameters::from_node_id(nodes[6]).with_route_hints(last_hops(&nodes)); // A path to nodes[6] exists when no penalties are applied to any channel. - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); let route = get_route( &our_id, &payment_params, &network_graph, None, 100, 42, Arc::clone(&logger), &scorer @@ -4850,7 +4866,7 @@ mod tests { let (secp_ctx, network_graph, _, _, logger) = build_graph(); let (_, our_id, _, nodes) = get_nodes(&secp_ctx); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); + let scorer = test_utils::TestScorer::with_penalty(0); // Make sure that generally there is at least one route available let feasible_max_total_cltv_delta = 1008; @@ -4895,7 +4911,6 @@ mod tests { }, }; let graph = NetworkGraph::read(&mut d).unwrap(); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); // First, get 100 (source, destination) pairs for which route-getting actually succeeds... let mut seed = random_init_seed() as usize; @@ -4908,6 +4923,8 @@ mod tests { let dst = PublicKey::from_slice(nodes.keys().skip(seed % nodes.len()).next().unwrap().as_slice()).unwrap(); let payment_params = PaymentParameters::from_node_id(dst); let amt = seed as u64 % 200_000_000; + let params = ProbabilisticScoringParameters::default(); + let scorer = ProbabilisticScorer::new(params, &graph); if get_route(src, &payment_params, &graph, None, amt, 42, &test_utils::TestLogger::new(), &scorer).is_ok() { continue 'load_endpoints; } @@ -4926,7 +4943,6 @@ mod tests { }, }; let graph = NetworkGraph::read(&mut d).unwrap(); - let scorer = test_utils::TestScorer::with_fixed_penalty(0); // First, get 100 (source, destination) pairs for which route-getting actually succeeds... let mut seed = random_init_seed() as usize; @@ -4939,6 +4955,8 @@ mod tests { let dst = PublicKey::from_slice(nodes.keys().skip(seed % nodes.len()).next().unwrap().as_slice()).unwrap(); let payment_params = PaymentParameters::from_node_id(dst).with_features(InvoiceFeatures::known()); let amt = seed as u64 % 200_000_000; + let params = ProbabilisticScoringParameters::default(); + let scorer = ProbabilisticScorer::new(params, &graph); if get_route(src, &payment_params, &graph, None, amt, 42, &test_utils::TestLogger::new(), &scorer).is_ok() { continue 'load_endpoints; } @@ -4982,7 +5000,7 @@ mod benches { use chain::transaction::OutPoint; use ln::channelmanager::{ChannelCounterparty, ChannelDetails}; use ln::features::{InitFeatures, InvoiceFeatures}; - use routing::scoring::Scorer; + use routing::scoring::{FixedPenaltyScorer, ProbabilisticScorer, ProbabilisticScoringParameters, Scorer}; use util::logger::{Logger, Record}; use test::Bencher; @@ -4992,15 +5010,6 @@ mod benches { fn log(&self, _record: &Record) {} } - struct ZeroPenaltyScorer; - impl Score for ZeroPenaltyScorer { - fn channel_penalty_msat( - &self, _short_channel_id: u64, _send_amt: u64, _capacity_msat: u64, _source: &NodeId, _target: &NodeId - ) -> u64 { 0 } - fn payment_path_failed(&mut self, _path: &[&RouteHop], _short_channel_id: u64) {} - fn payment_path_successful(&mut self, _path: &[&RouteHop]) {} - } - fn read_network_graph() -> NetworkGraph { let mut d = test_utils::get_route_file().unwrap(); NetworkGraph::read(&mut d).unwrap() @@ -5043,14 +5052,14 @@ mod benches { #[bench] fn generate_routes_with_zero_penalty_scorer(bench: &mut Bencher) { let network_graph = read_network_graph(); - let scorer = ZeroPenaltyScorer; + let scorer = FixedPenaltyScorer::with_penalty(0); generate_routes(bench, &network_graph, scorer, InvoiceFeatures::empty()); } #[bench] fn generate_mpp_routes_with_zero_penalty_scorer(bench: &mut Bencher) { let network_graph = read_network_graph(); - let scorer = ZeroPenaltyScorer; + let scorer = FixedPenaltyScorer::with_penalty(0); generate_routes(bench, &network_graph, scorer, InvoiceFeatures::known()); } @@ -5068,6 +5077,22 @@ mod benches { generate_routes(bench, &network_graph, scorer, InvoiceFeatures::known()); } + #[bench] + fn generate_routes_with_probabilistic_scorer(bench: &mut Bencher) { + let network_graph = read_network_graph(); + let params = ProbabilisticScoringParameters::default(); + let scorer = ProbabilisticScorer::new(params, &network_graph); + generate_routes(bench, &network_graph, scorer, InvoiceFeatures::empty()); + } + + #[bench] + fn generate_mpp_routes_with_probabilistic_scorer(bench: &mut Bencher) { + let network_graph = read_network_graph(); + let params = ProbabilisticScoringParameters::default(); + let scorer = ProbabilisticScorer::new(params, &network_graph); + generate_routes(bench, &network_graph, scorer, InvoiceFeatures::known()); + } + fn generate_routes( bench: &mut Bencher, graph: &NetworkGraph, mut scorer: S, features: InvoiceFeatures ) {