[Lightning-dev] Fwd: Re: Routing & Beacons

laurentmt laurentmt145 at gmail.com
Wed May 4 16:00:46 UTC 2016


Le 03/05/2016 01:27, Rusty Russell a écrit :
> laurentmt <laurentmt145 at gmail.com> writes:
>> Thanks for the information. Indeed, it raises questions but this is
>> exactly why I find the subject so interesting :)
>>
>> WRT the update of routing tables, let me try to summarize my
>> understanding with this scenario:
>>
>> 1/ Landmark nodes periodically send a message to their neighbours (every
>> 30s ?). This message initiates a new temporal frame (symbolized by
>> counter embedded in the message and sequentially increased by the
>> landmark node).
> 
> Technically, the landmark would ve a channel; it's just easier to select
> on that basis (since channels exist in the blockchain, you can prove it
> existed prior to landmark selection).
> 
> But your idea of temporal framing is new to me.

Actually, the process described in my previous message is directly
inspired from the Pulse Protocol I was citing in my first email (a
"pulse" is the periodic message sent by landmark nodes to update routing
tables). While this protocol was designed for a very different goal
(routing on "multi-hop wireless infrastructures"), there may be
interesting ideas for LN routing. This paper
(http://www.cs.jhu.edu/~dholmer/600.647/papers/pulse_infrastructure_access.pdf)
should be much better than explanations sent with my crappy english. :D

> 
> I had considered that we simply limit a single hop to advertising every
> 30 seconds, and you only re-broadcast if it's the best.  That requires
> maintaining a little state for each hop you rebroadcast.
> 
>> 2/ When a node receives the first message associated to a new temporal
>> frame for a given landmark, it waits for a delay before forwarding the
>> message to its own neighbours (it gives a chance to receive the same
>> message from a better route).
> 
> Hmm, I'm not sure how to calibrate that delay though?  If everyone is
> delaying it's not clear that you'll hear about the better route, is it?
> 

Agreed. Another constraint is related to the topology of the network
(more especially to its diameter). Time required to propagate the
message to the full network should be much lower than the period of the
mechanism (30s).

There's clearly a trade-off to be made. Delay should be long enough to
maximize the probability that you hear about the best route but short
enough to ensure fast propagation of the message across the network.


>> After this delay has elapsed, the node computes the best route to the
>> landmark node and forward the message (information defining the temporal
>> frame + best route to landmark node) to its neighbours.
>> 3/ Every node repeats the same process (step 2).
>>
>> When the process has completed, every node knows the best route to/from
>> a given landmark.
>> When a node needs to send a payment, the receiver sends her its best
>> routes to each landmark node. Therefore the sender is able to compute
>> the best route to reach the receiver and onion routing is possible.
> 
> s/to each landmark/from each landmark/

Yes ! The route to the landmark wouldn't be very useful :)

> 
>> Random remarks / questions:
>>
>> - Agreed that the "base+per-satoshi" fee model creates a difficulty to
>> define the best route.
>>   I don't know if I'm right, but I see the base fee as a way to say "I
>> don't want to transfer amounts lower than X satoshis" (the base fee
>> makes them economically unviable).
>>   So, as you wrote, a solution may be a set of nominal values and the
>> forwarding of a set of best routes (a route for each range of amounts
>> between 2 nominal values).
> 
> Yes, I think so.
> 
>> - A shower thought: with this model, fees seem conceptually associated
>> to the node and there's no distinction related to the direction of the
>> payment (sending or receiving).
>>   A different model would be to associate fees to individual payment
>> channels (with a different fee defined for sending and receiving on this
>> channel).
> 
> Yes; if landmarks are channels, then I think it falls out naturally.
> 
> There's a related question on how fees are collected: simplest is that
> the node pushing the HTLC into the channel collects the fee.  This
> implies that they unilaterally set the fee for that direction.
> 
> But I wonder about weird fee games where one side charges far more than
> the other; are they completely independent or do they negotiate?  My gut
> feeling is that it all works out: if the You->Me direction is popular
> today and you're making a mint, I'll be doing well from the Me->next-hop
> channels too.
> 

Interesting. My initial thought was that each side of a channel may
charge a fee for the use of the channel because it allows each one to
signal its (dis)agreement for the use of the channel in a specific
direction.

But it makes the implementation more complex and your observation
highlights that it can be achieved differently. For instance, if I
propose the unbalanced route (Me-->You), you may signal your
"disagreement" by deciding to charge a higher fee for the next hop and
in some cases it may lead you to forward another route as the best route.


>>   It means that for a given landmark, a node would forward 2 best routes
>> (for sending/receiving payments to/from the landmark).
>>   That may be useful to cope with unbalanced channels because it allows
>> the node to signal that, for instance, it's ok to receive payments on a
>> given route but sending payments is not encouraged.
> 
> Definitely need asymmetry for balancing.
> 
>> - Would it be useful to have simulations ? (that may be an interesting
>> side project on my hand).
> 
> This could well offer some insight.
> 
> Anthony Towns (added to To) did some simulations, but other than a
> simple YouTube video I'm not aware of any published results.
>
> Cheers,
> Rusty.
> 

laurent


More information about the Lightning-dev mailing list