[Babel-users] HEADS-UP: I've probably broken babeld

[Juliusz Chroboczek]

> Welcome to the path that OLSR.org chose years ago ;-)

Yeah, I know you're very proud (and rightly so) of your AVL implementation.

> May I ask out of curiosity which algorithmic changes you introduced?

Since the Babel protocol was in flux for a fairly long time, I've been
using very simple (and easy to modify) data structures.  In particular,
the route table (the RIB) was implemented as a simple array -- searching
for a given route was a O(n) operation.

One user has contacted me to say that in a 500 nodes network, they're
seeing 100% CPU usage and a number of packet drops for minutes before
the network converges.  Profiling indicates that at least 50% of the CPU
time is spent in find_installed_route, which is the function that
searches for the installed route to a given prefix.

What I've done is to replace the linear array by a sorted array of
linked lists, one per prefix, with the installed route (if any) at the
head.  This is the simplest data structure that I can think of that
makes find_installed_route be log(n).

OTOH, since it's just an array, inserting a route for a new prefix is
still O(n) (you need to shift the second part of the array).  I haven't
seen a profile yet, so I don't know if that's good enough.  If it turns
out it isn't, I'll switch to using some sort of self- balancing tree
(but perhaps not AVLs -- my guess is that B-Trees are perhaps
a better choice).

(My gut instinct, however, is that inserting new prefixes is a fairly
rare operation.  I'm more concerned by searching the source table, which
is still implemented as an unsorted array.)

-- Juliusz