On Fri, May 28, 2010 at 9:10 AM, Stephen Hemminger <shemminger@xxxxxxxxxx> wrote: > 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. > > 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 .. -- To unsubscribe from this list: send the line "unsubscribe linux-net" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
