Route discovery?

[fresheneesz]

I can't find any document relating to how route discovery will happen? Onion routing can be used once a source has the information necessary to construct a packet with the desired route, but how does a source discover the routes it needs to choose the optimal route?

[cdecker]

The routing gossip protocol, described in BOLT 7, propagates information to each node in the network. This includes a channel's existence, the channel's parameters (fees, capacity, ...) and the endpoint's information (host, port, alias, color, ...). Upon receiving these messages each node builds up a local view of the network's topology which can then be used (using textbook algorithms) to find a path from source to destination, with minimal fees and with sufficient capacity.

[fresheneesz]

I did check that out, but other than the "recommendations for routing", I don't see much about actual route discovery. Are you saying every node will theoretically know the entire network topology via receiving broadcast-messages from every node? How do nodes that just came online discover routing info? Do they just have to wait for update messages to happen, or are messages stored and rebroadcast?

[rustyrussell]

fresheneesz <notifications@github.com> writes:

I did check that out, but other than the "recommendations for routing", I don't see much about actual route discovery. Are you saying every node will theoretically know the entire network topology via receiving broadcast-messages from every node? How do nodes that just came online discover routing info? Do they just have to wait for update messages to happen, or are messages stored and rebroadcast?

They get a whole-network sync when they first connect, if they ask, a-la BOLT #9: | 3 | `initial_routing_sync` | The sending node needs a complete routing information dump | [BOLT #7](07-routing-gossip.md#initial-sync) | It's pretty crude, but each channel takes about 500 bytes (about 400 initially, 100 for the current update), and each node about 150 bytes. For the first few thousand channels, that will work fine. One intention for 1.1 is to have a smarter sync mechanism than "all or nothing".

[fresheneesz]

@rustyrussell Ok, so basically the v1 proposal is a simple broadcast, where all nodes know all routes? Do you need someone to draft a protocol proposal for 1.1, or is that already in progress? Is there anywhere I can participate in the discussion about how v1.1 routing should look?

[cdecker]

@fresheneesz I'd suggest posting a proposal to the mailing list as a first step to get some feedback, and once the discussion settles down, we can distill it into a formal proposal on this repo (PRs welcome) 😉

[fresheneesz]

Mailing lists.. man, you can tell you're in 2017 when...

But ok, I'll give it a shot.

[fresheneesz]

@cdecker Is there anywhere I can go to see past posts to the mailing list?

[fresheneesz]

Ugh, i just got my first mailing list digest. God is it ugly, and contains duplicate text - SO MUCH duplicate text. Why don't we start up a forum on a site like https://www.proboards.com/ ? Bring this discussion into the new millennium?

[fresheneesz]

Or maybe not proboards.. but http://www.nabble.com/ ?

[cdecker]

I'd suggest disabling the digest, it's pretty much unreadable and you can't reply to individual topics on the mailing list.

[fresheneesz]

I'm seeing no emails from lightning-dev@lists.linuxfoundation.org other than the one digest email I got when I signed up. Is this normal? I don't have a lot of confidence in this mailing list. I'm just going to post the email I sent to the list here, cause I have no idea if its working. This really needs a better forum for discussion than a mailing list with a regan era UI. My email:

I want to talk about route discovery and route generation in the lightning
network. It seems there's a couple types of things going on with routing:

• Super basic flood-the-network style routing to get things up and
  running, as I believe is implicitly proposed here:
  https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md
• More involved research projects that may not reach fruition any time
  soon. Eg this:
  http://bitfury.com/content/5-white-papers-research/whitepaper_flare_an_approach_to_routing_in_lightning_network_7_7_2016.pdf

I'd like to discuss a near-term approach that can replace the basic
flood-the-network style route discovery, but isn't so complicated that it
needs a ton of study and work. This won't be the end-all solution to route
discovery, but should take us a lot further than flood-the-network.

I propose a protocol where each node knows about its own local network
topology, and to find a final route, a transaction originator queries a
number of its connections for routes to the intended destination. By doing
this, it means that nodes are not receiving or storing the entire network
topology, which makes route discovery a lot less taxing on the network (in
terms of bandwidth and storage space).

To go into more detail...

When a node joins the network:

1. it broadcasts its information to all its channels (pretty much as
   proposed here
   https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md)
   announcing its relevant channel information
2. it requests local network topology information from all its channels for
   information about channels 1 hop beyond its direct connection (ie it will
   receive information about which addresses those channels are connected to,
   and their related fee info / etc)
3. it then requests topology information for channels 2 hops beyond, etc
   until it has filled its cache to its satisfaction (the user can choose some
   amount of megabytes as its limit of network topology data to store)
4. it also subscribes to topology changes for nodes at those distances (eg
   if a node has requested information from 3 hops away, it will receive info
   about any new channels or removed channels that fall within that distance)

When a node receives an announcement message from a node joining the
network:

1. it will store that node's info in its cache
2. it will also forward that info to any node that's subscribed to topology
   changes that fall within the relevant distance

When a node wants to construct a route for a transaction:

1. It checks to see if it has a path to that node in its cache. If it does,
   it finds the cost of the cheapest path it has.
2. It asks all the channels on the edge of its cached local view for their
   cheapest path (however you want to define cheapest), specifying that it
   only cares about paths with a maximum cost of the cheapest path it has
   already found in its cache. For example, if the node has nodes up to 3 hops
   away in its cache, it will only ask the nodes 3 hops away (it will not
   ask its direct connections, nor nodes 2 hops away, since it already has
   enough information to ignore them)
3. When it gets all its responses, it constructs a path

When a node receives a path request from a node:

1. It checks its cache for its cheapest cache-only path
2. It asks nodes on the edge of its cached local view for their cheapest
   path, specifying that it only cares about paths with a maximum cost of
   either its cheapest cache-only path or the max-cost specified by the
   requesting node minus the channel cost between it and the requesting node
   (whichever is cheaper). A node on the edge of its cached local view is
   not asked for route information if the cost to that node exceeds the
   max-cost this relay node would specify.
3. It reports the results that satisfy the max-cost requirements of the
   requesting node

And that's it. All the route information can be encrypted and signed so
relaying nodes can't read the information inside, and so the requesting
source node can verify which nodes sent that information.

This protocol should keep both node-announcement messages and route
request messages highly localized.

Thoughts?

[dcousens]

Provided there is an API (RPC, IPC, etc) into lnd, I think routing will solve itself quite organically with or without a broadcast network.
Certainly I think approach of a broadcast-to-all is going to be perfectly sane for the time being.

[blacktemplar]

The routing gossip protocol, described in BOLT 7, propagates information to each node in the network. This includes a channel's existence, the channel's parameters (fees, capacity, ...) and the endpoint's information (host, port, alias, color, ...). Upon receiving these messages each node builds up a local view of the network's topology which can then be used (using textbook algorithms) to find a path from source to destination, with minimal fees and with sufficient capacity.

Can you explain here what you mean by capacity? Is it the total capacity of the channel or the two current capacities in both directions (they change whenever a transaction is sent through the channel).

In the first case: How can a node compute a path if it does not know whats the capacity of a channel in one direction?
In the second case: That would really mean a lot of broadcasts since for every transaction all channels it uses need to update and broadcast their new capacities to the whole network. Furthermore it would reduce privacy a lot since a listener could reconstruct every transaction happening in the whole network.