BSD radix树路由表的设计原理——查找、添加、删…

在第一部分介绍完BSD radix树路由表的表头、节点、条目等数据结构之后，本部分将集中介绍BSD radix树路由表的查找、添加和删除算法。
目录：4 BSD路由表的路由查找：寻叶、辨重、回溯；  5 BSD路由表的路由添加：寻叶求异、存异求同、普适提升；  6 BSD路由表的路由删除：独有一叶、父子同源无后继、父子同源有后继、父子异源无后继、父子异源有后继。

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测试操作。


图5 路由查找的第一步：寻叶
举例而言，BSD路由表的局部如图5所示。图中位于最上方的标记有64的那个内部节点就是radix树的顶端根节点，即在初始化路由表时生成的三个根节点中的中间一个，64这个数字是IPv6地址的第一个bit在socket地址结构体中的偏移量。由于所有的路由查找操作都要从树的顶端开始向下进行，所以不管查找哪条路由，都会从IPv6地址的第一个bit开始进行比较。

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有