Distributed Pathfinding - Routing without a common routing table

#1

Firstly, thank you guys for putting up an ILP dedicated forum to discuss this stuff.

This came to me while thinking about how ILP abstracts away Rippled’s pathfinding functionality. When I was listening to this ILP community call with @adrianhopebailie’s comment at 33:20 and the conversation around routing, I thought this may be helpful.

The basic idea here, starts from me thinking about XRPLedger as a Connector within the framework of an open IoV, and the use of it’s pathfinding functionality as a sort of ‘freely available routing service’. Which leads to an IoV environment in which Market Makers aka Connectors must compete against the free service provided by XRPLedger.

From there I started thinking about RippleNet, assuming that each bank runs their own Rippled ledger which has it’s own pathfinding functionality, and further assuming that IOUs could be issued onto that banks private Rippled ledger representing the terms of their bilateral Nostro/Vostro relationships with other RippleNet banks… with the cost/spread represented as Quality In/Out which means the terms/spreads between each Connector remains private to each Connector.

To find the relevant parts skip about 2/3s down the write up and start at “Now with all that said… back to RippleNet”

The big idea… Once you have a series of banks, each with their N/V terms expressed on each other’s xCurrent ledgers via Quality in/out… then finding the best combination of many xCurrent ledger paths to send a payment through, is effectively preforming distributed pathfinding across all relationships, in an automated way!!!

#2

I’m not sure I completely understand your question or idea, but Interledger connectors do route packets without having one shared routing table. Each connector has a routing table that maps ILP address prefixes to a specific peer or “next hop” that they’ll forward the packet to. Connectors broadcast routing information to one another to help build those tables and together all of the routing tables do effectively enable “distributed pathfinding”. Feel free to ask if you have more questions about how that routing protocol/algorithm works.

Also, please keep this forum focused on discussing the open Interledger protocol, rather than specific blockchains like XRP Ledger or proprietary products like xCurrent.

#3

that’s how in understood it. if an ILP connector can’t help with a request, the process moves along to the next connector

#4

Right, the idea is basically for a Connector to just use a private Rippled ledger and express their multi relationships with other connectors via issuing IOUs onto their own private ledger… then just letting the Connector’s private ledger’s Pathfinding identify the best route through that ledger in the ILP payment path

The Quality in/out can be changed, or different IOUs with various quality settings used (refelecting various spreads) then the Connector can move around and provision liquidity to the orderbooks and IOUs that sum up to the market rate spread.

The change in liquidity rates can be communicated through the fufill amounts, as those are recieved and the changes can be calculated.

Idk, maybe it does not make sense. I just think about all the work it would take to run a Connector, and then look at all the functionality already built into Rippled and think, “hum, maybe I could use this accounting tool for internal operations?”

I mean, what a connector does is, manage liquidity across multiple orderbooks with changing spreads continuously… which Rippled already does quite well.

#5

You’re right that the functionality is somewhat similar, at least at a high level.

That said, I would bet that running purpose-built connector software would be best. There are plenty of features that are specific to Interledger (the details of ILP Address-based routing, settling using payment channels on different blockchains, the connector-to-connector communication, etc), and I think an implementation designed specifically for Interledger would handle them better than repurposed code.

1 Like
#6

Yeah, this was pretty much my thinking also.

I just figured with Rippled being opensource, a minimal amount of development work would need to be layered in to handle the ILP specific functionality. Which may make Rippled an attractive base ledger to build a reference Connector implementation on top of.

#7

I would recommend just using the reference implementation of an interledger connector: https://github.com/interledgerjs/ilp-connector

1 Like
#8

Just to be clear, here is a description of how routing works in Interledger, at least how it works at present. It is very, very similar to how Internet routing works.

Any node (sender or connector) which is trying to send a packet will always consult its local routing table to decide which peer to send the packet to. That is it. Nodes never query each other to figure out where to send a given packet nor do they ever send a packet to more than one neighbor. If the local routing table is incorrect or if the requested destination isn’t covered in the local routing table, the packet will not arrive at its intended destination.

