fn_trie_lookup and fn_hash_lookup

fn_trie_lookup and fn_hash_lookup

[ratheesh k]

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 ?


Thanks,
Ratheesh

Re: fn_trie_lookup and fn_hash_lookup

[Stephen Hemminger]

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

Re: fn_trie_lookup and fn_hash_lookup

[ratheesh k]

On Fri, May 28, 2010 at 9:10 AM, Stephen Hemminger
<shemminger@vyatta.com> wrote:
> 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
>
>
>

Thanks ..