From: Stephen Hemminger <shemminger@vyatta.com>
To: ratheesh k <ratheesh.ksz@gmail.com>
Cc: netdev@vger.kernel.org, linux-net@vger.kernel.org
Subject: Re: fn_trie_lookup and fn_hash_lookup
Date: Thu, 27 May 2010 20:40:55 -0700 [thread overview]
Message-ID: <20100527204055.406343eb@nehalam> (raw)
In-Reply-To: <AANLkTikmIzPaOKdlXtCwosfJXzaKY1vxib_MdqI0vN_5@mail.gmail.com>
On Fri, 28 May 2010 08:53:11 +0530
ratheesh k <ratheesh.ksz@gmail.com> wrote:
> hi ,
>
> I was looking into 2.6.18 kernel . I can see two functions
> fn_trie_lookup , fn_hash_lookup
>
> ipv4/fib_trie.c: tb->tb_lookup = fn_trie_lookup;
> ipv4/fib_hash.c: tb->tb_lookup = fn_hash_lookup;
>
> What is the differnce between these two functions ?
They are the two possible FIB algorithms configurable.
net/ipv4/Kconfig:
choice
prompt "Choose IP: FIB lookup algorithm (choose FIB_HASH if unsure)"
depends on IP_ADVANCED_ROUTER
default ASK_IP_FIB_HASH
config ASK_IP_FIB_HASH
bool "FIB_HASH"
---help---
Current FIB is very proven and good enough for most users.
config IP_FIB_TRIE
bool "FIB_TRIE"
---help---
Use new experimental LC-trie as FIB lookup algorithm.
This improves lookup performance if you have a large
number of routes.
LC-trie is a longest matching prefix lookup algorithm which
performs better than FIB_HASH for large routing tables.
But, it consumes more memory and is more complex.
LC-trie is described in:
IP-address lookup using LC-tries. Stefan Nilsson and Gunnar Karlsson
IEEE Journal on Selected Areas in Communications, 17(6):1083-1092,
June 1999
An experimental study of compression methods for dynamic tries
Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
http://www.nada.kth.se/~snilsson/public/papers/dyntrie2/
Also see Documentation/networking/fib_trie.txt
next prev parent reply other threads:[~2010-05-28 3:41 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2010-05-28 3:23 fn_trie_lookup and fn_hash_lookup ratheesh k
2010-05-28 3:40 ` Stephen Hemminger [this message]
2010-05-28 6:13 ` ratheesh k
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=20100527204055.406343eb@nehalam \
--to=shemminger@vyatta.com \
--cc=linux-net@vger.kernel.org \
--cc=netdev@vger.kernel.org \
--cc=ratheesh.ksz@gmail.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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.