Subject: [babel] Experiences implementing Babel in the Bird routing daemon

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Wed, 19 Aug 2015 12:41:36 +0100

Hi everyone

Over the last couple of weeks, I've amused myself with doing a
clean-slate implementation of the Babel protocol in the Bird routing
daemon, and thought I'd report my experiences here.

I saw Juliusz' talk at the Babel side meeting in Prague (and again at
Battlemesh), which is what convinced me that this was actually a viable
project. Otherwise, I based my implementation on the RFC and did basic
interoperability testing with the official babeld implementation.

Overall, I found the RFC clear and easy to follow. Section 2 gives a
nice background on how the protocol works, and sections 3 and 4 gives
the details of how the implementation should work; in sufficient detail
that the implementation can done by referring only to those two
sections. The details that are left up to the implementation have nicely
suggested solutions in the appendices (which I used for my
implementation).

The main thing that I found confusing in the text was the mention of
'id' in section 3.5; took me a while to realise that this was supposed
to be the router id. In the rest of the document, this is quite
explicit, but in sections 3.5.1 and 3.5.4 they are referred to simply as
'id'. This is technically defined in the text, but one has to go looking
for it, so when flipping back and forth between the code and the
document I found it somewhat confusing.

The second thing I would have liked to have available is some more
guidance on how to ensure an implementation is actually compliant to the
RFC. I.e. a test suite, or at least some description of what kind of
edge cases to test (tricky topologies, that sort of thing). My testing
so far has been fairly ad hoc, and I'm pretty sure there's still bugs in
there.

The main part of the implementation took about a week, with another week
to fix bugs and convince myself that it actually works as intended; this
includes time to familiarise myself with the Bird daemon API and
internal logic (but on the other hand, I didn't have to write any code
to talk to the kernel). I by no means consider it a production-quality
implementation at this point, but it does exchange routes with the
babeld daemon and hasn't crashed my laptop yet :)

I've posted the implementation as a patch on the Bird list here:
http://trubka.network.cz/pipermail/bird-users/2015-August/009855.html --
that email also describes the current limitations of the implementation.

There's also a github repository with the complete commit history for
those who want to amuse themselves with perusing my struggles:
https://github.com/tohojo/bird

I hope this can serve as a useful data point in the assessment of the
implementability of Babel. I started this mainly as a project to satisfy
my own curiosity (the best way to understand a protocol is to implement
it, and all that), but do plan to put in some effort to get it to a
more robust state, depending on the feedback I get from the Bird
developers :)

Cheers,
-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 19 Aug 2015 22:26:03 +0200

> daemon

Excellent news, Toke.  I've had a first read over your code, and it looks
almost correct (I have some minor nits).  I'll read it again, and do
a detailed review with stupid questions about the bits I don't understand.

For the record, while Toke and I are friends, this is a completely
independent implementation of the IPv6 subset of RFC 6126 together with
Appendices A and B (I once looked over Toke's shoulder when he was hacking
at it, and he quickly shooed me away).

> to be the router id.

Noted, thanks.

> edge cases to test (tricky topologies, that sort of thing).

Point taken.

I may be biased, but in my experience the only tricky bit in the protocol
is reacting to starvation.  Everytime I touch this code, I put a router in
the middle of the network then increase the cost to all neighbours, and
check that seqno requests behave according to spec.  If they don't, you'll
notice right away -- either there'll be a request storm, or your routes
will remain unreachable for a long time.

If anybody knows how to write a test suite for a routing protocol, I'm
interested.  I imagine a set of scripts that set up some virtual machines
and perform some tests, but I have trouble imagining how it could perform
a test such as the one described above.

> to fix bugs and convince myself that it actually works as intended;

Impressive.  I'll dust some old laptops, and we'll do some more serious
testing when you come to Paris.

-- Juliusz

---

From: Dave Taht <[email-masked]>
Date: Wed, 19 Aug 2015 21:31:44 +0100

