在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_nh之中的nexthop信息，其实例实现结构如下：
上图的Zone是Linux的FIB实现的程序对象概念，代表了特定长度的Prefix的路由的集合。因为Prefix长度可以有1到32，即总计32种，因此共有32个Hash table。Zone0对于0/0，即default路由。
为了加速最长掩码匹配，Linux FIB实现引入了zone list，用于按照prefix长度递减的方向将所有zone串接起来，这样从头到尾匹配即符合LPM算法要求。之所以说是优化，原因是可能FIB表中只有前缀长度为16和24的路由，这样遍历链表快于对于数组的完全遍历。
我对上述数据结构组织的看法是：这套数据结构是有工程经验但是算法能力较弱的工程师实现。一些树结构更加适合组织路由表项。