Subject: [babel] About Babel's complexity, and why it is unchanged by DTLS

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 18 Jul 2018 13:39:12 +0200

I'd like to clarify the comment I made about DTLS yesterday.

In principle, an implementation of Babel keeps state proportional to

  O(r * n)

where n is the number of neighbours and r the total number of routes being
advertised.  More precisely:

  - the neighbour table is O(n);
  - the route table is O(r * n).

An implementation can reduce that, with no protocol changes, to

  O(n)

by purging redundant routes from the route table, at the cost of slower
reconvergence after a failure (babeld will purge redundant routes when
malloc failes, but this code hasn't been tested much).

(Aside: naive link-state suffers from the same quadratic behaviour.  OSPF
and IS-IS work around the issue by using network pseudo-nodes and
delegated routers, and if your goal is to connect 20000 routers to
a single switch, you should be using OSPF or IS-IS rather than Babel.)

Both the DTLS and HMAC extensions expand the neighbour structure with
extra data -- DTLS adds the DTLS state, while HMAC adds the last index and
PC.  This increases the amount of state by O(n) -- which doesn't change
the complexity figures above.

In short -- adding DTLS to Babel does not fundamentally change the scaling
properties of the protocol.

-- Juliusz