Subject: [babel] Comments on RFC 6126

From: David Schinazi <[email-masked]>
Date: Tue, 27 Sep 2016 16:01:37 -0700

Fellow Babel enthusiasts,

As a fun research project, I have built a fully independent implementation of Babel, exclusively from specification. While it still has some rough edges, it works well enough for a demo and interoperates with devices running babeld. In the process of building it, I took notes on what parts of RFC 6126 were confusing to me, and also have written down random thoughts for parts of the document (and protocol) that I think could be improved. But before I dive into how the spec isn't perfect, let me say that it's a very well written document that allowed me to build my own implementation without ever looking at babeld's source code. These comments aren't very well organized, I'm sharing them with the list to start conversations that could potentially lead to changes in RFC 6126 bis. Feel free to shoot any questions my way.

*) Parts of the specification that I think may be incorrect
	• in 3.1, "a Babel speaker does not need to determine the destination address of a packet that it receives in order to interpret it" isn't necessarily true in the case of IHU TLVs with AE=0. Packets that are ambiguous could be explicitly forbidden but checking if we received the packet over unicast or multicast can be helpful.
	• 3.5.4 indicates that the route table is indexed by (neigh, id, prefix), this should not include the router ID (as in 3.2.5)
	• typo in 3.8.1.2 "A node MUST NOT increase its sequence number by more than 1 in response to a route request" should be seqno request

*) Parts of the specification that I found confusing
	• when discussing addresses, "compression is allowed" is unclear - further reading indicates that the only compression that exists is the omitted field, I ended up searching for more complex encodings.
	• it was initially unclear that Hellos always require a seqno increment
	• the feasibility condition is discussed in terms of updates sent instead of selected routes, which makes sense but feels odd
	• When text discusses if we have an entry for that prefix, it should be made clearer that it's for that explicit prefix, not one that contains the requested one (as in a shorter prefix)
	• shouldn't the table of pending seqno requests (3.2.6) be indexed by routerID too? 3.8.1.2 is not clear about defining what redundant requests should be indexed on
	• shouldn't the table of pending seqno requests also contain the destination neighbor we sent it to?
	• the omitted field in updates / corresponding flag are per-address family but it's unclear what to do when receiving AE=3(IPv6LL) and omitted>0 (are the 64bits of fe80 considered omitted?)
	• 3.2.5 should specify that the information in the source and route tables are not quite the same. This does feel obvious after the fact but as a first time routing protocol implementor I started with a pointer in the route table to the source table entry and that got me down a pretty deep rabbit hole of things that don't quite work...

*) Parts of the specification / protocol that could be improved
	• the jitter discussion concentrates on one possible solution, delaying and buffering, but there are other solutions such as not reseting timers based on outside events
	• there's no reason for the IHU timer to live in the interface table if IHUs are sent unicast
	• handling of Hellos - this deserves a thread all to itself but in a nutshell Hellos feel like the most constraining part of Babel. 3.4.3 states a MUST: "if no hellos were received recently, then the cost is infinite" which feels too limiting, if an implementation has access to out of bound mechanisms for neighbor discovery and bidirectional reachability checks (such as from the underlying link layer), it should not be constrained as much. Also allowing for unicast Hellos could improve performance in some networks.
	• would it make sense to use split horizon over wireless when sharing routes over unicast? (conceptually this could be equivalent to treating every neighbor as the other end of a point-to-point link)
	• if we get a seqno request from the same node that advertised the route would it make sense to treat that as a retraction?
	• what does an update with AE=0 and plen>0 mean?
	• what do you do on outgoing seqno requests if the route in question has been unselected between retransmissions?

David Schinazi

---

From: Juliusz Chroboczek <[email-masked]>
Date: Fri, 30 Sep 2016 13:17:23 +0200

Hi David,

Sorry for the delay, but I've been overwhelmed with teaching.  Tony's
mail is what brought me out of my apathy.

>       • in 3.1, "a Babel speaker does not need to determine the
>         destination address of a packet that it receives in order to
>         interpret it" isn't necessarily true in the case of IHU TLVs
>         with AE=0.

I don't see the issue.  AE=0 (which is NOT RECOMMENDED) can be used when
an implementation doesn't want to bother with bidirectional
reachability -- it just says "whoever you are, just assume I've heard you".
It can be processed without knowing the destination address.

>       • 3.5.4 indicates that the route table is indexed by (neigh, id,
>        prefix), this should not include the router ID (as in 3.2.5)

