BSD radix树路由表的设计原理

雨丝风片
在这里写下我的关于BSD radix树路由表的设计原理的文章之前，首先要感谢一个人：xie_minix，http://blog.chinaunix.net/index.php?blogId=2681。在我刚开始接触BSD 的radix树路由表的时候，是xie_minix发表在 http://www.cnfreeos.org/bsdsrc/ 的文章给我指明了最初的方向。滴水之恩，涌泉相报。自受惠于xie_minix公开的成果之日起，在下就决定将日后的心得也如xie_minix一般公之于众，以期能给其他的爱好、钟情、研究、使用BSD的朋友们一些帮助。
当然，还有一个人也是需要感谢的，W.Richard Stevens，没有他的书，也就没有了这里写下的一切。
写这篇文章的时候使用的是FreeBSD5.1的代码，举例用的是IPv6地址。
BSD路由表使用的是radix树，这种树的设计思想来自Donald R.Morrison于1968年提出的Patricia树（Practical Algorithm To Retrieve Information Coded In Alphanumeric）。这是一种基于以二进制表示的键值的查找树，尤其适合于处理非常长的、可变长度的键值。Partricia的基本思想是构建一个二叉树，在每个节点中都存储有进行下一次的bit测试之前需要跳过的bit数目，以此来避免单路分支（即避免二叉树的某一段呈现只往左或者只往右生长的趋势）。因此，一般意义上的Patricia树由内部节点和外部节点组成，内部节点用于指示需要进行bit测试的位置，并依据bit测试结果决定查找操作的前进方向，而外部节点则用于存储键值，查找操作将于外部节点处终止。
BSD正是借用了Partricia树的思想来组织路由表，但考虑到路由表的特殊性，即需要存储掩码并实现最长匹配路由查找，于是对Partricia树进行了改造，形成了BSD的radix树。在BSD的radix树中的路由查找操作将分为三个步骤，第一个步骤即是Partricia查找，终结于某个叶子节点，判断该叶子节点是否与查找键相同。第二个步骤，如果找到的叶子节点与查找键无法匹配，则在这个叶子节点的重复键链表中寻找网络匹配的可能。第三个步骤，如果找到的叶子节点及其重复键与查找键不满足网络匹配条件，则向树顶回溯，继续寻找网络匹配的可能。
1 BSD路由表的表头
BSD路由表的头指针存放在rt_tables[]数组中，这是一个radix_node_head结构体类型的指针数组。在BSD的协议栈中，所有协议的路由表都是用radix树进行组织的，而这些radix树的头指针就都存放在rt_tables[]数组中，IPv6路由表的头指针只是其中之一，即下标为AF_INET6的数组元素。
radix_node_head结构体的内存布局如图1所示。rnh_treetop是指向路由表顶部节点的指针。在这个结构体中还定义了8个函数指针，分别指向路由表提供的8个操作函数。在这个结构体的尾部还有三个radix_node结构体，这就是radix树的初始三节点，它们的rn_flags字段将被设置成RNF_ROOT，表示这是radix树的根节点。这三个节点是在路由表跏蓟?鄙?傻摹?

路由表初始化完成后，这三个根节点的链接关系如图3所示。从这个图中我们可以看出，在三个根节点组成的数组rnh_nodes[3]中，第二个根节点作为路由表的顶部节点，由rnh_treetop指针指向，它将是对路由表的所有操作的开始处。此外，第一个根节点被初始化为顶部节点的左孩子，第三个根节点被初始化为顶部节点的右孩子，而这三个初始根节点的父指针都指向了中间的那个顶部节点。这实际上已经搭起了一个radix树的基本框架。如图2所示。

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有