Repository: lightningnetwork/lnd
Pull request #4602 (2020-09-08 11:49:39)

routing: proportional attempt cost
In https://github.com/lightningnetwork/lnd/pull/2802 probability based routing was introduced. One of the control parameters introduced is the payment attempt cost.

The payment attempt cost is a virtual cost that is assigned to a failed payment attempt. This parameter influences the trade off between cheap and reliable routes. Specifically it adds an extra term to the pathfinding cost function of `attempt_cost / probability`.

Probability estimation is based on past failures and successes. The impact of failures on probability estimates diminishes relatively quickly (default "half life time" is one hour), but success experiences keep having a constant effect on probability until a failure happens.

For a presentation about mission control, see https://twitter.com/joostjgr/status/1186177262238031872.

For nodes that aren't continuously sending payments and use default mission control parameters, it is likely that failures don't have much impact on mission control performance beyond the currently active payment. For those nodes, recorded information about previously successful routes is the main driver for pathfinding.

The probability estimate is 60% (by default) for unknown hops (or hops with older failures recorded) and 95% for previously successful hops.

Suppose:
* There is a route S through a success hop with routing fee 0.1%
* There is a route U though an unknown hop with routing fee 0.01%
* We are sending 4M sats

What should the attempt cost `c` be set to for pathfinding to choose route S?
`4M * 0.1% + c / 0.95 = 4M * 0.01% + c / 0.6`
Solving for `c` results in an attempt cost = 5863 sats.

So we need to set a pretty high attempt cost to not get distracted by unknown routes. In the reality of the Lightning Network, these unknown routes do often fail and cause a lengthy payment process. Good liquidity isn't the cheapest liquidity generally.

The current default attempt cost is set at 100 sat. For the scenario described above with a relatively large gap in fees and a mid-size payment amount, the default setting would effectively disable probability based routing and lead to a lot of exploration even though successful routes may be known.

One thing that becomes clear is that an absolute attempt cost is unlikely to work for every payment amount. This PR therefore introduces an additional control parameter that allows setting a proportional attempt cost as well. The goal of this is to improve the default pathfinding performance in particular for large payment amounts.


