Han 通过 Google 阅读器发送给您的内容： 浅析Linux Kernel 哈希路由表实现(一) 于 11-3-13 通过 basic coder 作者：levin 1. 路由表 目前Linux内核中支持两种路由表，一种是Hash路由表，另一种是Trie路由表，Trie算法查找效率很高，但它也因极其消毫内存资源而闻名，因此一般用在大型机上，否则在路由项过多时很可能造成内存的耗尽。在一般的机器上最好还是使用Hash路由表，之前有争论说Linux使用Hash路由表相比于二叉树效率太低，不适合商用，其实只要设计良好的哈希算法，尽量减少哈希碰撞，Hash路由表的查找效率也是很高的，在最好的情况下算法复杂算可以达到O(1)，当然，最差也不过是O(n)，我们有理由相信Linux中存在各种优秀的哈希算法，这些都是值得我们学习的。 Linux内核中IPv4路由表采用了分层的结构，第一层是是fib_table，表示路由表，最多可以支持256张路由表，用户可以根据策略路由的需求来创建自己的路由表，系统默认的两张路由表为RT_TABLE_LOCAL和RT_TABLE_MAIN。下面是系统保留的路由表标识符： enum rt_class_t { RT_TABLE_UNSPEC = 0 , /* User defined values */ RT_TABLE_COMPAT = 252 , RT_TABLE_DEFAULT = 253 , RT_TABLE_MAIN = 254 , RT_TABLE_LOCAL = 255 , RT_TABLE_MAX = 0xFFFFFFFF } ; 下面是路由表的定义： struct fib_table { struct hlist_node tb_hlist ; /* 路由表的标识，即为上面提到的类型 */ u32 tb_id ; /* 该路由中默认路由条目在哈希路由表中的索...
评论
发表评论