[babel] About mandatory bits

[Juliusz Chroboczek <[e-mail]>]

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