[Babel-users] Diversity [was: babeld-2.0]

[Juliusz Chroboczek]

>> Yep.  My current interest is working on frequency diversity --
>> something that Benjamin Henrion has shown can dramatically improve
>> the throughput in a mesh network.  It's far from trivial, either from
>> a theoretical or implementation point of view, which makes it
>> particularly interesting for me.

> My solution to this was rather drastic - switch to the 5.8ghz band, use
> 802.11n - which has way more channels available than 2.4 - and move to
> a country with a non-existent regulatory regime for this spectrum. I'm
> hoping your solution is more elegant.

Well, the two are pretty much orthogonal.  I'm working on using channel
information in route selection, while yours is about increasing the
number of channels.  One doesn't prevent the other.

There are basically two topologies that I'm considering:

  - a network with transit at one frequency and host access at another
    one (think 2.4 GHz edge routers with a 5 GHz backbone);
  - a mesh composed of multi-radio routers (think putting three radios
    tuned on non-interfering channels in all of your mesh routers).

Normal Babel (ETX) will make sub-optimal decisions in either case, since
it ignores frequency information.  While it is possible to work around
that with manual filtering and/or biasing of metrics, it should be
possible to make this sort of decisions automatically.

There's a fair amount of published litterature on this subject (my desk
is currently littered with papers speaking about diversity routing), but
I find a lot of it highly suspect.  First, all of the results I'm seeing
are either derived analytically or come from simulations, while radio
interference is something that we don't understand well, and I don't
trust the simulations.  Second, every paper introduces a different
metric, often with little or no justification, and they only ever
compare their diversity-enabled protocols to basic ETX or ETT -- I'm not
finding any comparisons between different diversity metrics.

So the first theoretical task is to define a diversity metric that is
sufficiently easy to compute, and understand how it relates to the
metrics in the litterature.  I think I've finished that -- I have
3 metrics that I know how to implement cheaply, and I understand how
they relate both to each other and to a number of metrics found in the
litterature.

The other theoretical issue is that these metrics violate a standard
property of routing metrics known as "isotonicity".  The usual opinion
is that non-isotonic metrics don't work, so people typically go to a lot
of trouble to work around the lack of isotonicity.  While I don't have
proof of this fact, my intuition is that Babel is sufficiently robust to
give non-pessimal results with a non-isotonic metric, something that
will need to be checked both experimentally and theoretically.  (As an
additional bit of circumstantial evidence: Cisco's EIGRP, which has
similar properties to Babel, uses a non-isotonic metric by default.)

I should have a diversity branch of the Babel daemon in time for the
meeting in Italy, where we'll hopefully be able to do enough testing to
know for sure whether this approach makes sense.

                                        Juliusz