Re: [OT] use of patented algorithms in the kernel ok or not?

[Matti Aarnio]

On Sun, Dec 21, 2003 at 05:43:51PM -0800, James Lamanna wrote:
> On Sun, 21 Dec 2003 14:40:40 -0500 Lennert Buytenhek wrote:
> >There is one already, and it's suboptimal, to say it mildly.
> 
> What algorithm does the kernel currently use for prefix-matching? I'm 
> interested now...
> And when you say suboptimal, what kind of difference are we talking?
> O(n) vs. O(1) lookups?

(I am reading 2.6.0 kernel source)

It used to be PATRICIA -- where you have binary-searchable sub-tables,
and you look from longest mask table first to see matches. If longer
mask table does not have a match, you move up to larger entries entries.

Now things are somewhat different, and murky underneath FIB-rules.
( net/ipv4/fib_*.c )   The lowest level has fib_hash.c doing lookups
thru  fn_hash_lookup()  function.

It does use hashes, which can, perhaps, do things in speedier, if not
all that cache friendly way.   Still, when you have multiple different
size prefixes, they are all processed the same way as PATRICIA does.

Original question was aiming to run with _full_ internet routing tables
in Linux kernel.  Now _that_ can be somewhat slow, and the patented
algorithm in question is able to handle it under 12 memory lookups in
all cases, while present hash-patricia chunks away a lot more time in
pessimal case.

In normal single interface IPv4 end-node usage we have 4 route entries.
(eth0, loopback, multicast, and default -routes.)  Those should be very
quick to go thru in linear search order and be processor cache friendly.

Even with a handfull of routes (and interfaces), but relying on default-
route to handle most things, I do claim that linear (ordered by mask
specifity!) search table is fastest.(*)

*) It depends on your machine hardware details, but CPU and its associated
   caches are these days factor 100 faster, than main memory random access.
   (And the gap is growing...)

> James Lamanna

/Matti Aarnio
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/