ITPub博客

首页 > Linux操作系统 > Linux操作系统 > BSD radix树路由表的设计原理(转)

BSD radix树路由表的设计原理(转)

原创 Linux操作系统 作者:ilg 时间:2019-03-12 21:06:05 0 删除 编辑
BSD radix树路由表的设计原理(转)

  写这篇文章的时候使用的是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所示。

  在图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_nodes[2]。在这个数组中,第一个元素是叶子节点,负责存储路由表键值,即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中用粉红色表示。没有掩码链表的内部节点将不予考虑,直接通过。如果某个内部节点挂的有掩码链表,那说明在它的子树中可能存在着网络匹配的可能,需要停下来做一下判断再决定是否继续回溯。

  这里首先就遇到了一个问题,究竟什么样的内部节点才挂有掩码链表?这实际上就是要回答回溯的必要性和可行性,这和radix树的组织方式即路由添加时的设计方法有关。首先需要明确下面两个问题。

  为什么要回溯?

  在第一步“寻叶”中,我们根据查找键的一系列bit测试结果找到了一个叶子节点,具体找到哪个叶子节点完全取决于radix树当时的组织形态,但有一点是可以确定的,那就是这个叶子节点的键值在其起点之后的某个长度之内一定和我们的查找键是相同的。如果这个长度就是叶子键值的长度,那我们在第一步中就匹配成功了,否则我们就要在树中寻找满足以下三个条件的叶子节点:

  .它和我们在第一步中找到的叶子节点有共同部分;

.它的掩码短于或等于它和第一步中的叶子节点的共同部分;

.它的掩码短于或等于查找键和第一步中的叶子节点的共同部分。

  为什么可以回溯?

  如果radix树中存在满足上述条件的叶子节点,那我们通过回溯算法就一定可以找到它,这是由radix树的路由添加算法决定的。在这里我们只需要明确一个事实,那就是对于一个测试bit为n的内部节点的子树中的所有子孙叶子节点的键值而言,从实际IP地址的开始bit到第n-1 bit都是相同的。举例而言,如果一个内部节点的测试bit是71,那么它的子树中的所有子孙叶子节点的键值的第64到70共 7个bit的内容都是相同的。因此,如果这个内部节点的子树中有某个叶子节点的掩码短于或等于7的话,那它的键值事实上就是这个子树中所有路由的公共部分,而它本身也就成了这个子树中所有路由的普适路由。正是radix树中的这些普适路由组成了回溯查找时的候选路由的集合。

  一个内部节点的掩码链表正是它的子树中所有普适路由的记录链表,而对于一条普适路由来说,则会将其挂在它所能作为普适路由的最大可能的子树的顶端内部节点的掩码链表中。

  对于回溯过程中遇到的每一个掩码链表非空的内部节点,我们都需要遍历它的掩码链表,只要发现一个满足前述三个条件的节点,就表明我们对查找键的网络匹配已经成功,回溯过程结束。

