LC-trie for Linux ipv4.
Here is the first public Linux implementation of LC-trie for ipv4. It is an
experimental alternative to the original fib_hash. LC-trie is often referenced
is publications wrt IP routing lookups and have no patent issues. We have
confirmed this with the authors.Of course there are lot of issues and things
to improve we are planning to test some enhancements when we allocate time for
this project again.
Performance.
We have been testing performance in a forwarding context with route hash
disabled. So device drivers/network stack have all been involved. For a few
entries in the routing table the performance is equal maybe slightly better
than fib_hash. For route DoS w. full BGP table current LC-trie is 20-25%
better compared to fib_hash. This in a forward context as described above.
To get the numbers above we must merge local/main routing table as Linux
routing always looks up local and main. This discussed this with Alexey.
The reason for the merge is that backtracking is expensive in trie's.
(There are some ideas in this area)
Locking.
Not yet done. We have been discussing RCU with Dipankar Sarma. There are
three obvious wring functions insert/delete/flush. Dipanker gave a weak
promise to look how RCU be used as a first option.
Route select correctness.
Should be done again. We did lookup tests before we moved to kernel space
and we compared with fib_hash.
Use.
We test in small scale production in couple of boxes.
LC-trie vs fib_hash
fib_hash is a good and proven routing algorithm no doubt. LC-trie advantages
is it's very flat tree even with large routing tables and it's ability to
support arbitrary bit strings i.e ipv6.
Other lookup algorithms.
As a side effect of this and davem work to clean up and distill FIB and
semantics from lookup. Other lookup algorithms should be somewhar easily
to add.
The FIB reorg patches sent on this list is needed for the the patch.
below copies can be found from:
ftp://robur.slu.se/pub/Linux/net-development/LPC-work/kernel/
LC-trie-041126.pat.gz
Description: Binary data
Enjoy.
--ro
|