路由查找算法大作业[技巧]

路由查找算法大作业[技巧] 路由查找算法研究与仿真 xxxxxxxxx 摘要—随着Internet的迅猛发展，互联网的传输率已达到传统路由查找算法A. 10Gbps级别，路由器的路由表项也急剧膨胀，因此快速的路由 1) 线性查找 查找算法是实现高速分组转发的关键。本文介绍了几种经典的 线性表结构是最简单的查找数据结构，因此可以把所路由查找算法，并对基于binary-trie、multibit-trie的路由查找 由地址前缀用线性链表的方式组织起来。有的路每一次查算法进行仿真。此外，本文提出通过缓存暂时存放已匹配的前 缀的方法，避免了回溯操作，相对于完全Trie的算法，大大减找需要遍历线性表中的所有表项，在遍历过程中记录最长少了内存的使用， 相对于leaf pushing算法，由于没有改变二叉的路由前缀项，直到遍历完整个线性链表为止。对于 N 个树结构，所以不存在更新复杂的问题，并且也达到避免回溯的路由前缀表项，查找过程的算法复杂度为 O(N)，存储空效果。 间复杂度为O(N)，插入删除路由表项的算法复杂度为 O(1)(假设表项插入和删除均在线性表的末尾进行)。 关键词—路由查找算法;binary-trie、multibit-trie仿真;已 匹配前缀缓存 2) 缓存策略 在路由查找中可以使用缓存策略，把最近查找过的目 的地址路由存放在高速的路由缓存表(route cache)中。只有 当在路由缓存表中查找失败的时候，我们才需要进行真正I. 引言 完整的前缀查找匹配过程。为了能够在查找性能上获得较 大的提高，缓存的命中率就需要有一定的保证。随着 随着 Internet 的迅猛发展，用于主干网络互联的核心路Internet 的不断发展、网络用户的不断增加以及业务数据 这一速率要由器的接口速率已经达到了 2.5Gbps~10Gbps。量的多样化，数据的时间局部性变得越来越不明显，从而求核心路由器每秒能够转发几百万乃至上千万个以上的分大大地降低了缓存的命中率。 组。 3) 二进制Trie(binary trie) 分组转发的重要一步就是查找路由表，因此快速的路用二进制 Trie 结构来表示地址前缀是一个常用的方法 是实现高速分组转发的关键。IP报文从源到目由查找算法(图1)。Trie 采用一种基于树的数据结构，通过前缀中每一的被路由器转发的过程中，路由查找算法根据报文所要到位比特的值来决定树的分支。用二进制 Trie 结构(树中每达的目标地址，在转发表中查找对应路由并按该表所标识一个内部结点最多包含两个子结点)来表示的地址前缀的路径转发。目前由于CIDR(无类别域间寻址)的运表。在 Trie 树中，处于第 L 层的结点代表了一类地址前 L 用，在此过程中一个报文可能会找到多个匹 配的路由，个比特均相同的地址空间，并且这前 L 个比特串就是由从而路由查找算法将选出最长匹配前缀所对应的路径作为最根结点到这个结点路径上的 L 个比特组成。 佳路径。IP路由查找问题本身很简单，但由于其对性能要 求很高，因此有相当的难度。通常评价路由查表算法的标 准主要有高速查找、内存需求小、更新时间短、实现的灵 活性强、能够处理真实的大容量路由表以及预处理时间短 等。 最长地址前缀匹配算法的难点在于，在查找过程中不 仅需要和地址前缀匹配的比特进行匹配查找，而且需要考 虑地址前缀的长度。 近年来,研究人员提出了多种路由查找算法，以提高查 找性能。 II. 路由查找算法 图 1 bianry trie 的前缀。在根据独立前缀集构造的 Trie 树中，所有对应于4) Triepath compression路径压缩() 前缀的结点都出现在叶子结点。 通过删除单分支的非前缀节点降低binary trie的高度。(3) 压缩技术:压缩技术试图从编码中删除数据的冗余由于删除的单分支结点可能包含多个地址前缀信息，所以信息，对 Trie树使用压缩技术主要是考虑到 Trie树的扩展路径压缩 Trie 树结点中可能包含多个地址前缀。Trie 树搜转化过程大大增加了信息的冗余度，因此可以使用一定的索过程由于某些结点被删除，所以可忽略目的地址中某些压缩算法将信息的冗余度降低。当然，压缩方法应该不仅比特位的匹配操作，因此结点处需要维护一个变量指示下能缩小整个 Trie 树的存储空间，而且还应保证从压缩数据一个需要检查的比特位。另外，与二进制 Trie 树相比，路中恢复原有信息的操作不能过于复杂。 径压缩 Trie 树前缀结点处需要保存地址前缀的比特串。查 找过程与二进制 Trie 树类似，但是在结点选取分支时考虑(4) 优化技术:前缀转发方法是多种多样的，优化方法的是比特位变量所指示的比特位。当查找过程遇到前缀结能够使我们在一些限制条件的前提下找到满足约束条件的点时，需要进行前缀匹配操作。 最佳前缀集，比如说在查找速度的约束下尽量减少算法的 存储空间等。 (5)存储层次设计:目前我们所使用的计算机的整个存 储系统具有明显的层次结构，各个层次上的存储介质在速 度和容量上存在着差异。如果我们能够把尽可能多的查找 表放入 Cache 中，就可以获得更高的查找速度，因此 在算法设计中应尽量减少查找算法数据结构所占据的存储 容量。 2) 多分支Trie(multibit trie) 一种提高 Trie 树查找效率的方法就是在查找的每一步 检查地址中的多个比特，而不仅仅是一个。例如，如果我 们每次查找检查地址的 4 个比特，那么 IPv4 地址查找最 多只需 8 次存储器访问操作就可以了。我们把每一次查找 所需检查的比特数称为查找步宽(stride)。查找步宽可以是 固定的，也可以是可变的。 二分支 Trie 树实际上就是查找步宽为 1 的 Trie 树。我 们把查找步宽大于 1 的 Trie 树称为多分支 Trie 树(multibit Trie)。对于查找步宽为 k的多分支 Trie 树来说，每一个结图 2 图1路径压缩结果 点的最大分支数为2^k。在多分支 Trie 树中，同一层中不 同子树的步宽可以是一样的，也可以是不一样的。B. 路由查找新算法 近几年来，随着对路由器研究的逐步深入以及对路由一般来说，固定步宽的多分支 Trie 树实现简单，但会器性能要求的不断提高，研究人员提出了很多较为新颖的浪费较多的存储空间;而可变步宽的多分支 Trie 树在实现地址前缀查找算法。与二进制 Trie 树、缓存目的地址法等上复杂一些，但可以节省一定的存储空间。多分支 Trie 树传统的地址前缀查找方法相比，这些算法在性能方面有了查找过程的每一步需要检查多个比特，因此它不能支持任很大的提高。 意长度的地址前缀。为了能够用多分支 Trie 树来进行前缀 查找，前缀表中的地址前缀需要转换成多分支 Trie 树查找1) 查找算法使用的辅助策略 所允许的地址前缀才行，转化方法所采用的就是上一节介(1) 前缀扩展(prefix expansion):地址前缀是一系列主机绍的地址前缀扩展方法。 地址或者网络地址的合并。因此，地址前缀的转发信息涵 盖了所有这些主机或者网络的转发信息，所以我们可以将多分支 Trie 树的查找过程与二分支 Trie 树的查找过程一条长度较短的地址前缀展开成多条地址长度较长的前缀类似，是在每次结点访问过程中把到目前为止已经匹配上集，其中这些前缀集的转发信息就是原来地址前缀所对应的最长地址前缀记录下来，直至到达叶子节点，搜索过程的转发信息。这种前缀转化方式称为前缀扩展。例如，前结束。尽管多分支 Trie 树的查找也是基于地址前缀长度的缀 1*所覆盖的地址范围既可以用前缀 10*以及前缀 11*来线性遍历法，但是因为多分支 Trie 树采用的步宽大于 1，涵盖,也可以用前缀 100*，101*，110*以及111*来涵盖。所以其搜索效率大大提高了。 (2) 独立前缀转化(disjoint prefix transformation):最长前3) 地址前缀长度的二分查找法 缀匹配查找就是为了能够在多个匹配的地址前缀中寻找长为了减少查找的时间，提出了在地址前缀长度空间内 进行二分查找的算法。如果能够在前缀长度空间内实现二度最长的前缀。一种避免进行最长前缀匹配规则但仍然能 够找到最精确转发信息的方法是将地址前缀集转化为一些分查找，那么整个查找性能就可以从 O(W)提高到 O(logW)。但是，我们不能简单地将二分查找法直接应用完全独立的前缀集.在独立的前缀集中，各个前缀之间不存 在相互包含关系，因此不可能出现某个前缀是另一个前缀到前缀长度空间内。例如，假设有 3 个地址前缀 0*，00* 和 111*。假设现在需要查找 111，二分查找法首先从前缀point[2]; %左右子节点指针 长度为 2 的 Hash 表开始查找关键字 11，因为 Hash 表中只flag; %是否为前缀节点标记 有表项 00，所以查找失败，而实际上在长度为 3 的 Hash 表中具有匹配关键字。为了解决这个问题，我们在前缀长} 度为 2 的 Hash 表中添加一个表项 11，这种表项被称为 multibit_trie{ marker。现在查找关键字 111，首先在前缀长度为 2 的 port[8]; %下一条输出端口 Hash 表中查找就会查找成功，然后二分查找法将会在前缀 长度空间的下半部分继续查找。 point[8]; %8个子节点指针 flag[8]; %是否为前缀节点标记 III. 算法仿真 } 本章使用Matlab对基于binary-trie和multibit-trie的路由于Matlab的不支持指针操作，所以无法类似C语言由查找算法进行仿真。程序包含以下几个函数:那样通过指针建立链表，我这里通过建立相关的结构体数 组，所有节点存储在该结构体数组中，每个父节点的子节1)路由表生成函数:route_table_gen(); 点指针设置为子节点在结构体数组的标号。binary_trie和2)Trie生成函数:trie_gen(); multibit_trie数组为全局变量，供路由查找使用。 3)路由查找函数:route_search(); 路由查找函数: 4)主函数:main(); [route_port_binary,binary_depth, route_port_multibit,multibit_depth] = route_search(addr);该route_table_gen()生成如下转发表: 函数有一个输入为需要匹配的地址，有四个输出分别是基 于binary_trie和multibit_trie查找的端口结果和相应的查找表格 1 转发表 深度。 下一条输序号 前缀 出端口 在基于trie的路由查找算法中，如果不使用完全树或者 1 1* 1 leaf pushing，则可能存在需要回溯父节点的情况，在本程 序中，通过直接用缓存记录查找路径上最后经过的前缀节2 00* 2 点即可避免回溯操作。 3 101* 3 主函数mian()，输入四个需要匹配的地址: 4 111* 4 表格 2 匹配地址 序号 地址 5 1000* 5 1 1,1,1,0,0,1,1,1 6 11101* 6 2 0,0,1,1,0,1,0,0 3 0,1,1,1,0,0,1,0 7 111001* 7 4 1,1,1,0,1,0,0,0 8 * 0 对于每个地址主函数记录这四个参数: 1)port1，binary_trie查找的端口结果; 路由表的结构体: 2)port2，multibit_trie查找的端口结果; route_table{ 3)depth1，binary_trie的查找深度; 4)depth2，multibit_trie的查找深度。 addr; %前缀地址 masklength; %子网掩码长度 程序运行结果: port %下一条输出端口 四个地址的下一跳端口如下图: } trie_gen()函数根据如上的路由表分别生成binary_trie和 multibit_trie(stride=3)。 结构体如下: binary_trie{ port; %下一条输出端口 查找复杂度也有所增加。由于查找的时间和代码的优化程 度、实现的硬件结构有很大关系，所以本文并没有对每次 的查找时间进行统计。但是从分析上是可以知道，multibit trie的查找时间并不一定比binary trie少。 此外，如果在路由表稀疏的场景下，multibit trie会占 用大量的存储资源，因此，在bianry trie为接近完全树的 情况下使用multibit trie效率最高。 IV. 总结 图 3 端口结果 本文分析了路由查找问题的主要特点和基本的解决方 案，在此基础上全面总结了近年来研究人员提出的多种快两种算法查找的结果都是一样的，并且对比转发表，可速路由查找算法。 以知道查找结构是正确的。 两种算法的查找深度如下图: 此外，本文对基于binary trie和multibit trie的路由算法 进行仿真，并比较了仿真结果，仿真结果显示，multibit trie算法具有更少的查找深度 参考文献 [1] Huang, Nen-fu, Zhao, Shi-ming. A novel IP-routing lookup scheme and hardware architecture for multigigabit switching router.IEEE Journal on Selected Areas in Communications, 1999 [2] Srinivasan, V., Varghese, G. Fast IP lookups using controlled prefix expansion. ACM Transactions on Computer Systems, 1999 [3] Tzeng, Henry Hong-Yi., Przygienda, T. On fast address-lookup algorithms. IEEE Journal on Selected Areas in Communications,1999 图 4 查找深度 [4] 徐恪， 徐明伟， 吴建平， 吴剑，“路由查找算法研究综述”，软对比可以发现multibit_trie算法可以有效的减少查找深件学报，1999 度。 虽然说从直观上来讲，更小的查找深度可以减少查找 时间。但是，实际中的查找时间和每一层查找的复杂度也 有关系，multibit trie虽然降低了查找深度，但是每一层的