5 BSD路由表的路由添加

  在对路由查找中的回溯过程的描述中我们已经提到一个事实,即对于一个测试bit为n的内部节点的子树中的所有子孙叶子节点的键值而言,从实际IP地址的起始bit到第n-1 bit都是相同的。这个事实就是由路由添加操作来保证的。路由添加操作可以分为寻叶求异、存异求同和普适提升三个阶段。

  5.1 第一步:寻叶求异

  向路由表中添加一条路由的目的就是为了以后来查找它,因此,为了确定新路由在路由表中的位置,首先就要对新键值执行查找操作,也就是我们在路由查找部分中描述的第一步:寻叶。这一步实现的是Patricia查找,即从树顶开始按照内部节点的指示对新键值进行一系列的bit测试,直到遇见一个叶子节点为止。

  假设有如图8所示的一个路由表局部,这和描述路由查找时使用的实际上是一个图,图中叶子节点存储的键值是FE80::8210:0C00:7EC2:3800。现在假设我们要向路由表中添加FE80::8210:0:0:0/76这条路由,先对这个新键值执行Patricia查找,以实际IP地址的起始bit为第64 bit:第64 bit为1,向右;第71 bit为0,向左;第128 bit为1,向右;第144 bit为0,向左;第160 bit为0,继续向左。因此,这个查找将沿着图8中的红色曲线一直找到存放着FE80::8210:0C00:7EC2:3800键值的那个叶子节点。

  找到这个叶子节点之后,就需要判断它的键值和新键值是否相等。如果相等,则表示出现了重复键的情况,将根据新路由的掩码长度将其挂接在该叶子节点的重复键链表中的适当位置。在我们的例子中,叶子节点的键值与新键值并不相等,于是就要记录下它们第一次出现不同的bit位置,这也就是“寻叶”之后的“求异”操作。

  新键值FE80::8210:0:0:0和叶子节点键值FE80::8210:0C00:7EC2:3800的比较结果如图9所示。在这个图中,蓝色部分是用二进制表示的。我们可以看出,在现有radix的所有测试bit上,新键值和叶子节点键值都是相同的,因此才会找到这个叶子节点。但它们的键值实际并不相同,而这两个键值的第一个不同bit就是第148 bit。

  确定了新键值和前面找到的那个叶子节点键值的第一个不同bit,实际上也就是确定了这两个键值的共同部分。这些信息将决定新路由在radix树中的位置,具体操作则可以归纳为路由添加的第二步:存异求同。

  5.2 第二步:存异求同

  首先,让我们结合例子再来回顾一下前面提到的那个事实:对于一个测试bit为n的内部节点的子树中的所有子孙叶子节点的键值而言,从实际IP地址的起始bit到第n-1 bit都是相同的,参见图10,图中用不同颜色的圆环来抽象表示各个内部节点的子树。测试bit为64的那个内部节点是树的顶点,属于特例,它的子树(也就是整个radix树)中的IP地址是没有公共部分可言的。测试bit为71的那个内部节点的子树中的节点的第64到第70 bit都是相同的,以此类推。这是从添加第一条路由开始就必须遵从的规则,显然,此时对新路由的添加也必须遵从于这一规则。

  我们在第一步中已经计算出Patricia找到的叶子节点键值和新键值第一次出现不同的bit位置,即我们例子中的第148 bit。为了不违反上述事实,新键值就不能属于测试bit在第148 bit右边的内部节点的子树,而只能属于测试bit在第148 bit左边的内部节点的子树。因此,我们接下来的工作就是确定新键值究竟应该属于哪个内部节点的子树,而实现方法就是沿着来时的路径向树顶回溯,找到正好把第148 bit卡在中间的两个内部节点。注意,在这个回溯过程中是不可能有哪个内部节点的测试bit正好等于第148 bit的,因为如果那样的话,在第一步的Patricia查找中就不会走到存放着FE80::8210:0C00:7EC2:3800键值的那个叶子节点那儿了。

  回溯过程是从前面找到的那个叶子节点处开始的,在图10中用蓝色曲线表示。首先遇到的是测试bit为160的内部节点,它的子树中从第64到159 bit都是相同的。由于新路由和叶子节点键值的第一个不同bit是第148 bit,属于第64到159 bit的范围,因此新路由不能属于它的子树,否则就会违反前述规则。继续向树顶回溯,这次遇到的是测试bit为144的内部节点,它的子树中从第64到143 bit都是相同的,因此新路由至少要属于这个内部节点的子树才能遵从前述规则。

  就我们的例子来说,此时已经可以确定新路由应该插入在测试bit为144和160的两个内部节点之间,这是因为对新路由的第64、71、128和144 bit进行测试的结果都和前述叶子节点相同,我们必须保证路由查找操作在第144 bit之后、第160 bit之前对第148 bit进行测试,这样才能找到我们新加的这条路由。我们在前面提到过,每当往radix树中新加一条路由时,实际上都需要插入两个节点,即一个内部节点和一个叶子节点,或者说,路由条目的添加是以rtentry结构体为单位的,新加的两个节点正是这个结构体中的两个radix_node[2]结构体数组。

  我们先来看看新路由的内部节点。它的测试bit显然就是第148 bit,而它就将替代测试bit为第160 bit的内部节点作为测试bit 为144 bit的那个内部节点的新的左孩子,而测试bit为第160 bit的那个内部节点则将成为它的某个孩子。

  我们再来看看新路由的叶子节点,它存储着FE80::8210:0:0:0这个键值,而它此时显然也是新路由的内部节点的某个孩子。为了确定新叶子和测试bit为第160 bit的那个内部节点的左右名分,我们只需要判断新键值在新路由的内部节点的测试bit上是0还是1。对于我们的例子,新键值在第148 bit上为0,因此新叶子将作为新内部节点的左孩子,而测试bit为第160 bit的内部节点则作为右孩子。我们之所以可以在这里直接根据新键值就做出左右划分,是因为我们已经确定测试bit为第160 bit的内部节点的子树中所有叶子的第148 bit都是相同的,而新键值和这些叶子的第148 bit都是不同的。插入新路由之后的radix树如图11所示。

  5.3 第三步:普适提升

  在经过寻叶求异和按异求同两个步骤之后,路由添加的操作只能说是完成了一半。之所以这么说,是因为前面的操作对于只有键值没有掩码的Patricia树来说是够了,但对于作为路由表的radix树来说则还不行,因为路由查找操作是以最长匹配为原则的,在键值匹配失败的情况下我们还要去尝试网络匹配的可能,这也就是我们在路由查找部分描述的寻叶、辨重和回溯三个步骤。所以,在把新路由插入radix树之后,我们还要继续处理它的掩码,处理的结果可能会影响到新路由的某个父节点的掩码链表,关于掩码链表的使用可以参见路由查找部分的回溯步骤。

  我们知道,所谓路由的最长匹配查找,就是用某个路由条目的掩码和查找键进行逻辑与,然后再把逻辑与的结果和路由条目的键值进行比较,如果相同,则说明满足网络匹配条件,而查找操作最后返回的就是满足上述条件的掩码最长的那条路由。现在,我们假设A是radix树中的最外层内部节点之一,它有B和C两个作为叶子节点的孩子,如图12所示。

  在图12中用红色曲线给出了路由查找的第一步“寻叶”,这一步是只用查找键进行而与掩码无关的。我们假设叶子节点C的键值和查找键匹配失败,在重复键处理过程中也没有匹配成功,这时我们就需要继续寻找网络匹配的可能。前面已经提到,所谓网络匹配就是叶子节点和查找键的带掩码的比较,这实际上可以理解为用查找键和叶子掩码进行逻辑与之后的结果在树中再次进行查找,对于一个满足网络匹配条件的叶子节点来说,这样的查找必然就会找到它那儿。让我们再来看图12,要让这样的查找能够找到叶子节点B的条件之一就是B的掩码能够改变查找键在内部节点A处的行进方向,也就是说,B的掩码要能够把内部节点A的测试bit逻辑与成0,图中蓝色曲线表示的就是这种带掩码的查找过程。满足上述条件的路由B就称为节点A的子树中的普适路由。

  显然,一条路由的掩码越短,它就越可能作为更大一些的子树中的普适路由。而所谓普适提升就是在每次新加入一条路由的时候,我们都需要确定它究竟最大能作为哪一层子树中的普适路由,确定子树之后,这条新路由的掩码就会记录在作为该子树的顶点的内部节点的掩码链表中。

  结合我们在前面举的例子,在radix树中加入FE80::8210:0:0:0/76这条路由之后,我们就需要对其进行普适提升操作。这条路由的掩码是76 bit,也就是说,它的掩码中的第一个0 bit将出现在第140 bit,参见图9。普适提升的过程如图13所示。我们从新路由开始向树顶回溯,第一个遇到的是测试bit为第148 bit的内部节点,显然,新路由的掩码可以把它的测试bit与成0,因此,新路由可以作为它的子树中的普适路由。继续回溯,遇到的是测试bit为第144 bit的内部节点,同样,新路由也可以作为它的子树中的普适路由。下一个遇到的是测试bit为第128 bit的内部节点,这一次新路由的掩码就不能把这个内部节点的测试bit与成0了,因此,新路由最大只能作为测试bit为第144 bit的内部节点的子树中的普适路由,新路由的掩码将记录在它的掩码链表中。这条普适提升的行进路径在图13中用蓝色曲线表示,而内部节点的掩码链表在图中用粉色表示。

  一个内部节点的掩码链表中将记录它的子树中的所有满足普适条件的掩码。链表上的节点是按照掩码从长到短的顺序排列的,每个链表节点都有一个指针指向它们各自对应的叶子节点,而叶子节点也有一个指针指向这个掩码链表节点。

  在路由查找的回溯过程中,每当我们遇到掩码链表非空的内部节点的时候,就会遍历它的掩码链表,直接判断每个链表节点的掩码是否满足我们在描述路由查找的回溯步骤时列出的三个条件,一旦满足,我们就可以通过指针直接找到对应的叶子节点,而这样找到的第一个叶子节点就是我们要查找的最长匹配路由。

