[Babel-users] Babel protocol: about undoing history

[Juliusz Chroboczek]

I've just received (by PM) a request for clarification of section
2.2.1 of the Babel spec:

  When a hello is received, its sequence number is compared with the next
  expected sequence number for this neighbour.  If the sequence number of the
  received Hello is higher than expected, then one or more Hellos have been
  missed.  If the sequence number is lower, then this neighbour decreased the
  Hello interval without us noticing, and part of the history must be undone.
  In order to avoid undoing history, a node SHOULD always send a Hello
  immediately after increasing its periodic Hello interval.


Suppose that peer A has a hello interval of 1s.  At time t=0, it sends
a hello with sequence number 0.  Its neighbour B expects it to send
a hello with sequence number 1 at time t=1.

Now suppose that after sending the hello with seqno 0, A decides to
increase the hello interval to 10s.  At time t=1, B decides a hello
was lost; at time t=9, B decides 9 hellos were lost.  At time t=10, it
expects a hello with seqno=10, but instead it receives a hello with
seqno=1, which causes it to conclude that the loss was spurious, and
that actually no hellos have been lost.  Hence, the loss history must
be undone.

In order to avoid undoing history, this section recommends that a peer
should only change its hello interval *before* sending a hello; or,
equivalently, that a hello should be sent whenever the hello interval
changes.  This avoids undoing history when there is no packet loss.
Of course, in presence of packet loss, all bets are off.

                                        Juliusz