[Babel-users] rbtree branch for resend.c

[Dave Taht]

1) After exploring a few more suitable data structures (hat and flash
tries), I gave up and just grabbed a clean looking rbtree library.
This got me up to where babeld could carry 20k+ routes without
breaking a sweat. (there's some issues with that much I/O too) Not
sure if it's correct as yet, after I know that I'll push it out. For
the record that was this one

http://github.com/mirek/rb_tree

which has a nice writeup here:

http://eternallyconfuzzled.com

I liked it because it wasn't recursive and used an array cleverly
instead of explicit code for left and right. It's not ideal
(union/difference are not in the lib), but once I stopped dithering
and burned 3 hours ridding us of that linked list, the results were
quite satisfying,

It did "do in" all the other, weaker routers on the link that I didn't
push that code out to, and a mips box still couldn't deal with it for
reasons unknown... but arm and x86 were fine.

I was kind of hung up on wanting something that could also expire
stuff but walking the tree to do that happens a lot less often.

2) It seems to me rescheduling the garbage collection phase should always
be flung into the future somewhat.

3) using a trie ( https://github.com/AUTProjects/FlashTrie.go/ ? ) &
hashes to scale even more is feasible. (the code now bottlenecks in
the various match routines to what extent it still does, and I/O) I
was thinking that a new tlv for appending a hash to a route might be
helpful so it doesn't need to always be recalculated...

I *might* take this idea to the nlogn branch (where I didn't get
around to figuring out why some filters aren't working, as yet). I'm a
a conference this weekend, don't expect to get anything done.

-- 

Dave Täht
CTO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-831-205-9740