Subject: [babel] About mandatory bits

From: Juliusz Chroboczek <[email-masked]>
Date: Sun, 16 Apr 2017 02:52:43 +0200

Dear all,

As some of you have hinted (more or less rudely), there is an alternative
to the AE-based encoding of source-specific and TOS-sensitive routes that
I suggested: adding a mandatory bit to sub-TLVs.  The mandatory bit has
a number of advantages, and a number of cons when compared to the
multiplication of AEs.  Here are my thoughts on the subject -- I'm very
much interested in your opinions.

Encoding
********

The mandatory bit could be encoded as the top-order bit of the sub-TLV
type octet.  The sub-TLV format would then become:

     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |M|     Type    |    Length     |      Value
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

This reduces the sub-TLV type space, but that is not a problem since the
type space is extensible -- if we run out of sub-TLV numbers, 16-bit TLVs
can be encoded in a backwards compatible manner as follows:

     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |M|      127    |   Length + 2  |      Type                     |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | Value...
    +-+-+-+-+-+-+-+-+-

Semantics
*********

Mandatory and non-mandatory sub-TLVs are allocated separately -- mandatory
sub-TLV 2 does not necessarily have any relation with non-mandatory
sub-TLV 2.  An implementation MUST parse all the sub-TLVs of any TLV it
does not ignore, and if a TLV contains an unknown mandatory sub-TLV, then
the whole TLV MUST be silently ignored.

There's an implementation cost here: every implementation, even if it
doesn't do any extensions, MUST learn to parse all sub-TLVs, and to drop
TLVs that contain unknown mandatory sub-TLVs.

Compatibility
*************

No existing extensions are broken by mandatory bits: since all currently
defined sub-TLVs have small type numbers, they appear as non-mandatory
sub-TLVs, which preserves their semantics.

On the other hand, mandatory sub-TLVs stretch the weak compatibility that
we decided on in London.  Legacy implementations will get confused by
mandatory TLVs, treating them as non-mandatory, and, by mis-interpreting
updates with mandatory TLVs, might create routing loops.  I am not sure
whether this is acceptable at that stage.

Encoding of exciging extensions
*******************************

Mandatory bits allow a very simple encoding of both source-specific and
TOS-specific updates: a source-specific update is just a normal update
with a mandatory source-prefix sub-TLV, while a TOS-specific update just
carries a mandatory TOS sub-TLV.

The extensions combine easily -- just put both mandatory sub-TLVs.

Cost for implementations
************************

All implementations -- even minimal ones such as sbabeld or pybabel --
MUST learn to parse sub-TLVs in order to detect mandatory ones.  This is
an implementation cost, but one that only applies to minimal
implementations, since full-fledged implementations most likely already
know how to parse sub-TLVs.

This implementation cost is not outrageous -- we're speaking of a dozen
lines of C code or so.

Other applications
******************

The Italian mesh communities have requested the ability to tag routes with
opaque tags.  They want to be able to filter routes without configuring
each router with a list of prefixes, e.g. to have all Roman routers
originate routes with a "Roma" tag, and just configure non-Roman routers
to filter out the Roman routes.  Mandatory bits encode this easily.

Mandatory bits on Hello TLVs prevent associating with routers that don't
implement a given extension.  This allows an easy way to perform feature
negotiation, with no new mechanism.

Cultural compatibility
**********************

Mandatory bits are familiar from BGP and OSPF.  That puts people at ease.

Elegance
********

Elegance is in the eye of the beholder, but to my eyes mandatory sub-TLVs
are more elegant than the multiplication of AEs.

Conclusion
**********

Unless I'm missing something, mandatory bits are a simple, elegant and
powerful mechanism that fits well in Babel.  However, they silently break
compatibility in a manner that might or might not be unacceptable to our
user base.

Opinions?

-- Juliusz

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Sun, 16 Apr 2017 13:41:45 +0200

Juliusz Chroboczek <[email-masked]> writes:

> As some of you have hinted (more or less rudely), there is an
> alternative to the AE-based encoding of source-specific and
> TOS-sensitive routes that I suggested: adding a mandatory bit to
> sub-TLVs. The mandatory bit has a number of advantages, and a number
> of cons when compared to the multiplication of AEs. Here are my
> thoughts on the subject -- I'm very much interested in your opinions.

I like the fact that it can save us from combinatorial explosion.

