patricia tries vs. hash for routing?

patricia tries vs. hash for routing?

[Kristen Carlson]

Hi,
I'm wondering if somebody has already written a patch that replaces the
current routing algorithm (hash) with one that is based on a trie based
algorithm?  I'm also wondering if anybody has done any performance 
comparisons with very large route tables to see which one scales better?
thanks,
Kristen
 
-- 
WWXD (What Would Xena Do?) 

Re: patricia tries vs. hash for routing?

[David S. Miller]

On Thu, 18 Sep 2003 10:29:10 -0700
Kristen Carlson <kristenc@cs.pdx.edu> wrote:

> I'm wondering if somebody has already written a patch that replaces the
> current routing algorithm (hash) with one that is based on a trie based
> algorithm?  I'm also wondering if anybody has done any performance 
> comparisons with very large route tables to see which one scales better?

Patricia trees aren't going to help, most of the overhead in
the routing lookup is in implementing the various fancy features
our routing code supports.  For example, equal cost multi-pathing
and other such things.

The front end routing cache is a straight hash and is thus the
fastest way to lookup a route.  In the presence of well behaved
traffic and routing tables that do not change too often, it is
optimal.

Re: patricia tries vs. hash for routing?

[Kristen Carlson]

I was looking through some very old mail list discussions (1996!) on this 
topic, and the feeling then was that the code was optimal for < 60,000 routes.
Given that much has happened since then, is it still a fair assumption to say
that the linux routing algorithm is optimized for < 60,000 routes, but a
more BSD-like algorithm works better for > 60,000 routes?
Thanks,
Kristen

Re: patricia tries vs. hash for routing?

[David S. Miller]

On Fri, 19 Sep 2003 14:48:37 -0700
Kristen Carlson <kristenc@cs.pdx.edu> wrote:

> I was looking through some very old mail list discussions (1996!) on this 
> topic, and the feeling then was that the code was optimal for < 60,000 routes.
> Given that much has happened since then, is it still a fair assumption to say
> that the linux routing algorithm is optimized for < 60,000 routes, but a
> more BSD-like algorithm works better for > 60,000 routes?

That's not true at all, the current code can handle many more than
60,000 routes.

Don't speak with abstract claims that bear no content, do your own
experiments with a properly configured system and report them in
detail here.

Re: patricia tries vs. hash for routing?

[bill davidsen]

In article <20030919233730.75969de6.davem@redhat.com>,
David S. Miller <davem@redhat.com> wrote:
| On Fri, 19 Sep 2003 14:48:37 -0700
| Kristen Carlson <kristenc@cs.pdx.edu> wrote:
| 
| > I was looking through some very old mail list discussions (1996!) on this 
| > topic, and the feeling then was that the code was optimal for < 60,000 routes.
| > Given that much has happened since then, is it still a fair assumption to say
| > that the linux routing algorithm is optimized for < 60,000 routes, but a
| > more BSD-like algorithm works better for > 60,000 routes?
| 
| That's not true at all, the current code can handle many more than
| 60,000 routes.

I don't think "optimized for" meant it wouldn't handle more, just that
performance would degrade.
-- 
bill davidsen <davidsen@tmr.com>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.