Subject: [babel] In-depth look @ Babel towards PS ...

From: Tony Przygienda <[email-masked]>
Date: Fri, 25 Mar 2016 00:54:20 -0700

Here's my take before BoF after fairly careful reading & thinking through
Babel as documented/implemented today + some enlightening discussions with
Juliusz.  Comments/discussions/takes from the list before BoF would be very
welcome.

IMO Babel is sound in principle and worth pursuing for HomeNet world-wide
deployment scenarios iif

* some technical deficiencies are remedied and procedures defined more
tightly

* the solution is used on networks with relatively few devices (low 100s)
and fairly small diameter (~5-10) without large routing tables (>few K
addresses) or extensive aggregation. With suitable optimizations and
possibly protocol extensions the protocol may bear significantly larger
deployments as well.

Desirable properties and trade-offs as far I see them:

* significant implementation and standardization simplicity as compared to
a link-state protocol

* source-destination routing is almost trivial per
draft-boutier-babel-source-specific and seems correct from my experience
with further comments down.

* better stability in lossy networks for the cost of slower convergence
than link-state, probably a good trade-off given the likely wireless nature
of home style networks [as a trade-off for the stability a certain
“stickiness” is obviously to be expected as compared to link-state. This is
a normal consequence of a diffused rather than distributed computation. The
stickiness will get worse with diameter].

Now, what follows is the remaining work for the BoF (and/or possible WG) to
talk through/attack as recommendations from my side in rough sketch form (I
had very detailed discussions with Juliusz over email and some things we
agreed on, some we differ, some we agreed need further pondering upon by
people experienced in the art ;-) I omit many gritty details to keep the
picture fairly tractable (while giving underneath 2 examples of discussions
that ensued about why the spec as it stands today needs good amount of
attention to be of PS quality IME):

* first an optional but strongly suggested topic: detailed simulation of
Babel within the envelope agreed upon by the developers/chairs/requirements
set by HomeNet, i.e. mobility ratios, loss ratios, interference ratios to
ensure correct convergence within practical time limits and intended scale

* standardization of ideally a single one or max. 2-3 metrics (Juliusz
likes "default metric") which at least one of I would recommend to be
isotonic (but there seems  to be experience/consensus that left
distributivity [left isotonicity]) is not necessary for correct routing
[vs. optimal]). Something like metric dependent on interface type is
probably OK. The reasoning here is that the protocol must be stable,
converge well out-the-box amongst different vendors without requiring tons
of magic knobs or even if some routers had the "2-3 different metrics" knob
twisted.

 Proliferation of "experimental appendices and metrics" are perfectly fine
IMO as long they are understood as such, i.e. IETF-warranty-sticker is
peeled off the moment someone starts to twist those in a network.

 I read http://arxiv.org/pdf/1403.3488v1.pdf and the issues are well
researched and understood by authors. In case the simulations @ reasonable
sizes under required envelope prove stability/desired properties of such a
delay-metric under affine functions & hysteresis I see nothing wrong in
discussing this as a standard metric. Yes, it's risky IMO but the
traditional wisdom of last 20 years should be challenged with the world
changing on us. Without that, no progress can be made.

* standardization of default value for many constants e.g. for hysteresis,
timeouts that is guaranteed to internetwork in targeted networks
out-the-box (albeit doesn't have to be optimal).

* BoF/WG needs to discuss the multicast issue. How far is that in charter ?
Is another protocol needed ? Is Babel intended long-term to evolve into a
M-IGP ?

* BoF/WG should discuss/consider/answer the issue of auto-configuration of
router IDs. Albeit not within the scope of Babel I consider its deployment
success largely hinging off this issue.

* Procedures in 3.5.1 and 3.5.4 need tightening up. I expect under
simulations that the language will solidify in many more MUSTs than the
spec offers today. I do not question the convergence of the protocol
fundamentally (under an isotonic metric, otherwise it's one variable too
many for my current knowledge ;-) but I had discussions with Juliusz on
stable oscillations scenarios and will continue to have so. I give an
example below.

* From a practical standpoint, I suggest to make the spec strictly numbered
(i.e. clauses can be easily talked about like ISIS and OSPF) which will
simplify the ensuing discussions in the community significantly

* I suggest to introduce a glossary in the spec since many places the
reading is pretty loose (along the lines of ids, router ids, neighbor ids
which can be only read "in context" today and I ended up falling sometimes
on Bird implementation to be sure I understood correctly)

* I advise introduction of a mandatory flag on TLVs. src-dst routing works
as described in Juliusz' paper (i.e. all routers not understanding it
discard src-announcements and with that the multi-topology non-looping
properties are preserved correctly. A mandatory flag will allow to
differentiate between “an old router can just ignore unknown TLV and use
rest of information” to “old router can't understand extension and needs
ignore prefix or even whole tlv surrounding [to be specified])”.

 In short I consider the current treatment per "source specific routing"