As far as a flag day is concerned, that is probably going to be
necessary in many cases, since people running babeld using the
source-specific extension are still going to experience incompatibility
(I know that's the case for my network). And, well, if we are going to
introduce backwards-incompatible changes for the good of the future of
the protocol, now would be the time.

To me, the greatest drawback of this approach is that it raises the bar
for the minimum viable implementation. The current spec is dead simple
in this regard, and this would obviously change that, as you remark.
However, I would probably lean towards this cost being worth it...

> sub-TLV 2.

Is this just to save on sub-TLV numbers? Because I would think it is
bound to create confusion, which is probably not worth the few numbers
we could save on it.

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Sun, 16 Apr 2017 19:45:40 +0200

So I take it that you prefer mandatory bits to new AEs?

Markus, Margaret, David, I'd really like to hear your respective opinions.

> (I know that's the case for my network).

Plan is:

  babeld-1.9: sends the old format, parses both;
  babeld-2.0: sends the new format.

> And, well, if we are going to introduce backwards-incompatible changes
> for the good of the future of the protocol, now would be the time.

Probably.

> However, I would probably lean towards this cost being worth it...

I'll add sub-TLV parsing to sbabeld, see how much it bloats the code.
Does your implementation parse sub-TLVs?

> Is this just to save on sub-TLV numbers?

Yes.

> Because I would think it is bound to create confusion, which is probably
> not worth the few numbers we could save on it.

Noted.  I think this needs more discussion.

-- Juliusz

---

From: Dave Taht <[email-masked]>
Date: Sun, 16 Apr 2017 11:47:28 -0700

> So I take it that you prefer mandatory bits to new AEs?

I preferred an AE that was unambigious - so AEs 4 and 5 for source
specific seemed ok. 

> Markus, Margaret, David, I'd really like to hear your respective

I'm going to assume you mean apple's "david", as I am "dave".

>> Because I would think it is bound to create confusion, which is
>> probably not worth the few numbers we could save on it.
>

As you noted (and I was unaware of), the italian communities wanted
something similar to BGP, however I do not know how "tagging everything
with a Roma tag would work". (?)

Are there other latent requests out there? BGP in particular is chock
full of features that have ended up in it over time, some proven useful
by the test of time, others, not. I would certainly like to draw
inspiration from the good things in bgp and other routing protocols,
while still keeping things simple, robust, and well defined.

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Mon, 17 Apr 2017 18:53:30 +0200

> So I take it that you prefer mandatory bits to new AEs?

Well, if we are just talking about source specific routing, I think I
like the separate AE numbers better. That fits well with what my mental
model of a source-specific route is.

However, I can see your point that there could be other uses for
mandatory sub-TLVs, so introducing those is probably a good idea in any
case.

>   babeld-2.0: sends the new format.

What about making it configurable in 1.9 and just change the default for
2.0?

> Does your implementation parse sub-TLVs?

No, Babel in Bird 1.6 will be left confused by the introduction of
mandatory sub-TLVs. When I do actually get around to implementing
source-specific routing I'm planning to just do whatever encoding we end
up agreeing on, obviously...

-Toke

---

From: David Schinazi <[email-masked]>
Date: Mon, 17 Apr 2017 10:13:09 -0700

I do agree that a mandatory bit is a clean solution to enable more extensibility
without incurring the combinatorial explosion of AEs. The downside is that it
requires minimal implementations (such as mine) to parse sub-TLVs, which
mine didn't do until now. I can live with that. I see mandatory bits as a
reasonable tradeoff between simplicity and extensibility. I have no strong opinion,
only a slight preference for the mandatory bits, as I have a gut feeling they'll come
in handy somewhere down the line.

David

> On Apr 17, 2017, at 09:53, Toke Høiland-Jørgensen <[email-masked]> wrote:
> 
> _______________________________________________
> babel mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/babel

---

From: Matthieu Boutier <[email-masked]>
Date: Tue, 18 Apr 2017 16:49:26 +0200

I support mandatory bits.  Being incompatible is the only long-term *clean* solution I see.  I will provide an implementation of source-specific routing with mandatory sub-TLV (for babeld).

Matthieu

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 19 Apr 2017 14:24:28 +0200

> bound to create confusion, which is probably not worth the few numbers

After reflexion, I think that Toke has a point, but I'm still in favour of
separate allocation, since this avoids ambiguity when sending a mandatory
sub-TLV as non-mandatory and vice-versa.

How do people feel about that?

-- Juliusz

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Wed, 19 Apr 2017 14:31:24 +0200

> sub-TLV as non-mandatory and vice-versa.

Shouldn't the mandatory bit just be a part of the allocation? I.e.
"sub-tlv XX MUST be sent as mandatory", and setting the bit wrong should
be considered a format error? That would be the most unambiguous, in my
opinion.

If you have another sub-TLV with the same number, you can end up sending
something you did not intend to send if you get the bit wrong. E.g.,
"your timestamp is now a source prefix". That would be bad, I think? :)

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 19 Apr 2017 17:07:51 +0200

> be considered a format error? That would be the most unambiguous, in my

The way I think of it is

  TLV numbers 0-127 are non-mandatory;
  TLV numbers 128-255 are mandatory.

> "your timestamp is now a source prefix". That would be bad, I think? :)