Patch:
diff --git a/lnrpc/routerrpc/config.go b/lnrpc/routerrpc/config.go
index 045561dbf..1d1a6f8d4 100644
--- a/lnrpc/routerrpc/config.go
+++ b/lnrpc/routerrpc/config.go
@@ -46,9 +46,9 @@ func DefaultConfig() *Config {
 		AprioriWeight:         routing.DefaultAprioriWeight,
 		MinRouteProbability:   routing.DefaultMinRouteProbability,
 		PenaltyHalfLife:       routing.DefaultPenaltyHalfLife,
-		AttemptCost: routing.DefaultPaymentAttemptPenalty.
-			ToSatoshis(),
-		MaxMcHistory: routing.DefaultMaxMcHistory,
+		AttemptCost:           routing.DefaultAttemptCost.ToSatoshis(),
+		AttemptCostPPM:        routing.DefaultAttemptCostPPM,
+		MaxMcHistory:          routing.DefaultMaxMcHistory,
 	}
 
 	return &Config{
@@ -63,6 +63,7 @@ func GetRoutingConfig(cfg *Config) *RoutingConfig {
 		AprioriWeight:         cfg.AprioriWeight,
 		MinRouteProbability:   cfg.MinRouteProbability,
 		AttemptCost:           cfg.AttemptCost,
+		AttemptCostPPM:        cfg.AttemptCostPPM,
 		PenaltyHalfLife:       cfg.PenaltyHalfLife,
 		MaxMcHistory:          cfg.MaxMcHistory,
 	}
diff --git a/lnrpc/routerrpc/routing_config.go b/lnrpc/routerrpc/routing_config.go
index 98b3594cf..dd0fe93d1 100644
--- a/lnrpc/routerrpc/routing_config.go
+++ b/lnrpc/routerrpc/routing_config.go
@@ -29,10 +29,16 @@ type RoutingConfig struct {
 	// channel is back at 50% probability.
 	PenaltyHalfLife time.Duration `long:"penaltyhalflife" description:"Defines the duration after which a penalized node or channel is back at 50% probability"`
 
-	// AttemptCost is the virtual cost in path finding weight units of
-	// executing a payment attempt that fails. It is used to trade off
-	// potentially better routes against their probability of succeeding.
-	AttemptCost btcutil.Amount `long:"attemptcost" description:"The (virtual) cost in sats of a failed payment attempt"`
+	// AttemptCost is the fixed virtual cost in path finding of a failed
+	// payment attempt. It is used to trade off potentially better routes
+	// against their probability of succeeding.
+	AttemptCost btcutil.Amount `long:"attemptcost" description:"The fixed (virtual) cost in sats of a failed payment attempt"`
+
+	// AttemptCostPPM is the proportional virtual cost in path finding of a
+	// failed payment attempt. It is used to trade off potentially better
+	// routes against their probability of succeeding. This parameter is
+	// expressed in parts per million of the total payment amount.
+	AttemptCostPPM int64 `long:"attemptcostppm" description:"The proportional (virtual) cost in sats of a failed payment attempt expressed in parts per million of the total payment amount"`
 
 	// MaxMcHistory defines the maximum number of payment results that
 	// are held on disk by mission control.
diff --git a/routing/pathfind.go b/routing/pathfind.go
index 6d5e9abd5..cfc7afaed 100644
--- a/routing/pathfind.go
+++ b/routing/pathfind.go
@@ -45,11 +45,22 @@ type pathFinder = func(g *graphParams, r *RestrictParams,
 	[]*channeldb.ChannelEdgePolicy, error)
 
 var (
-	// DefaultPaymentAttemptPenalty is the virtual cost in path finding weight
-	// units of executing a payment attempt that fails. It is used to trade
-	// off potentially better routes against their probability of
-	// succeeding.
-	DefaultPaymentAttemptPenalty = lnwire.NewMSatFromSatoshis(100)
+	// DefaultAttemptCost is the default fixed virtual cost in path finding
+	// of a failed payment attempt. It is used to trade off potentially
+	// better routes against their probability of succeeding.
+	DefaultAttemptCost = lnwire.NewMSatFromSatoshis(100)
+
+	// DefaultAttemptCostPPM is the default proportional virtual cost in
+	// path finding weight units of executing a payment attempt that fails.
+	// It is used to trade off potentially better routes against their
+	// probability of succeeding. This parameter is expressed in parts per
+	// million of the payment amount.
+	//
+	// It is impossible to pick a perfect default value. The current value
+	// of 0.1% is based on the idea that a transaction fee of 1% is within
+	// reasonable territory and that a payment shouldn't need more than 10
+	// attempts.
+	DefaultAttemptCostPPM = int64(1000)
 
 	// DefaultMinRouteProbability is the default minimum probability for routes
 	// returned from findPath.
@@ -315,11 +326,16 @@ type RestrictParams struct {
 // PathFindingConfig defines global parameters that control the trade-off in
 // path finding between fees and probabiity.
 type PathFindingConfig struct {
-	// PaymentAttemptPenalty is the virtual cost in path finding weight
-	// units of executing a payment attempt that fails. It is used to trade
-	// off potentially better routes against their probability of
-	// succeeding.
-	PaymentAttemptPenalty lnwire.MilliSatoshi
+	// AttemptCost is the fixed virtual cost in path finding of a failed
+	// payment attempt. It is used to trade off potentially better routes
+	// against their probability of succeeding.
+	AttemptCost lnwire.MilliSatoshi
+
+	// AttemptCostPPM is the proportional virtual cost in path finding of a
+	// failed payment attempt. It is used to trade off potentially better
+	// routes against their probability of succeeding. This parameter is
+	// expressed in parts per million of the total payment amount.
+	AttemptCostPPM int64
 
 	// MinProbability defines the minimum success probability of the
 	// returned route.
@@ -550,6 +566,14 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 	// if the cltv limit is MaxUint32.
 	absoluteCltvLimit := uint64(r.CltvLimit) + uint64(finalHtlcExpiry)
 
+	// Calculate the absolute attempt cost that is used for probability
+	// estimation.
+	absoluteAttemptCost := int64(cfg.AttemptCost) +
+		int64(amt)*cfg.AttemptCostPPM/1000000
+
+	log.Debugf("Pathfinding absolute attempt cost: %v sats",
+		float64(absoluteAttemptCost)/1000)
+
 	// processEdge is a helper closure that will be used to make sure edges
 	// satisfy our specific requirements.
 	processEdge := func(fromVertex route.Vertex,
@@ -644,7 +668,7 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 		// probability.
 		tempDist := getProbabilityBasedDist(
 			tempWeight, probability,
-			int64(cfg.PaymentAttemptPenalty),
+			absoluteAttemptCost,
 		)
 
 		// If there is already a best route stored, compare this
diff --git a/sample-lnd.conf b/sample-lnd.conf
index b92f8b76c..873a6d6df 100644
--- a/sample-lnd.conf
+++ b/sample-lnd.conf
@@ -619,8 +619,12 @@ litecoin.node=ltcd
 ; probability (default: 1h0m0s)
 ; routerrpc.penaltyhalflife=2h                            
 
-; The (virtual) cost in sats of a failed payment attempt (default: 100)
-; routerrpc.attemptcost=90                                
+; The (virtual) fixed cost in sats of a failed payment attempt (default: 100)
+; routerrpc.attemptcost=90     
+
+; The (virtual) proportional cost in ppm of the total amount of a failed payment
+; attempt (default: 1000)
+; routerrpc.attemptcostppm=900
 
 ; The maximum number of payment results that are held on disk by mission control
 ; (default: 1000)
diff --git a/server.go b/server.go
index cba47e395..9fb89aef6 100644
--- a/server.go
+++ b/server.go
@@ -724,14 +724,16 @@ func newServer(cfg *Config, listenAddrs []net.Addr,
 	}
 
 	srvrLog.Debugf("Instantiating payment session source with config: "+
-		"PaymentAttemptPenalty=%v, MinRouteProbability=%v",
+		"AttemptCost=%v + %v%%, MinRouteProbability=%v",
 		int64(routingConfig.AttemptCost),
+		float64(routingConfig.AttemptCostPPM)/10000,
 		routingConfig.MinRouteProbability)
 
 	pathFindingConfig := routing.PathFindingConfig{
-		PaymentAttemptPenalty: lnwire.NewMSatFromSatoshis(
+		AttemptCost: lnwire.NewMSatFromSatoshis(
 			routingConfig.AttemptCost,
 		),
+		AttemptCostPPM: routingConfig.AttemptCostPPM,
 		MinProbability: routingConfig.MinRouteProbability,
 	}
 


Test patch:
diff --git a/routing/integrated_routing_context_test.go b/routing/integrated_routing_context_test.go
index b223668e6..8cbeea539 100644
--- a/routing/integrated_routing_context_test.go
+++ b/routing/integrated_routing_context_test.go
@@ -65,8 +65,8 @@ func newIntegratedRoutingContext(t *testing.T) *integratedRoutingContext {
 		},
 
 		pathFindingCfg: PathFindingConfig{
-			PaymentAttemptPenalty: 1000,
-			MinProbability:        0.01,
+			AttemptCost:    1000,
+			MinProbability: 0.01,
 		},
 
 		source: source,
diff --git a/routing/pathfind_test.go b/routing/pathfind_test.go
index 92696ca38..9c4194039 100644
--- a/routing/pathfind_test.go
+++ b/routing/pathfind_test.go
@@ -2461,25 +2461,43 @@ func TestProbabilityRouting(t *testing.T) {
 		p10, p11, p20  float64
 		minProbability float64
 		expectedChan   uint64
+		amount         btcutil.Amount
 	}{
 		// Test two variations with probabilities that should multiply
 		// to the same total route probability. In both cases the three
 		// hop route should be the best route. The three hop route has a
 		// probability of 0.5 * 0.8 = 0.4. The fee is 5 (chan 10) + 8
-		// (chan 11) = 13. Path finding distance should work out to: 13
-		// + 10 (attempt penalty) / 0.4 = 38. The two hop route is 25 +
-		// 10 / 0.7 = 39.
+		// (chan 11) = 13. The attempt cost is 9 + 1% * 100 = 10. Path
+		// finding distance should work out to: 13 + 10 (attempt
+		// penalty) / 0.4 = 38. The two hop route is 25 + 10 / 0.7 = 39.
 		{
 			name: "three hop 1",
 			p10:  0.8, p11: 0.5, p20: 0.7,
 			minProbability: 0.1,
 			expectedChan:   10,
+			amount:         100,
 		},
 		{
 			name: "three hop 2",
 			p10:  0.5, p11: 0.8, p20: 0.7,
 			minProbability: 0.1,
 			expectedChan:   10,
+			amount:         100,
+		},
+
+		// If a larger amount is sent, the effect of the proportional
+		// attempt cost becomes more noticeable. This amount in this
+		// test brings the attempt cost to 9 + 1% * 300 = 12 sat. The
+		// three hop path finding distance should work out to: 13 + 12
+		// (attempt penalty) / 0.4 = 43. The two hop route is 25 + 12 /
+		// 0.7 = 42. For this higher amount, the two hop route is
+		// expected to be selected.
+		{
+			name: "two hop high amount",
+			p10:  0.8, p11: 0.5, p20: 0.7,
+			minProbability: 0.1,
+			expectedChan:   20,
+			amount:         300,
 		},
 
 		// If the probability of the two hop route is increased, its
@@ -2492,6 +2510,7 @@ func TestProbabilityRouting(t *testing.T) {
 			p10:  0.5, p11: 0.8, p20: 0.85,
 			minProbability: 0.1,
 			expectedChan:   20,
+			amount:         100,
 		},
 
 		// If the same probabilities are used with a probability lower bound of
@@ -2502,6 +2521,7 @@ func TestProbabilityRouting(t *testing.T) {
 			p10:  0.8, p11: 0.5, p20: 0.7,
 			minProbability: 0.5,
 			expectedChan:   20,
+			amount:         100,
 		},
 
 		// With a probability limit above the probability of both routes, we
@@ -2512,21 +2532,24 @@ func TestProbabilityRouting(t *testing.T) {
 			p10:  0.8, p11: 0.5, p20: 0.7,
 			minProbability: 0.8,
 			expectedChan:   0,
+			amount:         100,
 		},
 	}
 
 	for _, tc := range testCases {
+		tc := tc
+
 		t.Run(tc.name, func(t *testing.T) {
 			testProbabilityRouting(
-				t, tc.p10, tc.p11, tc.p20,
+				t, tc.amount, tc.p10, tc.p11, tc.p20,
 				tc.minProbability, tc.expectedChan,
 			)
 		})
 	}
 }
 
-func testProbabilityRouting(t *testing.T, p10, p11, p20, minProbability float64,
-	expectedChan uint64) {
+func testProbabilityRouting(t *testing.T, paymentAmt btcutil.Amount,
+	p10, p11, p20, minProbability float64, expectedChan uint64) {
 
 	t.Parallel()
 
@@ -2558,7 +2581,6 @@ func testProbabilityRouting(t *testing.T, p10, p11, p20, minProbability float64,
 
 	alias := ctx.testGraphInstance.aliasMap
 
-	paymentAmt := lnwire.NewMSatFromSatoshis(100)
 	target := ctx.testGraphInstance.aliasMap["target"]
 
 	// Configure a probability source with the test parameters.
@@ -2582,11 +2604,14 @@ func testProbabilityRouting(t *testing.T, p10, p11, p20, minProbability float64,
 	}
 
 	ctx.pathFindingConfig = PathFindingConfig{
-		PaymentAttemptPenalty: lnwire.NewMSatFromSatoshis(10),
-		MinProbability:        minProbability,
+		AttemptCost:    lnwire.NewMSatFromSatoshis(9),
+		AttemptCostPPM: 10000,
+		MinProbability: minProbability,
 	}
 
-	path, err := ctx.findPath(target, paymentAmt)
+	path, err := ctx.findPath(
+		target, lnwire.NewMSatFromSatoshis(paymentAmt),
+	)
 	if expectedChan == 0 {
 		if err != errNoPathFound {
 			t.Fatalf("expected no path found, but got %v", err)
@@ -2656,7 +2681,7 @@ func TestEqualCostRouteSelection(t *testing.T) {
 	}
 
 	ctx.pathFindingConfig = PathFindingConfig{
-		PaymentAttemptPenalty: lnwire.NewMSatFromSatoshis(1),
+		AttemptCost: lnwire.NewMSatFromSatoshis(1),
 	}
 
 	path, err := ctx.findPath(target, paymentAmt)
diff --git a/routing/router_test.go b/routing/router_test.go
index 9844b5268..400bace6a 100644
--- a/routing/router_test.go
+++ b/routing/router_test.go
@@ -79,8 +79,8 @@ func createTestCtxFromGraphInstance(startingHeight uint32, graphInstance *testGr
 	chainView := newMockChainView(chain)
 
 	pathFindingConfig := PathFindingConfig{
-		MinProbability:        0.01,
-		PaymentAttemptPenalty: 100,
+		MinProbability: 0.01,
+		AttemptCost:    100,
 	}
 
 	mcConfig := &MissionControlConfig{