Re: path discovery / routing: economic significance and brainstorming

Hey Xavier,

Absolutely no contest that pathfinding is a hard problem. The reason the
white paper avoids it is because it's a layer on top of the raw escrow
chains. There are quite a few cases where you could use ILP with no
pathfinding or trivial pathfinding, e.g. when two ledgers are directly
connected, or when they share a common settlement ledger that they are both
connected to. In these cases it is still useful to use a common standard
for escrow conditions.

That said, let's talk pathfinding!

> As such it is surprisingly absent from both the white paper and the "reference
implementation", the latter which finds a path given a known graph of who
is connected to who, whereas in the real world finding these connections is
part of the problem.

I think you could give the reference implementation a bit more credit. :)
It's not true that it starts with a "known graph". It actually crawls the
network and discovers nodes that way. There isn't any fundamental reason
why a production implementation couldn't work similarly. Of course there
are a lot of ways in which it needs to be improved:

- Currently the ledger just gives you a list of its users. Obviously that
won't be an option in practice. I think the low-hanging fruit is to just
add a separate endpoint which only returns a list of connectors without
their balances. (More advanced solutions involve bypassing the ledger
entirely in discovery by having connectors track neighboring connectors.
But that's a whole separate email.)

- The current solution is pretty open to DoS. We need better ways to
distinguish spammy connectors from legitimate ones. This could be based on
the volume they've processed, how long they've been around, etc.

- The current solution is not very scalable. It'll work for short paths if
there aren't too many connectors at each hop. But there are almost
certainly improvements that could be made to prioritize and optimize.

- It's an open question whether centralized path finding is more
competitive (think Google Search) or decentralized path finding (think
distributed routing). Obviously we'd like to see distributed pathfinding,
but ultimately it's just an empirical question of which will work better
and which one people will choose.

Our focus right now is on setting up a permanent fake-money test network,
so we can begin to test path finding in a more realistic setting.

- Stefan


On Mon, Nov 23, 2015 at 5:31 AM, Xavier Vas <xavier@tr80.com> wrote:

> Hi,
>
> Anyone here agrees with me that path discovery, the thing that happens
> before an ILP transaction as per white paper starts,
> (a) will be what "defines" future inter-ledger payments in the sense
> that its yet to be determined concepts and implementations will be what
> makes or breaks the stated goals of inter-ledger payments (competitive
> market with low fees, low friction user experience), much sooner than
> concepts and implementations of the ILP itself, and
> (b) is a hard problem.
>
> As such it is surprisingly absent from both the white paper and the
> "reference implementation", the latter which finds a path given a known
> graph of who is connected to who, whereas in the real world finding
> these connections is part of the problem.
>
> If you agree join me for some path discovery brainstorming here on the
> ML or, preferably, on IRC (irc://irc.w3.org:6667/#interledger) which is
> sometimes a better forum for just tossing around half-baked ideas.
>
> Just to throw some ideas out there:
> - Someone suggested to look at inter-AS routing on the Internet for some
> inspiration. In routing protocols like OSPF so-called "area border
> routers" (ABRs) play a role similar to ILP connectors, connecting
> subnets the way ILP connectors connect ledgers.
> - Named data networking (NDN, http://named-data.net) has an as yet
> mostly unsolved path discovery problem trying to retrieve data from a
> network where it is not known which node(s) the data resides on. NDN's
> "interest and response" scheme looks similar to the
> preparation/execution cascade of ILP's universal mode. This could be
> worth paying attention to.
>
> Both ABRs and NDN scale by advertising "summaries" of nodes that can be
> reached through them, in the ABR case through CIDR (common prefixes of
> IP addresses) and in the NDN case through "path prefixes" which are
> substrings of file system path-like URIs that they use to name content.
> These "summaries" work because both IP addresses and file system paths
> are hierarchical. How would a connector summarize ledgers/other
> connectors that it connects to?
>
> Food for thought.
>
> Xav
>
>
>