You're probably going to detect the format error in any case, since the
sub-TLV will have the wrong length.  So I'm really not convinced that it's
worth dividing the space by two.

Perhaps somebody else has an opinion?

-- Juliusz

---

From: Gabriel Kerneis <[email-masked]>
Date: Wed, 19 Apr 2017 17:24:34 +0200

>   TLV numbers 128-255 are mandatory.

This makes sense, and this is how I thought about it too (except 255 is
neither mandatory nor non-mandatory, or 127 needs to be reserved too,
depending on how you want to deal with mandatory extended TLVs).

> Perhaps somebody else has an opinion?

But the problem Toke mentions bothers me too if you think of the mandatory
bit as an extra bit of information orthogonal to the TLV number. Since I
have not implemented a babel daemon myself, I'm not sure what approach is
more natural.

A related question is whether would it ever make sense to have a TLV that
would sometimes be sent as mandatory and sometimes not (eg. because it
would be safe to ignore some of the time based on the surrounding context).
If yes, then go with a shared pool. Otherwise, separate allocation makes
more sense.

Gabriel

---

From: David Schinazi <[email-masked]>
Date: Wed, 19 Apr 2017 09:56:55 -0700

It feels more natural to me have the mandatory part of the allocation number.
It's easier for an implementation to check equality on bytes than 7 bits.
I don't think we should divide the space in two.

David

> On Apr 19, 2017, at 08:24, Gabriel Kerneis <[email-masked]> wrote:
> 
> On Wed, Apr 19, 2017 at 5:07 PM, Juliusz Chroboczek <[email-masked] <mailto:[email-masked]>> wrote:
> This makes sense, and this is how I thought about it too (except 255 is neither mandatory nor non-mandatory, or 127 needs to be reserved too, depending on how you want to deal with mandatory extended TLVs).
>  
> But the problem Toke mentions bothers me too if you think of the mandatory bit as an extra bit of information orthogonal to the TLV number. Since I have not implemented a babel daemon myself, I'm not sure what approach is more natural.
> 
> A related question is whether would it ever make sense to have a TLV that would sometimes be sent as mandatory and sometimes not (eg. because it would be safe to ignore some of the time based on the surrounding context). If yes, then go with a shared pool. Otherwise, separate allocation makes more sense.
> 
> Gabriel

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 20 Apr 2017 00:03:46 +0200

> neither mandatory nor non-mandatory, or 127 needs to be reserved too,

The latter.  The plan is:

  0 --       special format (Pad1);
  1-111 --   non-mandatory, specification required;
  112-126 -- non-mandatory, local and experimental use;
  127 --     reserved for expansion of the non-mandatory space;
  128-239 -- mandatory, specification required;
  240-254 -- mandatory, local and experimental use;
  255 --     reserved for expansion of the mandatory space.

For what it's worth, Gwendoline is currently using 240.
  
> depending on how you want to deal with mandatory extended TLVs).

Oh, I think they need to have the mandatory bit at the same place, hence
the 127/255 scheme above.  If you have other suggestions, I listen.

> bit as an extra bit of information orthogonal to the TLV number. Since I have
> not implemented a babel daemon myself, I'm not sure what approach is more
> natural.

As David mentioned, the natural thing is to match on the whole type octet.
The implementation I just posted does something like:

  while(i < whatever) {
      type = buf[i];
      len = buf[i + 1];
      switch(type) {
          ...
      default:
          if((type & 0x80) != 0)
              return -1;
      }
      i += len + 2;
  }

Not a big deal, but the natural way to deal with it.

> A related question is whether would it ever make sense to have a TLV
> that would sometimes be sent as mandatory and sometimes not

Interesting idea.  I'll tell you if something comes to mind.

-- Juliusz

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Thu, 20 Apr 2017 11:05:43 +0200

>   TLV numbers 128-255 are mandatory.

Ah, right. Gotcha. I was thinking of it basically like this:

bool mandatory = tlv[0] & 0x80
u8 type = tlv[0] & 0x7f

where the contents of type would be what was specified in the RFC. That
would lead to two different "TLV type 2" being defined.

But if it's defined in terms of ranges of TLV numbers I see no problem
in assigning them separately :)

-Toke