在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的路由，这样遍历链表快于对于数组的完全遍历。

    我对上述数据结构组织的看法是：这套数据结构是有工程经验但是算法能力较弱的工程师实现。一些树结构更加适合组织路由表项。

建议继续学习：

1. 浅谈MySQL索引背后的数据结构及算法    (阅读：9961)
2. 爱喝啤酒的程序员是如何学习数据结构的    (阅读：5185)
3. 分布式系统的数据结构    (阅读：5021)
4. stream.js ：一个新的JavaScript数据结构    (阅读：4101)
5. 开源世界中的算法与数据结构 3 -- Linux Kernel List 和GList    (阅读：2957)
6. 开源世界中的算法与数据结构 2 -- Linux Skbuff实现    (阅读：2779)
7. 数据结构之treap    (阅读：2747)
8. 开源世界中的算法与数据结构 3 -- Linux IPv6 FIB表实现    (阅读：2385)
9. 深入剖析 redis 数据结构 skiplist    (阅读：2385)
10. 深入剖析 redis 数据结构 ziplist    (阅读：1641)