paper by Juliusz as theoretically correct but practically too limiting in
long term, large-scale deployments.

 The discussion of mandatory flag on future TLVs extending the protocol and
causing black holes/loops if not understood/ignored by old routers is
something that I consider prerogatory to be discussed during BoF/WG charter.

* The compression on the packet format would need good tightening in terms
of error conditions, multiplicities allowed, TLV sequence/split between
packets. The compression itself is a good, novel idea worth trying albeit I
assume the spec here will be bigger than "normal" TLVs, discussions longer
and implementations more tricky to get them correct including error case
treatment.

* I advise towards 32 bit metric (first bits can be used to choose 8/16/32
compression if packet sizes are of uttermost importance) and same for 16
bit TLV length or 8/16 first-bit selectable format. ISIS 1-byte TLV length
led to lots of issues over years (which can be resolved but are avoidable
and represent complexity without value). Metrics that have proven too short
were and are operational and specification impediments of first degree.
Overall, it may be e.g. quite natural to split 16 bits len into 12 bit len
+ 4 flags [e.g. mandatory]).

* Security is the elephant in the room and I think that security A-D/area
should get interested and strongly support the work with
input/text/implementations. I don't consider a WG gunning for any kind of
standards track feasible without mandatory security deliverables as
advisable. The protocol as it stands (and is acknowledged) is open to even
the simplest intentional or unintentional attack.

* I choose not to touch on ECMP here which is another interesting topic.

Overall, I think there is an understanding that the discussions/extensions
may cause a likely uplift in protocol version, i.e. Babel-experimental
would need to become a Babel-v2-PS. But if there is a good time to do so,
the time would be now (in case of working group formation with the
according interest, energy and promise of delivery of such a protocol with
new ideas in routing adapting to novel link technologies prevalent today
and treating problems like src-dst routing which had no real satisfactory
solution (on the edge) )

----

For the insatiably curious, below examples of

i) a nit-grit in procedures and discussion necessary for PS track and

ii) discussion with Juliusz to clarify my concerns that the experimental
spec today implemented would not work correctly (and looking @
implementation would not clarify the issue) and even if the spec is aligned
with implementation I still have oscillation concerns that a possible WG
would need to discuss out.

