I haven’t looked too closely at your proposal, but the first thing that hit me
(2 weeks ago, sorry for not answering right away), is that instead of the basic
flood-the-network-about-channels algorithm that currently is being used, this
makes each route discovery request behave more or less like flooding (ask
everybody within your local topology)?
Also it will be interesting to see when the network starts developing, I
suspect that if you keep every node within 3 hops in your local topology, you
end up storing most of the network anyway. So I think the routing algorithms
will be far easier to optimize and analyze after some real world data :)
That being said, interesting idea, I’m not dismissing it :D
On Tue, Aug 22, 2017 at 3:08, Billy Tetrud <billy.tet...@gmail.com> wrote:
Hey Guys,
I'm testing this mailing list out for the first time, so I'm probably gonna be
doing it wrong.
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
[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
[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 care 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?
~BT
_______________________________________________
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
