// 8. Choose the best route by the lowest total fee.
// As for the actual search algorithm,
- // we do a payee-to-payer Dijkstra's sorting by each node's distance from the payee
- // plus the minimum per-HTLC fee to get from it to another node (aka "shitty A*").
+ // we do a payee-to-payer pseudo-Dijkstra's sorting by each node's distance from the payee
+ // plus the minimum per-HTLC fee to get from it to another node (aka "shitty pseudo-A*").
+ //
+ // We are not a faithful Dijkstra's implementation because we can change values which impact
+ // earlier nodes while processing later nodes. Specifically, if we reach a channel with a lower
+ // liquidity limit (via htlc_maximum_msat, on-chain capacity or assumed liquidity limits) then
+ // the value we are currently attempting to send over a path, we simply reduce the value being
+ // sent along the path for any hops after that channel. This may imply that later fees (which
+ // we've already tabulated) are lower because a smaller value is passing through the channels
+ // (and the proportional fee is thus lower). There isn't a trivial way to recalculate the
+ // channels which were selected earlier (and which may still be used for other paths without a
+ // lower liquidity limit), so we simply accept that some liquidity-limited paths may be
+ // de-preferenced.
+ //
+ // One potentially problematic case for this algorithm would be if there are many
+ // liquidity-limited paths which are liquidity-limited near the destination (ie early in our
+ // graph walking), we may never find a path which is not liquidity-limited and has lower
+ // proportional fee (and only lower absolute fee when considering the ultimate value sent).
+ // Because we only consider paths with at least 5% of the total value being sent, the damage
+ // from such a case should be limited, however this could be further reduced in the future by
+ // calculating fees on the amount we wish to route over a path, ie ignoring the liquidity
+ // limits for the purposes of fee calculation.
+ //
+ // Alternatively, we could store more detailed path information in the heap (targets, below)
+ // and index the best-path map (dist, below) by node *and* HTLC limits, however that would blow
+ // up the runtime significantly both algorithmically (as we'd traverse nodes multiple times)
+ // and practically (as we would need to store dynamically-allocated path information in heap
+ // objects, increasing malloc traffic and indirect memory access significantly). Further, the
+ // results of such an algorithm would likely be biased towards lower-value paths.
+ //
+ // Further, we could return to a faithful Dijkstra's algorithm by rejecting paths with limits
+ // outside of our current search value, running a path search more times to gather candidate
+ // paths at different values. While this may be acceptable, further path searches may increase
+ // runtime for little gain. Specifically, the current algorithm rather efficiently explores the
+ // graph for candidate paths, calculating the maximum value which can realistically be sent at
+ // the same time, remaining generic across different payment values.
+ //
// TODO: There are a few tweaks we could do, including possibly pre-calculating more stuff
// to use as the A* heuristic beyond just the cost to get one node further than the current
// one.
let mut targets = BinaryHeap::new(); //TODO: Do we care about switching to eg Fibbonaci heap?
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,
+ // indicating that we may wish to try again with a higher value, potentially paying to meet an
+ // htlc_minimum with extra fees while still finding a cheaper path.
+ let mut hit_minimum_limit;
+
// When arranging a route, we select multiple paths so that we can make a multi-path payment.
- // Don't stop searching for paths when we think they're
- // sufficient to transfer a given value aggregately.
- // Search for higher value, so that we collect many more paths,
- // and then select the best combination among them.
+ // We start with a path_value of the exact amount we want, and if that generates a route we may
+ // return it immediately. Otherwise, we don't stop searching for paths until we have 3x the
+ // amount we want in total across paths, selecting the best subset at the end.
const ROUTE_CAPACITY_PROVISION_FACTOR: u64 = 3;
let recommended_value_msat = final_value_msat * ROUTE_CAPACITY_PROVISION_FACTOR as u64;
+ let mut path_value_msat = final_value_msat;
// 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
// Since we're choosing amount_to_transfer_over_msat as maximum possible, it can
// be only reduced later (not increased), so this channel should just be skipped
// 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 {
+ if amount_to_transfer_over_msat < $directional_info.htlc_minimum_msat {
+ hit_minimum_limit = true;
+ } else if contributes_sufficient_value {
// 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
// the further iterations of path finding. Also don't erase first_hop_targets.
targets.clear();
dist.clear();
+ hit_minimum_limit = false;
// If first hop is a private channel and the only way to reach the payee, this is the only
// place where it could be added.
if first_hops.is_some() {
if let Some(&(ref first_hop, ref features, ref outbound_capacity_msat)) = first_hop_targets.get(&payee) {
- add_entry!(first_hop, *our_node_id, payee, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), 0, recommended_value_msat);
+ add_entry!(first_hop, *our_node_id, payee, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), 0, path_value_msat);
}
}
// If not, targets.pop() will not even let us enter the loop in step 2.
None => {},
Some(node) => {
- add_entries_to_cheapest_to_target_node!(node, payee, 0, recommended_value_msat);
+ add_entries_to_cheapest_to_target_node!(node, payee, 0, path_value_msat);
},
}
// bit lazy here. In the future, we should pull them out via our
// ChannelManager, but there's no reason to waste the space until we
// need them.
- add_entry!(first_hop, *our_node_id , hop.src_node_id, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), 0, recommended_value_msat);
+ add_entry!(first_hop, *our_node_id , hop.src_node_id, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), 0, path_value_msat);
true
} else {
// In any other case, only add the hop if the source is in the regular network
htlc_maximum_msat: hop.htlc_maximum_msat,
fees: hop.fees,
};
- add_entry!(hop.short_channel_id, hop.src_node_id, payee, directional_info, None::<u64>, ChannelFeatures::empty(), 0, recommended_value_msat);
+ add_entry!(hop.short_channel_id, hop.src_node_id, payee, directional_info, None::<u64>, ChannelFeatures::empty(), 0, path_value_msat);
}
}
}
// Step (3).
- // Stop either when recommended value is reached,
- // or if during last iteration no new path was found.
- // In the latter case, making another path finding attempt could not help,
- // because we deterministically terminate the search due to low liquidity.
+ // Stop either when the recommended value is reached or if no new path was found in this
+ // iteration.
+ // In the latter case, making another path finding attempt won't help,
+ // because we deterministically terminated the search due to low liquidity.
if already_collected_value_msat >= recommended_value_msat || !found_new_path {
break 'paths_collection;
+ } else if found_new_path && already_collected_value_msat == final_value_msat && payment_paths.len() == 1 {
+ // Further, if this was our first walk of the graph, and we weren't limited by an
+ // htlc_minimum_msat, return immediately because this path should suffice. If we were
+ // limited by an htlc_minimum_msat value, find another path with a higher value,
+ // potentially allowing us to pay fees to meet the htlc_minimum on the new path while
+ // still keeping a lower total fee than this path.
+ if !hit_minimum_limit {
+ break 'paths_collection;
+ }
+ path_value_msat = recommended_value_msat;
}
}
outbound_capacity_msat: 100000,
inbound_capacity_msat: 100000,
is_live: true,
+ counterparty_forwarding_info: None,
}];
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)) {
outbound_capacity_msat: 250_000_000,
inbound_capacity_msat: 0,
is_live: 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].len(), 2);
outbound_capacity_msat: 250_000_000,
inbound_capacity_msat: 0,
is_live: 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].len(), 2);
outbound_capacity_msat: 250_000_000,
inbound_capacity_msat: 0,
is_live: 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].len(), 2);
outbound_capacity_msat: 250_000_000,
inbound_capacity_msat: 0,
is_live: true,
+ counterparty_forwarding_info: None,
}];
let mut last_hops = last_hops(&nodes);
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();
outbound_capacity_msat: 100000,
inbound_capacity_msat: 100000,
is_live: 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();
outbound_capacity_msat: 200_000_000,
inbound_capacity_msat: 0,
is_live: true,
+ counterparty_forwarding_info: None,
}];
{
assert_eq!(total_amount_paid_msat, 90_000);
}
}
+
+ #[test]
+ fn exact_fee_liquidity_limit() {
+ // Test that if, while walking the graph, we find a hop that has exactly enough liquidity
+ // for us, including later hop fees, we take it. In the first version of our MPP algorithm
+ // we calculated fees on a higher value, resulting in us ignoring such paths.
+ let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
+ let (our_privkey, our_id, _, nodes) = get_nodes(&secp_ctx);
+
+ // We modify the graph to set the htlc_maximum of channel 2 to below the value we wish to
+ // send.
+ update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 2,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(85_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 12,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: (4 << 8) | 1,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(270_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 1000000,
+ excess_data: Vec::new()
+ });
+
+ {
+ // Now, attempt to route 90 sats, which is exactly 90 sats at the last hop, plus the
+ // 200% fee charged channel 13 in the 1-to-2 direction.
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 90_000, 42, Arc::clone(&logger)).unwrap();
+ assert_eq!(route.paths.len(), 1);
+ assert_eq!(route.paths[0].len(), 2);
+
+ assert_eq!(route.paths[0][0].pubkey, nodes[7]);
+ assert_eq!(route.paths[0][0].short_channel_id, 12);
+ assert_eq!(route.paths[0][0].fee_msat, 90_000*2);
+ assert_eq!(route.paths[0][0].cltv_expiry_delta, (13 << 8) | 1);
+ assert_eq!(route.paths[0][0].node_features.le_flags(), &id_to_feature_flags(8));
+ assert_eq!(route.paths[0][0].channel_features.le_flags(), &id_to_feature_flags(12));
+
+ assert_eq!(route.paths[0][1].pubkey, nodes[2]);
+ assert_eq!(route.paths[0][1].short_channel_id, 13);
+ assert_eq!(route.paths[0][1].fee_msat, 90_000);
+ assert_eq!(route.paths[0][1].cltv_expiry_delta, 42);
+ assert_eq!(route.paths[0][1].node_features.le_flags(), &id_to_feature_flags(3));
+ assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(13));
+ }
+ }
}
#[cfg(all(test, feature = "unstable"))]
idx += 1;
});
}
+
+ #[bench]
+ fn generate_mpp_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, Some(InvoiceFeatures::known()), 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, Some(InvoiceFeatures::known()), None, &[], amt, 42, &DummyLogger{}).is_ok());
+ idx += 1;
+ });
+ }
}
projects / rust-lightning / blobdiff