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$(echo .)com \
--cc=linux-net@vger$(echo .)kernel.org \
--cc=netdev@vger$(echo .)kernel.org \
--cc=ratheesh.ksz@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
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