Re: fn_trie_lookup and fn_hash_lookup

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

On Fri, 28 May 2010 08:53:11 +0530
ratheesh k <ratheesh.ksz@xxxxxxxxx> 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.


	prompt "Choose IP: FIB lookup algorithm (choose FIB_HASH if unsure)"
	default ASK_IP_FIB_HASH

	bool "FIB_HASH"
	  Current FIB is very proven and good enough for most users.

config IP_FIB_TRIE
	bool "FIB_TRIE"
	  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.

Also see Documentation/networking/fib_trie.txt

To unsubscribe from this list: send the line "unsubscribe linux-net" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at

[Netdev]     [Ethernet Bridging]     [Linux 802.1Q VLAN]     [Linux Wireless]     [Kernel Newbies]     [Security]     [Linux for Hams]     [Netfilter]     [Git]     [Bugtraq]     [Photo]     [Yosemite]     [Yosemite News and Information]     [MIPS Linux]     [ARM Linux]     [Linux RAID]     [Linux PCI]     [Linux Admin]     [Samba]     [Video 4 Linux]     [Linux Resources]

Add to Google