Subject: [homenet] T.M.S. proudly presents - Babel: the 2nd implementation

From: Markus Stenberg <[email-masked]>
Date: Thu, 26 Mar 2015 09:38:35 -0500

On Tuesday, there was much whining about single Babel implementation. Luckily T.M.S.[1] to the rescue - ~15 hours after start, routes synchronized unidirectionally, and after fixing bug or two this morning they go both ways, loop-free, etc. So I would argue I have implemented RFC6126 (aka Babel).

Proof (with some github timestamps for amusement from commits): https://github.com/fingon/pybabel

Numbers:

mstenber@kosame ~/work/pybabel>ohcount pybabel/*.py babeld.py
Examining 3 file(s)

                          Ohloh Line Count Summary

Language          Files       Code    Comment  Comment %      Blank      Total
----------------  -----  ---------  ---------  ---------  ---------  ---------
python                3        766        112      12.8%         79        957
----------------  -----  ---------  ---------  ---------  ---------  ---------
Total                 3        766        112      12.8%         79        957

(+ some more in unit tests)

8430 byte flash footprint on a router (given Python 3.4 interpreter, + some rounding up for blocksize of course)

Caveats:

- I implemented it like ‘zeroconf IS-IS’ works, that is, without useful cost function. It fully interoperates with more comprehensive implemenations though.
- Linux only to deal with FIB (system interface for dealing with routes is ‘ip’ command from iproute2); core developed on OS X
- IPv6 only (who wants legacy IP?)
- No source routing (I am sure it would maybe add 100 LoC or so)
- officially Python 3.4+ required (likely any Python 3+ variant works, sub-3 probably would need some work)

Disclaimer:

- if you plan to use this for production use, don’t, unless you test it for yourself sufficiently; however, it _does_ work

- pull requests welcome as long as footprint does not increase much

- bucketloads of money to implement more features are welcome too.. *smirk*

Cheers,

-Markus

[1] My personal consulting company; I have been unable to find funding for weird hacks, I do not know why.

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 26 Mar 2015 16:00:18 +0100

> On Tuesday, there was much whining about single Babel
> implementation. Luckily T.M.S.[1] to the rescue - ~15 hours after start,
> routes synchronized unidirectionally, and after fixing bug or two this
> morning they go both ways, loop-free, etc. So I would argue I have
> implemented RFC6126 (aka Babel).

Markus, I'm impressed -- I was estimating it would take you a week, not
15 hours.

Matthieu and I refrained from communicating with Markus while he was
working on that -- we didn't want to give him any hints.  Alia, Ted, am
I allowed to discuss implementation details with Markus, or would that no
longer count as independent implementation?

-- Juliusz

---

From: Michael Thomas <[email-masked]>
Date: Thu, 26 Mar 2015 08:07:15 -0700

> longer count as independent implementation?

At the very least, I think it's totally fair to subject it to any 
torture tests you have :)

Mike

---

From: Alia Atlas <[email-masked]>
Date: Thu, 26 Mar 2015 11:28:34 -0400

Julius,

> longer count as independent implementation?

What I'd recommend is keeping track of questions and issues - so you can do
errata
or think about what a bis draft would look like.

People do - of course - talk, but the goal is to have a document that
covers all
the details enough.

Regards,
Alia

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 26 Mar 2015 17:36:12 +0100

After a first read, it looks like a pretty complete implementation of
RFC 6126.  I have't checked in detail, but it looks like you got both the
loop avoidance and the blackhole avoidance mechanisms right.  You're also
doing bidirectional reachability detection and fairly reasonable route
selection.

> - I implemented it like ‘zeroconf IS-IS’ works, that is, without useful
>   cost function. It fully interoperates with more comprehensive
>   implemenations though.

You're doing a little better than that -- you're taking txcost into
account, so if the neighbour is performing link quality estimation, you're
going to use his value.

For consistency with Appendix A.2.2 of RFC 6126, please change your cost
function to:

  cost = rxcost * MAX(txcost, 256) / 256

where rxcost is some value no smaller than 256, instead of the current

  cost = rxcost + txcost

which will cause pybabels to be too strongly preferred.

> - IPv6 only (who wants legacy IP?)

Well, you already parse and honour the Next-Hop TLV, so adding IPv4
support would be trivial.  (NH is needed to advertise an IPv4 route when
speaking over IPv6.)

> - No source [specific] routing

Since the source-specific protocol interoperates with plain RFC 6126,
that's probably not as big a deal as it sounds.  We'll want to modify the
default OpenWRT configuration to make sure that it announces a high metric
(non-specific) default route towards each source-specific edge router.

You should be using a multiplier of the interval as a hold time, rather
than a fixed value (is Section 3.4.1 unclear?).  Interestingly, you
already do the right thing with IHUs (is Section 3.4.2 any clearer than
3.4.1?).  See also Appendix B.

I think you should always be preferring redistributed routes to learned
ones.

Oh, one last thing -- I don't understand the comment on line 367.  How can
the source table entry be a historic copy?

-- Juliusz

---

From: Markus Stenberg <[email-masked]>
Date: Thu, 26 Mar 2015 12:20:33 -0500

> On 26.3.2015, at 11.36, Juliusz Chroboczek <[email-masked]> wrote:

Thanks for the comments ;)

> which will cause pybabels to be too strongly preferred.

Good point. Changed.

> support would be trivial.  (NH is needed to advertise an IPv4 route when

Yeah, the main cost is just adding logic to deal with e.g. getting local IPv4 address too etc. Obviously not many lines (and e.g. imported route addition would already works with IPv4 too, if I did not intentionally disable it). So essentially given 2 removed lines it would be IPv4 stub router too.

> 3.4.1?).  See also Appendix B.

As noted in the comments txt I generated when coding it, the whole ‘recently heard from’ was bit vague to me. That’s why I stuck in fixed # there for now, although I guess use of multiplier on hello interval is correct way to do it.

> I think you should always be preferring redistributed routes to learned

I am :) local_routes are handled after the learned traversal, and they override them.

> the source table entry be a historic copy?

Admittedly that is not really valid in terms of RFC6126 (strictly interpreted), but I am intentionally maintaining separate set of selected and full routes. Due to that, I can allow for e.g. route selection to be done with some delay, and I still have consistent ’snapshot’ of selected routes at some point in time available even if I update the routes based on TLVs in the interim.

(This is mostly a potential performance optimization I left on the table, and it is virtually free; one pointer essentially per selected route. Not sure if it is really needed as such.)

Cheers,

-Markus

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 26 Mar 2015 18:52:32 +0100

> Admittedly that is not really valid in terms of RFC6126 (strictly
> interpreted), but I am intentionally maintaining separate set of selected
> and full routes.

That's perfectly valid.

The data model in RFC 6126 is conceptual, and while it describes the set
of routes as a single set with a per-route boolean indicating which routes
are selected, implementing it as two sets is just fine.

I'll do some testing tomorrow (my laptop stayed at home today, and I don't
feel like reflashing a router with Python).

-- Juliusz

---

From: Ted Lemon <[email-masked]>
Date: Thu, 26 Mar 2015 13:19:16 -0500

On Mar 26, 2015, at 10:07 AM, Michael Thomas <[email-masked]> wrote:
> At the very least, I think it's totally fair to subject it to any torture tests you have :)

I would suggest that you do interop tests, rather than trying to give him hints.   Markus, did you come up with a list of clarifications for the Babel document, or did you not find any?

---

From: Michael Thomas <[email-masked]>
Date: Thu, 26 Mar 2015 11:21:08 -0700

On 03/26/2015 11:19 AM, Ted Lemon wrote:
> I would suggest that you do interop tests, rather than trying to give him hints.

???

Mike

---

From: Markus Stenberg <[email-masked]>
Date: Thu, 26 Mar 2015 13:24:01 -0500

> On 26.3.2015, at 13.19, Ted Lemon <[email-masked]> wrote:

It does interoperate (all TLVs seem to be accepted by both parties). I welcome further tests of course.

I made some notes ([1]) that are basically my (implementation POV) notes trying to map the RFC to the code. As a disclaimer, while I have used the main Babel implementation before, and also read the RFC once or twice before (summarily), this is the first time I actually looked really hard at it :)

While there are few things that are somewhat vague in the RFC, they did not stop the implementations from interoperating so to some degree I would say the current RFC is in and of itself sufficient.

-Markus

[1] https://github.com/fingon/pybabel/blob/master/rfc6126-comments.txt

---

From: Ted Lemon <[email-masked]>
Date: Thu, 26 Mar 2015 13:32:17 -0500

> It does interoperate (all TLVs seem to be accepted by both parties). I welcome further tests of course.

Getting the implementations to talk is certainly the first step in interop testing, but e.g. I would like to know what happens if Dave Taht installs your Babel implementation on half of his base stations and keeps Juliusz' on the other half.   And I'd like to see your Babel implementation deployed in a significant number of the nodes in Berlin's network, and see what happens there.

None of this is to say that what you've done isn't really great, by the way--I'm delighted that you've done this!  But it's not the last step in the two-implementations test.

---

From: Michael Thomas <[email-masked]>
Date: Thu, 26 Mar 2015 11:54:50 -0700

> I would suggest that you do interop tests, rather than trying to give him hints.

Just to be pedantic, my comment was completely serious and not a "hint". 
New implementations almost always suffer
from lack of testing of corner cases. Same thing with protocol specs. If 
something exists to exercise those cases,
that would be good both from an implementation standpoint, and to make 
certain that those cases are sufficiently
clear from the spec text.

Mike, not sure why that deserved hostility in any case.

---

From: Mikael Abrahamsson <[email-masked]>
Date: Thu, 26 Mar 2015 20:00:49 +0100 (CET)

On Thu, 26 Mar 2015, Michael Thomas wrote:

> New implementations almost always suffer from lack of testing of corner 
> cases. Same thing with protocol specs. If something exists to exercise 
> those cases, that would be good both from an implementation standpoint, 
> and to make certain that those cases are sufficiently clear from the 
> spec text.

I have a PDF with hundreds of test cases with red and green boxes for test 
cases the Auto-ISIS implementation has passed or failed. It's currently on 
par with Cisco IOS when it comes to compliance.

So making the ISIS code "work" in the FOSS sense of "working" was easy, 
making it work according to the standard for all kinds of cases took a lot 
more work.

These are the kinds of tools babel is going to need if we're going to see 
multiple implementations of it from vendors and that they're going to 
interoperate.

-- 
Mikael Abrahamsson    email: [email-masked]

---

From: Lorenzo Colitti <[email-masked]>
Date: Thu, 26 Mar 2015 14:11:29 -0500

On Thu, Mar 26, 2015 at 2:00 PM, Mikael Abrahamsson <[email-masked]>
wrote:

>> those cases, that would be good both from an implementation standpoint, and
>> to make certain that those cases are sufficiently clear from the spec text.
>>
>

No, it is *not* going to need that. IS-IS needs that sort of testing
because it is widely used on networks that carry substantial parts of the
entire Internet's traffic, in extremely complex configurations like
multi-topology, traffic engineering, etc. etc. The reliability required of
implementations that carry such a burden is orders of magnitude greater
than what is needed in a home network that in most cases will consist of a
few devices that can easily be rebooted by the operator.

Home gateway routers routinely have broken implementations and crash all
the time, and have close to zero testing. What's the point of making the
routing protocol they run be 100 times more reliable?

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 26 Mar 2015 20:51:23 +0100

CC-ing the babel-users list.  Do we want to move this discussion over there?

> [1] https://github.com/fingon/pybabel/blob/master/rfc6126-comments.txt

Thanks for the comments.

> 'recently heard from' = ?

You mean Section 2.1?  That's in the protocol overview section, so I think
it's fine.  The actual procedure is defined in Section 3.4.2, where it's
hopefully clear that it's done for each neighbour.

The problem is elsewhere -- we don't say when to discard a neighbour.  The
answer is that it doesn't matter, but it should be said somewhere.  (The
reference implementation discards a neighbour after we've missed 16 hellos
in a row.)

> 'timer' <> 'time value' distinction is somewhat lacking in my opinion; some
> things require action at time point, and others do need just to be kept
> track of (e.g. 'hello timer''s various incarnations)

Where?

I think I tried to be consistent -- a timer is something that is set to
a value, decreases over time, and expires when it reaches zero.  I got it
wrong only once, saying that a timer "triggers" instead of "expires".

Relative times are consistently called "interval".  There are no absolute
times in this protocol.

> route table defined in 3.2.5 does not contain router id entries, yet 3.5.4
> refers to one

Yes it does.  Section 3.2.5 says that the route table includes

   o  the source (prefix, plen, router-id) for which this route is
      advertised;

Whether you implement that by actually storing these three pieces of data
in the route table (and look-up sources each time you need a seqno) or as
a pointer into the source table is an implementation detail, but in the
conceptual data model the route table contains a router-id.

> 3.5.4 what is 'id' in the updates and where is it stored?

Section 3.5.3, "Encoding of updates".  The problem is that I used "id"
here instead of "router-id".

> and what does the link cost = cost mean?

Confusing because I cannot use italics for variables.  Should have been
"over a link with cost /cost/".  Given the ASCII-only document, "cost"
should be renamed to "C".

> 3.5.5 describes what is done in 3.5.4, but to little point (imho)

I disagree.  3.5.4 says that a retracted route is kept in the route table
(the RIB).  3.5.5 says that this retracted route is actually reflected in
the forwarding table (the FIB, the kernel routing table) as a blackhole
route.  One could very well imagine that the retracted route is a purely
algorithmic data structure, that needs not be reflected in the forwarding
table.

> 3.6 'unfeasible route' = ?.. I assumed route table only contains feasible
> routes to start with?

Last point of 3.5.4 -- an unfeasible update is accepted, and a route table
entry is maintained (although it cannot be selected).  (You don't want to
be discarding a redundant route when it becomes infeasible, since seqno
numbers propagate at different speeds over different links -- there's
a good chance that it will become feasible within a jiffy or two.)

> 3.7.3: 'modified entry'; what if it was not modified? no gc reset? I
> assume so..

The GC timer is reset in all cases (except for retractions).  This should
simply say "the entry" or "the entry under consideration".

> 3.8.1.2 .. in response to a _seqno_ request, not route request

Right, typo.

> cannot parse 'no smaller'; not smaller?

I think that's correct, but then I'm not a native speaker.

> 3.8.2.1 is there necessarily seqno in the source table for all nodes?
> much easier just to use seqno from the route that is being
> retracted.. (maybe there is, but shrug)

The only place seqnos are kept is the source table (look at the data
model).  There are no seqnos associated to either nodes or routes.

The goal of this procedure is to get a seqno that will make the route
feasible.  Since feasibility is determined by the source table
(Section 3.5.1), it's the seqno in the source table that's relevant.

> SHOULD AE 1 or 3 for NH; why not 2? (ok, LL is better I guess..)

This just says that the next-hop for an IPv6 prefix should be a link-local
address.  That's consistent with both RIPng and OSPFv3.

-- Juliusz

---

From: Dave Taht <[email-masked]>
Date: Thu, 26 Mar 2015 13:01:44 -0700

I note that the only difference in quagga babeld vs babeld behavior
(aside from https://tools.ietf.org/html/rfc7298 )  that I could detect
at the last time I did major interoperability testing (I still have
quagga babel up at various points of my network however and can look
harder in the source specific case where I have had some issues in my
deployment - more likely something else )

was that quagga installed blackhole routes, while babel installed
unreachable routes, and I'd felt the latter was more correct. I don't
know if this issue was resolved in later versions.

babeld had more powerful route filtering, I'd had a case where I'd
wanted to distribute ipv6 but not ipv4 over an interface and couldn't
figure out how to do it right in quagga.

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 26 Mar 2015 21:16:10 +0100

> I would like to know what happens if Dave Taht installs your Babel
> implementation on half of his base stations and keeps Juliusz' on the
> other half.

Markus' implementation doesn't currently do any attempt at link quality
estimation, so any pybabel-pybabel link will be treated as if it didn't
suffer any loss, which will cause long and highly lossy links to be
preferred.  I'm pretty sure that would break Dave's network, we'd need to
test in a somewhat less hostile environment.

As to wired nets, the only limitation I can see right now is that pybabel
doesn't disable the Linux kernel's uRPF filter, so unless you remember to
do it manually, you're going to get transient blackholes.  I'll hopefully
be able to tell you more once I've finished reviewing the code and done
some testing.

By the way -- what Markus has written is some compact, elegant and
comprehensible code, and the comments include pointers to RFC 6126.  If
you grok Python, and if you're the kind of person who understands things
better by looking at code, his is the implementation to look at.

-- Juliusz

---

From: David Lamparter <[email-masked]>
Date: Thu, 26 Mar 2015 21:35:56 +0100

> know if this issue was resolved in later versions.

It's the same Babel implementation (possibly an outdated version of it,
depending on what you look at).  The kernel interface is different, hence
the above difference, but all code between on-wire packets and the final
route selection is essentially the same.

> figure out how to do it right in quagga.

Some features were replaced with Quagga's equivalent, e.g. route maps
and prefix lists.  I guess this adaptation may result in a slightly
different feature set.

-David

---

From: Dave Taht <[email-masked]>
Date: Thu, 26 Mar 2015 13:37:52 -0700

> test in a somewhat less hostile environment.

Heh. Yes, I have one intentionally hostile environment... but...

I have multiple production and lab networks, and python is at least
partially supported by cerowrt, and fully supported by openwrt, so
someone else could test it easily. In my case several of my more hefty
routers run ubuntu or are debian based like the ubnt edgerouter - and
furthermore it's quite routine to just add a roaming laptop running
linux or OSx to also be a participating router...

so I can certainly test it pretty easily in one or more of my own
labs, as could anyone else willing to try it.

That said, I'm more tempted to burn a week rewriting the python into
rust or go, now that I know how easy it is.  (thx, markus, for
completely blowing my mind!)

Part of that effort would be tho to get a better kernel netlink
implementation and low level network API interface than either
language has already (someone update me if there is something for
those that can do sendmmsg and recvmmsg?), and to explore any
parallization opportunities that exist for finding the best route
using either of those languages' native primitives for co-(go)routines
with a large (10000s) number of routes.

Does python not have a decent netlink interface already?

> better by looking at code, his is the implementation to look at.

I don't grok python very well, but it is mildly easier to read than the c, yes.

lua, anyone?

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

-- 
Dave Täht
Let's make wifi fast, less jittery and reliable again!

https://plus.google.com/u/0/107942175615993706558/posts/TVX3o84jjmb

---

From: Dave Taht <[email-masked]>
Date: Thu, 26 Mar 2015 13:45:32 -0700

On Thu, Mar 26, 2015 at 12:11 PM, Lorenzo Colitti <[email-masked]> wrote:
>>> cases. Same thing with protocol specs. If something exists to exercise those
>>> cases, that would be good both from an implementation standpoint, and to
>>> make certain that those cases are sufficiently clear from the spec text.
>>
>>

A set of web pages, a dedicated effort, and continuous testing, with
good tools, would be nice to have for *all* routing protocols and
*all* routing protocol daemons.

I pointed to the on-going FIB table re-work going on in linux in a
previous email. I would be seriously comforted if this level of
testing was going on continuously as other people swap out the engines
in the airplane in mid-air.

For those that are not keeping up with all the innovations going on in
linux throughout the stack, a good summary can be had via dave
miller's keynote talk at the recent netdev01 conference:

talks slides and videos here:

https://www.netdev01.org/sessions

>> making it work according to the standard for all kinds of cases took a lot

Agreed corner cases are a pita. To give one example of a corner case,
recently solved, I hope, in babeld, is the case where an interface
comes up or goes down in a matter of us.

It first occurred with dnsmasq, and while the fix was trivial, testing
for this corner case is a PITA. Some details on that bug are in the
two messages on that thread here:

http://lists.alioth.debian.org/pipermail/babel-users/2014-October/001775.html

I imagine many a network facing daemon has a similar bug, possibly
even quagga-isis.

> No, it is *not* going to need that. IS-IS needs that sort of testing because
> it is widely used on networks that carry substantial parts of the entire
> Internet's traffic, in extremely complex configurations like multi-topology,
> traffic engineering, etc. etc. The reliability required of implementations
> that carry such a burden is orders of magnitude greater than what is needed
> in a home network that in most cases will consist of a few devices that can
> easily be rebooted by the operator.

You never know where your code will end up and I will always be
happier the more testing gets done on every mission critical portion
of a system.

If you had asked me 20 years ago if the entire future of the world's
space program would depend on open source code, I would have been
dubious... but as it now *is* - anything that can add another sigma to
reliability or capability in our software makes me happier.

In addition to spacex's operations, and now the ISS, there are
multiple satellite and spacecraft projects that leverage core bits of
linux and the networking stack. As one example, on april 8th, this
linux based spacecraft flies (I think) as a secondary payload on
spacex crs-6:

http://space.skyrocket.de/doc_sdat/arkyd-3.htm

and I've had many a discussion about what routing protocols to use in
a solar system filled with such spacecraft, (prefer dv to link state,
obviously) and...

... while eternally grateful that the open source process has led in
part to a vast growth in space-capable hardware, it is always possible
to do better.

So by all means! Please find ways to make all things less buggy and
more reliable! I appreciate very much all the work done here, and in
hardware, and software, to make our expanding out into the solar
system a little bit easier.

> Home gateway routers routinely have broken implementations and crash all the
> time, and have close to zero testing. What's the point of making the routing
> protocol they run be 100 times more reliable?

Every little bit towards making systems rock solid reliable counts. My
own metric for shipping a stable cerowrt "Cero - spanish word for
zero" "Wrt - Warts" - Zero Warts - was a minimum of 3 months of
uptime. We (finally) achieved that.

http://www.bufferbloat.net/projects/cerowrt/news

I am sad that so few others in the home router and cpe market have the
same standards for reliability...

...as you have no idea where your code will end up, one day.

It pays to try for the lowest bug count and the highest reliability,
possible, whenever you can.

So bring on better tests and testbeds!

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 26 Mar 2015 21:45:53 +0100

> It's the same Babel implementation

Mostly, yes.

> (possibly an outdated version of it, depending on what you look at).

A more up-to-date version, including source-specific routing, is available at

  https://github.com/boutier/quagga-merge

in the branch pull-request.

(We've stopped maintaining it last year, due to our failure to get it
merged into mainline Quagga -- sorry for that, but Matthieu has got to
write up his thesis at some point, and cannot afford to do much
maintanance right now.)

-- Juliusz

---

From: Ted Lemon <[email-masked]>
Date: Thu, 26 Mar 2015 18:00:53 -0500

> Mike, not sure why that deserved hostility in any case.

I didn't intent hostility.   I'm sorry it came across that way.

---

From: Ted Lemon <[email-masked]>
Date: Thu, 26 Mar 2015 18:10:08 -0500

> test in a somewhat less hostile environment.

Is this not in the spec, or he just skipped this part?

> be able to tell you more once I've finished reviewing the code and done

Is this mentioned in the spec?   :)

> better by looking at code, his is the implementation to look at.

That's a huge compliment.   Nice going, Markus!

---

From: Ted Lemon <[email-masked]>
Date: Thu, 26 Mar 2015 18:13:08 -0500

> lua, anyone?

Write-only.   :)

(Probably not true, but I wasn't able to trivially grok it by reading sample code.)

---

From: Juliusz Chroboczek <[email-masked]>
Date: Fri, 27 Mar 2015 00:45:48 +0100

>> estimation

> Is this not in the spec, or he just skipped this part?

Link quality estimation is in the informative appendix A.2.2.  It was Joel
Halpern who convinced me to put it there, and he was right.  Link quality
estimation is dependent on the link layer, and the routing protocol should
not mandate a particular algorithm.

>> do it manually, you're going to get transient blackholes.

> Is this mentioned in the spec?   :)

    When a Babel router arbitrarily drops a packet for a destination to
    which it advertises a route with finite metric, it MUST send a short
    series of pulses of 220V AC current over all active interfaces, unlink
    the file called /vmlinuz, and reboot the system.

-- Juliusz

---

From: Michael Thomas <[email-masked]>
Date: Thu, 26 Mar 2015 16:53:07 -0700

>      the file called /vmlinuz, and reboot the system.

I've been skeptical of all of this routing bizness, but I *MUST* have 
one of these!

Mike

---

From: Ted Lemon <[email-masked]>
Date: Thu, 26 Mar 2015 23:04:15 -0500

> not mandate a particular algorithm.

This is more than a little bit problematic if we want router vendors to be able to produce useful implementations: they generally are not interested in doing research, and just ship whatever firmware their wifi chip vendor tells them to.

(Note that this is a problem whatever routing protocol we choose--I'm just pointing out that if we leave this to chance, we haven't really solved the problem.)

---

From: Juliusz Chroboczek <[email-masked]>
Date: Fri, 27 Mar 2015 12:31:49 +0100

>> Link quality estimation is in the informative appendix A.2.2.

> This is more than a little bit problematic if we want router vendors to
> be able to produce useful implementations: they generally are not
> interested in doing research, and just ship whatever firmware their wifi
> chip vendor tells them to.

Yeah, it's the old issue of how to encourage vendors to ship quality
implementations.  You probably have a lot of experience with that (I hear
you're a DHCP person, ahem).

One approach would be to pepper the spec with MUSTs, and complain loudly
when they are violated.  If I were in a nasty mood, I'd call this
attempting to legislate implementation quality.  (And if I were in
a really nasty mood, I'd ask how well that worked for OSPF in the 1990s.)

Perhaps I'm being naive, but with Babel I tried to take the opposite
approach: RFC 6126 tries to be very liberal, but we've been making freely
available a reasonably high-quality, liberally licensed implementation.
The expected result is that a lazy or cheap vendor will just take our
implementation and stick it on their hardware, while a smart vendor has
a lot of latitude to improve on our work.  The first has happened (there
are at least some commercial vendors who run the reference implementation
while claiming that they use a proprietary routing protocol), while the
second hasn't (unless you count TMS as a vendor).

More precisely, here's the approach I've taken in RFC 6126 (credit to Joel
Halpern for helping me with that):

  * if something is required to ensure the integrity of the network, it's
    a MUST.  In particular, bidirectional reachability detection, loop
    avoidance and blackhole avoidance are MUSTs (although one could
    conceive a protocol that interoperates with Babel without implementing
    any of those).

  * if something is needed for good performance, it's a mere SHOULD, so
    that it is possible to build an RFC 1217 compliant version of Babel.

  * if an algorithm is necessary, but could be implemented in different
    ways, then the properties that the algorithm have are MUST in the body
    of the document, and a suitable algorithm is described in an
    informative appendix.

There's one place where no algorithm is described — it's hysteresis
(Section 3.6).  At the time I was using a rather hackish solution, the
current algorithm was done last year.

A good example of the latter would be Section 3.5.2: it merely says that
the metric algebra (M, ⊕, ≤) MUST have the following property

     c ⊕ m > m                        (strict left monotonicity)

and SHOULD have the following property:

     if m ≤ m' then c ⊕ m ≤ c ⊕ m'    (left distributivity or isotonicity)

An obvious implementation would be to use the bounded integers equipped
with saturating addition, as used in IS-IS or OSPF, and that is what
Appendix A recommends.  However, an implementation is free to use

    c ⊕ m = c + 256/(battery charge) + m

or even (widest path algorithm):

    c ⊕ m = MAX(c, m + 1)

(Aside for the theoretically minded: the required axioms are different for
distance vector and for link state.  Dijkstra builds paths from the
destination, so it needs the right-hand-side properties where BF needs the
left-hand-side properties.  The impact of distributivity is not well
understood at the moment: in its absence, there is no "shortest path"
solution, analogously to what happens with interesting BGP policies.
There exists a proof that BF converges in the absence of distributivity
(due to a student of Tim Griffin, I forget his name), but it's rather
difficult.  Surprisingly enough, Dijkstra appears to converge even in the
absence of distributivity, but it leads to a set of trees that are not
necessarily consistent with next-hop forwarding.  End of aside.)

(Aside for the practically minded: the metric used by EIGRP violates
distributivity.  At the time, some in the community believed that this
indicated that EIGRP was broken; we now understand better why EIGRP works
as well as it does.)

Ted, I do understand where you're coming from when you say that the
latitude left to implementers worries you, but I really think that the
flexibility of Babel is one of its more appealing properties, and that
providing a high-quality implementation under a liberal license is
a better way to encourage vendors to do the right thing.  If I'm being
naive, please don't hesitate to educate me.

— Juliusz

---

From: Andrew Mcgregor <[email-masked]>
Date: Fri, 27 Mar 2015 09:10:50 -0500

Link quality estimation really is dependent on the link layer, but that
doesn't mean we can't give good guidance about what to do with certain
common link layers.  There's only a couple of reasonable solutions for
wifi, for example, depending only on hardware capabilities, so that would
be very clear.

On 26 March 2015 at 23:04, Ted Lemon <[email-masked]> wrote:

> This is more than a little bit problematic if we want router vendors to be
> able to produce useful implementations: they generally are not interested
> in doing research, and just ship whatever firmware their wifi chip vendor
> tells them to.
>
> (Note that this is a problem whatever routing protocol we choose--I'm just
> pointing out that if we leave this to chance, we haven't really solved the
> problem.)
>

-- 
Andrew McGregor | SRE | [email-masked] | +61 4 1071 2221

---

From: Michael Thomas <[email-masked]>
Date: Fri, 27 Mar 2015 07:27:32 -0700

>      of the document, and a suitable algorithm is described in an

I'm not sure if bringing in rfc 2119 is really helpful because sausage 
factory dev managers take the
requirements language as "must=will, should=maybe, may=definitely not" 
for their schedules. My
bet is what would be even more effective is to have bits of code readily 
available (either in-spec, or
in-github) so that little-to-no thinking is required. It's unfortunate, 
but whether the code works is not
what drives the incentives for lots of crappy low end routers from what 
I've seen.

Mike

---

From: "Leddy, John" <[email-masked]>
Date: Fri, 27 Mar 2015 17:52:07 +0000

I agree that ISIS testing is critical for core networks because the traffic volumes make the impact issue large, but fixing is “relatively” easy.
The small number of vendors (products), with limited configurations and reasonably up to date code helps.

But, having bugs and interoperability issues in 10’s of millions of homes, with many vendors (products) and code versions spanning a decade…
And  you may not be able to get new software from vendors (some defunct) even if you could encourage upgrades.

Not sure how you “fix” this.  You can’t even assume operators can even reboot customer owned gear.

This is independent of which IGP.

Who gets the phone call?  Who rolls a truck?

From: Lorenzo Colitti <[email-masked]<mailto:[email-masked]>>
Date: Thursday, March 26, 2015 at 2:11 PM
To: Mikael Abrahamsson <[email-masked]<mailto:[email-masked]>>
Cc: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>, Michael Thomas <[email-masked]<mailto:[email-masked]>>
Subject: Re: [homenet] T.M.S. proudly presents - Babel: the 2nd implementation

On Thu, Mar 26, 2015 at 2:00 PM, Mikael Abrahamsson <[email-masked]<mailto:[email-masked]>> wrote:
Just to be pedantic, my comment was completely serious and not a "hint". New implementations almost always suffer from lack of testing of corner cases. Same thing with protocol specs. If something exists to exercise those cases, that would be good both from an implementation standpoint, and to make certain that those cases are sufficiently clear from the spec text.

I have a PDF with hundreds of test cases with red and green boxes for test cases the Auto-ISIS implementation has passed or failed. It's currently on par with Cisco IOS when it comes to compliance.

So making the ISIS code "work" in the FOSS sense of "working" was easy, making it work according to the standard for all kinds of cases took a lot more work.

These are the kinds of tools babel is going to need if we're going to see multiple implementations of it from vendors and that they're going to interoperate.

No, it is *not* going to need that. IS-IS needs that sort of testing because it is widely used on networks that carry substantial parts of the entire Internet's traffic, in extremely complex configurations like multi-topology, traffic engineering, etc. etc. The reliability required of implementations that carry such a burden is orders of magnitude greater than what is needed in a home network that in most cases will consist of a few devices that can easily be rebooted by the operator.

Home gateway routers routinely have broken implementations and crash all the time, and have close to zero testing. What's the point of making the routing protocol they run be 100 times more reliable?

---

From: Juliusz Chroboczek <[email-masked]>
Date: Fri, 27 Mar 2015 23:44:57 +0100

> My bet is what would be even more effective is to have bits of code
> readily available (either in-spec, or in-github) so that little-to-no
> thinking is required.

Perhaps that's worth repeating.  The reference implementation of Babel is
available on Github:

    https://github.com/jech/babeld

It is licensed under the MIT/X11 license (extremely liberal):

    https://github.com/jech/babeld/blob/master/LICENCE

The code works out of the box on Linux and BSD Unix (tested under Mac OS
and OpenBSD).  It should be trivial to port to any platform that has the
IPv6 sockets API.

-- Juliusz