（计算机应用技术专业论文）一种基于哈希策略的路由查找算法.pdf

ah a s h - b a s e dr o u t i n gl o o k u pa l g o r i t h m b y z h a n gl i y a n g b e ( u n i v e r s i t yo fs o u t hc h i n a ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro f e n g i n e e r i n g c o m p u t e ra p p l i c a t i o nt e c h n o l o g y c h a n g s h au n i v e r s i t yo fs c i e n c e & t e c h n o l o g y s u p e r v i s o r a s s o c i a t ep r o f e s s o rs h ic h a n g q i o n g m a r c h ，2 0 1 1 长沙理工大学 学位论文原创性声明 本人郑重声明：所旱交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本 声明的法律后果由本人承担。 作者签名：掀愿归 e 1 期：沙年岁月娩 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电f 版，允许论 文被查阅和借阅。本人授权长沙理工大学町以将本学位论文的伞部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扛j 描等复制手 段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密圈。 ( 请在以上相应方框内打“4 ”) 作者签名：苏瑶弦 日期：如年岁月巧自 导师签名：粤：长疬、 日期：2 0j1 年r 月) 占口 摘要 随着i n t e r n e t 的迅速发展，用于网络互联的主干链路上的核心路由器的接口速率达 到1 0 0 g b i t s 。这就要求骨1 二路由器每秒可以转发f 万以上：的分组，然而分组转发的关键 是查找路由表，高速的路由查找算法成为提高路由器性能的关键技术。本论文研究经典 路由查找算法的具体设计，分析了现有路由查找算法的优缺点，并从查找速度方面入手 给出了一种新的路由查找算法。论文主要从以下几个方面进行研究。 首先，研究了各种经典的路由查找算法，分析了路由查找算法的存在的问题以及路 由查找算法的性能参数，并分析了各种路由查找算法的复杂度；然后，给出了一种基于 满二叉树的分层哈希路由查找算法，算法充分考虑到路由查找前缀分布情况，将口 路由查找前缀的查找重点放在查找前缀长度在1 6 2 4 比特位之间m 路由前缀，从而大大 的加快了路由查找算法的查找速度；其次，给出了一种哈希负载平衡优化策略，将哈希 动态负载平衡的优化策略应用f 路由查找算法中。哈希算法的缺点就是会产生哈希碰 撞，哈希动态负载平衡优化策略能有效的降低哈希碰撞几率，从而能够提高哈希算法的 性能，从而进一步提高路由查找算法的性能。最后，通过仿真实验，得出基于满二叉树 的路由查找算法在查找速度上要明显优于以往算法。 关键字：i p 路由查找；分层哈希；满二叉树；哈希冲突 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e r n e t , t h ei n t e r f a c er a t eo fb a c k b o n er o u t e r si su pt 0 10 0 g b i t s c o r er o u t e r sm u s tp r o c e s sat e nm i l l i o no rm o r ep a c k e t sp e rs e c o n d , a n dt h em o s t i m p o r t a n ts t e po ff o r w a r d i n gp r o c e s si st ol o o k u pr o u t i n gt a b l e ，s ot h a th i 曲一s p e e dr o u t i n g l o o k u pa l g o r i t h mi st h em a j o rt e c h n o l o g yt oi m p r o v er o u t e rp e r f o r m a n c e i nt h i sp a p e r , t h e s p e c i f i cd e s i g no fc l a s s i c a l r o u t el o o k u pa l g o r i t h mi sr e s e a r c h e d t h ea d v a n t a g e sa n d d i s a d v a n t a g e so ft h ee x i s t i n gr o u t el o o k u pa l g o r i t h ma r ea n a l y z e d ，a n dan e wr o u t el o o k u p a l g o r i t h mw h i c hc o u l di m p r o v et h er o u t i n gl o o k u ps p e e di sg i v e n p a p e ri ss t u d i e do nt h e f o l l o w i n ga s p e c t s f i r s t , av a r i e t yo fc l a s s i c a lr o u t i n gl o o k u pa l g o r i t h m sa r ed i s c u s s e d ，t h ep r o b l e m so ft h e r o u t i n gl o o k u pa l g o r i t h ma n dt h ep e r f o r m a n c ep a r a m e t e r so fr o u t i n gl o o k u pa l g o r i t h m 躺 a n a l y z e d ，a n dt h ec o m p l e x i t yo fa l lr o u t i n gl o o k u pa l g o r i t h mi sa n a l y z e d s e c o n d ，ah a s h r o u t i n gl o o k u pa l g o r i t h mb a s e do nf u l lb i n a r yt r e eo f h i e r a r c h i c a li sp r o p o s e d ，w h i c hf o c u s e s o nt h es e a r c ht of m dt h ep r e f i xb e t w e e n16a n d2 4b i t s t h ed i s t r i b u t i o no fi pr o u t i n gp r e f i xi s f u l l yc o n s i d e r e d ，s ot h a tt h es p e e do fr o u t i n gl o o k u pa l g o r i t h mc o u l dg r e a t l yi n c r e a s e d t h i r d ， o n eo p t i m i z e dh a s hd y n a m i cl o a db a l a n c i n gs t r a t e g yi sg i v e n , w h i c hu s e di nr o u t i n gl o o k u p a l g o r i t h m t h ed i s a d v a n t a g ei st h a tt h eh a s ha l g o r i t h mw i l lp r o d u c eah a s hc o l l i s i o n t h e o p t i m i z e dh a s hd y n a m i cl o a db a l a n c i n gs t r a t e g yc o u l de f f e c t i v e l yr e d u c et h ep r o b a b i l i t yo f h a s hc o l l i s i o n s ，w h i c hc o u l di m p r o v et h ep e r f o r m a n c eo ft h eh a s ha l g o r i t h m h e n c e ，i tc o u l d i m p r o v et h ep e r f o r m a n c eo fr o u t i n gl o o k u pa l g o r i t h m f i n a l l y ，s i m u l a t i o ne x p e r i m e n t ss h o w t h a tt h er o u t i n gl o o k u pa l g o r i t h mb a s e do nf u l lb i n a r yt r e eo fh i e r a r c h i c a lh a s hi ss i g n i f i c a n t l y b e t t e rt h a nt h ep r e v i o u sa l g o r i t h m k e yw o r d s ：i pr o u t i n gl o o k u p ；h i e r a r c h i c a lh a s h ；f u l lb i n a r yt r e e ；h a s hc o n f l i c t s i i 盔沙疆歹戈掌 一种基于哈希策略的路由查找算法 目录 摘要i a b s t r a c t i i 第一章绪论 1 1 背景与意义。l 1 2 国内外研究现状l 1 3 - t 要内容及创新点3 1 4 论文结构。3 第二章路由查找算法综述 2 1 路由查找的有关定义。5 2 1 1 基本术语5 2 1 2 最长地址前缀匹配定义5 2 1 3 最长地址前缀匹配的实现难度5 2 2 路由查找算法分类6 2 2 1 基丁二地址前缀值的路由查找算法6 2 2 2 基于地址前缀长度的路由查找算法6 2 3 路由查找算法分析一7 2 3 1 线性查找7 2 3 2 缓存策略7 2 3 3 二进制t d e 树7 2 3 4 路径压缩t r i e 树( p a t h - c o m p r e s s e dt r i e ) 9 2 3 5 多分支t r i e 树( m u l t i b i tt r i e ) 一1 0 2 4 路由查找算法的评价标准一1l 2 4 1 查找速度1 1 2 4 - 2 存储容量1 2 2 4 3 预处理和更新速度1 2 2 4 4 算法实现的灵活性。1 2 2 4 5 算法的可扩展性1 2 2 5 算法的复杂度评价1 2 2 6 本章小结1 3 卫沙理歹史拳 一种基于哈希策略的路由查找算法 第三章基于满二叉树的分层哈希路由查找算法 3 1 满二叉树和路由查找算法1 5 3 1 1 满二叉树1 5 3 1 2 二进制t r i e 树路由查找算法一1 5 3 1 3 一种基j 二哈希表和t i l e 树的快速口路由查找算法1 6 3 2 基于满二叉树的分层哈希路由查找算法的设计方案1 6 3 3 基于满- 二叉树的分层哈希路由算法2 0 3 4 本章小结2 2 第四章哈希表动态负载平衡策略的优化 4 1 哈希表动态负载平衡策略2 3 4 2 哈希动态负载平衡优化策略2 4 4 3 哈希动态负载平衡优化策略的实现2 5 4 4 性能及实验结果分析2 7 4 4 1 性能分析2 7 4 4 2 实验结果分析一2 7 4 5 本章小结2 9 第五章算法实现以及性能分析 5 1 算法的实现3 0 5 1 1 路由表的设计3 0 5 1 2 路由查找算法的设计3 1 5 2 算法性能分析3 3 5 2 1 查找速度3 3 5 2 2 存储器容量。3 4 5 2 3 预处理和和更新速度3 4 5 2 4 算法的可扩展性3 4 5 3 仿真结果分析。3 4 第六章结论与展望 6 1 结论一3 7 6 2 展望3 7 参考文献3 8 致 射一4 1 附录( 攻读硕士学位期间发表录用论文) 4 2 名沙撂歹文学 一种基于哈希策略的路由查找算法 1 1 背景与意义 第一章绪论 随着网络规模的急剧膨胀，i n t e r n c t 的主机数目成指数方式增长，应用业务的多元化 导致网络流量的迅速增加，电子商务的应用对网络安全提出了更高的要求。i n t e r a c t 流量 平均三个月翻一翻，为了消除网络流星增加带来的影响，保证i n t e m e t 的性能，数据包 能够必须及时转发。影响数据包转发速度的主要因素有三个：链路传输速度，路由器的 数据处理能力和路由查找速度。前两个因素都已经存在较好的解决方案，例如，随着光 交换技术和半导体技术的发展，分组交换可以在很高的速率下进行。所以，路由查找速 度己成为数据包转发速度的瓶颈。 路由器的主要功能就是根据i p 数据报中的目的地址查找路由表转发分组，i n t e r n e t 的 迅猛发展，使用于主干网络匠联的核心路由器的接口速度已经达到了1 0 0 g b i t s 。由于国 际巨联网和电子商务的飞速发展、网络接入需求呈指数级增长，对路由器查找性能的要 求越来越高，这就要求有高速的路由查找算法。高速路由设计的e 要障碍是相对较慢的 i p 查找算法。为了将数据包转发到目的地址，一台路由器必须执行转发决定，输入数据 包下一跳地址取决于路由协议收集到的信息。随着1 9 9 3 年c i d r ( c l a s s l e s si n t e r - d o m a i n r o u t i n g ) 的发展【m 】，( 路由前缀，前缀长度) 确定了m 路由，这里前缀长度在1 位至1 j 3 2 位 之间变化。对一台有大量路由表入口的骨干路由器来说，可变前缀长度进行的b m p ( 最佳 匹配前缀) 搜索町能会花很长时间，国际互联网主机的指数级增长也给路由系统增加更大 的压力。数据包转发速度很难跟上日益增长的通信鼍需求，地址查找操作更是当今路由 器转发性能的主要瓶颈。因此提高路由查找速度的关键是采用好的查表算法。这时寻找 新的快速路由查找算法特别必要。 1 2 国内外研究现状 随着i n t e m e t 的不断发展，网络数据的时间局部性越来越不明显，从而大大降低了 缓存的命中率，有人提出了一种新型的路由查找法案，该方案中使用了一种新型的缓存 设备【3 1 。而p a t r i c i a 算法最早提出了路径压缩思想，但是当时没有采用最长l ； f 缀查找 4 1 。在这个基础上s k i o w c r 提出了一种支持最长前缀查找的算法【5 1 。随后有许多改进算 法，例如，r u n 1 e n g t h 压缩法，它能够很好的应用与地址前缀查找问题睁1 0 1 。经过大量的 盅沙疆歹戈霉 一种基于哈希策略的路由查找算法 实验证明，用表示典璎路由器4 7 1 1 3 表项数目的b s d 路径压缩算法t r i e 树的f j i 缀衷， 平均搜索深度是仅为2 0 ，最长搜索深度是2 6 i 1 1 】。 经过一批批的学者对路由器研究的深入，研究算法不断的改进，从而使对路由器的 性能也要求越来越高，研究人员提出了许多新颖的查找算法。与以前的算法相比，性能 得到了很大的提高。一种方法是加入辅助策略。前缀扩展，将一条长度较短的地址前缀 展开成多条地址i i 缀长度较长的前缀集【1 2 6 1 ；独立前缀转化，将有包含关系的地址前缀 转化成相互独立的地址f j 缀1 协1 7 1 ；压缩技术，它试图从编码中删除数据的冗余信息i m l 9 1 ； 优化技术1 2 0 - 2 1 1 ，存储层次设计，这种技术尽可能的将查找表内容放入c a s h 中1 2 2 - 2 3 1 。另一种 为多分支t r i e 树，它包括： ( 1 ) 基本算法，查找的每一步都检查地址中的多个比特，而不仅仅是一个比特位。 ( 2 ) 多分支树的优化算法，这种算法的设计关键是步宽的选择。 ( 3 ) 多分支t r i e 树的压缩算法，参考文献中给出了两种有效的的压缩算法1 2 ”5 1 。 ( 4 ) 多分支t r i e 树的硬件实现算法。 2 0 0 6 年以来，随着网络数据的迅猛增长，对路由查找算法的要求越来越高，研究人 员提出了一些新型的查找算法，如文献 2 6 1 提出了一种基于多分支t i l e 树的改进路由查找 算法，改算法保留了多分支t r i e 树的访存次数少，查询速度快的优点，并且占用存储空 间小的特点。而有些人提出了一种基f 哈希表和t r i e 树的快速内容路由查找算法，该 算法经过试验证明具有很好的查找速度1 2 7 1 。文献1 2 8 1 也对多分支路由查找算法进行了研 究。而在文献 2 9 1 提出了基于分段哈希和多分支t r i e 树的路由查找机制。这些方法都是从 路由查找算法的速度着手的，这些文献中提到的方法性能的好坏都要取决于选择的步长 的好坏。 其他的查找算法有地址前缀长度的二分查找算法，以及地址区间二分查找算法。由 于软件算法越来越完善，于是研究者又像硬件算法方面进行的大量的研究。目前使用硬 件实现方法最多的是使用c a m ( c o n t e n t a d d r e s s a b l em e m o r y ) ，以及t c a m 。而硬件查 找算法的性能很大程度上取决f 硬件的好坏【1 2 l 。 在2 0 0 8 年，文献【1 3 】提出了一种基于t c a m 的i p 路由查找算法，该算法进一步提 高了算法的时间和空间效率，但是这种算法同样受到硬件设施的限制。 2 0 1 0 年以来，不少专家提出很多i p 路由查找算法。文献【1 4 】提出了一种高吞吐率 的动态的路由查找算法，该算法能够支持2 m 的路由前缀。文献 1 5 】则提出了一种基于 c a m 的最长前缀匹配查找算法来提高路由算法的查找性能。文献 1 6 1 提出了一种动态负 2 。卫沙理歹文事 一种基于哈希策略的路由查找算法 载均衡策略来提高路由查找算法的性能。但是这些算法尽管提高了算法的性能，但足在 实际应用中性能还是不够理想。 目l i i 的查找算法在查找过程中，前缀比特值的匹配查找和前缀长度的查找是必须进 行的操作步骤。这些算法的最终目的都是从查找速度，存储容量，预处理和更新速度， 算法实现的灵活性和可扩展性方面来提高算法的性能d o - 3 3 1 。文献1 3 4 1 就是考虑到了i p 地 址前缀的分布规律，但是该方法的性能还可以进一步增强。文献【3 5 】证实了从2 0 0 2 到 2 0 0 9 期间，大部分的i p 前缀长度都分布在大于1 6 且小于2 4 的范围内。而很少有路由 查找算法针对这个特性设计专门查找算法。有也是性能不是很理想，而且算法性能还有 待丁二进一步提高。 综e 所示，m 路由查找算法还是有很多值得改进的地方，特别是现在网络数据的翻 倍增长，更要求寻找高速的路由查找算法。 1 3 主要内容及创新点 本论文对现行的路由查找算法进行分析比较，重点比较了路由查找算法的查找速 度，针对近年来m 路由地址l ；i 缀的分布规律，给了一种基于满二叉树的分层哈希路由 的查找算法，并将一种优化的哈希负载平衡策略应用其中。本文的研究： 作和创新点如 下： ( 1 ) 论文给出了一种基于满二叉树的分层哈希路由查找算法。本算法根据近年来 i p v 4 地址查找前缀鼍要分布在前缀长度为1 6 2 4 比特位之间，从而把查找的重点放在 1 6 2 4 比特长度的i p 地址l j 缀。本算法通过将p v 4 地址分成四个部分，采用哈希结构 与满二义树结构进行存储，这样可以减少链式存储结构的指针开销。 ( 2 ) 优化了一种哈希动态负载均衡策略，通过在网络空闲时间对哈希表的关键字 进行负载均衡处理，从而减少了哈希碰撞几率，提高了哈希算法的性能，并将其应用于 路由查找算法中。 ( 3 ) 通过仿真实验，在查找速度和存储容量方面进行分析研究，最后得出结论， 本文算法能够进行高速的路由前缀查找，在查找速度上要明显优于以往路由查找算法， 虽然存储容量稍大于以往算法。 1 4 论文结构 本文在研究过程中，参考了大最的中外文文献，根据近年来i p 地址查找前缀的分 3 坐沙理歹戈拳 一种基于哈希策略的路由查找算法 布规律，以及基f 存储容量的的考虑，提出了一种基f 满二义树的分层哈希路由查找算 法，并将一种优化的哈希动态负载平衡策略应用j 二其中。算法在查找速度方面要明显高 于以往算法。本文共分为6 章。 论文第一章讨论了路由查找算法的研究背景和意义，以及国内外研究现状。 第二章对路由查找的基本定义进行了介绍，综述了各种路由查找算法，对它们进行 了详细的分析和比较。 第三章首先分析了满二叉树和基二ft r i e 树的路由查找算法，给出了一种基于满二叉 树的分层哈希路由查找算法。设计了路由表的结构，并描述了基于满二叉树的分层哈希 路由查找算法的查找过程。 第四章首先分析了一种哈希负载平衡策略，并指出了其优缺点。然后对该哈希负载 均衡策略进行了优化，详细描述了优化策略的实现，并用实验验证了这种优化策略的优 越性。为将优化哈希策略应用于基于满二叉树的分层哈希路由查找算法中提供了依据。 第五章首先从查找速度，存储容量，更新速度，可扩展性等方面着手，将基于满二 叉树的分层哈希路由查找算法进行了理论分析。然后通过仿真实验，对基于满二叉树的 分层哈希路由查找算法的查找速度和存储容鼍进行了分析。 第六章对该论文做出总结与展望。 4 盔沙疆歹文学 一种基于哈希策略的路由查找算法 第二章路由查找算法综述 近年来，主干网络瓦联的核心路由器的接口速率已经达到了1 0 0 g b i t s 。这一速率要 求核心路由器能够每秒转发千万以上的分组。分组转发的关键步骤之一是查找路由表， 因此实现高速分组转发的关键是给出快速的i p 地址路由查找算法。本章将讨论路由查 找的有关定义以及路由查找算法的难点，并对各种路由查找算法进行研究分析，为路由 查找算法的改进做了理论铺垫。 2 1 路由查找的有关定义 2 1 1 基本术语 在给出路由查找的定义之前，首先介绍一些在定义中将会使用到的基本术语 3 6 1 。 ( 1 ) 目的地址d 定义为长度为w 的o ，l 比特字符串( b i ts t r i n g ) 。 ( 2 ) 路由地址前缀p 定义为长度值在区间【l ，w 】内的o ，1 比特字符串，用l ( p ) 表示前 缀p 的前缀长度，用p l o n g e s t 表示最长匹配地址前缀。 ( 3 ) 整个地址前缀表用p t a b l e 表示，地址前缀表中的地址前缀数目用n 表示。 ( 4 ) 地址前缀p 与地址d 相匹配，当且仅当地址d 的前l ( p ) 个比特字符串与地址前 缀p 的比特字符串相等。 2 1 2 最长地址前缀匹配定义 在地址前缀表p t a b l e 中查找地址d 所对应的最长匹配地址i ；i 缀p l o n g e s t ，当且仅当 p l o n g e s t 满足以下两个条件1 3 2 1 ： ( 1 ) 地址前缀p l o n g e s t 与地址d 相匹配。 ( 2 ) p t a b l e 中不存在其他地址前缀p ，满足地址前缀p 与地址d 相匹配，并且 l ( p ) l ( p l o n g e s t ) 。 2 1 3 最长地址前缀匹配的实现难度 在基于类的地址结构体系下，要想知道地址前缀的匹配长度，可以通过匹配目的i p 地址前几个比特位的值来决定，因此可以简单的进行地址前缀查找。根据3 类不同的前 缀的长度可以将路由表中的所有前缀分成3 个查找互不关联的前缀表，在各自对应的前 缀表中准确的查找关键字无疑三经是地址前缀的查找的关键操作，此时可以完全使用一 5 卫沙理歹戈事 一种基于哈希策略的路由查找算法 些经典的查找算法，例如基于h a s h 散列表或者基于二分法等传统的查找算法。 尽管在c t d r ( c l a s s l e s si n t e r - d o m a i nr o u t i n g ) 地址结构体系下，路由表的规模得到了 一定的控制，但是从另一方面看，地址前缀查找的：亡作变得非常复杂。在c i d r 地址结 构下，不再存在类的概念，地址i j 缀表中包含任意长度的前缀表项，要想知道该地址多 对应的前缀长度，不能简单的从目的地址的前几个比特来判断，从而关键字的精确匹配 查找不能作为地址查找操作的简单转化，c i d r 地址结构体系下地址前缀查找需要进行 两个操作：第一，对前缀的比特位进行匹配查找；第二，考虑地址前缀长度。正是基于 这个方面的考虑，最长地址前缀查找可以从地址前缀值以及地址前缀长度两个方面来考 虑，下面将要分析的各种路由查找算法从根本上都市町疑归纳为如何在这两个方面上增 加搜索效率的问题。 2 2 路由查找算法分类 最长地址前缀匹配查找有两个因素：地址前缀长度和地址前缀的比特值。因此对于 路由查找算法基本上都可以划分为从这两个因素出发而进行的匹配的查找过程。 2 2 1 基于地址前缀值的路由查找算法 基于地址前缀值路由查找算法的特点是通过穷举整个地址前缀空间进行地址关键 字来消除地址前缀长度的影响。基于地址前缀值查找中最简单直观的地址前缀查找方法 是线性匹配查找算法。基于地址前缀值的查找算法的另一查找算法是地址区域二分法， 而基于地址区域二分法采用了二分查找，在很大程度上改善了算法的性能。从本质上来 说，基于c a m ( c o n t e n ta d d r e s s a b l em e m o r y ) 的硬件实现方法也是属于地址前缀值的 查找算法。 2 2 2 基于地址前缀长度的路由查找算法 基j 二地址i j 缀长度的路由查找算法是另一个查找方法，在前缀长度空间内进行查找 是这类算的起始点，与2 2 1 节的查找算法类似，查找过程可以用线性遍历法，也可以 用二分遍历法。二进制t r i e 树查找算法就是使用本小节的查找算法，因为对于每一个查 找步骤来说，地址前缀的长度是必须进行匹配的。另一个基j f 在地址前缀长度空问内的 线性遍历法是多分支t r i e 查找算法，该算法每次查找大于一个比特位的值，从而使遍历 的地址长度数目减少了，从而提高了查找的性能。从算法的复杂度来看，由f 在前缀窄 间进行二分查找，使得前缀长度二分查找算法具有很好的性能。 6 0 盔沙疆歹文事 一种基于哈希簧略的路由查找算法 2 3 路由查找算法分析 2 3 1 线性查找 线性表结构是将路由地址前缀用链表方式组织在一块，从而成为一个简单的查找 数据结构，每一次线性查找需要查找所有的线性表项，查找的时间复杂度为o f n ) ，存 储空间的复杂度也为o ( ，插入或者删除线性表项需要进行一次操作，其复杂度为o ( 1 ) ( 所有操作均在线性表的后面进行) 。 2 3 2 缓存策略 通过使用缓存策略，在路由查找中，可以在高速的路由缓存表中( r o u t ec a s h ) 保 存最近查找的目的地址路由。完整的前缀查找匹配过程只有在路由缓冲表中查找不到时 才会发生。 为了能够提高在查找性能，就要保证一定缓存的命中率。假设路由前缀查找速度是 二十分之一的缓存的查找速度，经过实验计算可以得出，为了平均查找性能达到原来的 1 0 倍，需要缓存的命中率达到9 5 左右。由于i n t e m e t 的快速发展，网络用户也快速的 增加，越来越突显出一种局势，即数据局部性在时间上越来越变得不明显。进而使缓存 的命中率大大地降低了。 2 3 3 二进制t r i e 树 二进制t r i e 结构足最常用的一个方法是来表示地址前缀，t r i e 中，每一次查找一位 前缀地址值，它的走向是根据每一位的值来决定的。如图2 1 所示就是二进制t r i e 结构 ( 树中每个节点最多包含两节点，除了叶子节点外) 来表示的地址前缀表1 3 2 1 。 在t r i e 树中，地址前n 比特均相同的地址空间处于第n 层的节点之中，由根结点到 这个节点的路径上的n 比特组成了前n 个比特串。如图2 1 中结点c ，它表示前3 个比 特为0 1 1 的地址族，从节点c 到根结点路径上的比特位形成的比特串就是0 1 1 。图2 1 中带若该节点对应个地址前缀则用灰色填充表示，这些灰色节点中包含了与该地址前 缀有关的转发信息。图2 1 中叶子节点和中间节点都有可能用灰色填充表示。由于一些 特殊地址前缀出现在地址前缀合并过程中，所以在t r i e 树结构中有一些中间节点也对应 了地址前缀。 在图2 1 中，特殊地址的出现使得前缀b 和前缀c 对应的节点是前缀a 对应节点的 子孙节点。因此，地址查找的结果i j 丁能足多个地址前缀。例如以0 l l 开始的地址前缀c 7 廛沙理歹戈孝 一种基于哈希策略的路由查找算法 以及f i 缀a 都能相互匹配，但是根据最长地址前缀匹配规则前缀c 比l j i 缀a 更长，所以 前缀c 才是正确的查找结果。 t r i e 树结构的查找是一种简单的操作过程，t r i e 树通过前缀的比特值来进行各个 查找过程的走向。在查找匹配过程中，如果当前i p 前缀的位值为0 ，则查找t r i e 树的危 孩子节点；否则查找t r i e 树的右孩子节点。在t r i e 搜索过程中，对于遇到t r i e 树的中间 节点的时候，将该节点对应的前缀地址记录下来，作为当前的最长地址前缀。搜索过程 直到不再有后续节点可以选取时结束，此时找到的的最长地址前缀就是查找结果。 图2 1 _ 二进制t r i e 树结构 t r i e 树中的插入和删除操作也比较容易实现。当一个新的前缀表项插入路由表中时， 首先在t r i e 树以该前缀项为关键字中进行查找操作，有些查找过程在某一非叶子节点就 终止了，而有螳则在叶子：符点终止。对丁二在非叶子节点终止的情况，直接将前缀转发信 息加入到非叶子节点中；对于查找过程在叶子节点终止的情况，根据需要插入必要的后 续节点。对于删除操作，首先已查找操作作为i i 提条件，如果查找过程在非叶子节点终 8 a b c d e f g h i ，一 l 毒 盅沙理歹文学 一种基于哈希策略的路由查找算法 止，那么直接将转发信息从该符点删除；若查找过程在某一个叶子节点终i 七，此时首先 删除该节点，然后根据情况删除另外的一些内部节点。 2 3 4 路径压缩t r i e 树( p a t h c o m p r e s s e dt i l e ) 图2 1 中t r i e 树经过转化以后得到的t r i e 树如图2 2 所示 图2 2 路径压缩t r i e 树结构 比较图2 1 和图2 2 ，可以看到，节点b 的前两个父节点已经不在存在于图2 2 中， 节点a 从图2 1 中的单分支节点移动到了图2 2 中的_ _ ：分支节点处，图2 1 中的单分支节 点被删除。由于这一操作可能删除了多个地址前缀信息，因此多个地址前缀可能处于图 2 2 的路径压缩t r i e 树节点中。在t r i e 树的搜索过程中，由于去除了某些节点，所以口 目的地址中的某些比特位可以跳跃进行匹配操作，因此节点的下一个需要检查的比特位 需要维护一个变量。与二进制t r i e 树相比，地址前缀的比特串需要保存在路径压缩t r i e 树前缀节点处。，除了节点选取分支时考虑的足比特位变量所指示的比特位，其他查找 过程与二进制t r i e 树类似，当查找过程抵达一个前缀节点时，将与该节点对应的比特位 进行前缀匹配操作。当到达叶子节点或者在树中没有找到匹配项的时候终止，查找过程 9 ，工p 工 erp a b c d e f g h i 。坐沙理歹戈拳 一种基于哈希策略的路由查找算法 中的最后记采的结果则为查找结果。例如在图2 3 中查找的e i 的地址，该地址以0 1 0 11 0 为头部，以根节点为起始 了点，由于开始节点的比特值是l ，因此比较地址的第一位， 而第一位为o ，所以选取开始节点的左孩子节点，而地址前缀对应于左孩子节点到达节 点对应的路径，因此进行地址前缀匹配操作，结果为匹配，将到达当静节点为止记录为 a ，表示最长的地址前缀。由于3 是当前节点的比特指示位，所以检查第三位的目的地 址，而第i 位的值为零，于是选择左分支，记录该节点对应着地址前缀，然后进行匹配 前缀操作，而匹配结果的是失败，此时查找过程结束，查找结果就是此时的最长i i 缀a 。 2 3 5 多分支t r i e 树( m u l t i b i t 嘶e ) 在一次查找中检查多个比特位将会提高t r i e 树查找效率，而不是只查找一位1 3 2 1 。例 如，如果要查找检查的8 个比特，在i p v 4 地址查找过程中，最大的查找次数为4 次存 储器访问操作。查找步宽是指每次查找中需要检查的比特数，它的值要么是固定的，要 么是可变的。查找步宽为l 的t i l e 树实际上就是二分支t r i e 树。多分支t i l e 树查找步宽 大于1 。 在多分支t r i e 树中，同一层的节点包含的孩子节点数目可以是不一样的。图2 3 中 的t r i e 树的第二层节点a 与d 节点的步宽是不一样的，象图2 3 中这样的t i l e 树町以称 之为可变步宽的多分支t r i e 树；一般来说对于浪费较多的存储空间的固定步宽的多分支 t r i e 树实现起来简单；而可变步宽的多分支t r i e 树可以节省一定的存储空间，而其实现 起来要复杂一些。 对于查找过程的每一步需要检查多个比特的多分支t i l e 树来说，如果要求使用多分 支树的结构，必须保证前缀表中的地址前缀要变成多分支t i l e 树查找能够操作的地址l i 缀。图2 1 中的t r i e 树对应的多分支t i l e 树结构如图2 3 所示。 图2 3 的多分支t r i e 树中，开始的查找步宽为2 ，因此地址前缀长度为l 的前缀不 会存在于树中，于是要把前缀d 和a 转化为长度为2 的前缀集合。一样的情况，扩展了 地址前缀c 来满足多分支t r i e 树的建树需要。将图2 1 和图2 3 进行比较，最显眼的区别 就是图2 3 的多分支t r i e 的深度有了很大的减少，基于这个原因，多分支树要比二分支 t i l e 树具有更高的查找效率。 1 0 。坐沙疆歹戈拳 一种基于哈希策略的路由查找算法 刍0 ) 1 1 0 00 11 0 e 套遣 1 1 、涂 、一 图2 3 可变步宽的多分支t r i e 树结构 多分支i r i e 树与二分支t r i e 树的查找过程有很多相似的地方，每次查找一个节点， 就必须保存到目前为止已经匹配上的最长地址前缀，直到到达叶子节点或者或者杏找过 程结束。尽管基于前缀长度的线性遍历法是多分支t r i c 树的查找的一种方法，但是因为 多分支t r i e 树的大于1 的步宽，于是它的查找效率相对于二分查找t r i e 树来说，具有很 大的提高。 2 4 路由查找算法的评价标准 怎么评价一个路由查找算法性能的好坏，我们要从很多影响算法性能的因素着手， 从而进行性能评估，本节将主要介绍几种影响算法的性能因素。 2 4 1 查找速度 路由查找算法性能的一个重要的指标就是查找速度的好坏，这个指标还影响了路由 器处理报文能力。在软件环境下，设计实现了不少常用路由查找算法。查找过程需要进 行的存储器的访问次数决定了路由查找算法的速度，一般部足通过计算路由查找算法的 存储器的访问次数来评估算法的好坏1 3 2 。 、。弋1 土。d 7 d，70 1 ip 工erp a b c d e f g h i 卫沙理歹文学 一种基于哈希策略的路由查找算法 2 4 2 存储容量 算法的存储容量是指算法的占用的内存空间，路由器存储容量的设计是尽可能的减 少路由查找算法的占用的存储容量，因为存储容量越少，它运行的平台环境就越多，从 而保证了算法的较好的可移植性。 2 4 3 预处理和更新速度 预处理操作是在静态路由查找算法中提出来的，该算法的在更新操作的时候，数据 结构需要完全进行更改。而动态路由查找算法，在更新路由( 包括删除和增加) 时，算 法数据结果只需要在原有基础上进行改动，而不需要完全的改动。由于静态算法的运行 需要一个预处理过程，因此更新更长的时间来进行路由查找。不过虽然要进行一个预处 理过程，但足这个过程是在路由查找之前进行的操作，所以于查找过程来说，一般足感 觉不到那个预处理的时间的。路由增加和删除的过程由二fi n t e r n e t 路由的不稳定特性变 得非常频繁，最差情况下每秒内路由变化叮以变化几万次，于是更新速度必须更够与这 个速度同步。 2 4 4 算法实现的灵活性 路由查找算法灵活性是指算法尽量叮以既町以软件实现也可以硬件实现。迄今为 止，报文处理速度已经达到一个相当高的水平，路由查找引擎的主要实现的方式将是硬 件实现的，于是路由查找算法的应该尽量能够在硬件上实现。于是可以采集各种算法的 优点，从而提出的灵活的路由查找算法，这种算法实现起来就比较容易一点。 2 4 5 算法的可扩展性 近年来，网络数据的不断增加，这就导致了m v 4 地址的不足， i p v 6i n t e r a c t 协议 占据了越来越覆的比重，于是在设计i p v 4 路由查找算法的过程中就要考虑到算法是否 可以直接应用在i p v 6 协议上。于足未来路由查找算法研究的重点之一将会是算法是否 能够适用新的网络环境。 2 5 算法的复杂度评价 本小节将讨论路由查找算法的复杂度，如表2 1 所示。假设关键字的长度为l ，地 址前缀表中前缀的数