[Babel-users] Babel and multipath [was: atomic updates ...]

[Juliusz Chroboczek]

> Now that Linux 3.8 has support for IPv6 ECMP is there any plan to
> use that again to make updates more attomic

The current code works on a variety of kernels, and is good enough for
me.  Everytime I've tried to change it, somebody hit a bug on some
exotic kernel variant.

I can change my mind, of course.

> or even support multipath directly.

[...]

> Do I understand it correctly that in the case of babeld it might
> 'just' be make babeld recognize equal routes, have a way to keep
> track of them inside babeld and add multiple routes to the kernel.

It's a little more complicated than that.  First of all, Babel has
16-bit metrics, so if two routes have similar but not quite equal
metrics, you might want to install both of them -- call that "almost
equal cost multipath".  I'm not sure it's standard, but I believe that
Cisco do that in EIGRP.

Second, on a wireless network multipath might be unproductive if the
two routes interfere.  So you might want to use the interference
information provided by Babel-Z to only select non-interfering routes.

Third, Babel has a fairly sophisticated loop avoidance mechanism, and
it's not quite trivial to generalise it to multipath.  A Babel route
announcement consists of four pieces of data:

  (prefix, metric, router-id, seqno)

rather than just (prefix, metric) as in ordinary Bellman-Ford.  A FIB
route is readvertised as

  (prefix, cost + metric, router-id, seqno)

Now suppose you're doing AECMP on two routes

  (prefix, metric, router-id, seqno)
  (prefix, metric', router-id', seqno')

If router-id and router-id' are the same, then you should advertise

  (prefix, max(cost + metric, cost' + metric'), router-id, min(seqno, seqno'))

The max of the metrics is absolutely essential -- if you don't do
that, then you'll get persistent routing loops.  The min of the seqnos
is what makes loop avoidance work in this case.

If the two router-ids are different, then there is no good solution --
you won't have any persistent loops, but you might get transient loops
in some cases.  A fairly good solution is to advertise the router-id
and seqno that realise the max of the metrics, but apply the
update_source procedure to both routes.  This can cause transient
loops in some pathological cases, but I'm pretty confident they will
disappear speedily.

If anyone wants to work on that, make sure you understand Babel's
loop-avoidance properties.  I'll be glad to look at your code anytime.

-- Juliusz