Example 1: I went looking for SeqNr# rollover procedures and since the spec
only talked about “A node increments its sequence number (modulo 2^16)
whenever it receives a request for a new sequence number (Section 3.8.1.2
<https://tools.ietf.org/html/rfc6126#section-3.8.1.2>).“. I read that as
“don’t store in variable > 16 bit because you’ll overflow on inc” and only
after talking to Juliusz and looking @ Bird code I understood that the
following code below is meant. Now, this will work to _some_ reasonable
extent, the margin is fairly small (16 in best case) and whether it’s
enough for Babel deployments deserves a discussion given timeout values,
possible network partitioning times, seqnr frequency, possible storms of
seqnr requests (leading to discussion of the “keep request for some time”
logic and timers). A PS spec IMO should spell out clearly and easily how
the rollover is implemented and discuss the safety margin, run through
enough simulations to verify the margin of safety.

using u16 = unsigned short int;

static inline u16 ge_mod64k(u16 a, u16 b)

{

   return ((u16) a-b) < 0xfff0;

}

...

   auto prev = false;

   u16 i = 0;

   do {

       prev = false;

       u16 j =0;

       do {

           if (i>j && !ge_mod64k(i,j)) {

               if (!prev) {

                   cout << "from " << setw(4) << hex << "0x" << i

<< ", " << setw(2) << hex << "0x" << j ;

               }

               prev = true;

           }

           else {

               if (prev) {

                   cout << " until " << setw(4) << hex << "0x"

<< i << ", " << setw(2) << hex << "0x"

<< j << endl;

               }

               prev = false;

           }

           j++;

       } while (j);

       i++;

   }

   while (i);

from   0xfff0, 0x0 until   0xfff0, 0x1

from   0xfff1, 0x0 until   0xfff1, 0x2

from   0xfff2, 0x0 until   0xfff2, 0x3

from   0xfff3, 0x0 until   0xfff3, 0x4

from   0xfff4, 0x0 until   0xfff4, 0x5

from   0xfff5, 0x0 until   0xfff5, 0x6

from   0xfff6, 0x0 until   0xfff6, 0x7

from   0xfff7, 0x0 until   0xfff7, 0x8

from   0xfff8, 0x0 until   0xfff8, 0x9

from   0xfff9, 0x0 until   0xfff9, 0xa

from   0xfffa, 0x0 until   0xfffa, 0xb

from   0xfffb, 0x0 until   0xfffb, 0xc

from   0xfffc, 0x0 until   0xfffc, 0xd

from   0xfffd, 0x0 until   0xfffd, 0xe

from   0xfffe, 0x0 until   0xfffe, 0xf

from   0xffff, 0x0 until   0xffff, 0x10

----

Example 2: (one of the simpler discussions on oscillations and normative
language)

C -- B -- A -- S

source S advertising to A will start with A showing B D_s=1 and with that C
being shown D_s=2 and B having feasiblity condition of 1. In case link cost
from S to A bumps to 5 (it needs more nodes so S is not bumping seq number
but another node shows bigger metric but the idea holds), B will refuse
updates from A  being the only route to S _and_ it will not start an
explicit route request while C will still see the incorrect distance to S
based on procedures in 3.5.4  [which would benefit from numbering like ISIS
and OSPF spec in case we aim for PS].

The solution is in the fact that 3.8.2.2 casually mentions “In order to
keep routes from spuriously expiring because they have become unfeasible, a
node SHOULD send a unicast seqno request whenever it receives an unfeasible
update for a route that is currently selected.”

As Juliusz pointed out, it’s a MUST and not a SHOULD. The difference is
impossible to derive from reference implementations obviously and the
wording of 3.8.2.2 does not suggest connection to correctness of 3.5.4.

Even after the MUST fix, it merits a discussion how far an oscillation
behavior can be generated if the condition persists (i.e. a convergence
scenario exists where after a feasible route is installed an infeasible
route arrives every time due to timing constraints on the propagation of
the new seqnr#).

thanks

--- tony

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Fri, 25 Mar 2016 23:22:12 +0100

Tony Przygienda <[email-masked]> writes:

> Here's my take before BoF after fairly careful reading & thinking
> through Babel as documented/implemented today + some enlightening
> discussions with Juliusz. Comments/discussions/takes from the list
> before BoF would be very welcome.

Cherry-picking and replying to the parts I do have thoughts on, see
below...

> * first an optional but strongly suggested topic: detailed simulation
> of Babel within the envelope agreed upon by the
> developers/chairs/requirements set by HomeNet, i.e. mobility ratios,
> loss ratios, interference ratios to ensure correct convergence within
> practical time limits and intended scale

Probably a good idea. Having a test suite in a suitable simulation or
emulation environment that people can actually run their implementation
in would be nice too.

> * standardization of ideally a single one or max. 2-3 metrics

Yes, especially if this is to be implementable by people who are not
already routing protocol experts (like, say, homenet router vendors or,
well, me...). Upgrading from the current "look in the appendix if you
don't have a good idea for a metric to use" to "implement this to
comply, *then* go experiment with your own metrics if you want" would
probably be a good idea.

> Proliferation of "experimental appendices and metrics" are perfectly
> fine IMO as long they are understood as such, i.e.
> IETF-warranty-sticker is peeled off the moment someone starts to twist
> those in a network.

Maybe having a set of "standard metrics" that were well-understood and
configurable in implementations might be nice? Then (sufficiently
advanced) users could be told to "use the Mesh Metric", for instance.

> * standardization of default value for many constants e.g. for
> hysteresis, timeouts that is guaranteed to internetwork in targeted
> networks out-the-box (albeit doesn't have to be optimal).

I agree, for the same reason as above for metrics.

> * BoF/WG should discuss/consider/answer the issue of
> auto-configuration of router IDs. Albeit not within the scope of Babel
> I consider its deployment success largely hinging off this issue.

Probably a good idea. Isn't the space large enough that drawing them
randomly, or by hashing, would work?

> * The compression on the packet format would need good tightening in
> terms of error conditions, multiplicities allowed, TLV sequence/split
> between packets. The compression itself is a good, novel idea worth
> trying albeit I assume the spec here will be bigger than "normal"
> TLVs, discussions longer and implementations more tricky to get them
> correct including error case treatment.

Yes; when I wrote the Bird implementation I decided that I wouldn't even
try to implement this (on the sending side). Hashing out the edge cases
in the standard would probably be enough to make me reconsider :)

> * I advise towards 32 bit metric (first bits can be used to choose
> 8/16/32 compression if packet sizes are of uttermost importance) and
> same for 16 bit TLV length or 8/16 first-bit selectable format. ISIS
> 1-byte TLV length led to lots of issues over years (which can be
> resolved but are avoidable and represent complexity without value).
> Metrics that have proven too short were and are operational and
> specification impediments of first degree. Overall, it may be e.g.
> quite natural to split 16 bits len into 12 bit len + 4 flags [e.g.
> mandatory]).

I'd also tend to agree. After all, what is a few extra bytes between
friends?

> * Security is the elephant in the room and I think that security
> A-D/area should get interested and strongly support the work with
> input/text/implementations. I don't consider a WG gunning for any kind
> of standards track feasible without mandatory security deliverables as
> advisable. The protocol as it stands (and is acknowledged) is open to
> even the simplest intentional or unintentional attack.

Surely nobody will try to do evil things on the homenets of the future?
Certainly that seems to be the philosophy driving the internet of things :/

> Overall, I think there is an understanding that the
> discussions/extensions may cause a likely uplift in protocol version,
> i.e. Babel-experimental would need to become a Babel-v2-PS. But if
> there is a good time to do so, the time would be now (in case of
> working group formation with the according interest, energy and
> promise of delivery of such a protocol with new ideas in routing
> adapting to novel link technologies prevalent today and treating
> problems like src-dst routing which had no real satisfactory solution
> (on the edge) )

I'd agree that *if* we are to increment the protocol version number, now
would be the time. Not sure if the possible improvements from doing so
outweigh the cost (for myself the cost is fairly low: I can easily
upgrade my entire network at once when needed). After all, we'd also
want to have the people currently running Babel to use the IETF standard
version of it when that time comes.

-Toke

---

From: Tony Przygienda <[email-masked]>
Date: Fri, 25 Mar 2016 22:32:14 -0700

Toke, very good, seems we're  hitting roughly same wavelength. Let's see
whether more people chime in into this thread ...

BTW, Babel in Bird is pretty easy on the eyes (i.e. flows well and just the
right amount of comments to get over the rougher patches ;-) given it's C,
compliments ;-)

