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