X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=d85485fe82600b351e927db598889ea96a81ce1a;hb=75ca50f5c0834c01d84826b880f048ca031f08ce;hp=48960cdecae91947f1f71838157f1ef012998127;hpb=bb4413cc657532315145a22d2901238508be40e6;p=rust-lightning

diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs
index 48960cde..d85485fe 100644
--- a/lightning/src/routing/router.rs
+++ b/lightning/src/routing/router.rs
@@ -12,12 +12,12 @@
 //! You probably want to create a NetGraphMsgHandler and use that as your RoutingMessageHandler and then
 //! interrogate it to get routes for your own payments.
 
-use bitcoin::secp256k1::key::PublicKey;
+use bitcoin::secp256k1::PublicKey;
 
 use ln::channelmanager::ChannelDetails;
 use ln::features::{ChannelFeatures, InvoiceFeatures, NodeFeatures};
 use ln::msgs::{DecodeError, ErrorAction, LightningError, MAX_VALUE_MSAT};
-use routing::scoring::Score;
+use routing::scoring::{ChannelUsage, Score};
 use routing::network_graph::{DirectedChannelInfoWithUpdate, EffectiveCapacity, NetworkGraph, ReadOnlyNetworkGraph, NodeId, RoutingFees};
 use util::ser::{Writeable, Readable};
 use util::logger::{Level, Logger};
