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 -- 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
