（通信与信息系统专业论文）基于tcam的多下一跳路由并行查找的方法.pdf

摘要 摘要 i n t e m e t 的规模迅速扩大，业务种类越来越多，对网络带宽的需求不断上升， 但路由及数据分组转发技术却滞后于i n t e m e t 的发展。路由器已经成为制约 i n t e m e t 高速发展的主要因素。路由表作为路由器的一个核心部件，其查询速度 对路由器的性能有至关重要的影响。目前，路由查表速度已经难以适应不断增 长的链路速度和路由表的增长速度。为了实现负载平衡以及策略路由，路由表中 保存了相当数量的具有多个下一跳的路由表项。多下一跳路由的存在是i n t e m e t 路由表的重要特征之一，它增加了路由查找方案设计的复杂度。研究人员已经 提出了很多路由查找算法，但普遍都是针对单一下一跳路由的方法。本文主要 是围绕如何快速查找具有多个下一跳的路由展开的。 论文分析了当前路由器的应用以及发展趋势，进而对影响路由器性能的几 个方面进行了归纳，总结了路由查找面临的问题及难点，介绍了现有的高速路 由表查询算法，并对它们进行了详细的研究和比较。在此基础上提出了基于 t c a m 的多下一跳路由的并行查找方法。该方法采用前缀扩展技术，减少了前缀 长度种类；使用多个t c a m 芯片并行查找，提高了查找速度；调整表项数据结构， 使得表项阵列免排序；循环往复查找，充分利用了t c a m 资源。为多下一跳路由 查找提供了一种新的解决思路。 按照方法的设计思想，通过v h d l + f p g a 在m o d e l s i m 平台实现了功能仿真， 完整再现了方法的路由更新和匹配查找过程。在更新过程中，对前缀需要扩展、 前缀无需扩展和多下一跳路由的更新进行了模拟。查找过程中，对单一下一跳 及多下一跳路由的查找都进行了仿真。测试结果表明：该方法各模块的设计在 速度和资源利用方面均达到了要求，在功能上也满足了对路由更新、查找的需 要。 在总体设计与仿真实现的基础上，对其匹配结果的正确性进行了证明。并 且对前缀扩展实施中的步长选取问题进行了研究，给出了扩展前缀情况下最优 步长的选择公式，通过程序计算选定扩展步长及采用t c a m 芯片的个数。针对路 由更新问题，与传统路由查找算法进行了性能比较分析。 论文最后对本研究进行了总结，并指出继续研究改进的方向。 关键词：最长前缀匹配路由查找路由更新多下一跳t c a m a b s t r a c t a b s t r a c t t h ea b i l i t yo fp a c k e t sp r o c e s s i n g & f o r w a r d i n gi nr e u t e r sc a l ln o tk e 印u pw i m t h ed e v e l o p m e n to ft h ei n t e r n e t ，w l g c ha r ee x p l o s i v eg r o w t h ，o fw h i c haf a rm o r e b a n d w i d t hi si nd e m a n d t h u s t h ep e r f o r m a n c eo fr o u t e r sh a sb e c o m et h eb o t t l e n e c k o ft h e n t e m e t a st h ec o r ec o m p o n e n to far o u t e r , t h es p e e do ft h et a b l el o o k u p m o d u l eh a sm u c he f f e c to nt h er o u t e r sp e r f o r m a n c e f u r t h e r m o r e ，f o rl o a db a l a n c i n g a n dp o l i c yr o u t i n g r o u t e r sh a v et oh o l dc o n s i d e r a b l er o u t e s 晰t hm u l t in e x th o p s v a r i o u sa l g o r i t h m sf o rh i g hp e r f o r m a n c ei pa d d r e s sl o o k u ph a v eb e e np r o p o s e d ，b u t m o s to ft h e ma r eb a s e do ns i n g l en e x th o p i nt h i sd i s s e r t a t i o n , af a s tr o u t i n gl o o k u p s c h e m eh a sb e e np r o p o s e d ，i nw h i c hm u l t in e x th o p sc a nb ef e n d e di np a r a l l e l f i r s t ，t h ed i s s e r t a t i o na n a l y z e s t h e d e v e l o p m e n t 订e n d e n c y o nt h er o u t e r s p e r f o r m a n c ea sw e l la st h ed i f f i c u l t i e so fm u t i n gl o o k u p a n dp r e s e n t sas u r v e yo f l o o k u pa l g o d t h r n sc o m m o nu s e d ，t h e nm a k e sac o m p a r i s o n i nd e t a i l s t h et e c h n i q u e so ft h er o u t i n gl o o k u ps c h e m ew h i c hs u p p o r t i n gm u l t in e x th o p s a r ei n t r o d u c e di nc h a p t e r3 t h e r ea r et h r e em a i nt e c h n i q u e su s e di nt h es c h e m e p r e f i xe x p a n s i o n , p a r a l l e lt e a ms e a r c h i n gm a dn oe n t r ys o r t i n g i tg i v ea nn e we y e o nr o u t i n gl o o k u p nc h a p t e r4 ，t h ef u n c t i o n so ft h es c h e m ed e s c r i b e di nv h d la r es i m u l a t e do n t h em o d e l s i mp l a t f o r m t h em a t c h i n gp r e c e e d sa n du p d a t i n gp r e c e e d sa r et e s t e dw i t h i pp a c k e t sa n dr o u t ee n t r y sr e s p e c t i v l y t h en oe n t r ys o r t i n gm e c h a n i s mi sp r o v e di nt h e5 t hc h a p t er t h ee q u a t i o no f b e s ts t e pl e n g t hs e l e l c t i o ni np r e f i xe x p a n s i o ni sd e d u c e d ，a n dt h en u m b e ro ft e a m c h i p si sg e n e r a t e db yu s i n gt h ee q u a t i o n c o m p a r i n gt o t h eu s u a la l g o r i t h m si n u p d a t i n gp e r f o r m a n c e ，t h ef i g u r e ss h o wt h a to u rs o l u t i o ni sm o r ea t t r a c t i v e t h es t u d yi ss u m m a r i z e da n ds o m ep o s s i b l er e s e a r c hf i e l d s i nt h e f u t u r e a r e i n d i c a t e da tt h ee n do f t h ep a p e r k e yw o r d s ：l p m ( l o n g e s tp r e f i xm a t c h i n g ) r o u t i n gl o o k u pr o u t i n gu p d a t e m u l t in e x th o p s t e a m ( t e m a r yc o n t e n ta d d r e s s a b l em e m o r y ) i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：倪饫h2 虱 训5 年r 月修日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：倪扳f f f 及 沙秒s 年s 月，日 第一章引言 第一章引言 第一节in t e r n e t 发展概况 随着通信与计算机技术的飞速发展，i n t e m e t 规模不断扩大。图1 1 给出的 是从1 9 9 4 年1 月到2 0 0 5 年1 月i n t e r n e t 入网主机数的增长曲线”1 1 2 1 ，预计到 2 0 0 6 年入网主机总数将会突破3 5 0 ，0 0 0 ，0 0 0 台。 i n t e r n e t 入网主机数量调查 3 5 0 ，0 0 0 ，0 0 0 3 0 0 ，0 0 0 ，0 0 0 2 5 0 ，0 0 0 ，0 0 0 2 0 0 ，0 0 0 ，0 0 0 15 0 ，0 0 0 ，0 0 0 10 0 ，0 0 0 0 0 0 5 0 , 0 0 0 0 0 0 0 可 卜 口 一 n n可 田 口口t ：a口。口 士士士士士士占圭 圭叁 士士 叮 叮 叮叮 d叮叮叮a叮叮叮 11 1 1 _ 丁1 1 1 1 数据来源：i n t e r n e ts o f t w a r ee o n s o r t i u m 【w w w i s c 0 r g l 图1 1i n t e r n e t 主机增k 曲线图 ，伴随着网络规模的飞速增长，互联网络上的业务种类也越来越多。传统的 数据通信、e - m a i l 、w w w 业务向集音频、视频数据为一体的多媒体方向发展， 使得i n t e m e t 的流量以每年4 倍的速度递增( 图1 2 ) ，预计2 0 0 6 年，骨干节 点的流量可以达到1 0 0 t b p s 3 。但也正是这种高速的增长，使得当前的互联网陷 入了日u 所未有的困境：i n t e m e t 骨干网持续地面l 临来自向客户提供更快的反应时 间和更高的可靠性方面的压力的同时，路由及数据包转发技术却滞后于i n t e m e t 的发展。事实上作为网络世界的交通中枢，路由器已经成为i n t e m e t 高速发展的 瓶颈。 路由器本质上是一台特殊的专门执行报文转发和协议处理的计算机。它主 要负责连接多个网络，这些网络可能是同构或异构的。由于在两个不同网络的 网络层之间按报文传输时，需要改变两个不同类型网络报文中的第二层地址， 即决定在网络之间数据传输时的路由去向【4 】，所以需要对经过路由器的每一个数 第一章引言 据分组进行拆解包头、寻址、数据重组以及转发。这一处理过程所造成的时延 是导致网络性能下降的主要原因之一。因此，如何提高路由器处理速度，加快 路由寻路能力，使大量的数据分组能够及时得到转发，尽可能地减小传输时延 是i n t e m e t 网络发展面临的一个重要课题。 圈1 2i n t e r n e t 流量趋势图 第二节提高路由器性能的常用方法 路由器工作在o s i 参考模型的网络层，它对i p 数据包进行灵活的路由选择， 然后逐段地向目的地址转发。它掩盖了下层网络的细节，使各类网络都在i p 上 达到统一。 虽然路由器可以支持多种协议( 例如t c p i p 、 p x s p x 、a p p l e t a l k 等协议) ， 但是目前绝大多数路由器运行t c p i p 协议，本文中数据分组均指i p 数据包。 图1 _ 3 是路由器的结构简图1 5 j 。它一般由四个部分组成：输入端口，输出端 口，交换结构，以及路由处理器。输入端口与物理链路相连，是到达分组的入 口点；交换结构负责连接输入和输出端口；输出端口对分组进行发送调度；路 由处理器运行路由协议，并产生转发表用于分组转发。 2 第一章引言 图1 3 路由器结构简图 路由器内的数据分组交换过程是一个数据密集型的操作，c p u 、总线性能、 存储器访问速度、路由处理等多方面都对这一过程的性能有很大的影响 ”。为了 克服瓶颈，人们曾经尝试过很多种方法，目前主要采用以下几项的技术来对路 由器进行改进： 一、硬件功能实现 高速路由器将路由计算、控制等非实时任务同数据转发等实时任务分开，由 不同部分完成。路由计算、控制等非实时任务由c p u 运行软件来完成，数据转发 等实时任务由专门的a s i c 硬件来完成。与软件执行相比，a s i c 的性能是后者 的3 倍。但是全硬件化的路由器使用起来缺乏灵活性，具有一定的风险。 二、并行分布处理 最初的路由器采用了传统计算机体系结构，一颗c p u 完成所有的任务，从 而限制了系统的吞吐量。另外，系统容错性也不好，c p u 成为系统的单故障点， 若c p u 出现故障，则导致系统完全瘫痪。现代的路由器对报文转发采用并行、 分布式处理，做到在每个接口处都有一个独立c p u ，专门单独负责接收和发送 本接口数据包；管理接收发送队列；查询路由表并做出转发决定等【4 。 三、采用交换结构 在交换结构设计中，采取巨型计算机内部互连网络的设计或引入光交换结 构，以替换易造成拥塞的共享式总线【_ ”。通过核心交换板实现板问无阻塞交换， 即一个板上输入的报文经过寻路后可以象通过导线直连那样，被交换到另一个 板上输出。采用交换结构，系统吞吐量可以成倍扩充。 四、快速路由查寻 路由查找问题不仅仅是衡量高性能路由器性能的一个重要指标，而且也是 第一章引言 影响i n t e m e t 可伸缩性和稳定性的重要因素，同时也是高性能路由器设计的一个 难点。e l 前大部分路由器采用d r a m 来存储路由表，存储器的访问速度提升缓 慢以及路由表的持续增长导致了路由表查找速度无法满足带宽增长的需求。所 以需要寻找新的技术来提高路由表查找速度。研究人员提出了许多新的路由查 找方案，目前业界普遍认为最为有效的解决办法是采用专门的协处理器结合内 容可寻址存储器( 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 ) 悼j 来完成快速路由查找或 更新。 本文对快速路由查寻技术进行了研究，详细分析了以往路由查找算法的优 点及其不足，提出了一种新的路由查找方法，从而从路由表的快速查找角度实 现了对路由器性能的改进。 第三节多下一跳路由的并行查找方法 基于软件的路由查找算法，执行速度慢，而且与路由表的大小相关联；路 由表的更新花费时间长，降低了路由器的性能。采用c a c h e 技术可以提高路由 表的访问速度，但却无法解决策略路由以及负载均衡等问题。此外，多下一跳 路由的存在是i n t e m e t 路由表的重要特征之一，它增加了路由查找算法设计的复 杂度。而现有的路由查找技术，普遍都是针对单一下一跳路由的方法。本文基 于c a m 技术，提出了一种支持多下一跳路由查找的并行查找方法。该方法采用 | j 缀扩展技术，减少前缀长度种类；多个t c a m 芯片并行查找，提高查找速度； 调整了表项数据结构，使得路由表项存储过程免排序；循环往复查找，充分利 用了t c a m 资源，实现了路由的高速且支持多下一跳的匹配查找。该方法具有 简单、灵活、高效等特点。由于采用了多个t c a m 芯片，增加了关键部件的冗 余度，提高了该方法应用在工程上的稳定性。 第四节论文导读 本文从介绍了当前路由器的应用以及发展趋势入手，对提高路由器性能的 几项技术进行了阐述。针对快速路由查找方法进行了研究，提出了一种多下一 跳路由的并行查找方法，提高了路由查找性能。 第二章首先介绍了高速路由表查找算法的研究背景、面临的问题以及评价 准则，在此基础上调查了现有的查表算法，并对此进行了比较、总结。 4 第一章引言 第三章分析了i n t e m e t 路由表的多下一跳特点，提出了基于t c a m 的多下 - - 9 9 6 路由的并行查找方法。对设计思想、整体设计进行了详述，并通过实例介 绍了路由查找及路由更新。 第四章通过v h d l + f p g a 对方法进行了功能仿真，在m o d e l s i m 平台上完 整再现了路由更新和匹配查找的过程。 第五章对方法的正确性进行了证明，并且对前缀扩展实施中的步长选取问 题进行了分析，给出了扩展前缀情况下最优步长的选择公式，通过程序计算选 定了扩展步长及采用t c a m 芯片的个数，最后针对路由更新问题与传统路由查 找算法进行了性能对比分析。 第六章对本文所作的研究工作进行了总结，并对相关后续研究工作进行了 展望。 5 第二章路由查找技术 第二章路由查找技术 第一节研究背景 2 1 1 地址结构的发展变化 i p v 4 为目前i n t e r n e t 上广泛使用的i p ( i n t e m e tp r o t o c 0 1 ) 版本。它的地址 为3 2 b i t s ，分为网络号( n e t i d ) 和主机号( h o s f i d ) 两个部分，用( n e t i d ，h o s t i d ) 表示。 其中n e t i d 表示一个网络，h o s t i d 表示该网络中的一个主机，同属一个网络中的 主机应该具有相同的n e t i d 和不同的h o s f l d 。在口协议最初提出的时候采用的 是基于类的地址结构，后来为了解决地址利用效率低和路由表膨胀太快的问题， i n t e r a c t 工作组i e t f 于1 9 9 3 年9 月提出了无类域问路由( 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 ，c i d r l 概念【9 j ，这一变化解决了地址利用效率低的问题但却增加了查 表问题的复杂性。 2 1 1 1 基于类的地址结构 基于类的地址结构把i p 地址划分为5 类：a 、b 、c 类用于单播业务，d 类 用于组播业务，e 类保留给其它应用。地址所属的类别通过i p 地址的最高几位 来区分。各类单播地址的n e t i d 和h o s t i d 位数都不同，因此不同地址类型的网络 能容纳的主机数也不相同。如表2 1 所示。 表2 1 基于类的地址划分 ，粤童，类熏墨最高e 臻媾= -曩量n 融避，囊| 蔓褰譬葚凼翻j i 萎黧i ；蒸| 萋翟掣8 蠢曼j6 i 滋i 纂囊i ： 鞠曩，：ai 0b i t s l - 7b i t s8 3 10 0 0 0 一l2 7 2 5 5 2 5 5 2 5 5 - i 譬b 毳臻嚣 1 0b i t s2 一1 5b i t s1 6 3 l1 2 8 0 0 0 1 9 1 2 5 5 2 5 5 2 5 5 _ z ：g ”m1 1 0b i t s3 2 3b i t s2 4 3 11 9 2 0 0 0 - 2 2 3 2 5 5 2 5 5 2 5 5 曩嘲播) i 1 1 1 0 2 2 4 0 n o - 2 3 9 2 5 5 2 5 5 2 5 5 。t ( 豫留磁j 1 1 1 1 02 4 00 0 0 2 5 5 2 5 5 2 5 5 2 5 5 随着i n t e r n e t 的发展，这种地址分配方式存在的问题逐渐暴露出来： 第一个问题是i p 地址空间消耗太快。造成这一问题的原因在于按照 n e t i d h o s t i d 长度固定来分配网络地址的方法极不灵活，导致i p 地址的浪费。 例如，如果一个组织要申请多于2 5 4 个i p 地址，该组织就会被分配一个可以容 纳6 5 5 3 4 个主机的b 类网络号。到1 9 9 2 年2 月，1 2 6 个a 类地址已经分配了 6 第二章路由查找技术 4 6 个，1 6 3 8 2 个b 类地址也分配了5 4 6 7 个；而到1 9 9 3 年1 月，分配的a 类 地址已达到5 2 个，b 类地址达到7 1 3 3 个。按照这种速度，当时预计在1 5 个月 内，所有的b 类i p 地址将被耗光，尽管实际使用的i p 地址还不到1 1 1 0 1 1 1 1 1 。 第二个问题是路由表的大小呈指数增长。这是由于路由器需要为每一个网 络号保存一个表项，导致了l p 路由表的大小增长过快。路由表过大对处理器的 处理能力和存储容量带来很高要求，同时它使得路由表查找速度变慢。 2 1 1 2 无类域问路由 为减缓骨干路由表的增长速度，提高i p 地址空间的利用率，i n t e m e t 工作 组提出了无类域间路由技术。在分配地址时网络号不再限制为7 、1 4 或者2 l b i t s ， 可以为任意长度。c i d r 的网络号用i p 前缀( p r e f i x ) 表示，前缀的有效长度可以 从0 到3 2 b i t s ( 实际中最短的前缀长度为8 b i t s l l 2 1 ) 。i p 前缀的表示方法为 p r e f i x l e n g t h ，其中p r e f i x 为主机地址或者网络号，l e n g t h 为前缀的长度。例如， 8 8 9 2 1 9 7 8 3 2 为3 2 b i t s 网络前缀，2 0 2 1 1 3 0 0 1 6 为1 6 b i 招的网络前缀。采用c i d r 技术后，如果一个机构需要申请3 0 0 个口地址，可以为该机构分配2 3 b i t s 的网 络前缀，从而使i p 地址的分配更为合理有效。 变长网络前缀的采用使得口地址的层次化分配成为可能。连接到i n t e r n e t 骨干的i s p 首先申请较短的网络前缀，然后在该地址空间内向更小的1 s p 或者 机构分配更长的网络前缀。i p 地址的层次化分配使得i s p 在向更高层发布路由 信息时可以对该信息进行聚合。图2 1 显示的是地址聚合示例。 r 1 的路由衷 1 9 2 2 0o ，2 2 r 2 2 0 0 1 1 0 0 2 2 r 3 s n es 1 9 2 2 1 0 2 4 p 文、熙 固崎照 骨干 阿 ) 镕；r 1r 3 d g l i 竺s “兰e 竺t j i 图2 1 地址聚合示例 7 嚣一 ， 2荨 第二章路由查找技术 在图中，s 和t 连接到i s pp 。分配给i s pp 的网络前缀为1 9 2 2 0 0 2 2 ，在 这一区间内，p 向s 分配了前缀1 9 2 2 1 0 2 4 ，向t 分配了前缀1 9 2 2 2 0 2 4 ，这 样在p 的节点r 2 向骨干网发布路由信息时，只需要发布表项1 9 2 2 0 0 2 2 。地 址聚合使得骨干网络上的路由信息大大减少f 1 ，据统计在采用c i d r 之后的 1 9 9 4 1 9 9 8 年间，路由表的增长趋势接近线性，而不是在这之前的指数关系【4 j ， 有效地减缓了路由表增长的速度。 采用c i d r 之后，路由转发表的基本形式为 。 如果网络前缀的有效位与目的i p 地址的这几位相等，则称目的l p 地址与该网络 前缀匹配。这样，查表的过程就变成了寻找匹配路由表项的过程。 2 1 2 查找技术面临的问题 2 1 2 1 链路速率飞速发展 物理链路速率的提高要求路由表查找速度也要相应提高。在给定链路速率 情况下，一般考查以下两种查表速度：一种是按照i n t e m e t 最短分组长度和最坏 情况下的查表速度；另一种是按照平均分组长度的平均查表速度。其中前者一 般是对具有流识别能力、支持实时业务的系统的要求，以保证所要求的分组延 时等性能。在i n t e m e t 的网络流量中，仅t c p 回应报文( 2 0 字节的i p 头+ 2 0 字节t c p 头，计4 0 字节) 就占4 0 左右，因此对第一种情况要求按分组长度 4 0 字节计算1 1 5 j 【1 6 】【1 7 1 ，对o c l 9 2 链路接口来说最坏情况下的查询速度需要达 到31 2 5 m p p s ( p a c k e t sp e rs e c o n d ，分组，秒) 。对不提供流识别的系统，由于分 组可以在查表之静被适当地缓存，因此可以按照平均分组长度和平均查表性能 来计算。假如平均分组长度为2 4 0 字节，对o c 1 9 2 接口，平均查表速度只要达 到5 2 1 m p p s 即可。表2 2 给出了查表性能与链路速率和分组长度之间的关系。 表2 2 各种链路下的线速查表速率要求 链路速攀4 d 字节分筮8 4 字节分组2 4 0 字节分组 链路 ( g b p s )( m p p s )( m 瞪)( m p 雕) 薯：| 1 未，t l ，、笋 o 0 0 1 50 0 0 4 6 80 0 0 2 20 0 0 0 7 8 o c - 3 豫 i0 1 5 50 4 80 2 30 0 8 ：i ；| ：j i 【) l ( 薯l 磐掣。羹0 6 2 21 9 4 o 9 2 o 3 2 3 。鼍 j o 够；_ 燕器i 2 5 0 7 8 1 3 7 21 3 j 叠o c - 1 9 ! i j ： l o o3 1 21 4 95 2 1 燃o 7 甜薯一 4 0 o1 2 5 05 9 52 0 8 4 臻平兆跳窳网一 1 o1 4 90 5 2 8 第二章路由查找技术 上表中千兆以太网的接口与其它类型的接口不大相同，主要原因在于以太 网的最小帧长为6 4 字节，加上2 0 字节的前导码和分组问隙，共计为8 4 字节。 因此对于6 4 字节的千兆以太网分组，实际的传输速率仅为7 6 2 m b p s ，所以要求 的查表速率为1 4 9 m p p s t ”j 。 制约路由表查找速度的最大问题是存储器的访问时间。由于路由表越来越 大，静态r a m 的存储容量相对较小，价格偏高，因此目前大多采用d r a m 来 存储路由表。访问一次d r a m 按照5 0 n s 计算，对于o c 1 9 2 接口，即使按照平 均分组长度计算，查表速率也要达到5 2 1 m p p s ，相当于1 9 0 n s 必须完成一次查 找动作，这样最多只能读三次存储器【1 2 1 。因此设计查表算法时需要尽量减少存 储器的访问次数，以提高查询速度。 2 1 2 2 路由表增长迅速 越来越多的网络设备接入i n t e r e n t ，维护这些设备间可达性信息的路由表也 在不断增长。为了减轻骨干网络路由表增长的压力，人们使用c i d r 、网络地址 转换( n e t w o r ka d d r e s st r a n s l a t i o n , n a t ) 等技术来允许在两个不同的网络地址域 问进行一定的透明交互。然而这并没有停止路由表的增长，因为路由受网络拓 扑结构、自治系统个数以及个路由表项覆盖的地址数目等综合因素影响。当 一个网络向外部路由域广播路由更新信息时，这个路由项就会在整个i n t e m e t 的 所有外部路由域间传播。图2 2 为i n t e m e t 骨干网络路由表增长统计曲线f l ”。 图2 21 9 8 9 2 0 0 5 骨干网路由表大小增长曲线 9 第二章路由查找技术 目前骨干网络路由表已经达到2 0 0 ，0 0 0 项，而且还在继续增长。从图上可 以把整个路由表的变化分为4 个阶段： 1 、没有使用c 1 d r 以前的增长 从1 9 8 8 至1 9 9 4 年4 月，路由表明显呈指数增长。增长的主要原因是使用 了大量的c 类地址( 2 4 位前缀) 。这种增长速度大大超过了当时所用网络硬件和 软件的性能增长速度。 2 、c i d r 的使用 使用c i d r 的一个目的就是提供路由聚合。i s p 从i n t e m e t 地址注册机构申 请一个地址块，并把这个地址块向外部路由域广播。服务商的客户又从该地址 块中得到更小的地址( 这罩说的小地址是指前缀长度更长的地址，也就是更加明 确的地址) ，这些小地址并不直接在i n t e r n e t 上传播，而是经过服务商聚合以后才 广播出去。在1 9 9 4 年间，聚合的使用使整个路由表的容量一直持续在2 0 0 0 0 条 左右。 3 、c i d r 后的增长 从1 9 9 4 年一直到1 9 9 8 年初的4 年中，路由表的增长放慢了速度，呈线性 增长。每年大概增加1 0 0 0 0 条，在1 9 9 7 到1 9 9 8 年甚至还低于线性增长。使用 聚合和c i d r 使路由系统的稳定性增强。在一个网络边缘的不稳定性不会很快传 播给路由核心区，路由的不稳定在最后一跳被聚合点吸收了。c i d r 的使用在一 定意义上消除了网络的动态不稳定性。 4 、现在的增长 在1 9 9 8 年底，路由表的增长又开始变得激进起来了，最近几年所观测的数 据表明，路由表容量又有呈指数增长的趋势。这表明，c 1 d r 已经不能跟上i n t e r n e t 快速增长的步伐。如果按这种形势发展下去的话，路由表的增长速度又将会超 过硬件提高的速度。 如何应对路由表的动态增长成为路由查找所面临的最大难题。一方面在庞 大的路由表中，数据的时问局部性变得越来越不明显，待查找集合的持续增大， 降低了c a c h e 的命中率，使得以往在计算机领域发挥得淋漓尽致的c a c h e 技术 在这里不能完全奏效。另一方面新的路由查找方案要能够适应路由表的增长， 并且做到与路由表的大小不相关联，否则路由查找将会随着表项的增长，速度 越来越慢。 1 0 第二章路由查找技术 2 1 2 3 最长前缀匹配复杂 在基于类的地址结构下，路由器按照地址的不同类型( a ，b ，c 类) 把 路由表分成三个部分。如图2 - 3 所示，路由器收到分组后，首先通过目的地址 的高位判断分组所属类别，以决定采用哪个转发表，然后用n e t i d 在相应的转发 表中进行精确匹配。由于同一表项的n e t i d 长度固定( 对a ，b ，c 类地址分别为7 ， 1 4 和2 1 ) ，因此精确匹配可以通过h a s h 算法或者是其它一些快速查找算法柬实 现【2 0 】【2 ”。但是基于类的地址结构使得路由表呈指数次方飞速增长，以至于为了 降低路由表增长的速度，人们不得不放弃这种精确匹配结构。 转发表 笕“兰 日 旷 曰 1 1 竺广1 崮 c l a s sb wfv叫王d 1 1 c b l s sc i 图2 , 3 基于类的路由查找结构 c i d r 的使用，使得i p 地址的分配层次化。i s p 向更高层发布的是聚合后 的路由信息。聚合以后的路由前缀对应的是一段地址空间，多个目的地址可以 与之匹配。 路由聚合技术延缓了路由表的增长速度，但同时又带来新的问题：如果一 个机构更换了 s p ，但它仍然倾向于使用原来的i p 地址，在原来的i s p 中就会 造成地址空间的不连续。在这种情况下，路由器需要为该机构保存一条更详细 的路由信息，并按照该信息来转发分组。这时一个目的地址既匹配聚合后的前 缀，同时它还匹配该机构的更详细的路由信息，经过判断最终选取后者作为路 由转发信息。 这种一个目的地址对应多个网络前缀的选取问题就是最长前缀匹配的问 题。所谓最长自口缀匹配是指在所有与数据分组目的l p 地址匹配的表项中选取有 效前缀最长的表项。 第二章路由查找技术 表2 3 某路由器的路由表 表项编号 萌缀z 长度藁争踌地蛙 转发端口 骞。5 ：| 垂黔謦+1 0 o o o 81 2 1 3 1 1 2 a 曩2 i j 澎鞴1 0 2 0 0 1 61 2 1 3 2 ，5 5 b l 囊蠹舞鏊鬻 1 0 2 3 1 1 8 4 3 22 1 4 3 2 4 1 llc 4 囊蕾一j 。“1 0 2 _ 3 1 1 9 2 2 61 2 1 3 2 5 5b 叠0 5 、穗- 一1 0 2 t 3 1 o 2 41 2 1 3 2 5 5b 一一、6 “1 9 8 1 5 3 o ，2 41 0 2 1 4 6 3 4 1 3 8d “；：7 日；1 0 2 3 1 1 5 4 2 62 1 4 3 2 4 1 1 1c 例如，某路由器有表2 3 所示的七个表项，此时有一数据分组到来，且该分 组的目的地址为l o _ 2 3 1 1 8 3 ，显然该地址与表项l 、2 、5 、7 都匹配。根据最长 前缀匹配原则，由于表项7 为最长匹配，因此分组被转发到端口c 。 第二节查找算法的评价准则 2 2 1 算法复杂性 2 2 1 1 查找时间 查找速度是决定路由查找算法性能及路由器处理报文能力的最主要因素。 i n t e m e t 骨干网向更快的光纤速率发展，对路由器的数据分组转发要求越来越高。 路由器要想实现线速转发数据分组，必须加快自身的查找速度。常用的路由查 找算法都是在软件环境下设计实现的，算法查找速度主要是由查找过程需要进 行的存储器访问次数所决定，因此可以通过统计算法在查找过程中存储器访问 次数就可以基本估计该算法的查找性能。 2 2 1 2 存储空间 低的存储容量不仅可以降低成本，还有可能用快速存储器来实现，甚至通 过片内r a m 实现，以达到更高的查找速率。路由器总是要求路由查找算法占用 的存储容量应该尽量小，从而可以为算法的实现带来更大的灵活性。 2 2 1 3 预处理和更新时间 根据处理路由更新方式的不同，查找算法可以分为两种类型：一种称为动 态算法，即发生路由更新( 包括增加和删除) 时，算法数据结构只需要在原有 1 2 第二章路由杏找技术 基础上相应更新，而不需要完全重构；另一种被称为静态算法，即当发生路由 更新时，算法数据结构需要完全重新构建。与动态算法相比，静态算法的运行 需要一个预处理过程( 即重新构建过程) ，更新所消耗的时间会更长一些。对 于企业网路由器，由于路由协议很稳定，路由表更改的频率低，此时路由表的 更新速度( 包括插入删除和表项的更新) 并不重要。但是研究表明，i n t e m e t 路 由的不稳定性使得骨干网路由器的路由表的增加和删除过程变得非常频繁，更 改速度可以达到数百次秒f 2 2 1 ，这就要求路由查找算法应该能够及时更新路由表。 另外，为了不影响正常的查表操作，对查找表的修改必须是在当前查找表的基 础上进行，而不是完全重建。因此，好的路由算法更新是动态的。 2 2 2 算法灵活性 路由查找算法可以软件实现，也可以硬件实现。相对于软件来说，硬件实 现可以达到更高的查找速度，但是硬件实现的一个要求就是算法简单，以减少 逻辑，降低设计的工作量，同时也有利于流水线实现，以提高性能。因此从查 找算法的实现灵活性上考虑，好的算法应该能够同时具有软件和硬件实现方式。 在未来的几年中，报文处理速度需要达到一个相当高的水平，硬件实现将是路 由查找引擎的主要实现方法，因此路由查找算法的设计应该考虑算法在硬件实 现上的可能性。 2 2 3 算法扩展性 新一代的i n t e m e t 协议i p v 6 将会逐渐替代目前使用的i p v 4 协议，因此在设 计过程中需要考虑到算法的可扩展性，要求路由查找算法随地址长度的扩展性 好，以支持i p v 6 下的查表操作。 第三节查找算法的分类及其常用数据结构 c i d r 技术的采用给路由查找带来了一定难度。接收到的数据分组目的地址 中并不含有最长匹配的前缀长度，因此最长匹配查找算法不可能采用与基于类 的查表算法相同的结构。本节对查找算法的分类及其常用数据结构予以介绍。 2 3 1 查找算法分类 最长地址前缀匹配查找的难点在于在查找过程中，不仅需要与地址前缀的 1 3 第二章路由查找技术 比特值进行匹配查找，而且还需要考虑地址前缀的长度。针对这一问题，路由 查找存在以下两种方案：一是基于地址前缀值的路由查找算法；二是基于地址 前缀长度的路由查找算法。各种路由查找算法都可以归结为这两种匹配查找过 程。 2 3 1 1 基于地址前缀值的路由查找算法 基于地址前缀值路由查找算法的特点是通过对整个地址前缀空间进行地址 关键字穷举来消除地址前缀长度对查找的影响。 线性匹配查找算法是基于地址前缀值查找中最简单直观的地址前缀查找方 法。地址区间二分法也是基于地址前缀值的查找算法，但是由于它采用了二分 查找，所以在算法性能上有了很大的提高。基于c a m 的硬件实现方法也属于地 址前缀值的查找算法。 2 3 1 2 基于地址前缀长度的路由查找算法 另外一个查找方法是基于地址前缀长度的路由查找算法。这类算法的出发 点就是在前缀长度空间内进行查找。 与基于地址前缀值查找算法类似，查找过程可以使用线性遍历法，也可以 使用二分法遍历法。t r i e 树查找算法就是基于地址前缀长度的线性遍历法，因为 对于查找的第i 步来说匹配的是长度为i 的地址前缀。同理多比特t r i e 树查找算 法也是基于在地址前缀长度空间内的线性遍历法，但是由于它采用大于1 的步 长，所遍历的地址长度数目变少了，使查找性能得到了提高。从算法的复杂度 来看地址i i 缀长度的二分查找法的性能更好。 2 3 2 常用数据结构 2 3 2 1 线陛表 线性表结构是最简单的查找数据结构，因此可以把所有的路由地址前缀用 线性链表的方式组织起来。每一次查找从链表首部开始，检查各表项是否匹配， 并记录所遇到的最长匹配，直到遍历完整个线性链表。 对于n 个路由前缀表项，查找过程的算法复杂度为0 ( n ) ，存储空间复杂 度为0 ( n ) ，插入删除路由表项的算法复杂度为0 ( 1 ) ( 假设表项插入删除 均在线性表的术尾进行) 。通过对表项进行按最长前缀排序，就可以在遇到第 1 4 第二章路由查找技术 一个匹配的前缀后结束查找，减少查找时间，这时更新复杂度变为0 ( n ) 。 线性表的优点是通用性好，与平台无关：缺点是访问速度慢。 2 3 2 2 二进制t r i e 树 二进制t r i e 树是每一个分支上都带有标号的二叉树。其中左分支标记为0 ， 右分支标记为1 ，然后沿与i p 地址匹配的分支逐比特查找。 表2 4 中的路由表可以用如图2 4 所示的二进制t r i e 树结构来表示。图中带 阴影的节点表示该点为网络前缀，白点表示该点不是网络前缀。每一个阴影点 与一个n h p ( n e x th o pp o i n t e r ，下一中继点指针) 相对应，表示该网络前缀所 对应的下一跳目的地址。各节点的数据结构如图2 4 右下角所示，包括下一中继 点指针( 如果是有效前缀) 、左子节点指针以及右子节点指针。 表2 4 具有5 个前缀的路由表 l 弧；：# ；：嬲囊：曩囊= 萋麓前睡薹爱i i 誉鬻黧囊荔鬟蠢溺缝镳渤瀛稳瞄i 程弦酾麓瓢一瀵 ；i 鬃；罐麟羹 0 +h 0 鞭蒜臻蓦黧 1 +h 1 1 冀塞潮慧嚣0 0 h 2 ，_ 1 l i l 珞 * i i i i ；?0 1 1 h 3 + i 露瓣姒2 ；羔1 1 0 +h 4 图2 4 二进制t i l e 树结构 查找时从根节点开始查起，每次从目的i p 地址中读出1 比特，如果为1 则 查找当前节点的右子节点；为0 则查找左子节点。这样逐比特查找，直至遇到 叶子节点或者当前节点无相应子节点时结束查找操作。在查找过程中，记录最 新遇到的阴影点所对应的n h p ( 即当前找到的最长网络前缀所对应的表项) 。 1 5 第二章路由查找技术 仍以图2 4 为例，如果目的i p 地