Billy Tetrud [ARCHIVE] on Nostr: đź“… Original date posted:2017-09-04 đź“ť Original message: Johan, " I suspect that ...
đź“… Original date posted:2017-09-04
đź“ť Original message:
Johan,
" I suspect that if you keep every node within 3 hops in your local
topology"
Not every node would store 3 hops. Maybe for some nodes 2 hops is the right
number. Or if you're connected directly with a huge hub, maybe you would
only be able to store your direct connections and the 2nd hops for only
*some* of your connections. Or maybe the algorithm could aim for a certain
amount of topology data for each connection (eg 10MB per connection) so
that you'll only store a small percentage of 2nd hops for a large hub,
while still be able to store 5th or 6th hops for long chains of nodes with
few connections.
~BT
> ---------- Forwarded message ----------
> From: "Johan TorĂĄs Halseth" <johanth at gmail.com>
> To: Billy Tetrud <billy.tetrud at gmail.com>
> Cc: lightning-dev at lists.linuxfoundation.org
> Bcc:
> Date: Mon, 04 Sep 2017 11:13:15 +0200
> Subject: Re: [Lightning-dev] Route finding and route generation
> 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.tetrud at 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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20170904/db2b4551/attachment.html>;
đź“ť Original message:
Johan,
" I suspect that if you keep every node within 3 hops in your local
topology"
Not every node would store 3 hops. Maybe for some nodes 2 hops is the right
number. Or if you're connected directly with a huge hub, maybe you would
only be able to store your direct connections and the 2nd hops for only
*some* of your connections. Or maybe the algorithm could aim for a certain
amount of topology data for each connection (eg 10MB per connection) so
that you'll only store a small percentage of 2nd hops for a large hub,
while still be able to store 5th or 6th hops for long chains of nodes with
few connections.
~BT
> ---------- Forwarded message ----------
> From: "Johan TorĂĄs Halseth" <johanth at gmail.com>
> To: Billy Tetrud <billy.tetrud at gmail.com>
> Cc: lightning-dev at lists.linuxfoundation.org
> Bcc:
> Date: Mon, 04 Sep 2017 11:13:15 +0200
> Subject: Re: [Lightning-dev] Route finding and route generation
> 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.tetrud at 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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20170904/db2b4551/attachment.html>;