-- tony

-- 
*We’ve heard that a million monkeys at a million keyboards could produce
the complete works of Shakespeare; now, thanks to the Internet, we know
that is not true.*
—Robert Wilensky

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Sat, 26 Mar 2016 11:49:17 +0100

Tony Przygienda <[email-masked]> writes:

> Toke, very good, seems we're hitting roughly same wavelength. Let's
> see whether more people chime in into this thread ...

Yup. :)

> BTW, Babel in Bird is pretty easy on the eyes (i.e. flows well and
> just the right amount of comments to get over the rougher patches ;-)
> given it's C, compliments ;-)

Oh, wow, gee... thanks! :)

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Sun, 27 Mar 2016 19:50:56 +0200

Thanks for your work, Tony.

> * I advise introduction of a mandatory flag on TLVs.

Do you mean on sub-TLVs?  If you really mean TLVs, then I'd appreciate you
spelling out the proposed semantics.

(Pro memoria, Babel's packet structure is not recursive, it has just three
levels: a Packet contains a sequence of TLV which can optionally contain
sub-TLVs.  Putting a mandatory bit in sub-TLVs makes sense -- you drop the
whole enclosing TLV --, although I'm not yet convinced it's worth the
added complexity.  On the other hand, I don't see what a mandatory bit in
toplevel TLVs would mean -- you drop the whole packet?)

> src-dst routing works as described in Juliusz' paper

Matthieu's and Juliusz' paper.

> Babel-experimental would need to become a Babel-v2-PS.

RFC 6126 describes Babel version 2, so that would be Babel version 3.

> Example 1: I went looking for SeqNr# rollover procedures [...]

[...]

> and only after talking to Juliusz and looking @ Bird code I understood
> that the following code below is meant:

>     return ((u16) a-b) < 0xfff0;

No, Bird gets it wrong (I've mentioned it to Toke already).  The proper
definition is

   static inline int
   seqno_compare(unsigned short s1, unsigned short s2)
   {
       if(s1 == s2)
           return 0;
       else
           return ((s2 - s1) & 0x8000) ? 1 : -1;
   }

Which only strenghens your point that this needs to be spelled out in the
RFC.  (When writing RFC 6126, I was under the illusion that ordering
modulo is a standard, well known notion -- it turns out I was wrong.)

-- Juliusz

---

From: Juliusz Chroboczek <[email-masked]>
Date: Sun, 27 Mar 2016 19:58:46 +0200

> modulo is a standard, well known notion -- it turns out I was wrong.)