@@ -65,11 +65,10 @@ impl_writeable_tlv_based!(RouteHop, {
 #[derive(Clone, Hash, PartialEq, Eq)]
 pub struct Route {
 	/// The list of routes taken for a single (potentially-)multi-part payment. The pubkey of the
-	/// last RouteHop in each path must be the same.
-	/// Each entry represents a list of hops, NOT INCLUDING our own, where the last hop is the
-	/// destination. Thus, this must always be at least length one. While the maximum length of any
-	/// given path is variable, keeping the length of any path to less than 20 should currently
-	/// ensure it is viable.
+	/// last RouteHop in each path must be the same. Each entry represents a list of hops, NOT
+	/// INCLUDING our own, where the last hop is the destination. Thus, this must always be at
+	/// least length one. While the maximum length of any given path is variable, keeping the length
+	/// of any path less or equal to 19 should currently ensure it is viable.
 	pub paths: Vec<Vec<RouteHop>>,
 	/// The `payment_params` parameter passed to [`find_route`].
 	/// This is used by `ChannelManager` to track information which may be required for retries,
@@ -177,9 +176,23 @@ impl_writeable_tlv_based!(RouteParameters, {
 /// Maximum total CTLV difference we allow for a full payment path.
 pub const DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA: u32 = 1008;
 
-/// The median hop CLTV expiry delta currently seen in the network.
+// The median hop CLTV expiry delta currently seen in the network.
 const MEDIAN_HOP_CLTV_EXPIRY_DELTA: u32 = 40;
 
+// During routing, we only consider paths shorter than our maximum length estimate.
+// In the legacy onion format, the maximum number of hops used to be a fixed value of 20.
+// However, in the TLV onion format, there is no fixed maximum length, but the `hop_payloads`
+// field is always 1300 bytes. As the `tlv_payload` for each hop may vary in length, we have to
+// estimate how many hops the route may have so that it actually fits the `hop_payloads` field.
+//
+// We estimate 3+32 (payload length and HMAC) + 2+8 (amt_to_forward) + 2+4 (outgoing_cltv_value) +
+// 2+8 (short_channel_id) = 61 bytes for each intermediate hop and 3+32
+// (payload length and HMAC) + 2+8 (amt_to_forward) + 2+4 (outgoing_cltv_value) + 2+32+8
+// (payment_secret and total_msat) = 93 bytes for the final hop.
+// Since the length of the potentially included `payment_metadata` is unknown to us, we round
+// down from (1300-93) / 61 = 19.78... to arrive at a conservative estimate of 19.
+const MAX_PATH_LENGTH_ESTIMATE: u8 = 19;
+
 /// The recipient of a payment.
 #[derive(Clone, Debug, Hash, PartialEq, Eq)]
 pub struct PaymentParameters {
@@ -327,16 +340,16 @@ struct RouteGraphNode {
 	/// All penalties incurred from this hop on the way to the destination, as calculated using
 	/// channel scoring.
 	path_penalty_msat: u64,
+	/// The number of hops walked up to this node.
+	path_length_to_node: u8,
 }
 
 impl cmp::Ord for RouteGraphNode {
 	fn cmp(&self, other: &RouteGraphNode) -> cmp::Ordering {
 		let other_score = cmp::max(other.lowest_fee_to_peer_through_node, other.path_htlc_minimum_msat)
-			.checked_add(other.path_penalty_msat)
-			.unwrap_or_else(|| u64::max_value());
+			.saturating_add(other.path_penalty_msat);
 		let self_score = cmp::max(self.lowest_fee_to_peer_through_node, self.path_htlc_minimum_msat)
-			.checked_add(self.path_penalty_msat)
-			.unwrap_or_else(|| u64::max_value());
+			.saturating_add(self.path_penalty_msat);
 		other_score.cmp(&self_score).then_with(|| other.node_id.cmp(&self.node_id))
 	}
 }
@@ -401,6 +414,16 @@ impl<'a> CandidateRouteHop<'a> {
 		}
 	}
 
+	fn htlc_maximum_msat(&self) -> u64 {
+		match self {
+			CandidateRouteHop::FirstHop { details } => details.next_outbound_htlc_limit_msat,
+			CandidateRouteHop::PublicHop { info, .. } => info.htlc_maximum_msat(),
+			CandidateRouteHop::PrivateHop { hint } => {
+				hint.htlc_maximum_msat.unwrap_or(u64::max_value())
+			},
+		}
+	}
+
 	fn fees(&self) -> RoutingFees {
 		match self {
 			CandidateRouteHop::FirstHop { .. } => RoutingFees {
@@ -414,7 +437,7 @@ impl<'a> CandidateRouteHop<'a> {
 	fn effective_capacity(&self) -> EffectiveCapacity {
 		match self {
 			CandidateRouteHop::FirstHop { details } => EffectiveCapacity::ExactLiquidity {
-				liquidity_msat: details.outbound_capacity_msat,
+				liquidity_msat: details.next_outbound_htlc_limit_msat,
 			},
 			CandidateRouteHop::PublicHop { info, .. } => info.effective_capacity(),
 			CandidateRouteHop::PrivateHop { .. } => EffectiveCapacity::Infinite,
@@ -468,7 +491,8 @@ struct PathBuildingHop<'a> {
 
 impl<'a> core::fmt::Debug for PathBuildingHop<'a> {
 	fn fmt(&self, f: &mut core::fmt::Formatter) -> Result<(), core::fmt::Error> {
-		f.debug_struct("PathBuildingHop")
+		let mut debug_struct = f.debug_struct("PathBuildingHop");
+		debug_struct
 			.field("node_id", &self.node_id)
 			.field("short_channel_id", &self.candidate.short_channel_id())
 			.field("total_fee_msat", &self.total_fee_msat)
@@ -477,8 +501,11 @@ impl<'a> core::fmt::Debug for PathBuildingHop<'a> {
 			.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()
+			.field("cltv_expiry_delta", &self.candidate.cltv_expiry_delta());
+		#[cfg(all(not(feature = "_bench_unstable"), any(test, fuzzing)))]
+		let debug_struct = debug_struct
+			.field("value_contribution_msat", &self.value_contribution_msat);
+		debug_struct.finish()
 	}
 }
 
@@ -495,6 +522,10 @@ impl<'a> PaymentPath<'a> {
 		self.hops.last().unwrap().0.fee_msat
 	}
 
+	fn get_path_penalty_msat(&self) -> u64 {
+		self.hops.first().map(|h| h.0.path_penalty_msat).unwrap_or(u64::max_value())
+	}
+
 	fn get_total_fee_paid_msat(&self) -> u64 {
 		if self.hops.len() < 1 {
 			return 0;
@@ -509,6 +540,10 @@ impl<'a> PaymentPath<'a> {
 		return result;
 	}
 
+	fn get_cost_msat(&self) -> u64 {
+		self.get_total_fee_paid_msat().saturating_add(self.get_path_penalty_msat())
+	}
+
 	// 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.
 	//
@@ -596,6 +631,17 @@ fn compute_fees(amount_msat: u64, channel_fees: RoutingFees) -> Option<u64> {
 	}
 }
 
+/// The default `features` we assume for a node in a route, when no `features` are known about that
+/// specific node.
+///
+/// Default features are:
+/// * variable_length_onion_optional
+fn default_node_features() -> NodeFeatures {
+	let mut features = NodeFeatures::empty();
+	features.set_variable_length_onion_optional();
+	features
+}
+
 /// Finds a route from us (payer) to the given target node (payee).
 ///
 /// If the payee provided features in their invoice, they should be provided via `params.payee`.
@@ -645,7 +691,7 @@ where L::Target: Logger {
 pub(crate) fn get_route<L: Deref, S: Score>(
 	our_node_pubkey: &PublicKey, payment_params: &PaymentParameters, network_graph: &ReadOnlyNetworkGraph,
 	first_hops: Option<&[&ChannelDetails]>, final_value_msat: u64, final_cltv_expiry_delta: u32,
-	logger: L, scorer: &S, _random_seed_bytes: &[u8; 32]
+	logger: L, scorer: &S, random_seed_bytes: &[u8; 32]
 ) -> Result<Route, LightningError>
 where L::Target: Logger {
 	let payee_node_id = NodeId::from_pubkey(&payment_params.payee_pubkey);
@@ -779,11 +825,11 @@ where L::Target: Logger {
 	// 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();
+	let mut targets: BinaryHeap<RouteGraphNode> = 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_nodes.len());
+	let mut dist: HashMap<NodeId, PathBuildingHop> = HashMap::with_capacity(network_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
@@ -798,11 +844,12 @@ where L::Target: Logger {
 	let recommended_value_msat = final_value_msat * ROUTE_CAPACITY_PROVISION_FACTOR as u64;
 	let mut path_value_msat = final_value_msat;
 
-	// We don't want multiple paths (as per MPP) share liquidity of the same channels.
-	// This map allows paths to be aware of the channel use by other paths in the same call.
-	// This would help to make a better path finding decisions and not "overbook" channels.
-	// It is unaware of the directions (except for `outbound_capacity_msat` in `first_hops`).
-	let mut bookkept_channels_liquidity_available_msat = HashMap::with_capacity(network_nodes.len());
+	// Keep track of how much liquidity has been used in selected channels. Used to determine
+	// if the channel can be used by additional MPP paths or to inform path finding decisions. It is
+	// aware of direction *only* to ensure that the correct htlc_maximum_msat value is used. Hence,
+	// liquidity used in one direction will not offset any used in the opposite direction.
+	let mut used_channel_liquidities: HashMap<(u64, bool), u64> =
+		HashMap::with_capacity(network_nodes.len());
 
 	// Keeping track of how much value we already collected across other paths. Helps to decide:
 	// - how much a new path should be transferring (upper bound);
@@ -811,6 +858,29 @@ where L::Target: Logger {
 	// - when we want to stop looking for new paths.
 	let mut already_collected_value_msat = 0;
 
+	for (_, channels) in first_hop_targets.iter_mut() {
+		// Sort the first_hops channels to the same node(s) in priority order of which channel we'd
+		// most like to use.
+		//
+		// First, if channels are below `recommended_value_msat`, sort them in descending order,
+		// preferring larger channels to avoid splitting the payment into more MPP parts than is
+		// required.
+		//
+		// Second, because simply always sorting in descending order would always use our largest
+		// available outbound capacity, needlessly fragmenting our available channel capacities,
+		// sort channels above `recommended_value_msat` in ascending order, preferring channels
+		// which have enough, but not too much, capacity for the payment.
+		channels.sort_unstable_by(|chan_a, chan_b| {
+			if chan_b.next_outbound_htlc_limit_msat < recommended_value_msat || chan_a.next_outbound_htlc_limit_msat < recommended_value_msat {
+				// Sort in descending order
+				chan_b.next_outbound_htlc_limit_msat.cmp(&chan_a.next_outbound_htlc_limit_msat)
+			} else {
+				// Sort in ascending order
+				chan_a.next_outbound_htlc_limit_msat.cmp(&chan_b.next_outbound_htlc_limit_msat)
+			}
+		});
+	}
+
 	log_trace!(logger, "Building path from {} (payee) to {} (us/payer) for value {} msat.", payment_params.payee_pubkey, our_node_pubkey, final_value_msat);
 
 	macro_rules! add_entry {
@@ -819,8 +889,8 @@ where L::Target: Logger {
 		// since that value has to be transferred over this channel.
 		// Returns whether this channel caused an update to `targets`.
 		( $candidate: expr, $src_node_id: expr, $dest_node_id: expr, $next_hops_fee_msat: expr,
-		   $next_hops_value_contribution: expr, $next_hops_path_htlc_minimum_msat: expr,
-		   $next_hops_path_penalty_msat: expr, $next_hops_cltv_delta: expr ) => { {
+			$next_hops_value_contribution: expr, $next_hops_path_htlc_minimum_msat: expr,
+			$next_hops_path_penalty_msat: expr, $next_hops_cltv_delta: expr, $next_hops_path_length: expr ) => { {
 			// We "return" whether we updated the path at the end, via this:
 			let mut did_add_update_path_to_src_node = false;
 			// Channels to self should not be used. This is more of belt-and-suspenders, because in
@@ -829,18 +899,23 @@ where L::Target: Logger {
 			// - for first and last hops early in get_route
 			if $src_node_id != $dest_node_id {
 				let short_channel_id = $candidate.short_channel_id();
-				let available_liquidity_msat = bookkept_channels_liquidity_available_msat
-					.entry(short_channel_id)
-					.or_insert_with(|| $candidate.effective_capacity().as_msat());
+				let htlc_maximum_msat = $candidate.htlc_maximum_msat();
 
-				// It is tricky to substract $next_hops_fee_msat from available liquidity here.
+				// It is tricky to subtract $next_hops_fee_msat from available liquidity here.
 				// It may be misleading because we might later choose to reduce the value transferred
 				// over these channels, and the channel which was insufficient might become sufficient.
 				// Worst case: we drop a good channel here because it can't cover the high following
 				// fees caused by one expensive channel, but then this channel could have been used
 				// if the amount being transferred over this path is lower.
 				// We do this for now, but this is a subject for removal.
-				if let Some(available_value_contribution_msat) = available_liquidity_msat.checked_sub($next_hops_fee_msat) {
+				if let Some(mut available_value_contribution_msat) = htlc_maximum_msat.checked_sub($next_hops_fee_msat) {
+					let used_liquidity_msat = used_channel_liquidities
+						.get(&(short_channel_id, $src_node_id < $dest_node_id))
+						.map_or(0, |used_liquidity_msat| {
+							available_value_contribution_msat = available_value_contribution_msat
+								.saturating_sub(*used_liquidity_msat);
+							*used_liquidity_msat
+						});
 
 					// Routing Fragmentation Mitigation heuristic:
 					//
@@ -864,6 +939,9 @@ where L::Target: Logger {
 					};
 					// Verify the liquidity offered by this channel complies to the minimal contribution.
 					let contributes_sufficient_value = available_value_contribution_msat >= minimal_value_contribution_msat;
+					// Do not consider candidate hops that would exceed the maximum path length.
+					let path_length_to_node = $next_hops_path_length + 1;
+					let doesnt_exceed_max_path_length = path_length_to_node <= MAX_PATH_LENGTH_ESTIMATE;
 
 					// Do not consider candidates that exceed the maximum total cltv expiry limit.
 					// In order to already account for some of the privacy enhancing random CLTV
@@ -873,8 +951,7 @@ where L::Target: Logger {
 						.checked_sub(2*MEDIAN_HOP_CLTV_EXPIRY_DELTA)
 						.unwrap_or(payment_params.max_total_cltv_expiry_delta - final_cltv_expiry_delta);
 					let hop_total_cltv_delta = ($next_hops_cltv_delta as u32)
-						.checked_add($candidate.cltv_expiry_delta())
-						.unwrap_or(u32::max_value());
+						.saturating_add($candidate.cltv_expiry_delta());
 					let doesnt_exceed_cltv_delta_limit = hop_total_cltv_delta <= max_total_cltv_expiry_delta;
 
 					let value_contribution_msat = cmp::min(available_value_contribution_msat, $next_hops_value_contribution);
@@ -888,14 +965,22 @@ where L::Target: Logger {
 					let over_path_minimum_msat = amount_to_transfer_over_msat >= $candidate.htlc_minimum_msat() &&
 						amount_to_transfer_over_msat >= $next_hops_path_htlc_minimum_msat;
 
+					#[allow(unused_comparisons)] // $next_hops_path_htlc_minimum_msat is 0 in some calls so rustc complains
+					let may_overpay_to_meet_path_minimum_msat =
+						((amount_to_transfer_over_msat < $candidate.htlc_minimum_msat() &&
+						  recommended_value_msat > $candidate.htlc_minimum_msat()) ||
+						 (amount_to_transfer_over_msat < $next_hops_path_htlc_minimum_msat &&
+						  recommended_value_msat > $next_hops_path_htlc_minimum_msat));
+
 					// If HTLC minimum is larger than the amount we're going to transfer, we shouldn't
-					// bother considering this channel.
-					// 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.
-					if !over_path_minimum_msat && doesnt_exceed_cltv_delta_limit {
+					// bother considering this channel. If retrying with recommended_value_msat may
+					// allow us to hit the HTLC minimum limit, set htlc_minimum_limit so that we go
+					// around again with a higher amount.
+					if contributes_sufficient_value && doesnt_exceed_max_path_length &&
+						doesnt_exceed_cltv_delta_limit && may_overpay_to_meet_path_minimum_msat {
 						hit_minimum_limit = true;
-					} else if contributes_sufficient_value && doesnt_exceed_cltv_delta_limit {
+					} else if contributes_sufficient_value && doesnt_exceed_max_path_length &&
+						doesnt_exceed_cltv_delta_limit && over_path_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
@@ -981,9 +1066,16 @@ where L::Target: Logger {
 								}
 							}
 
-							let path_penalty_msat = $next_hops_path_penalty_msat.checked_add(
-								scorer.channel_penalty_msat(short_channel_id, amount_to_transfer_over_msat, *available_liquidity_msat,
-									&$src_node_id, &$dest_node_id)).unwrap_or_else(|| u64::max_value());
+							let channel_usage = ChannelUsage {
+								amount_msat: amount_to_transfer_over_msat,
+								inflight_htlc_msat: used_liquidity_msat,
+								effective_capacity: $candidate.effective_capacity(),
+							};
+							let channel_penalty_msat = scorer.channel_penalty_msat(
+								short_channel_id, &$src_node_id, &$dest_node_id, channel_usage
+							);
+							let path_penalty_msat = $next_hops_path_penalty_msat
+								.saturating_add(channel_penalty_msat);
 							let new_graph_node = RouteGraphNode {
 								node_id: $src_node_id,
 								lowest_fee_to_peer_through_node: total_fee_msat,
@@ -992,6 +1084,7 @@ where L::Target: Logger {
 								value_contribution_msat: value_contribution_msat,
 								path_htlc_minimum_msat,
 								path_penalty_msat,
+								path_length_to_node,
 							};
 
 							// Update the way of reaching $src_node_id with the given short_channel_id (from $dest_node_id),
@@ -1011,11 +1104,9 @@ where L::Target: Logger {
 							// the fees included in $next_hops_path_htlc_minimum_msat, but also
 							// can't use something that may decrease on future hops.
 							let old_cost = cmp::max(old_entry.total_fee_msat, old_entry.path_htlc_minimum_msat)
-								.checked_add(old_entry.path_penalty_msat)
-								.unwrap_or_else(|| u64::max_value());
+								.saturating_add(old_entry.path_penalty_msat);
 							let new_cost = cmp::max(total_fee_msat, path_htlc_minimum_msat)
-								.checked_add(path_penalty_msat)
-								.unwrap_or_else(|| u64::max_value());
+								.saturating_add(path_penalty_msat);
 
 							if !old_entry.was_processed && new_cost < old_cost {
 								targets.push(new_graph_node);
@@ -1069,14 +1160,17 @@ where L::Target: Logger {
 		} }
 	}
 
-	let empty_node_features = NodeFeatures::empty();
+	let default_node_features = default_node_features();
+
 	// Find ways (channels with destination) to reach a given node and store them
 	// in the corresponding data structures (routing graph etc).
 	// $fee_to_target_msat represents how much it costs to reach to this node from the payee,
 	// meaning how much will be paid in fees after this node (to the best of our knowledge).
 	// This data can later be helpful to optimize routing (pay lower fees).
 	macro_rules! add_entries_to_cheapest_to_target_node {
-		( $node: expr, $node_id: expr, $fee_to_target_msat: expr, $next_hops_value_contribution: expr, $next_hops_path_htlc_minimum_msat: expr, $next_hops_path_penalty_msat: expr, $next_hops_cltv_delta: expr ) => {
+		( $node: expr, $node_id: expr, $fee_to_target_msat: expr, $next_hops_value_contribution: expr,
+		  $next_hops_path_htlc_minimum_msat: expr, $next_hops_path_penalty_msat: expr,
+		  $next_hops_cltv_delta: expr, $next_hops_path_length: expr ) => {
 			let skip_node = if let Some(elem) = dist.get_mut(&$node_id) {
 				let was_processed = elem.was_processed;
 				elem.was_processed = true;
@@ -1093,14 +1187,17 @@ where L::Target: Logger {
 				if let Some(first_channels) = first_hop_targets.get(&$node_id) {
 					for details in first_channels {
 						let candidate = CandidateRouteHop::FirstHop { details };
-						add_entry!(candidate, our_node_id, $node_id, $fee_to_target_msat, $next_hops_value_contribution, $next_hops_path_htlc_minimum_msat, $next_hops_path_penalty_msat, $next_hops_cltv_delta);
+						add_entry!(candidate, our_node_id, $node_id, $fee_to_target_msat,
+							$next_hops_value_contribution,
+							$next_hops_path_htlc_minimum_msat, $next_hops_path_penalty_msat,
+							$next_hops_cltv_delta, $next_hops_path_length);
 					}
 				}
 
 				let features = if let Some(node_info) = $node.announcement_info.as_ref() {
 					&node_info.features
 				} else {
-					&empty_node_features
+					&default_node_features
 				};
 
 				if !features.requires_unknown_bits() {
@@ -1116,7 +1213,12 @@ where L::Target: Logger {
 											info: directed_channel.with_update().unwrap(),
 											short_channel_id: *chan_id,
 										};
-										add_entry!(candidate, *source, $node_id, $fee_to_target_msat, $next_hops_value_contribution, $next_hops_path_htlc_minimum_msat, $next_hops_path_penalty_msat, $next_hops_cltv_delta);
+										add_entry!(candidate, *source, $node_id,
+											$fee_to_target_msat,
+											$next_hops_value_contribution,
+											$next_hops_path_htlc_minimum_msat,
+											$next_hops_path_penalty_msat,
+											$next_hops_cltv_delta, $next_hops_path_length);
 									}
 								}
 							}
@@ -1131,9 +1233,8 @@ where L::Target: Logger {
 
 	// TODO: diversify by nodes (so that all paths aren't doomed if one node is offline).
 	'paths_collection: loop {
-		// For every new path, start from scratch, except
-		// bookkept_channels_liquidity_available_msat, which will improve
-		// the further iterations of path finding. Also don't erase first_hop_targets.
+		// For every new path, start from scratch, except for used_channel_liquidities, which
+		// helps to avoid reusing previously selected paths in future iterations.
 		targets.clear();
 		dist.clear();
 		hit_minimum_limit = false;
@@ -1143,8 +1244,10 @@ where L::Target: Logger {
 		if let Some(first_channels) = first_hop_targets.get(&payee_node_id) {
 			for details in first_channels {
 				let candidate = CandidateRouteHop::FirstHop { details };
-				let added = add_entry!(candidate, our_node_id, payee_node_id, 0, path_value_msat, 0, 0u64, 0);
-				log_trace!(logger, "{} direct route to payee via SCID {}", if added { "Added" } else { "Skipped" }, candidate.short_channel_id());
+				let added = add_entry!(candidate, our_node_id, payee_node_id, 0, path_value_msat,
+									0, 0u64, 0, 0);
+				log_trace!(logger, "{} direct route to payee via SCID {}",
+						if added { "Added" } else { "Skipped" }, candidate.short_channel_id());
 			}
 		}
 
@@ -1157,7 +1260,7 @@ where L::Target: Logger {
 			// 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_node_id, 0, path_value_msat, 0, 0u64, 0);
+				add_entries_to_cheapest_to_target_node!(node, payee_node_id, 0, path_value_msat, 0, 0u64, 0, 0);
 			},
 		}
 
@@ -1184,6 +1287,7 @@ where L::Target: Logger {
 				let mut aggregate_next_hops_path_htlc_minimum_msat: u64 = 0;
 				let mut aggregate_next_hops_path_penalty_msat: u64 = 0;
 				let mut aggregate_next_hops_cltv_delta: u32 = 0;
+				let mut aggregate_next_hops_path_length: u8 = 0;
 
 				for (idx, (hop, prev_hop_id)) in hop_iter.zip(prev_hop_iter).enumerate() {
 					let source = NodeId::from_pubkey(&hop.src_node_id);
@@ -1197,27 +1301,45 @@ where L::Target: Logger {
 							short_channel_id: hop.short_channel_id,
 						})
 						.unwrap_or_else(|| CandidateRouteHop::PrivateHop { hint: hop });
-					let capacity_msat = candidate.effective_capacity().as_msat();
+
+					if !add_entry!(candidate, source, target, aggregate_next_hops_fee_msat,
+								path_value_msat, aggregate_next_hops_path_htlc_minimum_msat,
+								aggregate_next_hops_path_penalty_msat,
+								aggregate_next_hops_cltv_delta, aggregate_next_hops_path_length) {
+						// If this hop was not used then there is no use checking the preceding
+						// hops in the RouteHint. We can break by just searching for a direct
+						// channel between last checked hop and first_hop_targets.
+						hop_used = false;
+					}
+
+					let used_liquidity_msat = used_channel_liquidities
+						.get(&(hop.short_channel_id, source < target)).copied().unwrap_or(0);
+					let channel_usage = ChannelUsage {
+						amount_msat: final_value_msat + aggregate_next_hops_fee_msat,
+						inflight_htlc_msat: used_liquidity_msat,
+						effective_capacity: candidate.effective_capacity(),
+					};
+					let channel_penalty_msat = scorer.channel_penalty_msat(
+						hop.short_channel_id, &source, &target, channel_usage
+					);
 					aggregate_next_hops_path_penalty_msat = aggregate_next_hops_path_penalty_msat
-						.checked_add(scorer.channel_penalty_msat(hop.short_channel_id, final_value_msat, capacity_msat, &source, &target))
-						.unwrap_or_else(|| u64::max_value());
+						.saturating_add(channel_penalty_msat);
 
 					aggregate_next_hops_cltv_delta = aggregate_next_hops_cltv_delta
-						.checked_add(hop.cltv_expiry_delta as u32)
-						.unwrap_or_else(|| u32::max_value());
+						.saturating_add(hop.cltv_expiry_delta as u32);
 
-					if !add_entry!(candidate, source, target, aggregate_next_hops_fee_msat, path_value_msat, aggregate_next_hops_path_htlc_minimum_msat, aggregate_next_hops_path_penalty_msat, aggregate_next_hops_cltv_delta) {
-						// If this hop was not used then there is no use checking the preceding hops
-						// in the RouteHint. We can break by just searching for a direct channel between
-						// last checked hop and first_hop_targets
-						hop_used = false;
-					}
+					aggregate_next_hops_path_length = aggregate_next_hops_path_length
+						.saturating_add(1);
 
 					// Searching for a direct channel between last checked hop and first_hop_targets
 					if let Some(first_channels) = first_hop_targets.get(&NodeId::from_pubkey(&prev_hop_id)) {
 						for details in first_channels {
 							let candidate = CandidateRouteHop::FirstHop { details };
-							add_entry!(candidate, our_node_id, NodeId::from_pubkey(&prev_hop_id), aggregate_next_hops_fee_msat, path_value_msat, aggregate_next_hops_path_htlc_minimum_msat, aggregate_next_hops_path_penalty_msat, aggregate_next_hops_cltv_delta);
+							add_entry!(candidate, our_node_id, NodeId::from_pubkey(&prev_hop_id),
+								aggregate_next_hops_fee_msat, path_value_msat,
+								aggregate_next_hops_path_htlc_minimum_msat,
+								aggregate_next_hops_path_penalty_msat, aggregate_next_hops_cltv_delta,
+								aggregate_next_hops_path_length);
 						}
 					}
 
@@ -1228,7 +1350,7 @@ where L::Target: Logger {
 					// In the next values of the iterator, the aggregate fees already reflects
 					// the sum of value sent from payer (final_value_msat) and routing fees
 					// for the last node in the RouteHint. We need to just add the fees to
-					// route through the current node so that the preceeding node (next iteration)
+					// route through the current node so that the preceding node (next iteration)
 					// can use it.
 					let hops_fee = compute_fees(aggregate_next_hops_fee_msat + final_value_msat, hop.fees)
 						.map_or(None, |inc| inc.checked_add(aggregate_next_hops_fee_msat));
@@ -1253,7 +1375,13 @@ where L::Target: Logger {
 						if let Some(first_channels) = first_hop_targets.get(&NodeId::from_pubkey(&hop.src_node_id)) {
 							for details in first_channels {
 								let candidate = CandidateRouteHop::FirstHop { details };
-								add_entry!(candidate, our_node_id, NodeId::from_pubkey(&hop.src_node_id), aggregate_next_hops_fee_msat, path_value_msat, aggregate_next_hops_path_htlc_minimum_msat, aggregate_next_hops_path_penalty_msat, aggregate_next_hops_cltv_delta);
+								add_entry!(candidate, our_node_id,
+									NodeId::from_pubkey(&hop.src_node_id),
+									aggregate_next_hops_fee_msat, path_value_msat,
+									aggregate_next_hops_path_htlc_minimum_msat,
+									aggregate_next_hops_path_penalty_msat,
+									aggregate_next_hops_cltv_delta,
+									aggregate_next_hops_path_length);
 							}
 						}
 					}
@@ -1276,13 +1404,13 @@ where L::Target: Logger {
 		// Both these cases (and other cases except reaching recommended_value_msat) mean that
 		// paths_collection will be stopped because found_new_path==false.
 		// This is not necessarily a routing failure.
-		'path_construction: while let Some(RouteGraphNode { node_id, lowest_fee_to_node, total_cltv_delta, value_contribution_msat, path_htlc_minimum_msat, path_penalty_msat, .. }) = targets.pop() {
+		'path_construction: while let Some(RouteGraphNode { node_id, lowest_fee_to_node, total_cltv_delta, value_contribution_msat, path_htlc_minimum_msat, path_penalty_msat, path_length_to_node, .. }) = targets.pop() {
 
 			// Since we're going payee-to-payer, hitting our node as a target means we should stop
 			// traversing the graph and arrange the path out of what we found.
 			if node_id == our_node_id {
 				let mut new_entry = dist.remove(&our_node_id).unwrap();
-				let mut ordered_hops = vec!((new_entry.clone(), NodeFeatures::empty()));
+				let mut ordered_hops: Vec<(PathBuildingHop, NodeFeatures)> = vec!((new_entry.clone(), default_node_features.clone()));
 
 				'path_walk: loop {
 					let mut features_set = false;
@@ -1300,7 +1428,7 @@ where L::Target: Logger {
 							if let Some(node_info) = node.announcement_info.as_ref() {
 								ordered_hops.last_mut().unwrap().1 = node_info.features.clone();
 							} else {
-								ordered_hops.last_mut().unwrap().1 = NodeFeatures::empty();
+								ordered_hops.last_mut().unwrap().1 = default_node_features.clone();
 							}
 						} else {
 							// We can fill in features for everything except hops which were
@@ -1327,7 +1455,7 @@ where L::Target: Logger {
 					// so that fees paid for a HTLC forwarding on the current channel are
 					// associated with the previous channel (where they will be subtracted).
 					ordered_hops.last_mut().unwrap().0.fee_msat = new_entry.hop_use_fee_msat;
-					ordered_hops.push((new_entry.clone(), NodeFeatures::empty()));
+					ordered_hops.push((new_entry.clone(), default_node_features.clone()));
 				}
 				ordered_hops.last_mut().unwrap().0.fee_msat = value_contribution_msat;
 				ordered_hops.last_mut().unwrap().0.hop_use_fee_msat = 0;
@@ -1354,26 +1482,30 @@ where L::Target: Logger {
 				// Remember that we used these channels so that we don't rely
 				// on the same liquidity in future paths.
 				let mut prevented_redundant_path_selection = false;
-				for (payment_hop, _) in payment_path.hops.iter() {
-					let channel_liquidity_available_msat = bookkept_channels_liquidity_available_msat.get_mut(&payment_hop.candidate.short_channel_id()).unwrap();
-					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 spent_on_hop_msat == *channel_liquidity_available_msat {
+				let prev_hop_iter = core::iter::once(&our_node_id)
+					.chain(payment_path.hops.iter().map(|(hop, _)| &hop.node_id));
+				for (prev_hop, (hop, _)) in prev_hop_iter.zip(payment_path.hops.iter()) {
+					let spent_on_hop_msat = value_contribution_msat + hop.next_hops_fee_msat;
+					let used_liquidity_msat = used_channel_liquidities
+						.entry((hop.candidate.short_channel_id(), *prev_hop < hop.node_id))
+						.and_modify(|used_liquidity_msat| *used_liquidity_msat += spent_on_hop_msat)
+						.or_insert(spent_on_hop_msat);
+					if *used_liquidity_msat == hop.candidate.htlc_maximum_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.
 						prevented_redundant_path_selection = true;
 					}
-					*channel_liquidity_available_msat -= spent_on_hop_msat;
+					debug_assert!(*used_liquidity_msat <= hop.candidate.htlc_maximum_msat());
 				}
 				if !prevented_redundant_path_selection {
 					// If we weren't capped by hitting a liquidity limit on a channel in the path,
 					// we'll probably end up picking the same path again on the next iteration.
 					// Decrease the available liquidity of a hop in the middle of the path.
-					let victim_scid = payment_path.hops[(payment_path.hops.len() - 1) / 2].0.candidate.short_channel_id();
+					let victim_scid = payment_path.hops[(payment_path.hops.len()) / 2].0.candidate.short_channel_id();
+					let exhausted = u64::max_value();
 					log_trace!(logger, "Disabling channel {} for future path building iterations to avoid duplicates.", victim_scid);
-					let victim_liquidity = bookkept_channels_liquidity_available_msat.get_mut(&victim_scid).unwrap();
-					*victim_liquidity = 0;
+					*used_channel_liquidities.entry((victim_scid, false)).or_default() = exhausted;
+					*used_channel_liquidities.entry((victim_scid, true)).or_default() = exhausted;
 				}
 
 				// Track the total amount all our collected paths allow to send so that we:
@@ -1398,7 +1530,9 @@ where L::Target: Logger {
 			match network_nodes.get(&node_id) {
 				None => {},
 				Some(node) => {
-					add_entries_to_cheapest_to_target_node!(node, node_id, lowest_fee_to_node, value_contribution_msat, path_htlc_minimum_msat, path_penalty_msat, total_cltv_delta);
+					add_entries_to_cheapest_to_target_node!(node, node_id, lowest_fee_to_node,
+						value_contribution_msat, path_htlc_minimum_msat, path_penalty_msat,
+						total_cltv_delta, path_length_to_node);
 				},
 			}
 		}
@@ -1442,24 +1576,31 @@ where L::Target: Logger {
 	}
 
 	// Sort by total fees and take the best paths.
-	payment_paths.sort_by_key(|path| path.get_total_fee_paid_msat());
+	payment_paths.sort_unstable_by_key(|path| path.get_total_fee_paid_msat());
 	if payment_paths.len() > 50 {
 		payment_paths.truncate(50);
 	}
 
 	// Draw multiple sufficient routes by randomly combining the selected paths.
 	let mut drawn_routes = Vec::new();
-	for i in 0..payment_paths.len() {
+	let mut prng = ChaCha20::new(random_seed_bytes, &[0u8; 12]);
+	let mut random_index_bytes = [0u8; ::core::mem::size_of::<usize>()];
+
+	let num_permutations = payment_paths.len();
+	for _ in 0..num_permutations {
 		let mut cur_route = Vec::<PaymentPath>::new();
 		let mut aggregate_route_value_msat = 0;
 
 		// Step (6).
-		// TODO: real random shuffle
-		// Currently just starts with i_th and goes up to i-1_th in a looped way.
-		let cur_payment_paths = [&payment_paths[i..], &payment_paths[..i]].concat();
+		// Do a Fisher-Yates shuffle to create a random permutation of the payment paths
+		for cur_index in (1..payment_paths.len()).rev() {
+			prng.process_in_place(&mut random_index_bytes);
+			let random_index = usize::from_be_bytes(random_index_bytes).wrapping_rem(cur_index+1);
+			payment_paths.swap(cur_index, random_index);
+		}
 
 		// Step (7).
-		for payment_path in cur_payment_paths {
+		for payment_path in &payment_paths {
 			cur_route.push(payment_path.clone());
 			aggregate_route_value_msat += payment_path.get_value_msat();
 			if aggregate_route_value_msat > final_value_msat {
@@ -1469,12 +1610,16 @@ where L::Target: Logger {
 				// also makes routing more reliable.
 				let mut overpaid_value_msat = aggregate_route_value_msat - final_value_msat;
 
-				// First, drop some expensive low-value paths entirely if possible.
-				// Sort by value so that we drop many really-low values first, since
-				// fewer paths is better: the payment is less likely to fail.
-				// 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.get_value_msat());
+				// First, we drop some expensive low-value paths entirely if possible, since fewer
+				// paths is better: the payment is less likely to fail. In order to do so, we sort
+				// by value and fall back to total fees paid, i.e., in case of equal values we
+				// prefer lower cost paths.
+				cur_route.sort_unstable_by(|a, b| {
+					a.get_value_msat().cmp(&b.get_value_msat())
+						// Reverse ordering for cost, so we drop higher-cost paths first
+						.then_with(|| b.get_cost_msat().cmp(&a.get_cost_msat()))
+				});
+
 				// We should make sure that at least 1 path left.
 				let mut paths_left = cur_route.len();
 				cur_route.retain(|path| {
@@ -1498,13 +1643,14 @@ where L::Target: Logger {
 				assert!(cur_route.len() > 0);
 
 				// Step (8).
-				// Now, substract the overpaid value from the most-expensive path.
+				// Now, subtract the overpaid value from the most-expensive path.
 				// 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.0.candidate.fees().proportional_millionths as u64).sum::<u64>() });
+				cur_route.sort_unstable_by_key(|path| { path.hops.iter().map(|hop| hop.0.candidate.fees().proportional_millionths as u64).sum::<u64>() });
 				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.
+
+				// We already dropped all the small value paths above, meaning all the
+				// remaining paths are larger than remaining overpaid_value_msat.
 				// Thus, this can't be negative.
 				let expensive_path_new_value_msat = expensive_payment_path.get_value_msat() - overpaid_value_msat;
 				expensive_payment_path.update_value_and_recompute_fees(expensive_path_new_value_msat);
@@ -1515,8 +1661,8 @@ where L::Target: Logger {
 	}
 
 	// Step (9).
-	// 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>());
+	// Select the best route by lowest total cost.
+	drawn_routes.sort_unstable_by_key(|paths| paths.iter().map(|path| path.get_cost_msat()).sum::<u64>());
 	let mut selected_paths = Vec::<Vec<Result<RouteHop, LightningError>>>::new();
 	for payment_path in drawn_routes.first().unwrap() {
 		let mut path = payment_path.hops.iter().map(|(payment_hop, node_features)| {
@@ -1564,45 +1710,58 @@ fn add_random_cltv_offset(route: &mut Route, payment_params: &PaymentParameters,
 	for path in route.paths.iter_mut() {
 		let mut shadow_ctlv_expiry_delta_offset: u32 = 0;
 
-		// Choose the last publicly known node as the starting point for the random walk
-		if let Some(starting_hop) = path.iter().rev().find(|h| network_nodes.contains_key(&NodeId::from_pubkey(&h.pubkey))) {
-			let mut cur_node_id = NodeId::from_pubkey(&starting_hop.pubkey);
+		// Remember the last three nodes of the random walk and avoid looping back on them.
+		// Init with the last three nodes from the actual path, if possible.
+		let mut nodes_to_avoid: [NodeId; 3] = [NodeId::from_pubkey(&path.last().unwrap().pubkey),
+			NodeId::from_pubkey(&path.get(path.len().saturating_sub(2)).unwrap().pubkey),
+			NodeId::from_pubkey(&path.get(path.len().saturating_sub(3)).unwrap().pubkey)];
+
+		// Choose the last publicly known node as the starting point for the random walk.
+		let mut cur_hop: Option<NodeId> = None;
+		let mut path_nonce = [0u8; 12];
+		if let Some(starting_hop) = path.iter().rev()
+			.find(|h| network_nodes.contains_key(&NodeId::from_pubkey(&h.pubkey))) {
+				cur_hop = Some(NodeId::from_pubkey(&starting_hop.pubkey));
+				path_nonce.copy_from_slice(&cur_hop.unwrap().as_slice()[..12]);
+		}
 
-			// Init PRNG with path nonce
-			let mut path_nonce = [0u8; 12];
-			path_nonce.copy_from_slice(&cur_node_id.as_slice()[..12]);
-			let mut prng = ChaCha20::new(random_seed_bytes, &path_nonce);
-			let mut random_path_bytes = [0u8; ::core::mem::size_of::<usize>()];
+		// Init PRNG with the path-dependant nonce, which is static for private paths.
+		let mut prng = ChaCha20::new(random_seed_bytes, &path_nonce);
+		let mut random_path_bytes = [0u8; ::core::mem::size_of::<usize>()];
 
-			// Pick a random path length in [1 .. 3]
-			prng.process_in_place(&mut random_path_bytes);
-			let random_walk_length = usize::from_be_bytes(random_path_bytes).wrapping_rem(3).wrapping_add(1);
+		// Pick a random path length in [1 .. 3]
+		prng.process_in_place(&mut random_path_bytes);
+		let random_walk_length = usize::from_be_bytes(random_path_bytes).wrapping_rem(3).wrapping_add(1);
 
-			for _random_hop in 0..random_walk_length {
+		for random_hop in 0..random_walk_length {
+			// If we don't find a suitable offset in the public network graph, we default to
+			// MEDIAN_HOP_CLTV_EXPIRY_DELTA.
+			let mut random_hop_offset = MEDIAN_HOP_CLTV_EXPIRY_DELTA;
+
+			if let Some(cur_node_id) = cur_hop {
 				if let Some(cur_node) = network_nodes.get(&cur_node_id) {
-					// Randomly choose the next hop
+					// Randomly choose the next unvisited hop.
 					prng.process_in_place(&mut random_path_bytes);
-					if let Some(random_channel) = usize::from_be_bytes(random_path_bytes).checked_rem(cur_node.channels.len())
+					if let Some(random_channel) = usize::from_be_bytes(random_path_bytes)
+						.checked_rem(cur_node.channels.len())
 						.and_then(|index| cur_node.channels.get(index))
 						.and_then(|id| network_channels.get(id)) {
 							random_channel.as_directed_from(&cur_node_id).map(|(dir_info, next_id)| {
-								dir_info.direction().map(|channel_update_info|
-									shadow_ctlv_expiry_delta_offset = shadow_ctlv_expiry_delta_offset
-										.checked_add(channel_update_info.cltv_expiry_delta.into())
-										.unwrap_or(shadow_ctlv_expiry_delta_offset));
-								cur_node_id = *next_id;
+								if !nodes_to_avoid.iter().any(|x| x == next_id) {
+									nodes_to_avoid[random_hop] = *next_id;
+									dir_info.direction().map(|channel_update_info| {
+										random_hop_offset = channel_update_info.cltv_expiry_delta.into();
+										cur_hop = Some(*next_id);
+									});
+								}
 							});
 						}
 				}
 			}
-		} else {
-			// If the entire path is private, choose a random offset from multiples of
-			// MEDIAN_HOP_CLTV_EXPIRY_DELTA
-			let mut prng = ChaCha20::new(random_seed_bytes, &[0u8; 8]);
-			let mut random_bytes = [0u8; 4];
-			prng.process_in_place(&mut random_bytes);
-			let random_walk_length = u32::from_be_bytes(random_bytes).wrapping_rem(3).wrapping_add(1);
-			shadow_ctlv_expiry_delta_offset = random_walk_length * MEDIAN_HOP_CLTV_EXPIRY_DELTA;
+
+			shadow_ctlv_expiry_delta_offset = shadow_ctlv_expiry_delta_offset
+				.checked_add(random_hop_offset)
+				.unwrap_or(shadow_ctlv_expiry_delta_offset);
 		}
 
 		// Limit the total offset to reduce the worst-case locked liquidity timevalue
@@ -1629,13 +1788,15 @@ fn add_random_cltv_offset(route: &mut Route, payment_params: &PaymentParameters,
 #[cfg(test)]
 mod tests {
 	use routing::network_graph::{NetworkGraph, NetGraphMsgHandler, NodeId};
-	use routing::router::{get_route, add_random_cltv_offset, PaymentParameters, Route, RouteHint, RouteHintHop, RouteHop, RoutingFees, DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA};
-	use routing::scoring::Score;
+	use routing::router::{get_route, add_random_cltv_offset, default_node_features,
+		PaymentParameters, Route, RouteHint, RouteHintHop, RouteHop, RoutingFees,
+		DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA, MAX_PATH_LENGTH_ESTIMATE};
+	use routing::scoring::{ChannelUsage, Score};
 	use chain::transaction::OutPoint;
 	use chain::keysinterface::KeysInterface;
 	use ln::features::{ChannelFeatures, InitFeatures, InvoiceFeatures, NodeFeatures};
 	use ln::msgs::{ErrorAction, LightningError, OptionalField, UnsignedChannelAnnouncement, ChannelAnnouncement, RoutingMessageHandler,
-	   NodeAnnouncement, UnsignedNodeAnnouncement, ChannelUpdate, UnsignedChannelUpdate};
+		NodeAnnouncement, UnsignedNodeAnnouncement, ChannelUpdate, UnsignedChannelUpdate};
 	use ln::channelmanager;
 	use util::test_utils;
 	use util::chacha20::ChaCha20;
@@ -1653,7 +1814,7 @@ mod tests {
 
 	use hex;
 
-	use bitcoin::secp256k1::key::{PublicKey,SecretKey};
+	use bitcoin::secp256k1::{PublicKey,SecretKey};
 	use bitcoin::secp256k1::{Secp256k1, All};
 
 	use prelude::*;
@@ -1668,19 +1829,26 @@ mod tests {
 				node_id,
 				unspendable_punishment_reserve: 0,
 				forwarding_info: None,
+				outbound_htlc_minimum_msat: None,
+				outbound_htlc_maximum_msat: None,
 			},
 			funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
+			channel_type: None,
 			short_channel_id,
+			inbound_scid_alias: None,
 			channel_value_satoshis: 0,
 			user_channel_id: 0,
 			balance_msat: 0,
 			outbound_capacity_msat,
+			next_outbound_htlc_limit_msat: outbound_capacity_msat,
 			inbound_capacity_msat: 42,
 			unspendable_punishment_reserve: None,
 			confirmations_required: None,
 			force_close_spend_delay: None,
 			is_outbound: true, is_funding_locked: true,
 			is_usable: true, is_public: true,
+			inbound_htlc_minimum_msat: None,
+			inbound_htlc_maximum_msat: None,
 		}
 	}
 
@@ -1705,10 +1873,10 @@ mod tests {
 
 		let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_announcement.encode()[..])[..]);
 		let valid_announcement = ChannelAnnouncement {
-			node_signature_1: secp_ctx.sign(&msghash, node_1_privkey),
-			node_signature_2: secp_ctx.sign(&msghash, node_2_privkey),
-			bitcoin_signature_1: secp_ctx.sign(&msghash, node_1_privkey),
-			bitcoin_signature_2: secp_ctx.sign(&msghash, node_2_privkey),
+			node_signature_1: secp_ctx.sign_ecdsa(&msghash, node_1_privkey),
+			node_signature_2: secp_ctx.sign_ecdsa(&msghash, node_2_privkey),
+			bitcoin_signature_1: secp_ctx.sign_ecdsa(&msghash, node_1_privkey),
+			bitcoin_signature_2: secp_ctx.sign_ecdsa(&msghash, node_2_privkey),
 			contents: unsigned_announcement.clone(),
 		};
 		match net_graph_msg_handler.handle_channel_announcement(&valid_announcement) {
@@ -1723,7 +1891,7 @@ mod tests {
 	) {
 		let msghash = hash_to_message!(&Sha256dHash::hash(&update.encode()[..])[..]);
 		let valid_channel_update = ChannelUpdate {
-			signature: secp_ctx.sign(&msghash, node_privkey),
+			signature: secp_ctx.sign_ecdsa(&msghash, node_privkey),
 			contents: update.clone()
 		};
 
@@ -1750,7 +1918,7 @@ mod tests {
 		};
 		let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_announcement.encode()[..])[..]);
 		let valid_announcement = NodeAnnouncement {
-			signature: secp_ctx.sign(&msghash, node_privkey),
+			signature: secp_ctx.sign_ecdsa(&msghash, node_privkey),
 			contents: unsigned_announcement.clone()
 		};
 
@@ -1761,7 +1929,7 @@ mod tests {
 	}
 
 	fn get_nodes(secp_ctx: &Secp256k1<All>) -> (SecretKey, PublicKey, Vec<SecretKey>, Vec<PublicKey>) {
-		let privkeys: Vec<SecretKey> = (2..10).map(|i| {
+		let privkeys: Vec<SecretKey> = (2..22).map(|i| {
 			SecretKey::from_slice(&hex::decode(format!("{:02x}", i).repeat(32)).unwrap()[..]).unwrap()
 		}).collect();
 
@@ -1788,6 +1956,57 @@ mod tests {
 		}
 	}
 
+	fn build_line_graph() -> (
+		Secp256k1<All>, sync::Arc<NetworkGraph>, NetGraphMsgHandler<sync::Arc<NetworkGraph>,
+		sync::Arc<test_utils::TestChainSource>, sync::Arc<crate::util::test_utils::TestLogger>>,
+		sync::Arc<test_utils::TestChainSource>, sync::Arc<test_utils::TestLogger>,
+	) {
+		let secp_ctx = Secp256k1::new();
+		let logger = Arc::new(test_utils::TestLogger::new());
+		let chain_monitor = Arc::new(test_utils::TestChainSource::new(Network::Testnet));
+		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));
+
+		// Build network from our_id to node 19:
+		// our_id -1(1)2- node0 -1(2)2- node1 - ... - node19
+		let (our_privkey, _, privkeys, _) = get_nodes(&secp_ctx);
+
+		for (idx, (cur_privkey, next_privkey)) in core::iter::once(&our_privkey)
+			.chain(privkeys.iter()).zip(privkeys.iter()).enumerate() {
+			let cur_short_channel_id = (idx as u64) + 1;
+			add_channel(&net_graph_msg_handler, &secp_ctx, &cur_privkey, &next_privkey,
+				ChannelFeatures::from_le_bytes(id_to_feature_flags(1)), cur_short_channel_id);
+			update_channel(&net_graph_msg_handler, &secp_ctx, &cur_privkey, UnsignedChannelUpdate {
+				chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+				short_channel_id: cur_short_channel_id,
+				timestamp: idx as u32,
+				flags: 0,
+				cltv_expiry_delta: 0,
+				htlc_minimum_msat: 0,
+				htlc_maximum_msat: OptionalField::Absent,
+				fee_base_msat: 0,
+				fee_proportional_millionths: 0,
+				excess_data: Vec::new()
+			});
+			update_channel(&net_graph_msg_handler, &secp_ctx, &next_privkey, UnsignedChannelUpdate {
+				chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+				short_channel_id: cur_short_channel_id,
+				timestamp: (idx as u32)+1,
+				flags: 1,
+				cltv_expiry_delta: 0,
+				htlc_minimum_msat: 0,
+				htlc_maximum_msat: OptionalField::Absent,
+				fee_base_msat: 0,
+				fee_proportional_millionths: 0,
+				excess_data: Vec::new()
+			});
+			add_or_update_node(&net_graph_msg_handler, &secp_ctx, next_privkey,
+				NodeFeatures::from_le_bytes(id_to_feature_flags(1)), 0);
+		}
+
+		(secp_ctx, network_graph, net_graph_msg_handler, chain_monitor, logger)
+	}
+
 	fn build_graph() -> (
 		Secp256k1<All>,
 		sync::Arc<NetworkGraph>,
@@ -2490,7 +2709,8 @@ mod tests {
 		let random_seed_bytes = keys_manager.get_secure_random_bytes();
 
 		// Disable nodes 1, 2, and 8 by requiring unknown feature bits
-		let unknown_features = NodeFeatures::known().set_unknown_feature_required();
+		let mut unknown_features = NodeFeatures::known();
+		unknown_features.set_unknown_feature_required();
 		add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[0], unknown_features.clone(), 1);
 		add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[1], unknown_features.clone(), 1);
 		add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[7], unknown_features.clone(), 1);
@@ -2727,7 +2947,7 @@ mod tests {
 		assert_eq!(route.paths[0][4].short_channel_id, 8);
 		assert_eq!(route.paths[0][4].fee_msat, 100);
 		assert_eq!(route.paths[0][4].cltv_expiry_delta, 42);
-		assert_eq!(route.paths[0][4].node_features.le_flags(), &Vec::<u8>::new()); // We dont pass flags in from invoices yet
+		assert_eq!(route.paths[0][4].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet
 		assert_eq!(route.paths[0][4].channel_features.le_flags(), &Vec::<u8>::new()); // We can't learn any flags from invoices, sadly
 	}
 
@@ -2803,7 +3023,7 @@ mod tests {
 		assert_eq!(route.paths[0][4].short_channel_id, 8);
 		assert_eq!(route.paths[0][4].fee_msat, 100);
 		assert_eq!(route.paths[0][4].cltv_expiry_delta, 42);
-		assert_eq!(route.paths[0][4].node_features.le_flags(), &Vec::<u8>::new()); // We dont pass flags in from invoices yet
+		assert_eq!(route.paths[0][4].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet
 		assert_eq!(route.paths[0][4].channel_features.le_flags(), &Vec::<u8>::new()); // We can't learn any flags from invoices, sadly
 	}
 
@@ -2900,7 +3120,7 @@ mod tests {
 		assert_eq!(route.paths[0][3].short_channel_id, last_hops[0].0[1].short_channel_id);
 		assert_eq!(route.paths[0][3].fee_msat, 100);
 		assert_eq!(route.paths[0][3].cltv_expiry_delta, 42);
-		assert_eq!(route.paths[0][3].node_features.le_flags(), &Vec::<u8>::new()); // We dont pass flags in from invoices yet
+		assert_eq!(route.paths[0][3].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet
 		assert_eq!(route.paths[0][3].channel_features.le_flags(), &Vec::<u8>::new()); // We can't learn any flags from invoices, sadly
 	}
 
@@ -2965,14 +3185,14 @@ mod tests {
 		assert_eq!(route.paths[0][2].short_channel_id, last_hops[0].0[0].short_channel_id);
 		assert_eq!(route.paths[0][2].fee_msat, 0);
 		assert_eq!(route.paths[0][2].cltv_expiry_delta, 129);
-		assert_eq!(route.paths[0][2].node_features.le_flags(), &Vec::<u8>::new()); // We dont pass flags in from invoices yet
+		assert_eq!(route.paths[0][2].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet
 		assert_eq!(route.paths[0][2].channel_features.le_flags(), &Vec::<u8>::new()); // We can't learn any flags from invoices, sadly
 
 		assert_eq!(route.paths[0][3].pubkey, nodes[6]);
 		assert_eq!(route.paths[0][3].short_channel_id, last_hops[0].0[1].short_channel_id);
 		assert_eq!(route.paths[0][3].fee_msat, 100);
 		assert_eq!(route.paths[0][3].cltv_expiry_delta, 42);
-		assert_eq!(route.paths[0][3].node_features.le_flags(), &Vec::<u8>::new()); // We dont pass flags in from invoices yet
+		assert_eq!(route.paths[0][3].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet
 		assert_eq!(route.paths[0][3].channel_features.le_flags(), &Vec::<u8>::new()); // We can't learn any flags from invoices, sadly
 	}
 
@@ -3063,7 +3283,7 @@ mod tests {
 		assert_eq!(route.paths[0][4].short_channel_id, 8);
 		assert_eq!(route.paths[0][4].fee_msat, 100);
 		assert_eq!(route.paths[0][4].cltv_expiry_delta, 42);
-		assert_eq!(route.paths[0][4].node_features.le_flags(), &Vec::<u8>::new()); // We dont pass flags in from invoices yet
+		assert_eq!(route.paths[0][4].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet
 		assert_eq!(route.paths[0][4].channel_features.le_flags(), &Vec::<u8>::new()); // We can't learn any flags from invoices, sadly
 	}
 
@@ -3093,7 +3313,7 @@ mod tests {
 		assert_eq!(route.paths[0][1].short_channel_id, 8);
 		assert_eq!(route.paths[0][1].fee_msat, 100);
 		assert_eq!(route.paths[0][1].cltv_expiry_delta, 42);
-		assert_eq!(route.paths[0][1].node_features.le_flags(), &Vec::<u8>::new()); // We dont pass flags in from invoices yet
+		assert_eq!(route.paths[0][1].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet
 		assert_eq!(route.paths[0][1].channel_features.le_flags(), &Vec::<u8>::new()); // We can't learn any flags from invoices, sadly
 
 		last_hops[0].0[0].fees.base_msat = 1000;
@@ -3130,7 +3350,7 @@ mod tests {
 		assert_eq!(route.paths[0][3].short_channel_id, 10);
 		assert_eq!(route.paths[0][3].fee_msat, 100);
 		assert_eq!(route.paths[0][3].cltv_expiry_delta, 42);
-		assert_eq!(route.paths[0][3].node_features.le_flags(), &Vec::<u8>::new()); // We dont pass flags in from invoices yet
+		assert_eq!(route.paths[0][3].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet
 		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
@@ -3171,7 +3391,7 @@ mod tests {
 		assert_eq!(route.paths[0][4].short_channel_id, 8);
 		assert_eq!(route.paths[0][4].fee_msat, 2000);
 		assert_eq!(route.paths[0][4].cltv_expiry_delta, 42);
-		assert_eq!(route.paths[0][4].node_features.le_flags(), &Vec::<u8>::new()); // We dont pass flags in from invoices yet
+		assert_eq!(route.paths[0][4].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet
 		assert_eq!(route.paths[0][4].channel_features.le_flags(), &Vec::<u8>::new()); // We can't learn any flags from invoices, sadly
 	}
 
@@ -3223,7 +3443,7 @@ mod tests {
 		assert_eq!(route.paths[0][1].short_channel_id, 8);
 		assert_eq!(route.paths[0][1].fee_msat, 1000000);
 		assert_eq!(route.paths[0][1].cltv_expiry_delta, 42);
-		assert_eq!(route.paths[0][1].node_features.le_flags(), &[0; 0]); // We dont pass flags in from invoices yet
+		assert_eq!(route.paths[0][1].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet
 		assert_eq!(route.paths[0][1].channel_features.le_flags(), &[0; 0]); // We can't learn any flags from invoices, sadly
 	}
 
@@ -3333,7 +3553,7 @@ mod tests {
 			assert_eq!(path.last().unwrap().fee_msat, 250_000_000);
 		}
 
-		// Check that setting outbound_capacity_msat in first_hops limits the channels.
+		// Check that setting next_outbound_htlc_limit_msat in first_hops limits the channels.
 		// Disable channel #1 and use another first hop.
 		update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
 			chain_hash: genesis_block(Network::Testnet).header.block_hash(),
@@ -3348,7 +3568,7 @@ mod tests {
 			excess_data: Vec::new()
 		});
 
-		// Now, limit the first_hop by the outbound_capacity_msat of 200_000 sats.
+		// Now, limit the first_hop by the next_outbound_htlc_limit_msat of 200_000 sats.
 		let our_chans = vec![get_channel_details(Some(42), nodes[0].clone(), InitFeatures::from_le_bytes(vec![0b11]), 200_000_000)];
 
 		{
@@ -4892,6 +5112,32 @@ mod tests {
 			assert_eq!(route.paths[1][0].short_channel_id, 2);
 			assert_eq!(route.paths[1][0].fee_msat, 50_000);
 		}
+
+		{
+			// If we have a bunch of outbound channels to the same node, where most are not
+			// sufficient to pay the full payment, but one is, we should default to just using the
+			// one single channel that has sufficient balance, avoiding MPP.
+			//
+			// If we have several options above the 3xpayment value threshold, we should pick the
+			// smallest of them, avoiding further fragmenting our available outbound balance to
+			// this node.
+			let route = get_route(&our_id, &payment_params, &network_graph.read_only(), Some(&[
+				&get_channel_details(Some(2), nodes[0], InitFeatures::known(), 50_000),
+				&get_channel_details(Some(3), nodes[0], InitFeatures::known(), 50_000),
+				&get_channel_details(Some(5), nodes[0], InitFeatures::known(), 50_000),
+				&get_channel_details(Some(6), nodes[0], InitFeatures::known(), 300_000),
+				&get_channel_details(Some(7), nodes[0], InitFeatures::known(), 50_000),
+				&get_channel_details(Some(8), nodes[0], InitFeatures::known(), 50_000),
+				&get_channel_details(Some(9), nodes[0], InitFeatures::known(), 50_000),
+				&get_channel_details(Some(4), nodes[0], InitFeatures::known(), 1_000_000),
+			]), 100_000, 42, Arc::clone(&logger), &scorer, &random_seed_bytes).unwrap();
+			assert_eq!(route.paths.len(), 1);
+			assert_eq!(route.paths[0].len(), 1);
+
+			assert_eq!(route.paths[0][0].pubkey, nodes[0]);
+			assert_eq!(route.paths[0][0].short_channel_id, 6);
+			assert_eq!(route.paths[0][0].fee_msat, 100_000);
+		}
 	}
 
 	#[test]
@@ -4937,7 +5183,7 @@ mod tests {
 		fn write<W: Writer>(&self, _w: &mut W) -> Result<(), ::io::Error> { unimplemented!() }
 	}
 	impl Score for BadChannelScorer {
-		fn channel_penalty_msat(&self, short_channel_id: u64, _send_amt: u64, _capacity_msat: u64, _source: &NodeId, _target: &NodeId) -> u64 {
+		fn channel_penalty_msat(&self, short_channel_id: u64, _: &NodeId, _: &NodeId, _: ChannelUsage) -> u64 {
 			if short_channel_id == self.short_channel_id { u64::max_value() } else { 0 }
 		}
 
@@ -4955,7 +5201,7 @@ mod tests {
 	}
 
 	impl Score for BadNodeScorer {
-		fn channel_penalty_msat(&self, _short_channel_id: u64, _send_amt: u64, _capacity_msat: u64, _source: &NodeId, target: &NodeId) -> u64 {
+		fn channel_penalty_msat(&self, _: u64, _: &NodeId, target: &NodeId, _: ChannelUsage) -> u64 {
 			if *target == self.node_id { u64::max_value() } else { 0 }
 		}
 
@@ -5111,6 +5357,35 @@ mod tests {
 		}
 	}
 
+	#[test]
+	fn limits_path_length() {
+		let (secp_ctx, network, _, _, logger) = build_line_graph();
+		let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
+		let network_graph = network.read_only();
+
+		let scorer = test_utils::TestScorer::with_penalty(0);
+		let keys_manager = test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet);
+		let random_seed_bytes = keys_manager.get_secure_random_bytes();
+
+		// First check we can actually create a long route on this graph.
+		let feasible_payment_params = PaymentParameters::from_node_id(nodes[18]);
+		let route = get_route(&our_id, &feasible_payment_params, &network_graph, None, 100, 0,
+			Arc::clone(&logger), &scorer, &random_seed_bytes).unwrap();
+		let path = route.paths[0].iter().map(|hop| hop.short_channel_id).collect::<Vec<_>>();
+		assert!(path.len() == MAX_PATH_LENGTH_ESTIMATE.into());
+
+		// But we can't create a path surpassing the MAX_PATH_LENGTH_ESTIMATE limit.
+		let fail_payment_params = PaymentParameters::from_node_id(nodes[19]);
+		match get_route(&our_id, &fail_payment_params, &network_graph, None, 100, 0,
+			Arc::clone(&logger), &scorer, &random_seed_bytes)
+		{
+			Err(LightningError { err, .. } ) => {
+				assert_eq!(err, "Failed to find a path to the given destination");
+			},
+			Ok(_) => panic!("Expected error"),
+		}
+	}
+
 	#[test]
 	fn adds_and_limits_cltv_offset() {
 		let (secp_ctx, network_graph, _, _, logger) = build_graph();
@@ -5250,8 +5525,9 @@ mod tests {
 				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.read_only(), None, amt, 42, &test_utils::TestLogger::new(), &scorer, &random_seed_bytes).is_ok() {
+				let logger = test_utils::TestLogger::new();
+				let scorer = ProbabilisticScorer::new(params, &graph, &logger);
+				if get_route(src, &payment_params, &graph.read_only(), None, amt, 42, &logger, &scorer, &random_seed_bytes).is_ok() {
 					continue 'load_endpoints;
 				}
 			}
@@ -5286,8 +5562,9 @@ mod tests {
 				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.read_only(), None, amt, 42, &test_utils::TestLogger::new(), &scorer, &random_seed_bytes).is_ok() {
+				let logger = test_utils::TestLogger::new();
+				let scorer = ProbabilisticScorer::new(params, &graph, &logger);
+				if get_route(src, &payment_params, &graph.read_only(), None, amt, 42, &logger, &scorer, &random_seed_bytes).is_ok() {
 					continue 'load_endpoints;
 				}
 			}
@@ -5333,6 +5610,7 @@ mod benches {
 	use ln::features::{InitFeatures, InvoiceFeatures};
 	use routing::scoring::{FixedPenaltyScorer, ProbabilisticScorer, ProbabilisticScoringParameters, Scorer};
 	use util::logger::{Logger, Record};
+	use util::test_utils::TestLogger;
 
 	use test::Bencher;
 
@@ -5360,15 +5638,20 @@ mod benches {
 				node_id,
 				unspendable_punishment_reserve: 0,
 				forwarding_info: None,
+				outbound_htlc_minimum_msat: None,
+				outbound_htlc_maximum_msat: None,
 			},
 			funding_txo: Some(OutPoint {
 				txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0
 			}),
+			channel_type: None,
 			short_channel_id: Some(1),
+			inbound_scid_alias: None,
 			channel_value_satoshis: 10_000_000,
 			user_channel_id: 0,
 			balance_msat: 10_000_000,
 			outbound_capacity_msat: 10_000_000,
+			next_outbound_htlc_limit_msat: 10_000_000,
 			inbound_capacity_msat: 0,
 			unspendable_punishment_reserve: None,
 			confirmations_required: None,
@@ -5377,6 +5660,8 @@ mod benches {
 			is_funding_locked: true,
 			is_usable: true,
 			is_public: true,
+			inbound_htlc_minimum_msat: None,
+			inbound_htlc_maximum_msat: None,
 		}
 	}
 
@@ -5410,17 +5695,19 @@ mod benches {
 
 	#[bench]
 	fn generate_routes_with_probabilistic_scorer(bench: &mut Bencher) {
+		let logger = TestLogger::new();
 		let network_graph = read_network_graph();
 		let params = ProbabilisticScoringParameters::default();
-		let scorer = ProbabilisticScorer::new(params, &network_graph);
+		let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
 		generate_routes(bench, &network_graph, scorer, InvoiceFeatures::empty());
 	}
 
 	#[bench]
 	fn generate_mpp_routes_with_probabilistic_scorer(bench: &mut Bencher) {
+		let logger = TestLogger::new();
 		let network_graph = read_network_graph();
 		let params = ProbabilisticScoringParameters::default();
-		let scorer = ProbabilisticScorer::new(params, &network_graph);
+		let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
 		generate_routes(bench, &network_graph, scorer, InvoiceFeatures::known());
 	}