免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 9553 | 回复: 12

BSD radix树路由表的设计原理 [复制链接]

论坛徽章:
0
发表于 2006-02-11 07:35 |显示全部楼层
原来在这里没有专门讨论BSD内核和程序开发的版块,所以有些东西就先写在blog里了。BSD程序开发版开张之后,这些东西就该逐步搬家了! 我一直相信,最好的学习应该是开放式的,让大家一起来考虑一个问题会比一个人冥思苦想的效率要高得多。事实上,下面这篇最先发表在我的blog里的关于BSD radix树路由表的文章就曾经得到过多位朋友的指正,非常感谢他们!以下是原文,继续期待各位朋友的指正!

本文pdf版本:
BSD radix 树路由表的设计原理 - 雨丝风片.pdf (1.17 MB, 下载次数: 1455)

论坛徽章:
0
发表于 2006-02-11 07:53 |显示全部楼层
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。



图8 路由添加的第一步:寻叶求异——寻叶


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



图9 路由添加的第一步:寻叶求异——求异


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 路由添加的第二步:存异求同——求同


回溯过程是从前面找到的那个叶子节点处开始的,在图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所示。



图11路由添加的第二步:存异求同——插入


5.3 第三步:普适提升

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

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



图12 路由添加的第三步:普适提升——普适


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



图13 路由添加的第三步:普适提升——提升


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

结合我们在前面举的例子,在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 路由删除——rtentry结构体的逻辑分离


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

6.1 独有一叶

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



图15 路由删除——独有一叶


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

6.2 父子同源无后继

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



图16 路由删除——父子同源无后继


6.3 父子同源有后继

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



图17 路由删除——父子同源有后继


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

6.4 父子异源无后继

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



图18 路由删除——父子异源无后继


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

6.5 父子异源有后继

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




图19 路由删除——父子异源有后继


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

[ 本帖最后由 雨丝风片 于 2006-2-11 09:24 编辑 ]

论坛徽章:
1
寅虎
日期:2013-09-29 23:15:15
发表于 2006-02-11 08:53 |显示全部楼层
收藏!
期待ing.

论坛徽章:
0
发表于 2006-02-11 09:03 |显示全部楼层
原帖由 congli 于 2006-2-11 08:53 发表
收藏!
期待ing.


多谢老大捧场!偶以后努力做到两手抓两手都要硬:一手抓原创,一手争取把更多的关于BSD内核和程序开发的文章资料翻译、介绍到这里来,供大家参考、讨论!

论坛徽章:
1
寅虎
日期:2013-09-29 23:15:15
发表于 2006-02-11 09:31 |显示全部楼层
原帖由 雨丝风片 于 2006-2-11 09:03 发表


多谢老大捧场!偶以后努力做到两手抓两手都要硬:一手抓原创,一手争取把更多的关于BSD内核和程序开发的文章资料翻译、介绍到这里来,供大家参考、讨论!

兄弟能否写一些入门的资料,让有程序开发倾向的先入门,队伍才会壮大.
或者说如何引导有程序开发倾向的跨过这个门槛?
讨论的人多了,兄弟的热情誓必高涨!
不知道兄弟对这个有什么看法?

论坛徽章:
0
发表于 2006-02-11 09:39 |显示全部楼层
原帖由 congli 于 2006-2-11 09:31 发表

兄弟能否写一些入门的资料,让有程序开发倾向的先入门,队伍才会壮大.
或者说如何引导有程序开发倾向的跨过这个门槛?
讨论的人多了,兄弟的热情誓必高涨!
不知道兄弟对这个有什么看法?


不瞒版主,这正是我最近几天考虑得最多的问题,当初推动这个版的成立,主要目的就是让更多的人
喜欢并参与BSD内核分析和程序开发的讨论,所以在下必当为此殚精竭虑。

我目前的想法就是写一些BSD内核分析和程序开发方面的概念性文章,把曾经遇到过的困难都分享
出来,让别人不再走我走过的弯路。另外就是推动读书活动,比如《设计与实现》和《系统编程》等
经典书籍,并在适当时机把一些论述BSD内核最新功能的论文介绍过来。

上面想法还不太成熟,关于这个板块的发展,可以搞一个公开讨论,让大家来提提意见!

论坛徽章:
2
丑牛
日期:2013-09-29 09:47:222015七夕节徽章
日期:2015-08-21 11:06:17
发表于 2006-02-11 10:09 |显示全部楼层
原帖由 雨丝风片 于 2006-2-11 09:39 发表


不瞒版主,这正是我最近几天考虑得最多的问题,当初推动这个版的成立,主要目的就是让更多的人
喜欢并参与BSD内核分析和程序开发的讨论,所以在下必当为此殚精竭虑。

我目前的想法就是写一些BSD内核分析和 ...

我比较赞成以某本书为骨架去讨论,这样比较系统些,这也是我在分版的时候一直提倡专门分出一个Books&&Documents的理由,不过现在想想也不一定非要它,可以把那几本经典的书在各个合适的板块内专门置顶一个帖子去讨论,一章一章的来,以前搞过handbook的,可惜没人参加,不了了之了,甚憾

论坛徽章:
0
发表于 2006-02-11 10:13 |显示全部楼层
原帖由 剑心通明 于 2006-2-11 10:09 发表

我比较赞成以某本书为骨架去讨论,这样比较系统些,这也是我在分版的时候一直提倡专门分出一个Books&&Documents的理由,不过现在想想也不一定非要它,可以把那几本经典的书在各个合适的板块内专门置顶一 ...


经验就是在尝试中积累啊!具体的操作形式大家可以再讨论一下,

我也非常赞同读书的方式,这样有利于形成系统的基础知识。

论坛徽章:
1
寅虎
日期:2013-09-29 23:15:15
发表于 2006-02-11 10:16 |显示全部楼层
原帖由 剑心通明 于 2006-2-11 10:09 发表

我比较赞成以某本书为骨架去讨论,这样比较系统些,这也是我在分版的时候一直提倡专门分出一个Books&&Documents的理由,不过现在想想也不一定非要它,可以把那几本经典的书在各个合适的板块内专门置顶一 ...

以书为骨架也不错.
以前讨论handbook只能说是急了点,大家跟不上讨论速度.呵~~

论坛徽章:
1
荣誉版主
日期:2011-11-23 16:44:17
发表于 2006-02-11 10:27 |显示全部楼层
先收藏了.
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP