pathfinding: capacity-dependent apriori model probability (path finding)

https://github.com/lightningnetwork/lnd/pull/6857

Host: bitromortac  -  PR author: bitromortac

Notes

  • In this PR review club we will have a closer look at pathfinding internals and upcoming improvements in this regard.
    • Original issue: https://github.com/lightningnetwork/lnd/issues/5988
    • Follow-up PR: https://github.com/lightningnetwork/lnd/pull/6815
  • Additional info:
    • https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)
    • https://en.wikipedia.org/wiki/Shortest_path_problem

Questions

  • What is the underlying algorithm used for pathfinding, where is it located in the LND code base?
  • What’s the graph type of the Lightning network in your opinion (in terms of pathfinding)?
  • What kind of ingredients enter into the pathfinding edge weight?
  • What is the role of the probability term?
  • Why should we include the capacity into pathfinding?
  • What’s the commit adding the new functionality?
  • Why don’t we just introduce a hard cutoff say at 3/4 of the channel capacity?
  • How is the probability of an edge altered, what is its effect (look at TestCapacityCutoff)?
  • Are channel capacities part of the gossip protocol? Are there cases when they are not available?
  • Which API endpoints are altered by this change?