From bastien at acinq.fr Thu Aug 1 08:33:33 2019 From: bastien at acinq.fr (Bastien TEINTURIER) Date: Thu, 1 Aug 2019 10:33:33 +0200 Subject: [Lightning-dev] Improving Lightning Network Pathfinding Latency by Path Splicing and Other Real-Time Strategy Game Techniques In-Reply-To: References: Message-ID: Good morning ZmnSCPxj, Thanks for sharing this analysis, you're touching on a lot of interesting points and giving a lot of good resource pointers. It echoes many ideas we also had to improve eclair's routing algorithm (which currently uses Yen's k-shortest paths with Dijkstra, a few configurable heuristics and a compact in-memory representation of the graph). I think that the main points that make routing in the Lightning Network different from game path-finding algorithms are: - Paths are consumed by payments, effectively moving available balance between sides of a channel - The routing algorithm doesn't know remote channels balance allocation (and that changes constantly) - The cost of a path depends on the value you're sending (proportional fees) - - This encourages algorithms not to search for an optimal solution (because an optimal solution on outdated/incomplete data doesn't even make sense) but rather fast and good enough solutions with retries There are a few technicalities that might be a problem for some of your suggestions, I'm interested in your opinion on how to address them. For `permuteroute`, you mention the following pre-requisite: the original payer is informed of which node reported the failure and which > channel failed. > We currently don't have a solution for reliable error reporting, as pointed out in [1]. I think making progress on this thread would be interesting and useful for routing heuristics. I thought about path pre-computation and path caching, but what bothered me is that the cost depends on the amount you want to send. When pre-computing / caching, you have to either ignore that completely (which can be fine, I don't think trying to always find the most cost-efficient route is a reasonable goal) or take into account some kind of "universal" factor that works for most amounts. How did you take that into account in your pre-computation experiments? I do agree that multi-part payments and trampoline (hierarchical routing) can offer a lot of room for algorithmic improvements and your ideas on how to leverage them resonate with mine. An interesting thing to note is that trampoline (in the current proposal at least) allows trampoline nodes to leverage multi-part payments "at each hop", meaning that a trampoline node can join/split arbitrarily an incoming payment to reach the next trampoline node. While implementing a first version of multi-part payments, I realized that they need to be tightly integrated to the routing algorithm. Since each payment "consumes" a path, potentially "stealing" it from other payments, a naive implementation of multi-part payments would try to use different paths for each sub-payment, but that's an inefficient way of solving it. Working on multi-part payments made me think that maybe our routing problem is more similar to a circulation or network flow problem [2] rather than path-finding. Have you thought about this? If so what is your opinion? Thanks again for sharing all this and starting those interesting discussions. Cheers, Bastien [1] https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-June/002015.html [2] https://en.wikipedia.org/wiki/Circulation_problem Le jeu. 1 ao?t 2019 ? 07:14, ZmnSCPxj via Lightning-dev < lightning-dev at lists.linuxfoundation.org> a ?crit : > 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 > _______________________________________________ > Lightning-dev mailing list > Lightning-dev at lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev > -------------- next part -------------- An HTML attachment was scrubbed... URL: