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

ZmnSCPxj ZmnSCPxj at protonmail.com
Thu Aug 1 05:02:59 UTC 2019


Good morning laolu,


Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Thursday, August 1, 2019 10:29 AM, Olaoluwa Osuntokun <laolu32 at gmail.com> wrote:

> > I found out recently (mid-2019) that mainnet Lightning nodes take an
> > inordinate amount of time to find a route between themselves and an
> > arbitrary payee node.
> > Typical quotes suggested that commodity hardware would take 2 seconds to
> > find a route
>  
> Can you provide a reproducible benchmark or further qualify this number (2
> seconds)?

No reproducible benchmark.
However, this is my reference: https://medium.com/@cryptotony/why-does-ln-payments-arent-instantaneous-d24f7e5f88cb which claims this 2 seconds for LND implementations.
(It is entirely possible this information is obsolete, as it was published a month ago and things move fast in LN.)

As per Rene, from his C-Lightning mainnet node, `getroute` typically takes 1.1 to 1.3s to a particular unspecified destination.
I do not know details of his hardware; it would be better to ask him.

> Not commenting on the rest of this email as I haven't read the
> rest of it yet, but this sounds like just an issue of engineering
> optimization.

The rest of the email *is* engineering optimization.

> AFAIK, most implementations are using unoptimized on-disk
> representations of the graph, do minimal caching, and really haven't made
> any sort of push to optimize these hot spots.

C-Lightning has always used in-memory representation of the graph (helped massively by the low-level nature of C so we can fit a larger graph in the same space), and has the "million channel project" to attempt to generate graphs at 1 million channels that seem to represent the distribution of actual graphs today.
C-Lightning is barely able to fit in a RPi-level computer today with the actual mainnet graph.

> There's no reason that finding
> a path in a graph of a 10s of thousands of edges should take _2 seconds_.
>
> Beyond that, to my knowledge, all implementations other and lnd implement a
> very rudimentary time based edge/node pruning in response to failures. I
> call it rudimentary, as it just waits a small period of time, then forgets
> all its past path finding history. As a result, each attempt will include
> nodes that have been known to be offline, or nonoperational channels,
> effectively doing redundant work each attempt.

Indeed, C-Lightning does this.

>
> The latest version of our software has moved beyond this [1], and will
> factor in past path finding attempts into its central "mission control",
> allowing it to learn from each attempt, and even import existing state into
> its path finding memory (essentially a confidence factor that takes into
> account the cost of a failed attempt mapped into a scalar weight we can use
> for comparison purposes). This is just an initial first step, but we've seen
> a significant improvement with just a _little_ bit more intelligence in our
> path finding heuristics.

Indeed.
Our main algorithm for pathfinding is Dijkstra, which is O(n log n) formally with proper data structure implementation, though at large sizes approaches O(n ^ 2) as caching and so on get involved.
I believe this is approximately what you will find in the "best" pathfinding algorithms.

Limiting what you scan to a smaller slice of the graph is a valid engineering change to optimize pathfinding, as you will get near-optimal results while greatly cutting down on runtime.

> We should take care to not get distracted by more
> distant "pie in the sky" like ideas (since many of them are half-baked),
> lest we ignore these low hanging engineering fruits and incremental
> algorithmic updates.

As you have not read the rest of the email, I believe you should.
They are almost entirely low-hanging engineering fruits, and many are practically deployable today.

The primary point of this thread is to show that there exists a similar field (real-time strategy games) whose pathfinding problems are suspiciously similar to ours:

1.  Dynamically-changing world.
2.  Limited knowledge of actual world conditions (fog of war).
3.  Low-latency for UX.
4.  Large maps.

Taking a short visit to this field may be helpful, regardless.

Regards,
ZmnSCPxj


More information about the Lightning-dev mailing list