开源世界中的算法与数据结构 1 -- Linux FIB实现
在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的路由,这样遍历链表快于对于数组的完全遍历。
我对上述数据结构组织的看法是:这套数据结构是有工程经验但是算法能力较弱的工程师实现。一些树结构更加适合组织路由表项。
建议继续学习:
- 浅谈MySQL索引背后的数据结构及算法 (阅读:9886)
- 爱喝啤酒的程序员是如何学习数据结构的 (阅读:5070)
- 分布式系统的数据结构 (阅读:4956)
- stream.js :一个新的JavaScript数据结构 (阅读:4083)
- 开源世界中的算法与数据结构 3 -- Linux Kernel List 和GList (阅读:2901)
- 开源世界中的算法与数据结构 2 -- Linux Skbuff实现 (阅读:2723)
- 数据结构之treap (阅读:2688)
- 开源世界中的算法与数据结构 3 -- Linux IPv6 FIB表实现 (阅读:2327)
- 深入剖析 redis 数据结构 skiplist (阅读:2262)
- 深入剖析 redis 数据结构 ziplist (阅读:1591)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:appleleaf 来源: kernelchina blogs
- 标签: FIB 数据结构
- 发布时间:2012-02-05 23:15:03
- [54] IOS安全–浅谈关于IOS加固的几种方法
- [52] android 开发入门
- [52] 如何拿下简短的域名
- [51] 图书馆的世界纪录
- [49] Go Reflect 性能
- [49] Oracle MTS模式下 进程地址与会话信
- [47] 【社会化设计】自我(self)部分――欢迎区
- [46] 读书笔记-壹百度:百度十年千倍的29条法则
- [36] 程序员技术练级攻略
- [29] 视觉调整-设计师 vs. 逻辑