From mboxrd@z Thu Jan 1 00:00:00 1970 From: Steven Blake Subject: Re: Route cache performance under stress Date: 09 Jun 2003 23:05:47 -0400 Sender: linux-net-owner@vger.kernel.org Message-ID: <1055214346.1199.65.camel@photon> References: <87wuge59w2.fsf@deneb.enyo.de> <20030526.233211.54217447.davem@redhat.com> <87he70re62.fsf@deneb.enyo.de> <20030608.050500.28795668.davem@redhat.com> <874r30r9z2.fsf@deneb.enyo.de> Mime-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit Cc: netdev@oss.sgi.com, linux-net@vger.kernel.org Return-path: To: Florian Weimer In-Reply-To: <874r30r9z2.fsf@deneb.enyo.de> List-Id: netdev.vger.kernel.org On Sun, 2003-06-08 at 09:10, Florian Weimer wrote: > "David S. Miller" 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