routing table improvements

routing table improvements

[Tobias DiPasquale]

Hi all,

I am starting work on improving the routing table in Linux by removing
the route cache altogether and reimplemting the FIB with a radix tree
search implementation. However, I have some questions/RFCs before I
get too deep into it.

First of all, is anyone else doing something in this area?

Second, it doesn't look (to me) as if the lib/radix-tree.c
implementation is sufficiently generic to be used in this capacity.
What I mean is, it appears as if this code can't be used in interrupt
context, which is sort of a necessity for this particular purpose. Am
I just out of my mind or is that the case?

Finally, can anyone think of a reason not use a radix tree search for
the FIB? I was going to implement a simple binary radix tree (similar
to what FreeBSD has). I had originally thought of using something like
CEF uses (a 256-way radix tree), but this would be too
memory-intensive, IMO.

Anyone have any comments?

-- 
[ Tobias DiPasquale ]
0x636f6465736c696e67657240676d61696c2e636f6d

Re: routing table improvements

[David S. Miller]

On Sun, 24 Oct 2004 20:19:55 -0400
Tobias DiPasquale <codeslinger@gmail.com> wrote:

> First of all, is anyone else doing something in this area?

Yes, this has been discussed on this list over the past
2 months.  Let me save you some time:

1) We are already working on abstracting out the algorithmic
   portions of net/ipv4/fib_hash.c, see recent changeset
   history of this file in 2.6.x for details

2) Using the BSD Radix tree will not improve performance,
   it has the same algorithmic complexity as the current
   32-hashtable algorithm for large routing tables

3) Once the complexity of the mid-level routing table FIB
   algorithms is made better, there is no evidence that this
   means the routing cache should be removed.

   You should instead evaluate it's performance after the
   mid-level algorithms perform acceptably.

If you remove the routing cache, I don't believe you understand
the implications of this.  Firstly, you have to store the
routing metrics for every remote host we talk to, where do you
plan to store this and what will it be keyed upon?  How will you
handle per-socket routes?  How will you handle the interface with
the IPSEC layer which uses trees of routing cache entries as it's
fundamental object type?

Please scan the list postings, particularly on netdev, and I've
even given a keynote on our planned work just the other week in
Tokyo.