在Linux 2.4 IPv4 FIB的数据结构基础上实现IPv6的FIB是否可行呢？如果读了我前面这篇文字你应该会有一个判断。IPv4的FIB实现可以说有些拙劣，如果照搬一个IPv6版本，最差情况下需要进行128次hash key计算这还不包括链表的查找过程。看了一下Linux 2.6的IPv6 FIB实现，已经有了调整，用了Patrix(Radix)树实现了这个算法，下面是一些背景知识：首先是Trie树，下图是Wiki http://en.wikipedia.org/wiki/Trie 之中的一个例子 Trie树，尤其是二叉Trie树属于：是一直被使用 ，从未被(教科书)重视的东东。其特点是键值的内容成为树的检索路径，例如上图的to，tea等几条键值标明的路径。如果要对trie分类的话，我想只能按照出度来分类，上图假定键值的每一字节取值a-z，则这个trie是26叉trie树，最小

    在Linux2.4的时候，对于Linux的FIB表有些研究。凭着残存的记忆和code，恢复一下FIB的数据结构。首先扫盲一下几个路由协议架构相关的概念： 上图为路由协议的基本架构，相关内容在Cisco出版社出版的某一本图书上有概念描述，大概是《Routing TCP》。 1． 每个路由协议根据自己收集到的路由信息产生内部的路由表。所有的路由协议的路由信息汇聚到统一的RIB之中。 2． RIB的管理模块根据RIB之中的路由条目按照优先级优选出实际用于转发的路由下发到FIB之中。 3． 最终在Packet到来的时候，系统查找FIB表做路由查找。对于FIB的主要需求有两个： 1. 组织和存储选出的路由表项。 2. 按照LPM(最长掩码匹配)算法提供路由检索接口。下图是Linux24之中的FIB表中几个主要的数据对象的数据结构关系。 具体字段不做解释，最终的目的就是找到dn_fib_n