Re: Route cache performance under stress

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

"David S. Miller" [off-list ref] writes:

quoted

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-(

quoted

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