From: "David S. Miller" <davem@redhat.com>
To: Kristen Carlson <kristenc@cs.pdx.edu>
Cc: netdev@oss.sgi.com
Subject: Re: linux 2.4 routing algorithm?
Date: Thu, 18 Sep 2003 19:57:53 -0700 [thread overview]
Message-ID: <20030918195753.676e76c8.davem@redhat.com> (raw)
In-Reply-To: <20030917234753.GB11250@sirius.cs.pdx.edu>
On Wed, 17 Sep 2003 16:47:53 -0700
Kristen Carlson <kristenc@cs.pdx.edu> wrote:
> I'm trying to understand the routing algorithm for linux 2.4. I thought
> it would use a longest prefix match due to some documentation I had googled,
> but the code in route.c looks like a hash. I probably just don't understand
> how lpm would be coded in practice. Am I looking in the right place? Can
> someone give me a clue about how this works?
route.c is the routing cache, it caches prefix based lookup results
so that a direct hash based lookup can be used for subsequent lookups
on the same exact key.
The prefix based lookup occurs in fib_hash.c, it uses 32+1 hash tables
to implement the prefix based lookup, one for each bit in the IPV4 address
plus an extra for "default" routes requiring matching of no bits. The
hash tables are lookup up from most specific to least specific so that
we truly get a longest matching prefix lookup.
Any time the routing tables are changed, the routing cache in route.c
is flushed completely.
prev parent reply other threads:[~2003-09-19 2:57 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2003-09-17 23:47 linux 2.4 routing algorithm? Kristen Carlson
2003-09-19 2:57 ` David S. Miller [this message]
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=20030918195753.676e76c8.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).