Re: Route cache performance under stress

[Steven Blake <slblake@petri-meat.com>]

On Sun, 2003-06-08 at 09:10, Florian Weimer wrote:

> "David S. Miller" <davem@redhat.com> writes:
> 
> > Although, I hope it's not "too similar" to what CEF does because
> > undoubtedly Cisco has a bazillion patents in this area.
> 
> Most things in this area are patented, and the patents are extremely
> fuzzy (e.g. policy-based routing with hierarchical sequence of
> decisions has been patented countless times). 8-(
> 
> > This is actually an argument for coming up with out own algorithms
> > without any knowledge of what CEF does or might do. :(
> 
> The branchless variant is not described in the IOS book, and I can't
> tell if Cisco routers use it.  If this idea is really novel, we are in
> pretty good shape because we no longer use trees, tries or whatever,
> but a DFA. 8-)

Based on my quick reading of your code sample, I think you have just
reinvented multibit trees; in your case with a fixed stride of 8 bits. 

> Further parameters which could be tweaked is the kind of adjacency
> information (where to store the L2 information, whether to include the
> prefix length in the adjacency record etc.).

If you are curious, or just have a lot of time on your hands, you might
find the following set of references useful:

http://www.petri-meat.com/slblake/networking/refs/lpm_pkt-class/

IMHO, the best LPM algorithm (in terms of balancing lookup speed vs.
memory consumption vs. update rate) is CRT, described in the first paper
[ASIK].  It is patented, but there is hope that it might get released
under GPL in the near future.


Regards,

// Steve