Published on: 2019-08-09T10:37:38+00:00
A recent discovery has revealed that Lightning nodes are experiencing delays in finding routes between themselves and payee nodes. This has led to the exploration of alternative algorithms to improve the efficiency of pathfinding. One such algorithm proposed is `permuteroute`, which offers faster route discovery by avoiding the need to scan a large number of channels. However, it is noted that many public channels in the network are underutilized, indicating a need to focus on more achievable engineering improvements rather than distant ideas.The latest version of the Lightning Network software has made enhancements by incorporating past pathfinding attempts into its central "mission control" and learning from each attempt. This approach, known as JIT-Routing, is considered superior to `permuteroute`, but it is still suggested that immediate benefits can be gained from utilizing `permuteroute`. Additionally, to expedite payment routing to arbitrary nodes, a new command called `getroutequick` can be implemented, which utilizes cached Dijkstra data to find acceptable routes. Another option is to utilize the A* algorithm, provided that the costs from a node to all other nodes are precomputed and cached. However, it is important to note that if the channel topology changes, the cached data may become outdated and require recalculation.In terms of map preprocessing, the use of differential heuristics in A* can help reduce the number of nodes visited during pathfinding. This involves using multiple heuristics and their differences to guide the search algorithm towards the goal state. Differential heuristics are particularly effective when the terrain or obstacles on the map are irregular or non-uniform.The implementation of multi-path payments (MPP) in eclair is also discussed, with suggestions for utilizing algorithms similar to flocking or `permuteroute`. The routing algorithm in the Lightning Network presents challenges due to paths being consumed by payments and limited knowledge about remote channel balance allocation. Optimal solutions are difficult to achieve due to the varying costs of paths depending on the value being sent. It is noted that the routing problem is more akin to a circulation or network flow problem rather than traditional pathfinding. To improve efficiency, balancing factors can be employed, average payment sizes can be recorded, and multi-part payments and trampoline nodes can be leveraged.In summary, the Lightning Network team has proposed various improvements to the pathfinding algorithms, including alternative approaches such as `permuteroute`, the use of differential heuristics, and optimizations like caching and precomputation. These enhancements aim to reduce the time taken to find routes and improve overall efficiency in the Lightning Network. The article suggests drawing inspiration from techniques used in real-time strategy games to further enhance pathfinding techniques for the Lightning Network.
Updated on: 2023-07-31T21:50:47.703264+00:00