How nodes populate their local routing table depends on the type of node. For a client, the typical routing table is likely just hardcoded and says something like: “Send everything to my Interledger access provider.” At the other extreme, a tier 1 Interledger connector will have almost every possible destination in its routing table which it assembled from routing updates that are circulating via CCP (connector-to-connector protocol), a path vector routing protocol.

XRP Ledger pathfinding works very differently because the entire network topology is known by all participants, so we can calculate the entire route locally. This type of routing is sometimes called link-state routing. We went with path-vector routing for Interledger because it provides more flexibility and scalability in an open network setting. Also, because the Internet uses path-vector routing, there is a tremendous amount of research and experience that we can leverage.

5 Likes
#9

I’m thinking of this with XRPLedger or any private Rippled acting as a Connector, consulting only its internal topology to determin the route/path through it’s internal connections to other Connectors.

Fyi these are new detail to me, but after looking at this to try and understand “vector routing” I think that methodology fits within the framework of what I wrote about.

In reality I think a lot of Rippled would need to be stripped out, and the pathfinding/arbatrage algo continuously improved upon. But maybe XRPLedger could play the role of a decentralized exchange / public ILP Connector?

If actual tear 1 Connectors issued IOUs on XRPLedger, that would open up an alternative path for liquidity to flow through without going through direct connector-to-connector paths. Like a distribited tear 1 ILSP.

Im sure I dont have the details ironed out, just sharing the direction of thought.

#10

I do think the idea of a decentralized connector is an interesting one (though I might still opt for building one from scratch rather than trying to re-purpose such a complicated codebase).

1 Like
#11

What if it could be done via scripting, using the existing APIs that support Rippled?

Trustline Quality communicates a lot, when you also consider Orderbook depth to be a parallel for “liquidity bandwidth”, or a liquidity curve. The tool is there, more or less.

Let an introductory rate IOU’s orderbook (the cheaper one) dry up, then let the Pathfinding algo auto reroute the payment’s path through liquidity on another IOUs orderbook which has a lower Quality, ie a higher spread for the Connector.

There are html wallets out there. Although I’m not technical enough to weigh in on if all of those features (trustline quality set, and order placing to manage liquidity depth) can be deployed through an html header or body, or just not possible… idk

#12

Can a global liquidity provider (like a Moneygram) become a Tier 1 ILP connector with a massive global routing table? Also, how do connectors compete with one another if only the local routing table is consulted? Who decides for the sender whom is on the local routing table? Thanks in advance for the replies.

#13

Welcome @Santiago_Velez.

Moneygram could become a tier 1 provider. A global routing table is a loaded term and would depend how they decided to deploy there infrastructure.

Option 1
One option would be to run a large connector that supported all their various currencies. All clients would then connect to this connector and allow routing across all currencies supported. This would effectively give you the concept of a large global routing table. Though the question would be what legal jurisdiction does this connector operate in.

Option 2
Another is Moneygram would run connectors in all the markets/jurisdictions it wants to operate within (USA, Europe, Australia etc) and then peer all their connectors peers with eachother. There wouldn’t be a global routing table but the Interledger network would handle that for you.

For me it is far more likely they would operate with Option 2 as I suspect that would be the only way to actually conform to current legal compliance regarding Money Transmission etc.

Matt

#14

I saw “CCP” and “RBP” used in different places.
What is their present, and intended future relationship, please?

https://docs.rs/interledger/0.5.1/interledger/ccp/index.html

At present, are there any differences in how routing updating works between the Rafiki, Reference, Rust, Java connectors? Are/SHOULD the implementations be able to exchange compatible routing info, or there will/can be different “route gossipping” on the network?

#15

We don’t have any thorough integration tests yet to validate this, but the CCP implementations in Java, JS, and Rust should be compatible.