Improving Lightning Network Pathfinding Latency by Path Splicing and Other Real-Time Strategy Game Techniques

Summary:

The Lightning Network's routing algorithm is different from game path-finding algorithms because paths are consumed by payments, and the algorithm does not know remote channel balance allocation which changes constantly. The cost of a path depends on the value being sent, which encourages algorithms to search for fast and good enough solutions with retries rather than optimal solutions using outdated/incomplete data.For `permuteroute`, there is no need for better error reporting as there is already sufficiently-good error reporting on route failures. The balancing factor between fixed and proportional costs can be determined by recording the average payment size of the user. Multi-part payments and trampoline offer room for algorithmic improvements and leveraging them resonates with the Lightning Network's routing algorithm.The routing problem is more similar to a circulation or network flow problem rather than path-finding. Flocking behavior can be used to retain the cohesion of a blob of units to avoid walking nearly the exact same path in multi-part payments. Another solution is to use `permuteoute` to find alternate routes that avoid the smallest-capacity channels but share the rest of the path with the original route until `permuteroute` fails.

Updated on: 2023-06-02T19:37:51.495910+00:00