search

dtaht / babeld-hacking

The Babel routing daemon
http://www.pps.univ-paris-diderot.fr/~jch/software/babel/
MIT License
1 stars 0 forks source link

naive implementation of set difference #31

Open dtaht opened 6 years ago

dtaht commented 6 years ago

This is the core of the xroute import problem. It's also similar to the resend problem. In both cases, we could use a way better structure to deal with it, and probably the same kind. rb_tree? I think avl would be better.

https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Set_operations_and_bulk_operations

https://github.com/dtaht/rabeld/blob/master/xroute.c#L355

dtaht commented 6 years ago

kernel rbtree is "augmented". Looks useful. It's GPL.

dtaht commented 6 years ago

this where resend goes nuts > 5k routes and desperately needs to not be a singly linked list. 36 byte compare too....

https://github.com/dtaht/babeld/blob/master/resend.c#L67

and the whole congestion control #11 and other issues #26 #20 with doing too much busty work would be better handled with a timer wheel.

dtaht commented 6 years ago

https://lkml.org/lkml/2005/10/19/46 was good

dtaht commented 6 years ago

I was not particularly happy with the overhead of an rbtree in these cases. So, reaching back into prehistory, I went looking at various tries.

"Hardware/Software IP Lookups with Incremental Updates" was good reading:

http://cseweb.ucsd.edu/~varghese/PAPERS/ccr2004.pdf

with some example code here: https://github.com/xnhp0320/prefix_lookup_mc

dtaht commented 5 years ago

The uthash version seems performant.