[Babel-users] rbtree branch for resend.c

[Dave Taht]

Christof Schulze <christof.schulze at gmx.net> writes:

> Hi
>> [ replace linked list with rb-tree]
> That sounds great, thank you for your efforts!
>
>>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.
> I do not think this is entirely a question of the data structure but
> also of the structure of babeld itself. 
>
> In l3roamd I also have the use case of scheduling tasks in the future
> to expire data or retry tasks. There I am using a heap to manage
> tasks. When the associated timer fires, the task is executed.
>
> It could be helpful to have something like that in babeld as well if
> auto-expiry is a concern. That would get rid of walking the structure
> to find expired items and get rid of the need to delay collecting
> garbage.

Well, it's more a case where I'd like to spread out updates, so
you would pull off the timerwheel all the updates you needed to do in
that interval, and no more. And stuff would also auto-expire.

My pathological test case (where I'm dumping in 20k routes all at once),
is just hell on networks, and for that matter, the local socket
buffer. Spreading that kernel dump into the future would help.

I remembered everything I disliked about rbtrees in a few days of
fiddling with my implementation in babel (deletion is a PITA), and
switched to using this hash library instead, which has all kinds of
nifty features (like bloom filters), is clean, and seems faster than
heck. 

http://troydhanson.github.io/uthash/

Still testing that...

>
> Christof
>
>
>
>>
>>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.