Ripple's shortest-path algorithm

[bx549]

Does anyone know if a technical description of Ripple's path-finding algorithm is available? This must be a distributed algorithm  (e.g. Bellman-Ford algorithm) in the sense that no single node knows what the entire network looks like. Is it guaranteed to find the best path, or is it a heuristic method? Thanks for any info.

[Sukrim]

https://github.com/ripple/rippled/issues/207

[yxxyun]

https://github.com/ripple/rippled/tree/develop/src/ripple/app/paths

 

[tulo]

It is a centralized algorithm.

If I recall correctly it runs in anytime fashion and it's based on IDDFS. But the documentation is 0 and the code is hard to read.

[KarmaCoverage]

2 hours ago, yxxyun said:

https://github.com/ripple/rippled/tree/develop/src/ripple/app/paths

 

https://github.com/ripple/rippled/blob/develop/src/ripple/app/paths/Pathfinder.h

Reading this reminded me about quality in/out.

I have also been looking at ILP pathfinding and it just dawned on me that some of the conceptual thinking on quality in/out is similar to the Liquidity Curves in ILP  (I think?)

[mDuo13]

10 hours ago, bx549 said:

Does anyone know if a technical description of Ripple's path-finding algorithm is available? This must be a distributed algorithm  (e.g. Bellman-Ford algorithm) in the sense that no single node knows what the entire network looks like. Is it guaranteed to find the best path, or is it a heuristic method? Thanks for any info.

If you're talking about pathfinding within the XRP Ledger, it's not a distributed algorithm, because every node (rippled server) has a full copy of the entire ledger trie (aka the graph described by the ledger data where pathfinding for XRP and issued currencies takes place).

It's not a guaranteed best path. The algorithm runs in limited time on a graph that frequently updates. It tries certain pre-planned path archetypes such as account-account-account, or account-orderbook-account, or a-a-o-a-a, etc. and quits if it doesn't find anything matching those archetypes.

 

7 hours ago, KarmaCoverage said:

https://github.com/ripple/rippled/blob/develop/src/ripple/app/paths/Pathfinder.h

Reading this reminded me about quality in/out.

I have also been looking at ILP pathfinding and it just dawned on me that some of the conceptual thinking on quality in/out is similar to the Liquidity Curves in ILP  (I think?)

Yes, they are similar concepts. Liquidity curves (which are not actually "curvy") are a finer-grained control than quality in/out:

• Quality in/out is for same currency pairs (FOO:FOO) with different issuers.
• Liquidity curves can represent same currency or different currency pairs (FOO:FOO or FOO:BAR). Because ILP doesn't actually care about currency codes and issuers—if the currency is on one ledger, it's the same, and if it's not, it's different.
• Liquidity curves allow multiple ratios at different scales, such as "volume discounts" (or, likely, the opposite). (For example, a liquidity curve could basically say, $1USD:$5MXN for amounts under $100USD, then $1USD:$4.50 MXN for amounts $101-200 USD, then $1USD:$4 MXN for amounts $201+) Quality in/out is limited to a single ratio regardless of amount.

[KarmaCoverage]

Thanks @mDuo13 this makes sense. I didnt think about quality in/out only applying to the same currency, and I do realize that many Liquidity Curves can be combined to facilitate a multi hop path.

I dont want to derail this thread about Pathfinding within RCL, but if you have links to any other resources around Liquidity Curves, or how this solution is developing, could you share on this thread. Got any multi hop, multi currency, multi ledger, math examples? Also, I think I remember seeing something about a routing table for liquidity curves that ILP connectors can publish to, and am wondering what is the thinking around CCP these days?