BSD radix树路由表的设计原理

写这篇文章的时候使用的是FreeBSD5.1的代码，举例用的是IPv6地址。BSDradixDonaldR.Morrison1968树PracticalAlgorithmToRetrieveInformationCodedInAlphanumerc。这是一种基于以二进制表示的键值的查找树，尤其适合于处理非常长的、可变长度的键值Partricia的基本思想是构建一个二叉树，在每个节点中都存储有进行下一次bitbit上的Patriciabitbit测试结果决定查找操作的前进方向BSDPartriciaPartriciaBSD的radixBSD的radixPartricia查找，终结于某个叶子节点节点的重复键链表中寻找网络匹配的可能BSDBSDradix_node_headBSDradixradix就都存放在AF_INET6radix_node_head结构体的内存布局如图1rnh_treetop8还有三个radix_noderadixrn_flags，表示这是radix3根节点组成的数组rnh_treetop指针指向个根节点被初始化为顶部节点的右孩子这实际上已经搭起了一个radix2在图2子节点。BSDBSDradixbit点时需要判断是01的bitbitIP内部节点前已述及，内部节点在radix树中用于表示一个bit测试位置。radix_node通过内部节点来查看一下radix_noderadix33radix_mask结构体链表。对于内部节点来说这个链表上的掩码都取自它的子树中的叶子节点所对应的掩码AND运算时能够把这个内部节点的测试bit0的rn_mklist指针就会指向这个掩码链表中对应于它自己的掩码的那个节点。指向它自己的。路由查找时的回溯过程将沿父指针进行。bitIP地址的socket-10的bitsocket:这是一个1bit为1。在实际的路由查找中，为了加快查bitbit点，这个字段为0。rn_flags:这个字段的可能取值一共有3个，RNF_NORMAL，表示这是一个含有常规路由的叶子节点；RNF_ROOT，表示这是一个位于radix_node_head结构体中的节点，即路由表中的三个根节点；RNF_ACTIVE，表示这条路由的状态是好的。socketrn_bmaskrn_L:这是内部节点独有的字段，指向这个内部节点的左孩子。rn_R:这是内部节点独有的字段，指向这个内部节点的右孩子。叶子节点叶子节点和内部节点的大部分字段都是一样的义已在前面的内部节点部分进行了描述，最后三个字段的定义如下。rn_Off子节点键值（即IP）的socketrn_Pfxlen:这个字段就内存位置而言相当于内部节点中的rn_L字段。这个字段用于存储前缀长度。rn_Dupedkey:rn_R况出现的时候，即有多个叶子节点的键值IP地址）相同，这些叶子节点是以链表的形式挂接在树在radix根节点radix233RNF_ROOT志，以表示它们是根节点。中间的那个根节点是radixbit64，socketBSD际的BSDbit64，整个radixbit64bit此，第64bit1000。另外的两个根节点分列于树的最左端和最右端。我们可以看到，它们rn_bit01在路由查找操作中，任何时刻都不能返回根节点本身。如果查找操作定位到了根节点，将代之以返回空指针。重复键节点BSD路由表中的重复键节点是指路由树中键值IP地址）完全相同的叶子节点。rn_Dupedkey这串重复键节点，就可以保证掩码最长的路由最先匹配。BSDBSDrtentry到的内部节点和外部节点实际上都是存放在这个结构体中的rtentry4我们可以看到，在rtentryradix_nodeIPrtentryrtentry结构体，并对应着各自的叶子节点。在rtentry结构体的剩余部分中存储的是这条路由的接口、接口地址以及网关路由等关键信息。BSDBSDPatriciaBSDradix树。在这种树bitbit逻辑AND成0第一步：寻叶这一步实际上就是Patriciabitbit0还是1止。当radix_node结构体作为内部节点的时候bitrn_bitbitIP位这个bitbitrn_Offrn_bmaskbit对于socket8bitbit1bitBSD564的那个内部节点就是radix树的顶端根节点，即在初始化路由表时生成的三个根节点中的中间一个64这个数字是IPv6地址的第一个bit在socketIPv6bitradix树中查找FE80::210:5CFF:FEC2:38E7这条路由。从树的顶端开bit64bit1，向右。第65bit1，继续向右。第71bit，向左。第128bit0，继续向左。第160bit1到一个rn_bit0第一步的查找路径在图5中用红色曲线进行了标识。第二步：辨重如果在第一步中找到的叶子节点与查找键不满足匹配的条件IP地址）是完全相同665各自掩码的长短，可以看出，掩码是呈逐渐变短趋势的。bitradix_node0的bitbit际的掩码操作。如果在重复键链表中有某个叶子节点满足网络匹配条件了。第二步的查找路径在图65键链表中。第三步：回溯IPradixbitradix树中还存在有其它可能满足网络匹配条件的叶子节点7回溯过程在图7rn_parent即它的rn_mklist7这里首先就遇到了一个问题radix为什么要回溯？在第一步“寻叶”中，我们根据查找键的一系bit.它和我们在第一步中找到的叶子节点有共同部分；.它的掩码短于或等于它和第一步中的叶子节点的共同部分；.它的掩码短于或等于查找键和第一步中的叶子节点的共同部分。为什么可以回溯？如果radix树中存在满足上述条件的叶子节点，那我们通过回溯算法就一定可以找到它，这是由radixbit为nIPbitn-1