Re: LC-trie FIB major rework

Re: LC-trie FIB major rework

[David S. Miller]

From: Robert Olsson <Robert.Olsson@data.slu.se>
Date: Thu, 26 May 2005 16:24:11 +0200

> Below much reworked version of the LC-trie for FIB lookup's. Much closer
> to current FIB anatomy and locking. Parent pointers in the trie to avoid 
> own stacks etc. The option to merge tables has been removed and much things 
> to keep things as simple and clean as possible. Although it's somewhat 
> complex. 
>  
> Performance. We now perform about 25-30% better than current FIB in 
> heavy lookup situations (we test with full rDoS) The test below illustrates
> this 123 kroutes in the routing table and rDoS is injected into eth0 at 
> 720 kpps routed traffic on eth1/eth3. route hash is not used and both 
> dst and src are looked up. LC-trie should work fine any size of routing table..

Very nice work Robert.  Once TSO becomes less of a time sink I
intend to help you out a bit.

Re: LC-trie FIB major rework

[Robert Olsson]

[-- Attachment #1: message body text --]
[-- Type: text/plain, Size: 1031 bytes --]


David S. Miller writes:

 > > Below much reworked version of the LC-trie for FIB lookup's. Much closer
 > > to current FIB anatomy and locking. Parent pointers in the trie to avoid 
 > > own stacks etc. The option to merge tables has been removed and much things 
 > > to keep things as simple and clean as possible. Although it's somewhat 
 > > complex. 
 > >  
 > > Performance. We now perform about 25-30% better than current FIB in 
 > > heavy lookup situations (we test with full rDoS) The test below illustrates
 > > this 123 kroutes in the routing table and rDoS is injected into eth0 at 
 > > 720 kpps routed traffic on eth1/eth3. route hash is not used and both 
 > > dst and src are looked up. LC-trie should work fine any size of routing table..
 > 
 > Very nice work Robert.  Once TSO becomes less of a time sink I
 > intend to help you out a bit.

 Thanks!
 Appreciate that.. take your time.

 Seems the patch wasn't distributed on the list probably due to size. 
 So below is a gzipped version.

 Cheers.
					--ro


[-- Attachment #2: trie.pat.gz --]
[-- Type: application/octet-stream, Size: 17082 bytes --]