> testing when you come to Paris.

I can bring over the same 7 routers I had at battlemesh.

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

-- 
Dave Täht
worldwide bufferbloat report:
http://www.dslreports.com/speedtest/results/bufferbloat
And:
What will it take to vastly improve wifi for everyone?
https://plus.google.com/u/0/explore/makewififast

---

From: Markus Stenberg <[email-masked]>
Date: Wed, 19 Aug 2015 23:32:56 +0300

> On 19.8.2015, at 23.26, Juliusz Chroboczek <[email-masked]> wrote:

You don’t really need bunch of VMs. In order of decreasing hackiness:

[1] you need to only steal i/o (hello, LD_PRELOAD) and play with the black box that talks network protocols. 
[2] Or alternatively, do some root level raw packet i/o on the interface(s) the daemon uses.
[3] Or provide a box (/VM) which pretends to be whatever else is on the network and changing topology and whatever, which deals with the device/daemon/… (of course, you’re screwed if the protocol requires L2 events, but some boxes can simulate this too)

It is not really rocket science (I used to do test automation software for a living at some point), but very seldom really done comprehensively unless there is  serious industrial interest. 

Cheers,

-Markus

---

From: Markus Stenberg <[email-masked]>
Date: Wed, 19 Aug 2015 23:39:59 +0300

> On 19.8.2015, at 23.32, Markus Stenberg <[email-masked]> wrote:

Note: I everything I talk about applies to testing ‘a protocol’, there isn’t really anything particular magic about testing a routing protocol.

And in case this was not obvious from the context, you _do not_ typically use a full implementation as the reference to test against, but instead e.g. write the tests based on particular test cases that are obviously derived from the spec, and test each implementation against each of those individually. You may need subset of the implementation (or even full one) to really pretend to be one, but usually limiting complexity of tests (=> having small subset of full protocol used per test case) is sensible.

Usually you need
- way to reset implementation system under test (SUT) to a specific state (e.g. ‘reset’)
- way to inspect SUT state which is not visible externally (in case of routing protocol, probably locally installed routes)
- way to do the I/O with SUT (in case of a RP, probably a socket, wrapped in one of the few ways noted above)

Standard disclaimer: It’s been years since I did any other tests than hnetd ones (or unit tests for my own hobby things) :) 

Cheers,

-Markus

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Wed, 19 Aug 2015 22:12:47 +0100

Juliusz Chroboczek <[email-masked]> writes:

> Excellent news, Toke. I've had a first read over your code, and it
> looks almost correct (I have some minor nits). I'll read it again, and
> do a detailed review with stupid questions about the bits I don't
> understand.

Thanks. I'll look forward to your comments :)

> independent implementation of the IPv6 subset of RFC 6126 together
> with Appendices A and B (I once looked over Toke's shoulder when he
> was hacking at it, and he quickly shooed me away).

Yes, can confirm. Juliusz has likewise been most insistent on not giving
any hints. Most annoying, making me read like that...

> I may be biased, but in my experience the only tricky bit in the
> protocol is reacting to starvation. Everytime I touch this code, I put
> a router in the middle of the network then increase the cost to all
> neighbours, and check that seqno requests behave according to spec. If
> they don't, you'll notice right away -- either there'll be a request
> storm, or your routes will remain unreachable for a long time.

Well, basically taking the above paragraph and putting it in an appendix
as "things to test for" would be useful. I.e. some list of "make sure
these scenarios work and you should be set".

For the packet format, I targeted having wireshark agree with me on the
contents of the packets. That was fairly straight forward.

> interested. I imagine a set of scripts that set up some virtual
> machines and perform some tests, but I have trouble imagining how it
> could perform a test such as the one described above.

The CORE emulator might be useful in this regard:
http://www.nrl.navy.mil/itd/ncs/products/core

> testing when you come to Paris.

It'll be instructive, annoying and fun, I expect :)

-Toke