From billy.tetrud at gmail.com Mon Sep 4 09:52:55 2017 From: billy.tetrud at gmail.com (Billy Tetrud) Date: Mon, 4 Sep 2017 02:52:55 -0700 Subject: [Lightning-dev] Lightning-dev Digest, Vol 25, Issue 1 In-Reply-To: References: Message-ID: 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" > To: Billy Tetrud > 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 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 > > - 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 > ) > 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: