路由查找算法大作业.doc

路由查找算法研究与仿真 x xxxxxxxx 摘要—随着 的迅猛发展,互联网的传输率已达到 10Gbps 级别,路由器的路由表项也急剧膨胀,因此快速的路由查找算法是实现高速分组转发的关键。本文介绍了几种经典的路由查找算法,并对基于 binary-trie 、 multibit-trie 的路由查找算法进行仿真。此外,本文提出通过缓存暂时存放已匹配的前缀的方法,避免了回溯操作,相对于完全 Trie 的算法,大大减少了内存的使用, 相对于 leaf pushing 算法,由于没有改变二叉树结构,所以不存在更新复杂的问题,并且也达到避免回溯的效果。关键词—路由查找算法; binary-trie 、 multibit-trie 仿真;已匹配前缀缓存 I. 引言随着 的迅猛发展,用于主干网络互联的核心路由器的接口速率已经达到了 ~10Gbps 。这一速率要求核心路由器每秒能够转发几百万乃至上千万个以上的分组。分组转发的重要一步就是查找路由表,因此快速的路由查找算法是实现高速分组转发的关键。 IP 报文从源到目的被路由器转发的过程中,路由查找算法根据报文所要到达的目标地址,在转发表中查找对应路由并按该表所标识的路径转发。目前由于 CIDR (无类别域间寻址)的运用,在此过程中一个报文可能会找到多个匹配的路由, 而路由查找算法将选出最长匹配前缀所对应的路径作为最佳路径。 IP 路由查找问题本身很简单,但由于其对性能要求很高,因此有相当的难度。通常评价路由查表算法的标准主要有高速查找、内存需求小、更新时间短、实现的灵活性强、能够处理真实的大容量路由表以及预处理时间短等。最长地址前缀匹配算法的难点在于,在查找过程中不仅需要和地址前缀匹配的比特进行匹配查找,而且需要考虑地址前缀的长度。近年来, 研究人员提出了多种路由查找算法,以提高查找性能。 II. 路由查找算法 A. 传统路由查找算法 1) 线性查找线性表结构是最简单的查找数据结构,因此可以把所有的路由地址前缀用线性链表的方式组织起来。每一次查找需要遍历线性表中的所有表项,在遍历过程中记录最长的路由前缀项,直到遍历完整个线性链表为止。对于 N个路由前缀表项,查找过程的算法复杂度为 O(N) ,存储空间复杂度为 O(N) ,插入删除路由表项的算法复杂度为 O(1)( 假设表项插入和删除均在线性表的末尾进行)。 2) 缓存策略在路由查找中可以使用缓存策略,把最近查找过的目的地址路由存放在高速的路由缓存表(route cache) 中。只有当在路由缓存表中查找失败的时候,我们才需要进行真正完整的前缀查找匹配过程。为了能够在查找性能上获得较大的提高,缓存的命中率就需要有一定的保证。随着 的不断发展、网络用户的不断增加以及业务数据量的多样化,数据的时间局部性变得越来越不明显,从而大大地降低了缓存的命中率。 3) 二进制 Trie ( binary trie ) 用二进制 Trie 结构来表示地址前缀是一个常用的方法(图 1)。 Trie 采用一种基于树的数据结构,通过前缀中每一位比特的值来决定树的分支。用二进制 Trie 结构( 树中每一个内部结点最多包含两个子结点) 来表示的地址前缀表。在 Trie 树中,处于第 L 层的结点代表了一类地址前 L 个比特均相同的地址空间,并且这前 L 个比特串就是由从根结点到这