（通信与信息系统专业论文）基于trie的路由查找算法研究.pdf

硕士学位论文 摘要 由于i n t e r n e t 的飞速发展，网络用户数目的增长，多媒体网络应用日益广泛， 网络流量呈爆炸式的增长趋势。i n t e r n e t 若要想继续提供较好的服务，要求核心路由 器每秒能转发几百万个以上的分组，快速路由查找技术成为路由器报文转发的瓶颈。 因此如何实现高速路由表的查找和更新是研究的难点。同时随着i p v 6 技术的逐步成 熟和推广，也进一步要求提升路由查找的性能。 文章在通过对近年来提出的各种路由查找方法进行详细阐述基础上，对各种算法 的性能以及对i p v 6 的适应性进行了分析，结果发现t r i e 数据结构是实现高速路由查 找和报文转发的关键，且t r i e 算法具有易于与硬件结合的特点，因此提出基于t r i e 的最长前缀的查找算法。 该算法中某些节点包含多条路由信息，减少了t r i e 树的节点数目。这样大大减少 了存储空间。考虑到当前路由表中前缀分布的特点，改进后的算法降低了树的高度。 同时，该算法能够应用于i p v 6 网络。尤其适于当前快速变化的i n t e r n e t 更新要求。 总之，该算法不仅保障了路由表的快速查找，同时在执行更新操作时，不需要重新构 建路由表。这种算法用到i e v 6 同样收到很好大效果，因此，它可以兼顾i p v 4 i p v 6 网络。 最后，作者总结全文，综合了作者在该课题研究中的主要成果，并且提出了需要进 一步研究和讨论的问题。 关键词：i p 路由查找；最长前缀匹配；t ri e 树 基于t r i e 的路由壹找算法研究 a b s t r a c t w i t ht h ef a s tp r o g r e s so fi n t e m e t , t h en u m b e ro fw e bu s c i si si n c r e a s i n g , a n d m u l t i m e d i aa p p l i c a t i o n si sw i , t c l ya n dw i d e l y h e n c ef o ri m p r o v i n gi n t e m e tp e r f o n a n e e ， i to r d e r st h ec o l et o u t e rt ob ca b l et of o r w a r dt e nm i l l i o no fp a c k e t sp e rs e c o n d f a s t r o u t i n gl o o k u ph a sb e c o m et h eb o t t l e n e c ko fh i 曲s p e e dp a c k e tf o r w a r d i n g t h u sh o wt o i m p r o v es e a r c ha n du p d a t ep 盯t o r m a n c ei st h ek e y b e s i d e s m v 6t e c h n o l o g yh a sb e e n i n o r ca n dm o l em a t u r e , a n di sb e i n ga p p l i e di n t om a n yd o m a i n s 。a n di ta l s oo r d e rt o i m p r o v et h op e r f o r m a c eo f r o u t i n gl o o k u p t h ea r t i c l es u m m a r i z e st h er o u t el o o k i n g - u pa l g o r i t h me x i s t e d , a n a l y z e sa n dp o i n t s o u tt h ea d v a n t a g e sa n dd r a w b a c k so ft h ea l g o r i t h m s i ti sf o u n dt h a tt r i ed a t as t r u c t u r ei s t h ek e yt oa e h i e v oah i g hs p e e df o rr o u t i n gl o o l a l pa n dp a c k e tf o r w a r d i n g a c c o r d i n gt o t r i ed a t as t r u c t u r ei so p tt ob e i n ga p p l i e dt oh a r d w a r et e c h n o l o g y , w op r e s e n tt l a el m p ( l o n g e s tp r e f i xm a t e l a ) a l g o r i t h mb a s e do nt r i e s o m en o d e si nt h ea l g o r i t h mc o n t a i n e dt w or o u t i n ge n t r i e s ，w h i c hc a nd e c r e a s et h e n u m b e ro f n o d e 8 t h a tm a k e st h em i n i m a ln u m b e ro f m e m o r ya c c e s s 髓a c c o r d i n gt ot h e p r e f i xl e n g t hd i s t r i b u t i o n s w em a k es o m ei m p r o v e m e n t , w h i c hc a l le f f i c i e n t l yl o w e rt h e t r e eh e i g h t g e n e r a l l ys p e a k i n g , t h ep r o p o s e ds c h e m en o to n l ya c h i e v er a p i dl o o k u ps p e c d ， b u ta l s ob r i n gab e t t e r n a t ap e r f o r m a n c e b e c a u s et h et r e cc a i lb uu p d a t e dw i t h o u tb e i n g r e c o n s t r u c t e df r o ms e r a t e l aw h e nt h er o u t i n gt a b l ei s c h a n g e d t h ea p p r o a e l ai se q u a l l y a t t r a c t i v ef o ri p v 6 t h u s i t nb ea p p l i e di n t ob o t hi p v 4a n di p v 6n e t w o r k f i n a l l y , t h ea u t h o rd r a w s1 3 c o n c l u s i o na n dd i s c u s s e sf l o m l ：i $ s u cf o rf u l t l l c rr e s e a r c h k e yw o r d s ：i pr o u t i n gl o o k u p ；l o n g e s tp r e f i xm a t e l a ；t r i e - t r c e 硕士学位论文 插图索引 图1 1i p v 6 基本报头与i p v 4 报头的比较 图1 2 路由器的体系结构 图2 1 五类i p 地址比较 图2 2 线性存储 图2 3 二进制t r i e 结构 图2 4 路径压缩的t i r e 树的结点结构 图2 5 路径压缩t r i e 结构 图2 6 步宽为2 的多分支t r i e 树结构 图2 7 表2 1 的2 位t r i e 结构 图2 8h a s h 表实例 图2 9 基于前缀长度的二分查找结构图 图2 1 0 前缀对应的地址区间图 图3 1 结点结构 图3 2 插入算法举例 图3 3 删除结点的实例 i i i 。2 0 。2 2 2 3 。2 3 2 5 2 8 2 8 2 9 3 4 2 5 3 基于吨的路卣壹找篝法研究 附表索引 表1 1 查询速度的要求 表2 1 前缀表 表2 2 算法复杂度列表 表3 1 前缀长度分布统计表 兰州理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：j q 、拐日期：砷年占月户日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位沦文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保律j 闭。 作者签名： 导师签名： ( 请在以1 年虹方框内打“”) 日期：印年厂月少日 【 期：石7 年z 月莎日 q 乡 袱，1 ，奇7，(跫q 硕士学位论文 1 1 研究背景 第1 章绪论 近年来，随着i n t e r n e t 的迅速增长，要求唯一i p 地址的无线设备的激增， i p v 4 地址呈现枯竭趋势。 i p v 4 地址为3 2 位长，经常以4 个两位十六进制数字表示，也常常以4 个o 至2 5 5 间的数字表示，数字间以小数点间隔。每个i p 主机地址包括两部分： 网 络地址，主机地址 。网络地址，用于指出该主机属于哪一个网络( 属于同一个 网络的主机使用同样的网络地址) ；主机地址，它唯一地定义了网络上的主机。 这种安排一方面是i p 协议的长处所在，另一方面也导致了地址危机的产生。 i p v 4 采用了3 2 一b i t 的地址结构，这从理论上讲可以提供近4 3 亿的主机数 量，但实际上所能分配的地址远远小于该数目。这种地址配置的低效率，主要 是由于i p v 4 地址以a 、b 、c 等类别进行人为划分。在i n t e r n e t 的发展初期， 由于对其发展速度估计不足，都以为地址空间将会一直是非常宽裕的，在分配 时，a 类地址只有1 2 6 个，用于那些最大的实体，如政府机关，因为它们连接 着最多的主机：理论上最多可达一千六百万台。b 类地址大约1 60 0 0 个，用于 大型机构，如大学和大公司，理论上可支持超过6 50 0 0 台主机。很多时候，一 个公司、一所大学就能获得一个a 类或b 类地址。c 类网络超过两百万个，每 个网络上的主机数量不超过2 5 5 个，用于使用i p 网络的其他机构。更小的公司， 某些只有几台主机，它们对于c 类地址的使用效率很低；而大型机构在寻找b 类地址时却发现越来越难；那些幸运地获得a 类地址的少数公司很少能够高效 地使用它们的一千六百万个主机地纰。同时由于历史的原因，美国一些大学和 公司占用了大量的i p 地址，如康柏公司就有3 个a 类地址，麻省理工大学、斯 坦福大学都有a 类地址。而截止到2 0 0 5 年底，我国大陆i p v 4 地址总数仅为7 4 3 9 12 9 6 个，合4 a1 1 1 b3 1 c 也就是说每2 6 个中国人只能分享一个地址，与 此形成鲜明对比的是，美国2 亿多人口拥有近1 2 亿地址，占i p 、，4 地址的四分 之一强，平均每个美国人享有5 个地址。由此产生的结果是，一方面被占用的 地址大量空置，另一方面是在互联网快速发展的国家i p 地址紧缺。据官方预测， 根据目前使用i p v 4 地址的趋势，i p v 4 未分配地址池将在2 0 1 1 年6 月2 8 日被 耗尽。而就中国目前的人口而言，如果全部使用i p 网络通信，目前可分配的地 址，已经不能满足人均一个。而新技术的实现，如p d a 、无线终端、3 g 移动电 话、信息汽车、信息家电等，也频频要求用户拥有更多的i p 地址。 这导致了在过去几年中一直使用的网络地址指派规程陷入了困境，在试图更 有效地分发地址空间的同时，还要注意保存现有的未指派地址。与此同时，一些 基于t r i e 的路由查找算法研究 解决地址危机的办法开始得以广泛使用，其中包括无类域间选路( c i d r ) 、网络地 址翻译( n a t ) 和使用非选路网络地址。但是这些并不能完全解除i p 地址空问危机。 为了进一步满足网络规模的不断增长，i e t f 设计了新一代网络协议i p v 6 ( i n t e r n e tp r o t o c o lv e r s i o n6 ) 。如图1 1 所示。 版本( 4 )长度洲服务类型r 8 )数据包总长度n 6 ) 标识符f 1 们 标志( 3 11 分段偏移量( 1 3 ) 生存时间( 8 )传输协议f 8 1报头校验和f l 研 信源：1 删t 1 1 ：( 3 2 ) 信宿地址( 3 选项侣1填充项f 变长1 版本( 4 ) k 输流类型( 8 ) 数据流标签( 2 0 ) 有效载荷长度( 1 6 )卜f 一个报头( 8 ) 跳数限制( 8 ) 信源地址( 1 2 8 ) 信宿地址( 1 2 8 ) 图1 1i p v 6 基本报头与i 4 报头的比较 较i p v 4 而言，i p v 6 有了一些重要的改变。从上表可以看出，最为凸显的一 点就是地址格式发生了巨大改变地址格式由原来的3 2 位变成了1 2 8 位。 i p v 4 中所有包头以3 2 个字节为单位，即基本的长度单位是4 个字节。图1 ( a ) 为ip 、r 4 的包头格式。i p v 6 中，包头以1 2 8 个字节为单位，且包头的总长度是 4 0 个字节。i p v 6 的包头格式如图l ( b ) 所示。取消了i p v 4 包头的6 个字段：i p 包头长度( h e a d e rl e n g t h ) 、服务类型( s e r v i c et y p e ) 、标识( i d e n t i f i c a t i o n ) 、 标志( f l a g ) 、标志偏移量( f r a g m e n to f f s e t ) 及头标校验和( h e 酣e rc h e c k s u m ) ； 在i p v 6 中有三个控制字段重新命名，并在一些条件下重新定义：长度( l e n g t h ) 、 服务类型( s e r v i c et y p e ) 、生存时间( t i m et ol i v e ) ：最后，增加了两个新的 字段：优先级( p r i o r i t y ) 和流标识( f l o wl a b e l ) 。其次在地址分配上也有了一 些改进。目前i p v 6 的推荐地址分配策略是分配一个4 8 位的地址前缀给国际互 联网的每个站点。4 8 位的地址前缀允许每个站点中6 5 ，0 0 0 个子网，每个子网 2 e h，v4的报头g争n的基本报头 硕士学位论文 能容纳无数台主机。再者，i p v 6 中的i p s e c 是强制实现的，不像在i p v 4 中只 是一个可选的扩展协议。兼之增加了对移动主机的内在支持以及对流媒体的支 持。因此，在几乎无限的地址容量彻底解决了地址枯竭的问题之后，由i p 地址 危机产生和发展起来的i p v 6 作为下一代互联网协议已经得到了各方的公认，未 来互联网的发展离不开i p v 6 的支持和应用，甚至被认为是后起发展网络的国家 追赶“发达”国家的一个良好机遇。由i p 地址危机产生和发展起来的i p v 6 作 为下一代互联网协议已经得到了各方的公认，未来互联网的发展离不开i p v 6 的 支持和应用，甚至被认为是后起发展网络的国家追赶“发达”国家的一个良好 机遇。正因为如此，目前各方面都在加紧对i p v 6 的研究和应用开发。但是，i p v 6 的发展主要得益于政府和厂商两方面的支持。 1 政府支持 许多国家对i p v 6 技术都已经引起足够的重视，并且都采取了一些切实可行 的措施，尤其是一些欧洲国家。作为互联网络的发源地，美国也在积极地进行 i p 、r 6 的研究和建设。中国对于i p v 6 技术的态度是“积极跟踪、把握机遇、稳 妥推进”，并且在部分地区实行了网上实验，如刘东等人积极推动中国i p v 6 的 开展。中国政府密切关注着i p v 6 的发展，目前中国高校和科研机构已经与国外 一些运营商合作，对i p v 6 进行研究实验。并且在日前有消息说，国家发改委划 拨的4 亿元资金和各大运营商配套的l o 亿元资金已经基本到位，中国发展i p v 6 的时间表也将在月内出笼。但是该协议在中国的大规模应用还要有一段时间。 2 厂商支持 i p v 6 作为下一代互联网协议已经引起了各地区、各运营商的足够重视，因 为所有的人都已经认识到这样一种前景：谁能够率先在i p v 6 方面有所作为，谁 就能够在未来的竞争中占住有利位置。在众多的设备提供商和运营商的努力下， i p v 6 协议已经从实验室走向了应用阶段。已有5 0 多个国家和地区加入有关i p v 6 的研究。法、日、美等国的研究机构，i b m 、s u n 、日立等公司，分别研制开发 了不同平台上的i p v 6 系统软件和应用软件；美国思科、加拿大北电网络、n o k i a 等路由器厂商已经开发出了面向i p v 6 网络的路由器产品。操作系统方面，基于 开放源码的l i n u x 对i p v 6 提供了比较强的支持，s u n 、i b m 、康柏、惠普和微软 的最新操作系统都提供了i p v 6 支持。因此，从整体上来讲，i p v 6 的技术已经 成熟，标准也基本完善，一些网络基础设施和核心设备都已陆续开始支持其使 用，但是在具体实施的闯题上，由于经济利益上的关系，在目前还没有普遍推 广，而是处于与i p v 4 相互并存和过渡的阶段。 尽管i p v 6 的地址结构与i p v 4 相比有许多不同之处，但整个地址空间还是 层次性结构，仍然存在类似于i p v 4c i d r 地址结构下的路由合并，i p v 6 路由查 找同样是最长的网络前缀匹配问题，而且i p v 6 使用长度为1 2 8 位的地址，本身 地址宽度的增加使得最长前缀匹配问题变得更加突出。显而易见，处理1 2 8 位 3 基于t i l e 的路由查找算法研究 的i p v 6 地址和前缀所需的访问次数是i p v 4 的数倍，查找速度大大降低。 1 2 路由器的基本原理及体系结构 1 2 1 路由器在i p 网络中的位置 整个i p 网络由许多子网络构成，各个子网络又由许多主机组成。子网内部 的主机通信，由链路协议直接进行；子网之间的主机通信，要通过路由器来完 成。路由器是多个子网的成员，它是互联网的主要结点设备。在它的内部有一 张表示网络i d 与下一跳端口对应关系的路由表。通信起点主机发出i p 包被路 由器接收后，路由器查路由表，确定下一跳输出端口，发给下一台路由器，这 台路由器又转发给另外一台路由器，用这样一跳接着一跳的方式，直到通信终 点另一台主机收到这个i p 包。 按照t c p i p 模型，i p 协议把网络划分为物理层( l 1 ) 、链路层( l 2 ) 、网络层 ( l 3 ) 、传输层( l 4 ) 及应用层( l 7 ) 五个层次。处理物理层的设备为集线器， 处理链路层的设备为l 2 以太交换机，路由器它处模型的网络层，是在网络层转发 数据的设备。l 3 以太网交换机是i p 网络路由器的特例，通常只有以太线路接口， 工作在纯以太网络环境中。与交换机和网桥相比，在实现骨干网的互联方面，路 由器、特别是高端路由器有着明显的优势。路由器高度的智能化，对各种路由协 议、网络协议和网络接口的广泛支持，还有其独具的安全性和访问控制等功能和 特点是网桥和交换机等其他互联设备所不具备的。路由器的中低端产品可以用于 连接骨干网设备和小规模端点的接入，高端产品可以用于骨干网之问的互联以及 骨干网与互联网的连接。特别是对于骨干网的互联和骨干网与互联网的互联互 通，不但技术复杂，涉及通信协议、路由协议和众多接口，信息传输速度要求高， 而且对网络安全性的要求也比其他场合高得多。因此采用高端路由器作为互联设 备，有着其它互联设备不可比拟的优势。 1 2 2 路由器结构体系 图1 2 给出了一般路由器的逻辑体系结构。它主要由下面几部分组成：路 由引擎、转发引擎、路由表、网络适配器和相关的逻辑电路等。转发引擎负责 把从一个网络适配器来的数据包转发到另一个网络适配器出去。i p 协议，包括 对路由表的查找，构成了转发引擎中最主要的部分。由于每个通过路由器并需 要其转发的数据包都要对路由表进行查找，所以路由表的查找效率如何往往决 定了整个路由器的性能。路由引擎则包括了高层协议，特别是路由协议，它负 责对路由表的更新。由于路由引擎不涉及通过路由器的数据通路，故它可用通 用的c p u 代替。 4 硕士学位论文 控 图1 2 路由器的体系结构 路由器的控制平面，运行在通用c p u 系统中，多年来一直没有多少变化。 在高可用性设计中，可以采用双主控进行主从式备份，来保证控制平面的可靠 性。路由器的数据通道，为适应不同的线路速度，不同的系统容量，采用了不 同的实现技术。路由器的结构体系正是根据数据通道转发引擎的实现机理来区 分。简单而言，可以分为软件转发路由器和硬件转发路由器。软件转发路由器 使用c p u 软件技术实现数据转发，根据使用c p u 的数目，进一步区分为单c p u 的集中式和多c p u 的分布式。硬件转发路由器使用网络处理器硬件技术实现数 据转发，根据使用网络处理器的数目及网络处理器在设备中的位置，进一步细 分为单网络处理器的集中式、多网络处理器的负荷分担并行式和中心交换分布 式。 1 2 3 路由器的作用 顾名思义路由器的一个主要作用是选择信息传送的线路。选择通畅快捷的近 路，能大大提高通信速度，减轻网络系统通信负荷，节约网络系统资源，从而让 网络系统发挥出更大的效益来。 从过滤网络流量的角度来看，路由器的作用与交换机和网桥非常相似。但是 与工作在网络物理层，从物理上划分网段的交换机不同，路由器使用专门的软件 协议从逻辑上对整个网络进行划分。例如，一台支持1 p 协议的路由器可以把网络 划分成多个子网段，只有指向特殊i p 地址的网络流量才可以通过路由器。对于每 一个接收到的数据包，路由器都会重新计算其校验值，并写入新的物理地址。因 5 基于c r i c 的路由查找算法研究 此，使用路由器转发和过滤数据的速度往往要比只查看数据包物理地址的交换机 慢。但是，对于那些结构复杂的网络，使用路由器可以提高网络的整体效率。路 由器的另外一个明显优势就是可以自动过滤网络广播。从总体上说，在网络中添 加路由器的整个安装过程要比即插即用的交换机复杂很多。 1 2 4 路由器工作原理 路由表是工作在i p 协议网络层实现子网之间转发数据的设备。路由器内部 可以划分为控制平面和数据通道。在控制平面上，路由协议可以有不同的类型。 路由器通过路由协议交换网络的拓扑结构信息，依照拓扑结构动态生成路由表。 在数据通道上，转发引擎从输入线路接收i p 包后，分析与修改包头，使用转发 表查找输出端口，把数据交换到输出线路上。转发表是根据路由表生成的，其 表项和路由表项有直接对应关系，但转发表的格式和路由表的格式不同，它更 适合实现快速查找。转发的主要流程包括线路输入、包头分析、数据存储、包 头修改和线路输出。 路由协议根据网络拓扑结构动态生成路由表。i p 协议把整个网络划分为管 理区域，这些管理区域称为自治域，自治域区号实行全网统一管理。这样，路 由协议就有域内协议和域间协议之分。域内路由协议，如o s p f 、i s i s ，在路 由器间交换管理域内代表网络拓扑结构的链路状态，根据链路状态推导出路由 表。域问路由协议相邻结点交换数据，不能使用多播方式，只能采用指定的点 到点连接。 1 2 5 路由器性能分析 路由器控制平面部分和数据通道部分对路由器的使用有着不同的影响。在 数据通道上，i p 报文处理能力主要受交换部件的有效带宽和转发部分的处理速 度影响。交换带宽，用技术指标b p s ( 比特秒) 来衡量，一般在纯大包的条件 下测定。转发速度，用技术指标p p s ( 包秒) 来衡量，一般在纯小包的条件下 测定。软件转发单c p u 路由器，交换带宽和转发能力为系统共享，线路卡个数 不同，各线路卡会有不同的性能表现。软件转发多c p u 路由器，转发能力有明 显优势，交换带宽没有明显提高。硬件转发路由器，一般要针对线速进行设计， 系统交换带宽大于各线路接口的总和，转发处理能力在纯小包的情形下也能胜 任，区别的只是容量和价格。线速路由器，保证线路接口在各种情况下能够达 到满速，这时候，是线路而非设备是网络的瓶颈。另外，i p 业务，如a c l ，n a t 、 i p s e c 等，是否造成性能下降，也是设计和使用路由器要考虑的问题。 6 硕士学位论文 1 2 6 路由器性能小结 总之，路由器是一种包交换设备，是构成i n t e r n e t 的核心模块。在定义上 它主要完成两个基本功能：第一，对每一个到达的数据包进行转发决策，路由 器通过在转发表中查找数据包目的地址来完成之一功能。通过查找，路由器将 得到数据包的下一跳路由地址与发送数据包的输出端口，这一查询操作称为路 由查找( r o u t i n gl o o k u p ) 或者地址查找( a d d r e s sl o o k u p ) 。第二，路由器需 要将数据包从输入端口传送到路由查找操作得到的输出端口，这一步称为交换 ( s w i t c h i n g ) ，它是数据包的物理转移。本文所关注的主要是其第一个基本功 能：高速路由查找技术。它从分组头中提取出i p 的目的地址，按照i p 分组中 的目的地址转发分组，查找路由表决定将分组发往哪个端口是分组转发过程的 重要一步，因此快速的i p 路由查找算法是实现高速分组转发的关键。当一个分 组正在查找转发表时，后面紧跟着从这个输入端口又收到另一个分组，这后面 的分组必须在队列里等待。若分组处理的速度跟不上分组进入队列的速度，队 列的空闲存储空间最终必定减少至0 。当没有存储空间时，后面再进入队列的 分组只能被丢弃。因此，路由查找的速度直接影响着报文转发的速度，进而影 响路由器的整体性能。 路由表是不断变化的，比如路由表中的表项可能会被不断地进行增加、删 减。当到达某一网络的最短路径发生变化时，相应表项中的下一跳地址信息也 会发生变化。路由表发生变化时。路由处理器会将这些变化反馈到各转发表中， 以保证转发表于路由表的信息同步。 1 3 路由查找现状 路由查找问题等价于寻找最长前缀匹配的问题，其难点在于不仅需要考虑 与地址前缀相匹配，而且还需要考虑地址前缀的长度。 。 为了提高查表效率，找到最理想的路由器，人们做了许多尝试和研究。根 据其发展历程，最先是线性查找算法。线性表的结构是最简单的查找数据结构， 此方法是把所有的路由地址前缀用线性连标的方式组织起来。每一次查找需要 遍历线性表中的所有表项，遍历过程中记录最长的路由前缀项，直到遍历完整 个线性链表。线性查找算法有内存利用率非常高的优点，这在c i d r 应用初期非 常适用。显然，这种查找算法的复杂度与路由规则的数量成比例，随着路由表 项的增加查找速度变得非常缓慢，因此现在只能应用于网络边缘结点 缓存策略的引入，适当地改善了路由查找的性能。该算法把最近最常用的 地址对应的最长匹配前缀路由规则放在路由缓存表中，只有当路由缓存表中查 找失败的时候，才需要进行完整的最长前缀匹配查找。显然，这种技术的性能 与缓存的大小以及网络流量目标地址的短时分布特性有关。这种技术曾经很好 7 基于耐e 的路由查找算法研究 的满足路由查找问题的需求，然而对于骨干路由器而言，而随着i n t e r n e t 的迅 速发展，网络用户不断增加，网络数据业务量也急剧增加，网络流量目标地址 的短时分布特性逐渐消失，大大降低了缓存的命中率，从而降低了路由查找速 度。为了能够在查找性能上获得较大的提高，缓存的命中率就需要有一定的保 证。但是，对c a c h e 体积的要求使其信价比难以令人接受，教而路由缓存表容 量有限。因此，该方法很难适应未来的发展。 尽管如此，硬件查找仍逐渐成为一个热点研究方向。目前使用最多的硬件 实现方式是使用内容寻址存储器( c o n t e n ta d d r e s s a b l em e m o r y ，简记c a m ) 来 进行快速的路由查找。c a m 能够在一个硬件时钟周期内完成关键字的精确匹配。 c a m 查找效率很高，但是路由条目更新变得十分复杂，比较耗时，且成本很高。 尤其不太适于i p v 6 下的路由查找。 用t r i e 结构来构建路由表示一种常用方法。此算法最基础的是二进制 t r i e 。二进制t r l e 通过前缀中每一位比特值来决定树的分支。但此方法查找 效率仍然不高，在最坏情况下对一个i p v 4 地址查找要访问内存次数为3 2 次。 此后，针对t r i e 的改进算法不断涌现。通过t r i e 结构相关技术构造t r i e 树， 以此t r i e 树为基础进行基于地址前缀值或基于地址前缀长度的查找。此时，在 查找过程中还可以结合路径压缩技术、地址前缀长度扩展技术以及多分支t r i e 树技术来实现路由查找，其优势与不足将在第二章中进行详细阐述。 不容忽视的是，在未来的一段时间内。i p v 6 不可能很快得到彻底的普及。 以后将是i p v 4 与i p v 6 共存的时代。兼容i p v 4 和i p v 6 的高速路由表与网络的 可编程性结合起来，可以方便地从i p v 4 过渡到i p v 6 ，而不是全部更换新的硬 件，是一个i p v 4 升级到i p v 6 很好的解决方案。因此，开发同时支持i p v 4 与 i p v 6 的算法是当前的首要任务。 1 4 路由查找算法的设计标准 路由查找算法的设计标准，这是研究和设计路由查找算法的前提之一。在 评价一种地址查找方案的优劣时。必须综合考虑以下性能。 1 路由查找速度 这是评价一个i p 查找算法的最重要的标准。在算法的时间复杂性上有三种评 价指标：最坏情况、平均情况和统计情况。最坏情况是对一个包进行i p 查找时间 的最坏可能情况。平均情况是指在完全随机的情况下，对一个包进行i p 查找时间 的平均值：统计情况是指在符合某神预先指定的包分布和过滤规则匹配率分布的 假设下，对一个包进行i p 查找时间的期望值。 路由表的查找时间决定了数据包在路由器中的缓冲时间即路由器的时延。 为了转发一个数据包，路由器必须检查输入包的目的地址，从而确定下一跳路 由器地址，并将包发送到下一跳。下一跳路由存贮在由路由协议( 如b 6 p ，o s p f ， 8 颐士学位论文 r i p 等) 创建和维护的路由表中。检查输入包的目的地址并确定下一跳地址的过 程包含了对路由表的查找，路由表的查找时间决定了包在本路由器中的缓冲时 间即路由器的时延。在此过程中可能又有新的数据包到来，当路由器无法缓冲 时导致丢包。所以路由表的查找时间应该尽量短。 路由表查找速度大致决定于找出匹配路由表项所需内存访闯次数和内存的 速度，内存访问次数是用于衡量路由算法性能的一个重要性能指标。查找速度 是决定路由查找算法性能以及路由器处理报文能力的最主要因素。 在保证服务质量的网络中，决策需要在查表以后做出。因查表造成的排队 会影响到服务质量，因此，查找算法应能够实现线速查找。 为了理解高速的查询问题，首先让我们来研究一个高速i n t e r n e t 路由器必 须做的工作实例。它必须以大约l o g b i t s s 的速度处理最小尺寸的报文( 例如， 4 0 或6 4 字节，这取决于链路的类型) ，这要求路由器用3 2 n s ( 对于4 0 字节的 报文) 或5 1 n s ( 对于6 4 字节的报文) 的时间来决定对报文需要做的处理! 参 见表1 1 。( 一般所使用的指标是每秒查找分组数( g g ：) 考虑到各种方案在 测试时所使用硬件不同、测试条件的不同会对测试结果产生很大影响，所以使 用一次查找，特别是最差情况下一次查找需要迸行的存储器访问次数作为衡量 速度的标准更为合理。) 表1 1 查询速度的要求 y e a rl i n e4 0 bp a c k e tm p k t s 1 9 9 76 2 2 m b s 1 9 4 1 9 9 9 2 5 g b s 7 8 l 2 0 0 l l o g b s 3 1 2 5 2 0 0 34 0 g b s 1 2 5 2 路由表项的速度 报文转发方案中两个重要的标准是最大连续包转发速率和路由表大小，最大 的连续和突发( b u r s t ) 性路由表更新速率、路由表更新时延和路由表的可用性不 十分明显，但对路由器的性能一样至关重要。路由表更新时延之所以重要，因为 、它反映了网络的拓扑结构，当网络拓扑结构发生变化时，数据包在路由表更新之 前可能走的是非最优化路径，从而导致短暂的延长包迂回时间和增加丢包率。更 新速率是至关重要的，当路由器不能维持所有更新时，会引发所谓的路由拍打风 暴( r o u t ef l a ps t o r m ) ，在这种情况下，一台路由器得到的路由更新信息被另外 一台路由器标记为网络不可达。这种状态变化导致路由更新上的多米诺效应，而 降低网络性能。最后，如果路由表因为更新原因两不可用，输入包将被缓冲或丢 弃。因为路由不可用而丢弃t c p 包时，触发t c p 拥塞预防机制，从而降低稳定状态 时的吞吐率和整个网络的性能。 基于这些标准，理想的包转发方案必须能够支持链路数据速率，而且必须足 够大，以容纳下一代路由设备的路由表( 边界上多达5 1 2 k 条路由) 。同时，它必须 9 基于c r i c 的路由查找算法研究 能用最短时延处理路由更新的突发延长。虽然顺序路由更新一般每秒产生几百 次，而短暂的突发更新却以更高速率发生。例如，关于i n t e r n e t 核心的稳定性研 究表明，在每6 小时期间，有超过3 千万次路由更新，平均每秒接近1 3 0 0 次，完全 有理由相信，当连接到i n t e r n e t 的主机数增加时，突发更新将超过每秒几千次。 路由信息的变化所引起的查找性能的下降应尽可能的小。由于i n t e r n e t 路由 的不稳定性，路由表必须定期更新。算法的更新速度是算法应用场合的重要判据 之一。研究表明，主干网路由器表项更新速度很快，可以达到1 0 0 次秒。路由表 频繁的更新，要求查表算法必须能够动态插入删除表项；同时，为了不影响查 表操作，插入与删除时间应该在尽量短的时间内完成。更新过程分两步：第一步 是查找结构树找到相应的结点。但由于一个规则可能存于多个叶子结点，使得更 新过程的第一步所需时间可能比识别一个包的第一步所需时间长；更新过程的第 二步是更改所查到的叶子结点内的规则，这儿有三种情况：叶子结点为空。对增 加规则，则直接创建一个新的叶子结点；对删除规则，则证明没有要删除的规则， 删除过程结束。叶子结点内已有的规则数小于最大值。对增加规则，则直接根据 规则的优先级添加；对删除规则，则在该结点内线性查找完全相同的规则，有完 全相同的规则就删除之，再检查该结点的规则数是否为0 ，为o 则把该结点也删除， 若没找到完全相同的规则，则删除过程结束。叶子结点内已有的规则数等于最大 值。对增加规则，则需以该结点为根结点创建新的子树，这是更新的最坏情况； 对删除规则，则只需线性查找完全相同的规则，有则删除之，无则结束删除过程。 以上三种情况都设计到对叶子结点内所有规则的检测，再更改原结点或创建新的 结点，故需要较长时间，是算法更新速度的决定量。 3 路由表容量以及支持的表项个数 路由表容量，即指路由器运行中可以容纳的路由数量。 首先，大容量的路由表直接要求消耗大量的存储空间，即空间复杂度较高， 这关系到路由器的成本。i p v 6 采用1 2 8 位地址，路由表占用空间在容量不变时 要增大到原来的4 倍，而a s i c 中的硬件转发的路由表存储在a s i c 专用的地址 空间中，硬件地址表空问很有限，一般情况下也就在几十k 的水平，因此a s i c 平台在i p v 6 的环境中，如果保持i p v 4 一样的地址表空间将会大大提高成本， 因此硬件在设计上需要尽量节省私有空间大小而提高路由表容量。在实际的应 用环境中，在过渡期，设备往往运行在双栈环境下，同时面临i p v 6 和i p v 4 的 路由表需求，因此对地址空间的要求将大于目前的纯i p v 4 环境。 其次，不管目前存储器的技术如何，路由器的存储系统总是要求算法占用 的存储容量应该尽量小，从而可以为算法的实现带来更大的灵活性，存储空间 小的算法可以考虑使用较为昂贵但是速度较高的存储器，例如使用c a c h e 或者 片上静态随机访问存储器( o n - c h i ps r 删) ，这些都能提高算法运行的速度。因 此，对骨干路由器，至少支持5 0 k 个表项。在此前提下，尽量减少所需要的存 l o 硬士学位论文 储器容量。 基于以上这三个标准，理想的包转发方案必须能够支持链路数据速率，而 且必须足够大，以容纳下一代路由设备的路由表( 边界上多达5 1 2 k 条路由) 。同 时，它必须能用最短时延来处理路由更新的突发延时。 4 算法实现的灵活性 路由查找算法可以软件实现，也可以硬件实现。因此，从查找算法的实现灵 活性上考虑，我们希望算法能够同时具有软件和硬件实现方式。在未来的几年中。 报文处理速度需要达到一个相当高的水平，硬件实现将是路由查找引擎的主要 实现方法。我们综合多种算法的优点提出的可配置的路由查找算法就具有实现 灵活的优点。 5 算法的可扩展性 在未来的几年中，新一代的i n t e r n e t 协议i p v 6 将会逐渐替代目前使用的 i p v 4 协议，因此，在设计过程中需要考虑到算法的可扩展性，算法是否能够适用 新的网络环境已经成为未来查找算法研究的重点之一。也是本文的研究重点。 总之，路由表的动态更新开销与静态查找速度、查找速度与所需存储器容 量之间的矛盾是各种快速路由查找方案应处理的两对主要矛盾。因此一个好的 路由查找算法应该可以在其中作适当的调节，选择一个较好的平衡点。 1 5 本文的意义 由于现有的路由查找算法在实现查找的时间复杂度、空间复杂度以及插入、 删除和更新路由时或多或少地存在着矛盾，实现了快速查找却增加了空间复杂度 的需求，减小空间复杂度的需求却增加了插入、删除和更新的难度。本课题力图 在这三者之中寻求一个较好的平衡点。 在本文中，设计了一种适合i p v 6 的路由查找方案，并且兼容现有的i p 、r 4 网络。其主要特点如下： v 兼容i p v 4 、i p v 6 网络。 v 基于t r i e 结构特点，便于实现。 丫路由信息进行更新时，不需要重新构建路由表。 1 6 本文的内容安排 第l 章是绪论。首先介绍了路由查找算法产生背景，分析了国内外在i p 路由 查找技术领域的研究状况，给出了算法设计标准，概括了本文的研究意义，最后 描述了本文的组织结构。 第2 章对传统路由查找算法按照软件与硬件两个方面进行回顾与归纳，尤 其对基于t r i e 的路由查找算法进行了详细的分析，通过对算法的性能分析，指 出了路由查找算法的优势与不足，并对i p v 4 向i p v 6 扩展时的使用限制予以说 堆叶二t r i e 的路由查找算法研究 明。 第3 章提出基于t r i e 的新型算法。该算法基于最长前缀匹配，其查找速度 较快，对于路由表的更新操作，不需要重新构建路由表。t r i e 树中的某些结点， 包含两条路由信息，节省了存储空间。在每一步算法中，为了方便理解，给出 实例。 第4 章是结束语。包括对全文工作的总结和对未来工作的展望。 1 2 硬+ 学位论文 第2 章常用路由查找算法总结 2 1 发展前由 在i n t e r n e t 发展初期，使用3 2 比特( 4 字节) 长的分类i p 地址( i p y 4 ) 。 即把i p 地址简单地划分成a 、b 、c 、d 、e 五类。在这五类中，d 类用于组播， e 类保留为今后使用，常用的单播i p 地址主要是a 、b 、c 三类。分类i p 都由 两个固定长度的字段组成，即i p v 4 地址= ，且各个类之间 通过地址前几个比特位来区分。如图2 1 所示。 a 类地址l b 类地址： c 类地址： d 类地址： e 类地址 图2 1 五类i p 地址比较 此时的路由器为转发分组而查找路由表时主要利用i p 地址中的网络i d 来 查找目的网络。在i n t e r n e t 发展初期，这种基于类的地址结构由于其简单性而 得到了广泛的应用。 i p 地址的编址方案使用类的概念。通过图2 1 可以得出常用的a ，b ，c 类网 中，a 类网络具有最大的规模，每个网络可具有2 “- 2 = 1 6 7 7 7 2 1 4 台主机，适用 于大型网；当地址的第一位为“0 ”时表示为a 类网络。每个b 类网络可具有 2