[Babel-users] Unicast Hellos

[Juliusz Chroboczek]

Dear all,

[This message is crossposted between both mailing lists, followups to
babel at ietf, please.]

I think there are at least four people interested in making a unicast-only
version of Babel, and that requires adding support to the protocol for
sending Hellos over unicast.  We had a discussion on this subject with
David Schinazi on Friday, let's please continue on the list.

Background
==========

Babel was designed so that the choice between sending a given TLV over
unicast or multicast is purely an implementation decision: all TLVs can be
sent over either, and have exactly the same meaning whether they are sent
over unicast or multicast.  There is however one limitation to that:
Hellos carry a per-interface sequence number, and unless they are sent to
all neighbours on a given interface, the seqnos will get out of synch.
More on that below.

At the time, it didn't seem important to be able to send unicast Hellos.
After all, Hellos are used for both neighbour discovery and neighbourship
maintenance, and discovery can only happen over multicast.  However, once
a neighbour has been discovered (either through multicast Hellos or
through means exterior to the protocol), then unicast Hellos can be used
to maintain the neighbour relationship.

People have found good reasons to use unicast for Hellos:

  1. Toke and Dave have a passionate hatred of multicast, and want to
     avoid it whenever possible;
  2. others want to protect Babel with DTLS or IPSec, and these protocols
     only work for unicast;
  3. Margaret is using Babel over a non-broadcast network, where multicast
     is not supported at all.

All of these are legitimate applications, and as I mentioned in Chicago,
it would be a terrible wasted opportunity if we didn't get unicast Hellos
into the spec in time for Prague.

The issue
=========

Every Hello contains two pieces of information: the Interval, a 16-bit
number of centiseconds (ranging from 10ms to 11 minutes), and a 16-bit
Seqno, which is an integer modulo 2^16.  The Interval is a promise to send
another Hello within a given time; babeld uses it to derive a hold time
(3*Interval, if memory serves).  The Seqno is incremented with each Hello,
and allows for reliable accounting of packet loss.

A Babel speaker maintains a single Hello Seqno per interface, which is
incremented whenever a (multicast) Hello is sent.  If a Hello is sent over
multicast to a single neighbour, the expected Seqno will become
desynchronised between the various neighbours, which will cause spurious
detection of packet loss.

A Hello also carries a 16-bit Reserved field, which currently must be zero
on transmission, and is silently ignored on reception.  David suggests
that this field could be repurposed as a flags field.

Possible solutions
==================

It is my opinion that it is allowable to add an incompatible extension as
long as it does not break existing networks and does not require a flag
day.  If a unicast-only speaker fails to establish an adjacency with
a legacy speaker, that's fine with me, as long as it does not break the
rest of the network.  Given that constraint, David and I see the following
ways to add unicast Hellos.

Allow unicast, no other protocol changes
****************************************

Margaret suggests that we should allow unicast Hellos, but require that
the same number of Hellos be sent to all neighbours on a given interface.
In other words, whenever a Hello is sent, it is either sent over
multicast, or the same Hello is sent to all neighbours over unicast.

This is tempting, since it doesn't require any changes to the protocol,
just minor editorial changes.  While it meets Margaret's use case, it
might not be flexible enough for all the uses of unicast Hellos.  I also
dislike the fact that the receiver cannot distinguish unicast from
multicast without checking the destination address -- this would be the
only place in the protocol where the destination address is needed.

Make the Hello counter per-neighbour
************************************

No protocol changes, just require that the Hello counter be per-neighbour.
This means that an implementation must either send all Hellos over
multicast, so all per-neighbour counters are equal, or all Hellos over
unicast.  Once a Hello has been sent over unicast and the counters have
become unsynchronised, it is impossible to send a Hello over multicast.

This is not acceptable to me, since sending Hellos over multicast is the
only in-band way to perform neighbour discovery.

Two kinds of Hellos, distinguished using a flag
***********************************************

David suggests that we have two Seqno counters: a per-interface and
a per-neighbour counter.  The two kinds of counters run independently.
A flag in the Hello packet's Reserved field serves to distinguish the two.

This is simple, elegant, and require few protocol changes.  Unfortunately,
legacy implementations that don't parse the Reserved field will get
confused, and spuriously tear down neighbour associations when they see
discontinuities in the seqno.  However, no flag day is necessary: we first
deploy implementations that understand the Reserved field, but don't send
any unicast Hellos.  At a later date, when legacy implementations have
disappeared, we start sending unicast Hellos.

This is currently my preferred solution.

Two kinds of Hellos, using different TLV types
**********************************************

My suggestion was to have two Seqno counters, just like in David's
proposal, but use a new TLV number for Unicast hellos.  This avoids the
compatibility issue -- unicast Hellos will be ignored by legacy
implementations, so unless an implementation periodically sends multicast
Hellos, it will be ignored by legacy implementations.

This used to be my preferred solution.  David has convinced me to use
a flag, but I'm willing to reconsider.

Use empty packets
*****************

Russ suggested that we interpret every Babel packet as a Hello.  This way,
sending an empty packet (just the packet header) will play the role of
a Hello.  This has two significant flaws:

  - there is no seqno or interval in the Babel header;
  - there is no way to attach a sub-TLV to an empty packet, most notably
    a timestamp.

This is not acceptable to me.

Something else?
***************

Other ideas?

Other issues
============

What does Interval mean?
************************

Currently, the Interval field of a (multicast) Hello is a promise to send
another (multicast) Hello within the given time.  If we switch to having
two kinds of Hello, what does Interval mean?  Is it a promise to send any
kind of Hello in the given interval, or a promise to send the same kind of
Hello within the given interval.  The former makes more sense to me, but
I'm willing to be convinced otherwise.

How is link quality estimated?
******************************

Most implementations of Babel use Hello history to derive a link quality
for each neighbourship association; this is described in Appendix A of
RFC 6126.  How is link quality computed in the presence of two kinds of
Hellos?  Please consider that at least in 802.11, unicast is protected by
ARQ while multicast isn't.