[Babel-users] [babel] Unicast Hellos

[james woodyatt]

On Apr 3, 2017, at 01:50, Juliusz Chroboczek <jch at irif.fr> wrote:
> 
> Something else?
> ***************
> 
> Other ideas?

I want to explore the idea of finding the minimum possible change to the protocol to make the necessary refinement and still permit multicast Hello for in-band neighbor acquisition.

Without any changes to the protocol, I’m not sure it’s strictly true that it’s impossible to multicast a Hello after unicasting with different intervals and desynchronized Hello seqno progressions to two or more different neighbours. Yes, the reverse reachability detection logic says that when a Babel speaker receives a Hello, when it can determine that a previous Hello seqno was not received, it recomputes the association cost and recommences the route selection procedure. Accordingly, it could be prohibitively costly to force a discontinuity in the Hello seqno at every periodic multicast in any system where, except for neighbor acquisition, speakers normally send only unicast Hello messages, so judiciously redefining the 16-bit reserved field in the Hello message to help with that problem may be warranted.

One approach is to define a (D)ISCONTINUITY flag for use only in unicast Hello messages, which a Babel speaker would use to signal to its neighbours that a Hello seqno discontinuity SHOULD be expected in processing this message, therefore recomputing the association cost and recommencing the route selection procedure is NOT RECOMMENDED. Instead neighbours would update their history information in the Neighbor Table entry for the speaker to disregard the discontinuity and make no adjustment to the rxcost.

Babel speakers that can send both unicast and multicast Hello messages would immediately precede every multicast (interval=T, seqno=N) by unicasting (D=1, interval=T, seqno=N-1) to each neighbour that was most previously unicast a Hello other than (seqno=N-1). Speakers SHOULD choose N to minimize the number of independent unicasts preceding a multicast. The interval MUST be the same in all the unicasts and the multicast, so every neighbour will store the correct interval value in their Neighbour Table for use in recomputing the association cost, which happens for each neighbour as one of three possible cases: 1) the unicast message with (D=1, seqno=N-1) is lost and the multicast (D=0, seqno=N) is received and N is recognized as discontinuous, adjusting rxcost to account for the loss of one unicast Hello packet, 2) the multicast message with (D=0, seqno=N) is lost, the unicast (D=0, seqno=N+1) in the succeeding message is received, and N+1 is then recognized as discontinuous, adjusting rxcost to account for the loss of one multicast Hello packet, or 3) both unicast and multicast messages are lost, in which case the discontinuity will be recognized and rxcost adjusted by at least two messages (except in the rare case that the most recently sent Hello seqno for the neighbor is N, when the next delivered unicast will be seqno=N+1, and no adjustment to rxcost will be made, despite the loss of two packets).

In any Babel system where unicast or multicast are used exclusively, no Hello messages need the D=1 signal. In any Babel system with two or fewer speakers, no Hello messages need the D=1 signal. In any Babel system where every speaker sends the same number Hello messages to every neighbour it acquires, no Hello messages need the D=1 signal. The D=1 signal is only required in a Babel system where 1) a speaker has two or more neighbours, 2) it unicasts Hello to two or more of them with different interval and Hello seqno progressions, then 3) it later needs to multicast a Hello without forcing all but one of the neighbors to recompute their association costs and recommence their route selection procedure.

Admittedly, I haven’t yet implemented my own Babel speaker, so I’m not sure this idea is well-formed. I think this proposal works even in the case where no multicast is used at all and neighbour discovery proceeds out of band.

--james woodyatt <jhw at google.com <mailto:jhw at google.com>>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.alioth.debian.org/pipermail/babel-users/attachments/20170404/17812e0e/attachment.html>