From: "David S. Miller" <davem@redhat.com>
To: Kristen Carlson <kristenc@cs.pdx.edu>
Cc: netdev@oss.sgi.com
Subject: Re: patricia tries vs. hash for routing?
Date: Thu, 18 Sep 2003 20:17:43 -0700 [thread overview]
Message-ID: <20030918201743.11d88366.davem@redhat.com> (raw)
In-Reply-To: <20030918172910.GA22091@sirius.cs.pdx.edu>
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.
next prev parent reply other threads:[~2003-09-19 3:17 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2003-09-18 17:29 patricia tries vs. hash for routing? Kristen Carlson
2003-09-19 3:17 ` David S. Miller [this message]
-- strict thread matches above, loose matches on Subject: below --
2003-09-19 21:48 Kristen Carlson
2003-09-20 6:37 ` David S. Miller
2003-10-28 13:29 ` bill davidsen
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20030918201743.11d88366.davem@redhat.com \
--to=davem@redhat.com \
--cc=kristenc@cs.pdx.edu \
--cc=netdev@oss.sgi.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).