> 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 _______________________________________________ Babel-users mailing list [email protected] http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/babel-users
