BSD radix树路由表的设计原理

《BSD radix树路由表的设计原理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、写这篇文章的时候使用的是FreeBSD5.1的代码，举例用的是IPv6地址。　　BSD路由表使用的是radix树，这种树的设计思想来自DonaldR.Morrison于1968年提出的Patricia树（PracticalAlgorithmToRetrieveInformationCodedInAlphanumeric）。这是一种基于以二进制表示的键值的查找树，尤其适合于处理非常长的、可变长度的键值。Partricia的基本思想是构建一个二叉树，在每个节点中都存储有进行下一次的bit测试之前需要跳过的bit数目，以此来避免单路分支（即避免二叉树的某一段呈现只往左或者只往右生长的

2、趋势）。因此，一般意义上的Patricia树由内部节点和外部节点组成，内部节点用于指示需要进行bit测试的位置，并依据bit测试结果决定查找操作的前进方向，而外部节点则用于存储键值，查找操作将于外部节点处终止。　　BSD正是借用了Partricia树的思想来组织路由表，但考虑到路由表的特殊性，即需要存储掩码并实现最长匹配路由查找，于是对Partricia树进行了改造，形成了BSD的radix树。在BSD的radix树中的路由查找操作将分为三个步骤，第一个步骤即是Partricia查找，终结于某个叶子节点，判断该叶子节点是否与查找键相同。第二个步骤，如果找到的叶子节点与查找键无法

3、匹配，则在这个叶子节点的重复键链表中寻找网络匹配的可能。第三个步骤，如果找到的叶子节点及其重复键与查找键不满足网络匹配条件，则向树顶回溯，继续寻找网络匹配的可能。1BSD路由表的表头　　BSD路由表的头指针存放在rt_tables[]数组中，这是一个radix_node_head结构体类型的指针数组。在BSD的协议栈中，所有协议的路由表都是用radix树进行组织的，而这些radix树的头指针就都存放在rt_tables[]数组中，IPv6路由表的头指针只是其中之一，即下标为AF_INET6的数组元素。　　radix_node_head结构体的内存布局如图1所示。rnh_tree

4、top是指向路由表顶部节点的指针。在这个结构体中还定义了8个函数指针，分别指向路由表提供的8个操作函数。在这个结构体的尾部还有三个radix_node结构体，这就是radix树的初始三节点，它们的rn_flags字段将被设置成RNF_ROOT，表示这是radix树的根节点。这三个节点是在路由表跏蓟时生成的?　　路由表初始化完成后，这三个根节点的链接关系如图3所示。从这个图中我们可以看出，在三个根节点组成的数组rnh_nodes[3]中，第二个根节点作为路由表的顶部节点，由rnh_treetop指针指向，它将是对路由表的所有操作的开始处。此外，第一个根节点被初始化为顶部节点的左孩

5、子，第三个根节点被初始化为顶部节点的右孩子，而这三个初始根节点的父指针都指向了中间的那个顶部节点。这实际上已经搭起了一个radix树的基本框架。如图2所示。　　在图2中，我们将中间的作为路由树顶的根节点用圆圈表示，因为它属于内部节点。而另外的两个根节点我们用方框表示，它们属于叶子节点。在本文档中将始终按照这一约定来图示内部节点和叶子节点。2BSD路由表的节点　　BSD路由表的radix树实际上就是由一系列的内部节点和叶子节点组成的。内部节点位于树的中间位置，每个内部节点都会指定一个bit测试位置，即当从树的顶端开始向下查找，遇到这个内部节点时需要判断是0还是1的bit位置，接下

6、来的查找将根据bit测试的结果来决定是向左走还是向右走。叶子节点位于树的边缘，用于存储路由表键值，即IP地址。　　2.1内部节点　　前已述及，内部节点在radix树中用于表示一个bit测试位置。　　内部节点和叶子节点使用的都是radix_node结构体，只是少数字段的定义有所不同。我们首先通过内部节点来查看一下radix_node结构体中的各个字段。在radix树中的3个根节点中，位于中间的那个顶端节点就是内部节点，因此我们的描述就以图3为例。　　rn_mklist:这个指针指向的是一个radix_mask结构体链表。对于内部节点来说这个链表上的掩码都取自它的子树中的叶子节点所

7、对应的掩码，但只有那些在做逻辑AND运算时能够把这个内部节点的测试bit变成0的掩码才能够加入到这个链表中，这类掩码的作用将在路由查找时的回溯过程中体现出来。对于叶子节点，如果它的掩码满足上述条件而被选入它的某一级父节点的掩码链表的话，那么它的rn_mklist指针就会指向这个掩码链表中对应于它自己的掩码的那个节点。rn_parent:这是节点的父指针，从叶子节点一直向上指到树的顶端节点，而树的顶端节点的父指针是指向它自己的。路由查找时的回溯过程将沿父指针进行。　　rn_bit:对于内部节点