6 BSD路由表的路由删除

  BSD路由表中的路由删除操作涉及的内容是和路由添加相对应的。在描述路由删除步骤之前,我们需要明确一个事实,在前面已经见过,路由条目的内存管理是以rtentry结构体为单位的,但radix树的操作却看不到这个结构体的存在,它只看得到一系列的内部节点和叶子节点。因此,同一个rtentry结构体内的两个radix_node结构体在该路由刚加入radix树的时候是直接相连的,但随着之后的操作,这两个radix_node结构体可能就相隔很远了。如图14所示。

  在图14中,左边的图用绿色表示刚加入radix树中的一对radix_node结构体,其中,内部节点的测试bit为第148 bit。右边的图表示在这之后又加入了一对radix_node结构体,用粉色表示,其中,内部节点的测试bit为第150 bit。我们可以看到,由于新路由的加入,属于同一个rtentry结构体的两个绿色的节点在逻辑上被分开了。在删除路由的时候,我们就必须对这种情况进行处理,把rtentry结构体作为一个整体从radix树中摘除,具体做法因被删除节点的位置的不同而不同。

  6.1 独有一叶

  一般情况下,一个rtentry结构体内的两个radix_node结构体将同时出现在radix树中,但有一个例外,那就是出现了重复键的情况。参见路由查找以及路由添加部分的描述,在添加路由的时候,如果遇到了重复键的情况,我们就会把新路由直接挂到重复键链表中的适当位置。注意,重复键链表中都是叶子节点,它们是作为一个链表挂在同一个内部节点下的。因此,作为重复键加入的路由条目中的内部节点部分是闲置不用的。

  非重复键链表头节点的删除过程如图15所示。在图中我们用绿色表示准备删除的路由条目对应的叶子节点,而用虚线在这个叶子节点的旁边画了一个内部节点,表示它虽然在物理上存在着,但却没有使用,不是radix树的一部分。对于这种情况,我们只需要直接将指定路由叶子节点从树中摘除,并将rtentry结构体释放即可。

  6.2 父子同源无后继

  除了前一节中描述的“独有一叶”的情况之外,其余的路由删除就需要牵扯到内部节点的处理了。所谓“父子同源无后继”指的是被删除的叶子节点是重复键链表上的唯一节点,而且它和作为父节点的内部节点同属于一个rtentry结构体,此时也只需要直接把这两个节点从radix树中摘除即可,如图16所示,图中用绿色表示一对属于同一个rtentry结构体的叶子节点和内部节点。

  6.3 父子同源有后继

  所谓“父子同源有后继”指的是被删除的叶子节点位于重复键链表头部,在它之后还有其它的重复键节点。对于这种情况,我们就不能把内部节点一删了事,而需要用替补上来的那个重复键节点对应的闲置内部节点空间去把被删除的叶子节点对应的内部节点替换下来。如图17所示,图中分别用绿色和粉色表示两对属于同一个rtentry结构体的叶子节点和内部节点,其中,绿色表示将要删除的路由对应的两个节点。

  我们可以看到,在图17中,除了用粉色的叶子节点替换掉绿色的叶子节点作为重复键链表上的第一个节点之外,还要用原来闲置的粉色内部节点空间去把绿色的内部节点从radix树中替换下来,以便将绿色的节点对应的rtentry结构体空间作为一个整体释放。注意,这里对内部节点的替换是完全拷贝,因此粉色内部节点将完全替代绿色内部节点在radix树组织结构中的作用。

  6.4 父子异源无后继

  所谓“父子异源无后继”是指被删除的叶子节点是重复键链表中的唯一节点,且它和它的父节点不属于同一个rtentry结构体,也就是说,和它同属一个rtentry结构体的内部节点空间肯定在radix树中其它的某个地方。在图18中,我们分别用绿色和粉色表示两对属于同一个rtentry结构体的叶子节点和内部节点,其中,绿色表示将要删除的路由条目对应的两个节点。

  这里的删除过程是这样的:首先是把绿色的叶子节点和粉色的内部节点从radix树中摘除,使粉色的叶子节点作为绿色内部节点的左孩子,然后再用粉色内部节点的空间去把绿色内部节点从radix树中替换下来。

  6.5 父子异源有后继

  所谓“父子异源有后继”是指被删除路由的叶子节点后面还有重复键节点,而它的父节点和它不属于同一个rtentry结构体。在图19中,我们分别用绿色和粉色表示两对属于同一个rtentry结构体的叶子节点和内部节点,其中,绿色表示将要删除的路由对应的两个节点,而粉色则表示将要替补上来的重复键叶子节点及其闲置内部节点。

  具体删除过程是这样的:首先是把绿色的叶子节点从radix树中摘除,将粉色的叶子节点替补成测试bit为第150 bit的内部节点的左孩子,然后再用本来闲置的粉色内部节点空间将绿色内部节点从radix树中替换下来。

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/14102/viewspace-116613/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2002-06-18

  • 博文量
    1715
  • 访问量
    1300189