BSD radix树路由表的设计原理.doc

写这篇文章的时候使用的是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_nodes3中，第二个根节点作为路由表的顶部节点，由rnh_treetop指针指向，它将是对路由表的所有操作的开始处。此外，第一个根节点被初始化为顶部节点的左孩子，第三个根节点被初始化为顶部节点的右孩子，而这三个初始根节点的父指针都指向了中间的那个顶部节点。这实际上已经搭起了一个radix树的基本框架。如图2所示。在图2中，我们将中间的作为路由树顶的根节点用圆圈表示，因为它属于内部节点。而另外的两个根节点我们用方框表示，它们属于叶子节点。在本文档中将始终按照这一约定来图示内部节点和叶子节点。2 BSD路由表的节点BSD路由表的radix树实际上就是由一系列的内部节点和叶子节点组成的。内部节点位于树的中间位置，每个内部节点都会指定一个bit测试位置，即当从树的顶端开始向下查找，遇到这个内部节点时需要判断是0还是1的bit位置，接下来的查找将根据bit测试的结果来决定是向左走还是向右走。叶子节点位于树的边缘，用于存储路由表键值，即IP地址。2.1 内部节点前已述及，内部节点在radix树中用于表示一个bit测试位置。内部节点和叶子节点使用的都是radix_node结构体，只是少数字段的定义有所不同。我们首先通过内部节点来查看一下radix_node结构体中的各个字段。在radix树中的3个根节点中，位于中间的那个顶端节点就是内部节点，因此我们的描述就以图3为例。rn_mklist:这个指针指向的是一个radix_mask结构体链表。对于内部节点来说这个链表上的掩码都取自它的子树中的叶子节点所对应的掩码，但只有那些在做逻辑AND运算时能够把这个内部节点的测试bit变成0的掩码才能够加入到这个链表中，这类掩码的作用将在路由查找时的回溯过程中体现出来。对于叶子节点，如果它的掩码满足上述条件而被选入它的某一级父节点的掩码链表的话，那么它的rn_mklist指针就会指向这个掩码链表中对应于它自己的掩码的那个节点。rn_parent:这是节点的父指针，从叶子节点一直向上指到树的顶端节点，而树的顶端节点的父指针是指向它自己的。路由查找时的回溯过程将沿父指针进行。rn_bit:对于内部节点，这个值大于等于0，用于指示在这个内部节点处需要进行测试的bit位置。这个位置是从用于存储IP地址的socket地址结构体的起始位置开始计算的。对于叶子节点，这个值是一个负数，具体数值就是-1减去这个叶子节点所对应的掩码的索引值。而所谓掩码的索引值就是指这个掩码中第一次出现0的bit位置，这个位置也是从socket地址结构体的起始位置开始计算的。rn_bmask:这是一个1字节的掩码，其中只有一个bit为1。在实际的路由查找中，为了加快查找速度，就是使用这个字段直接对指定的字节进行bit测试，而不是指定bit进行测试。对于叶子节点，这个字段为0。rn_flags:这个字段的可能取值一共有3个，RNF_NORMAL，表示这是一个含有常规路由的叶子节点；RNF_ROOT，表示这是一个位于radix_node_head结构体中的节点，即路由表中的三个根节点；RNF_ACTIVE，表示这条路由的状态是好的。rn_Off:这是内部节点独有的字段，表示一个从socket地址结构体的起始位置开始计算的字节偏移量，用于指定在这个内部节点处需用rn_bmask进行单字节比较的字节偏移量。rn_L:这是内部节点独有的字段，指向这个内部节点的左孩子。rn_R:这是内部节点独有的字段，指向这个内部节点的右孩子。2.2 叶子节点叶子节点和内部节点的大部分字段都是一样的，只是最后三个字段的定义不一样。相同字段的定义已在前面的内部节点部分进行了描述，最后三个字段的定义如下。rn_Key:这个字段就内存位置而言相当于内部节点中的rn_Off字段。这个字段用于指向存储着叶子节点键值（即IP地址）的socket地址结构体。rn_Pfxlen: 这个字段就内存位置而言相当于内部节点中的rn_L字段。这个字段用于存储前缀长度。rn_Dupedkey: 这个字段就内存位置而言相当于内部节点中的rn_R字段。当路由表中有重复键情况出现的时候，即有多个叶子节点的键值（IP地址）相同，这些叶子节点是以链表的形式挂接在树中的某个叶子节点下的，rn_Dupedkey即指向重复键链表中的下一个叶子节点。在radix树中，左右两个根节点即属于叶子节点。2.3 根节点radix树中的根节点即是在图2和图3中给出的3个节点。这三个节点都被设置了RNF_ROOT标志，以表示它们是根节点。中间的那个根节点是radix树的顶部节点，所有的路由查找操作都是从它开始的。我们可以看到，这个根节点的bit测试位置是64，也就是说，对于存储在socket地址结构体中的BSD地址而言，实际的BSD地址开始的第一个bit在结构体中的偏移量是64，整个radix树的bit比较算法就是从这第64 bit开始。前已述及，为了加快查找速度，实际的查找操作中使用的是字节偏移和字节掩码。因此，第64 bit对应的字节偏移就是8，而字节掩码就是二进制的1000 0000。另外的两个根节点分列于树的最左端和最右端。我们可以看到，它们的rn_bit字段都小于0，表明这两个根节点属于叶子节点。事实上，它们一个对应的是全0键值，一个对应的是全1键值。在路由查找操作中，任何时刻都不能返回根节点本身。如果查找操作定位到了根节点，将代之以返回空指针。2.4 重复键节点BSD路由表中的重复键节点是指路由树中键值（IP地址）完全相同的叶子节点。这些重复键节点由各自的rn_Dupedkey指针串成一个链表，通过位于链表头部的叶子节点挂在路由树中。位于链表中的重复键节点是按照掩码的精确程度从高到低排列的，即位于链表头部的叶子节点的掩码最精确，对于掩码连续的情况而言也就是它的掩码最长。这样在路由查找的时候如果找到了这串重复键节点，就可以保证掩码最长的路由最先匹配。3 BSD路由表的路由条目如前所述，BSD路由表是由一系列的内部节点和叶子节点组织起来的，这是BSD路由表的逻辑结构。如果从内存布局来讲，BSD路由表中的路由条目则是通过rtentry结构体来存放的，我们前面提到的内部节点和外部节点实际上都是存放在这个结构体中的。rtentry结构体的组成如图4所示。我们可以看到，在rtentry结构体的头部就是由两个radix_node结构体组成的数组rt_nodes2。在这个数组中，第一个元素是叶子节点，负责存储路由表键值，即IP地址，第二个元素是内部节点，负责完成树的连接。因此，就一般情况而言，每当往路由树中添加一条路由的时候，我们实际上添加的是两个节点，一个叶子节点和一个内部节点，只不过这两个节点的存储空间是我们事先用rtentry结构体分配好了的。虽然这两个节点在物理上是紧挨着的，但是由于后续路由条目的加入，它们之间就可能会插入一系列的内部节点，而这些内部节点又分别属于各自的rtentry结构体，并对应着各自的叶子节点。在rtentry结构体的剩余部分中存储的是这条路由的接口、接口地址以及网关路由等关键信息。4 BSD路由表的路由查找前已述及，BSD路由表使用的是经BSD修改之后的Patricia树，也就是BSD radix树。在这种树中，内部节点用于指定需要对查找键进行测试的一系列bit位置，而外部节点则用于存储键值。为了适合路由表的需求，每个叶子节点都会有一个与之对应的掩码。内部节点可能有也可能没有对应的掩码，这取决于在它的子树中是否存在能够将它的测试bit逻辑AND成0的掩码。于是，根据这些特性，BSD路由表中的路由查找就分成了三个步骤，即找到叶子节点进行精确匹配、在重复键链表中进行网络匹配和通过回溯过程进行网络匹配。4.1 第一步：寻叶这一步实际上就是Patricia查找，即从路由表的顶部节点开始，根据所遇内部节点中指示的bit测试位置进行测试，根据该bit是0还是1来决定继续往右走还是往左走，直至到达一个叶子节点为止。当radix_node结构体作为内部节点的时候，它的bit测试位置是由rn_bit字段来给出的。但是，仅仅是这样一个bit测试位置对于有多个字节的IP地址来说显然是不合适的，在查找的时候再去定位这个bit会影响查找效率，所以在添加这个内部节点的时候就会根据bit测试位置计算一个字节偏移量和相应的字节掩码，即rn_Off和rn_bmask字段。字节偏移量用于指定bit测试位置所在字节相对于socket地址结构体起始处的偏移量，而字节掩码则是一个8 bit的掩码，其中只有一个bit为1，在通过字节偏移量定位了字节之后，即可由字节掩码进行bit测试操作。举例而言，BSD路由表的局部如图5所示。图中位于最上方的标记有64的那个内部节点就是radix树的顶端根节点，即在初始化路由表时生成的三个根节点中的中间一个，64这个数字是IPv6地址的第一个bit在socket地址结构体中的偏移量。由于所有的路由查找操作都要从树的顶端开始向下进行，所以不管查找哪条路由，都会从IPv6地址的第一个bit开始进行比较。假设我们现在需要在这个radix树中查找FE80:210:5CFF:FEC2:38E7这条路由。从树的顶端开始，根据沿途内部节点指定的bit进行测试。这条路由的第64 bit为1，向右。第65 bit为1，继续向右。第71 bit为0，向左。第128 bit为0，继续向左。第160 bit为1，向右。这时，将会遇到一个rn_bit字段为负值的节点，即叶子节点，于是查找操作将停止在此处。接下来的操作就是比较找到的这个叶子节点与我们的查找键是否匹配。比较操作是以字节为单位进行的，参与比较的字节数将以叶子节点掩码的最后一个非0字节为限，即若在此范围内叶子节点与查找键相同则认为匹配，查找操作成功结束，否则认为不匹配，并记录下查找键与叶子节点键值第一次出现不同的字节位置。在返回查找结果时有一点需要注意，即在任何时候都不能返回根节点自身，如果在这一步找到的叶子节点是一个根节点，那么就必须返回它的重复键指针rn_dupedkey，而不是它自己。第一步的查找路径在图5中用红色曲线进行了标识。4.2 第二步：辨重如果在第一步中找到的叶子节点与查找键不满足匹配的条件，则需要遍历这个叶子节点的重复键链表。由于重复键链表中的叶子节点与第一步中找到的叶子节点的键值（也就是IP地址）是完全相同的，只是掩码呈逐渐缩短的趋势，因此可能在重复键链表中存在网络匹配的可能。重复键处理的过程如图6所示。图6是在图5的基础上绘制的。对于图中所示的三个重复键节点，我们用绿色的长短表示了它们各自掩码的长短，可以看出，掩码是呈逐渐变短趋势的。由于在第一步中我们已经确定了查找键和叶子节点键值第一次出现不同的字节位置，因此可以方便地换算出查找键和叶子节点键值第一次出现不同的bit位置。前已述及，在叶子节点的radix_node结构体中，rn_bit字段就是由叶子节点的掩码中第一次出现0的bit位置换算出来的。因此，在接下来的重复键处理中，我们只需要把查找键和叶子键值第一次出现不同的bit位置跟叶子节点的rn_bit字段进行比较就可以方便地确定某个重复键节点是否满足网络匹配的条件，而不需要进行实际的掩码操作。如果在重复键链表中有某个叶子节点满足网络匹配条件，则向调用者返回这个叶子节点。否则查找操作将回到最初找到的那个叶子节点（也就是重复键链表上的第一个节点），准备开始向树顶回溯了。第二步的查找路径在图6中依然用红色曲线进行标识，实际上是将图5中的红色曲线延伸至重复键链表中。4.3 第三步：回溯到目前为止，我们只是使用作为查找键的IP地址在radix树中根据内部节点指示的bit测试位置找到了某个叶子节点，并进行了重复键处理，仍然没有找到匹配的叶子节点。这并不能排除在radix树中还存在有其它可能满足网络匹配条件的叶子节点，因此就需要沿着来时的内部节点路径向树顶回溯，寻求网络匹配的可能。回溯过程如图7所示。回溯过程在图7中用蓝色曲线标识，方向从下到上。我们可以看出，回溯过程是从第一步中找到的那个叶子节点处开始，沿着每个节点的父指针rn_parent向树顶前进，这实际上就是我们在第一步中从树顶找到叶子节点所经由的路径，因此才把这一步称为回溯。回溯途中经过的是一系列的内部节点，对于每一个内部节点，将会判断它是否挂的有掩码链表，即它的rn_mklist字段是否为空。掩码链表在图7中用粉红色表示。没有掩码链表的内部节点将不予考虑，直接通过。如果某个内部节点挂的有掩码链表，那说明在它的子树中可能存在着网络匹配的可能，需要停下来做一下判断再决定是否继续回溯。这里首先就遇到了一个问题，究竟什么样的内部节点才挂有掩码链表？这实际上就是要回答回溯的必要性和可行性，这和