It is defined in RFC 1982, altough the RFC doesn't define the case
s1 = s2 + 2^15.

---

From: Tony Przygienda <[email-masked]>
Date: Sun, 27 Mar 2016 11:11:21 -0700

> toplevel TLVs would mean -- you drop the whole packet?)

yes,

i) I advise completely symmetric type/len/flags field on all
TLV/sub-tlv/sub^n-TLV
for the simple reason that parsin' is much simpler but you'll figure
ii) laugh or not, after initial tlv/sub-tlv and never deeper
"sign-in-blood-and-cross-my-heart"
structure started in ISIS we are discussing possible sub^3-TLVs for better
or
for worse for certain things now. Price of "wild success" we discussed in
other conversations.

> Matthieu's and Juliusz' paper.

sorry, forgot how to do BibTex ages ago ;-)

> RFC 6126 describes Babel version 2, so that would be Babel version 3.

nit ... ack.

> modulo is a standard, well known notion -- it turns out I was wrong.)

yepp, now THIS looks more like lolli-pop space I mentioned (if memory
carries
after all those years) and this was FAR more safe  but yes, it would need a
write-down
or reference to OSPF spec (don't remember John ever described it carefully
@ the end either).
Current OSPF folks will have it present.

Yuh, reference implementations and all ;-)  and this is  of course only a
single
nit but exemplifies the "scar tissue" and PS track point. E'one who read
John's book will read
the entertaining story of "you have to shut down the _WHOLE_ internet to
fix it".
Whether it's the Internet of the "shut your whole home network" is just a
flavor of
"unhappy customer" at the end ...

--- tony

---

From: Tony Przygienda <[email-masked]>
Date: Sun, 27 Mar 2016 11:12:46 -0700

Wow, good catch. Forgot all about that.

---

From: Denis Ovsienko <[email-masked]>
Date: Mon, 28 Mar 2016 14:25:32 +0100

Hello all.

[...]

>* Security is the elephant in the room and I think that security A-D/area should get interested and strongly support the work with input/text/implementations. I don't consider a WG gunning for any kind of standards track feasible without mandatory security deliverables as advisable. The protocol as it stands (and is acknowledged) is open to even the simplest intentional or unintentional attack.  

[...]

That's the motivation behind RFC 7298. I am looking forward both to present my own input and to listen to any other input on this subject. On this note, if anybody considers some document(s) meaningful for this BoF discussion (not just security), may I suggest they mention such documents on the mailing list soonest possible to help the participants to prepare better? Thank you.

-- 
    Denis Ovsienko

---

From: Juliusz Chroboczek <[email-masked]>
Date: Mon, 28 Mar 2016 15:53:20 +0200

> if anybody considers some document(s) meaningful for this BoF discussion
> [...] mention such documents on the mailing list

Seconded.

Here's my current reading list for the plane, further suggestions welcome:

  - details of the IS-IS packet format (Gredler?);
  - DVMRP (RFC 1075, anything else?);
  - RFC 7298 (I'm a little rusty);
  - ???

-- Juliusz

---

From: Dave Taht <[email-masked]>
Date: Mon, 28 Mar 2016 06:57:52 -0700

>   - RFC 7298 (I'm a little rusty);

bgp-pgp

rfc3971

>
> -- Juliusz
>
> _______________________________________________
> babel mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/babel

---

From: "Joel M. Halpern" <[email-masked]>
Date: Mon, 28 Mar 2016 10:10:26 -0400

I must be missing something.  What is the relevance of SEND (RFC 3971, 
Secure Neighbor Discovery) to Babel?
Also, as anyone actually rolled out SEND in operation?

Yours,
Joel

---

From: Dave Taht <[email-masked]>
Date: Mon, 28 Mar 2016 07:14:25 -0700

> Also, as anyone actually rolled out SEND in operation?

It is a very good example of a failure to deploy, yes, a good learning
experience.

Given that arp, and nd, and ra, still have problems in these regards,
and that things like bgp-pgp also have issues, and there are other
major issues with these problems in other in-home protocols (dnssec,
mdns, upnp, pcp), what's one more insecure protocol going to do to us?

/me ducks