Colour me confused.  3.2.5 says

   It is indexed by triples of the form (prefix, plen, neighbour)

>       • typo in 3.8.1.2 "A node MUST NOT increase its sequence number by
>         more than 1 in response to a route request" should be seqno
>         request

Ack, noted.

>       • when discussing addresses, "compression is allowed" is unclear -

Ack.

>       • it was initially unclear that Hellos always require a seqno increment

Perhaps 3.4.1 needs a detailed step-by-step description in the style of 3.5.4 ?

>       • the feasibility condition is discussed in terms of updates sent
>         instead of selected routes, which makes sense but feels odd

It's actually not equivalent -- what you're suggesting is a uselessly
stronger condition (one that makes more routes unfeasible).  If you select
a better route, until you've sent an update you haven't made any routes
unfeasible, which can be important in periods of instability (path
exploration doesn't make any routes unfeasible).  And it's just as simple
to implement as the uselessly stronger condition.

>       • When text discusses if we have an entry for that prefix, it
>         should be made clearer that it's for that explicit prefix, not
>         one that contains the requested one (as in a shorter prefix)

Not sure, but noted.

>       • shouldn't the table of pending seqno requests (3.2.6) be indexed by
          routerID too? 3.8.1.2 is not clear about defining what redundant
          requests should be indexed on

You might be right, I'm not sure.  More comments on that at the very
bottom of this mail.

>         destination neighbor we sent it to?

What for?

>       • the omitted field in updates / corresponding flag are
>         per-address family but it's unclear what to do when receiving
>         AE=3(IPv6LL) and omitted>0 (are the 64bits of fe80 considered
>         omitted?)

Compression is not allowed for AE 3.  This should be made explicit, noted.

>       • 3.2.5 should specify that the information in the source and
>         route tables are not quite the same.

That's an editorial call, but I'd like to keep the description of the
protocol as concise as reasonable, so any such clarifications should
probably go into Section 2.

>       • the jitter discussion concentrates on one possible solution,
>         delaying and buffering, but there are other solutions such as
>         not reseting timers based on outside events

No objection, but since you want to accumulate multiple TLVs in a single
packet, you're going to want to buffer TLVs anyhow.

>         table if IHUs are sent unicast

Right.  The data structures are conceptual, any implementation that yields
equivalent results is fine.  (Another example, noted by Markus, is that
the route table could be split into a table of selected routes and a table
of redundant ones.)

>       • handling of Hellos - this deserves a thread all to itself but in
>         a nutshell Hellos feel like the most constraining part of
>         Babel.

Yes, that's an editorial flaw.  It was actually even worse in earlier
drafts, Joel did a great work forcing me to unconstrain this part of the
protocol.  I'm definitely open to that.

> Also allowing for unicast Hellos could improve performance in some networks.

Yes.  This would require an actual protocol change -- either a new TLV for
unicast Hellos, or adding a flag to the existing Hello.  (Note that Hellos
are already allowed to carry options, and there is one deployed extension
that has Hellos with options, so it's not completely trivial to do in
a backwards compatible manner.)

>       • would it make sense to use split horizon over wireless when
>         sharing routes over unicast? (conceptually this could be
>         equivalent to treating every neighbor as the other end of
>         a point-to-point link)

Yes.  I should try to write up the general property (the cases when split
horizon is harmless).

>       • if we get a seqno request from the same node that advertised the
>         route would it make sense to treat that as a retraction?

No.  Babel carefully avoids overloading any TLVs -- every TLV has
a well-specified meaning, and if you want to send two pieces of
information, you send two TLVs.  This is a very important property, and
the one that makes the protocol so flexible.  (For example, when doing the
initial design, I was under pressure to overload the packet header with
the semantics of Hello; had I done that, we would have been unable to
extend Hellos, as we have done in the RTT extension).

As you noted, you usually send a retraction together with a seqno request.
Since the two TLVs get aggregated into a single packet, there's very
little additional cost.

>       • what does an update with AE=0 and plen>0 mean?

I'm planning to drop AE 0.

>       • what do you do on outgoing seqno requests if the route in
>         question has been unselected between retransmissions?

This issue doesn't occur with RFC 6126, where seqno requests are indexed
by prefix (see above).  However, you might be right htat the request must
be indexed by router-id, in which case soemthing needs to be done.

(It's no big deal -- either you continue resending it, which helps
maintain your redundant routes, or you drop the request.  Either is fine.)

-- Juliusz