（计算机系统结构专业论文）支持ipv4ipv6的快速ip路由查找和更新技术研究.pdf

中国科学技术大学硕士毕业论文 摘要 目前，随着应用的快速发展和图像、音频、视频等多媒体信息传输的大量增 加，i n t e r n e t 流量呈指数方式增长，对骨干路由器提出了越来越高的性能需求。 在i n t e r n e t 发展初期，路由器大多基于c p u + n 存结构，其路由查找过程大多由 软件采用二进制树的方法实现。在高性能路由器中，多种基于硬件方法实现的i p 路由查找技术被广泛使用，如直接存储器访问、基于三态c a m 和c a c h e 的查找 技术等。随着第三代网络处理核心网络处理器的出现，i p 路由查找过程大 多被集成在网络协处理器中。 路由器的转发速率通常受限于选择路由的速度，因此，路由查找和更新的方 法是路由器进行包转发的基础和提高其性能的关键性技术，在路由器设计中至关 重要。本文在详细分析多种现有i p 路由查找技术的基础上，提出了一种可硬件 实现的快速i p 路由查找方法，将i p 前缀匹配等价为地址范围搜索，采用b - 树结 构存储路由表。这种方案对存储要求较低，仅由小容量的片上s r a m 和片外 d r a m 构成即可。实验结果表明，对于一个具有3 2 k 个路由表项的i p v 4 路由表， 在1 6 0 位存储带宽下，只需要2 m b 的片上s r a m ，平均访存7 次，路由更新的 速度为微秒量级；对于一个具有2 0 k 个路由表项的i p v 6 路由表，在5 5 2 位存储 带宽下，只需要3 m b 的片上s r a m ，平均访存6 次。本文描述的快速i p 路由查 找技术在简单硬件支持下就能够达到o c 4 8 的转发要求，并能支持i p v 4 和i p v 6 下的路由查找。如果采用硬件流水线来组织b 树的查找过程，那么可以达到一 次存储器访问时间的查找速率。 此外，由于在设计中采用了b 树结构存储路由表数据，并利用“空间换取 时问”的思想在片外d r a m 中存储了路由表更新所需要的信息，本文的设计方 案在具有快速路由查找能力的同时能达到较高的路由表更新速度。 【关键词】硬件，片上存储器，i p 路由查找，i p 路由更新，b - 树，地址范围，前 驱查找，流水线 中国科学技术大学硕：i = 毕业论文 a b s t r a c t i nt h ee a r l yd a y so fi n t e r n e t ，m o s tr o u t e r sb a s eo ng e n e r a lc p ua n dm e m o r y , a n d t h ei pr o u t el o o k u pi nt h er o u t e r sa r ea l w a y si m p l e m e n t e db ys o f t w a r eu s i n gb i n a r y t r e e t oa d a p tt ot h er a p i dg r o w t ho fi n t e m e tt r a f f i c s ，t h ei pr o u t el o o k u pp r o c e d u r e s i nb a c k b o n er o u t e r sa r ei m p l e m e n t e db yh a r d w a r ei n s t e a do fs o f t w a r eu s i n gb i n a r y t r e e ，s u c ha ss t r a i g h tm e m o r ya c c e s s ，t e r n a r yc o n t e n t a d d r e s s a b l em e m o r ya n d c a c h e a l o n gw i t ht h ea p p e a r a n c e o fn e t w o r kp r o c e s s o r , t h ei p r o u t e l o o k u p p r o c e d u r e sa r em o s t l yi n t e g r a t e di nv a r i e d l yn e t w o r kc o 。p r o c e s s o r t h er o u t e r sf o r w a r d i n gr a t ei su s u a l l yl i m i t e db yt h er a t eo fr o u t el o o k u p t h u s ，t h e m e t h o do fr o u t el o o k u pa n du p d a t ea r ea l l i m p o r t a n tf o rr o u t e rd e s i g n i nt h i sp a p e r , t h ep r i n c i p l e sa n df e a t u r e so fi pr o u t el o o k u pa l g o r i t h m si ns o f t w a r ea n ds i xk i n d so f h a r d w a r ea r c h i t e c t u r et oi m p l e m e n tr o u t el o o k u pa r ed i s c u s s e da n da n a l y z e d t h e nw e p r o p o s e san e wm e t h o df o ri m p l e m e n t i n gf a s ti pr o u t el o o k u pa n du p d a t e ，w h i c h t r a n s l a t e sp r e f i xm a t c h i n gi n t oa d d r e s sr a n g ef i n d i n ga n du s e sb t r e et os t o r er o u t i n g t a b l e o u rd a t as t r u c t u r ei st a i l o r e dt oah a r d w a r ed e s i g nr e f e r e n c em o d e lp r e s e n t e di n t h i sp a p e r , w h i c hj u s tc o n t a i n sap r o c e s se n g i n e ，as m a l lo n - c h i ps r a ma n da n o f f - c h i pd r a m b ye x p l o i t i n gt h el o wm e m o r ya c c e s sl a t e n c ya n dh i g hb a n d w i d t ho f o n - c h i pm e m o r y , h i g h - s p e e dp a c k e tf o r w a r d i n gc a nb e a c h i e v e du s i n g t h i sd a t a s t r u c t u r e w i t ht h ea d d i t i o no fp i p e l i n ei nt h eh a r d w a r e ，i pr o u t el o o k u pc a no n l yb e l i m i t e db yt h em e m o r ya c c e s ss p e e d e x p e r i m e n t a la n a l y s i ss h o w st h a t ，g i v e nt h e m e m o r yw i d t ho f16 0b i t s ，o u ra l g o r i t h mn e e d so n l y2 m bm e m o r yf o rs t o r i n ga3 2 k e n t r i e si p v 4r o u t i n gt a b l ea n ds e v e nm e m o r ya c c e s s e sf o ras e a r c h ，a tt h es a m et i m e ， r o u t eu p d a t ej u s tn e e d sa b o u tlu s w i t hm e m o r yw i d t ho f5 5 2b i t s ，w ee s t i m a t et h a t w en e e d3 m bm e m o r ya n ds i xm e m o r ya c c e s s e sf o rar o u t i n gt a b l ew i t h2 0 ki p v 6 p r e f i x e s 【k e y w o r d s 】h a r d w a r e ，o n - c h i pm e m o r y , i pr o u t el o o k u p ，i pr o u t eu p d a t e ，b t r e e ， a d d r e s sr a n g e ，p r e c u r s o rl o o k u p ，p i p e l i n e 中国科学技术大学硕士毕业论文 1 概述 在今天的网络中，人们已经普遍使用光纤作为数据传输的介质。光传输系统 为我们提供了g b s 量级的高网络带宽，o c 4 8 = 2 4 g b s ，o c 一1 9 2 = 1 0 g b s 己渐成 主流【3 3 l 。同时，名目繁多的各类应用也对网络结点提出了多样的要求，如q o s ， 安全性等等。为了充分利用物理介质带给我们的高网络带宽和满足各种应用需 求，网络中的结点需要达到很快的数据包处理速度。 网络处理器 2 1 5 1 ( n e t w o r kp r o c e s s o r ，简称n p ) 正是由此而提出来的一项新 的技术。由于通用c p u 编程处理方式在速度上有所欠缺，而a s i c 的设计周期 很长且不够灵活，因此兼顾速度和灵活性的n p 成为一种有吸引力的选择，将在 下代网络设备中广泛使用。目前国外有多家公司开发了一系列的n p ，如i n t e l 的i x p l 2 0 0 3 们、i x p 2 8 0 0 1 5 1 和i b m 的p o w e rn p 1 0 】，其处理速度不断提高，i n t e l 的最新产品i x p 2 8 5 0 更是加强了安全性能。而国内的网络处理器研究还处于开 始阶段。 1 1 研究背景 网络处理器主要由一个通用处理器，若干个可编程微引擎，和几个协处理器 等组成。通用处理器完成一些控制和管理的工作；微引擎用于数据包的接收转发； 协处理器可用于路由表的查询更新、流量控制，安全验证等特定任务。 图1 1 数据包在n p 中的大致流程 图1 1 说明了数据包在n p 中的大致流程。n p 周期性检测m a c 收到的数据 包，然后存入接收队列( r f i f o ) ，再进行分类、过滤，丢弃某些包：然后将包 分成固定大小的段，存入数据队列存储器；在存入之前，还要进行拥塞管理。之 后通过内部总线，读出数据包进行路由查找、队列调度等一系列操作，或者由微 中国科学技术大学硕：b 毕业论文 引擎实现安全算法等等。最后再从存储器读出段，各段重组成数据包，缓冲到输 出队列再发送出去。 针对n p 的应用特点高吞吐量和可编程性，国外很多研究人员对此进行 了研究。提高吞吐量主要通过两个途径：一是通过快速的硬件接口和存储设备来 加速数据包处理，存储器带宽是整个系统的瓶颈，急需改进；二是在处理过程中 使用多种并行技术。一方面，n p 有天然的并发性，另一方面，高速网络中n p 面临着内存访问时间的瓶颈，因此提高并发性也是必要的。而高度的并发性不仅 需要多线程，也需要多处理器一起完成。同时，需要提供一个强大的指令集来支 持可编程性，而一个灵活的存储器设计方案对提高可编程性也是至关重要的。 随着路由表的增大，存储代价和查找与更新的效率问题也越来越凸现出来。 当路由表变得庞大时，对一个给定的目标地址，决定目标输出端口所需的访存次 数也相应增加。而大路由表存储在片内存储器或者c a c h e 中的成本太高，因此需 要使用时间开销较高的片外存储器。目前，一次片上s r a m 访存需要1 - 5 n s ，一 次片上d r a m 访存需要1 0 n s ，而片外s r a m 需要1 0 。2 0 n s ，片外d r a m 需要 6 0 1 0 0 n s 。如何在存储器成本和查找更新速率之间达到良好的平衡，在网络处理 器存储系统设计中较为关键。 当前计算机网络中应用最广泛的网络层协议是i p v 4 2 4 1 ，但是它正暴露出越 来越多的不足，比如地址匮乏，安全性不足等问题。对此，研究人员提出了新一 代网络层协议i p v 6 2 5 】【3 0 1 。因此，支持i p v 6 的i p 路由查找技术也受到研究人员 的关注。此外，用于i p 路由查找的专用网络协处理器需要一个简单的硬件结构， 易于实现且成本较低。 1 2i p 路由查找的原理 i p 协议【2 4 】( i n t e r n e tp r o t o c 0 1 ) 规定每个子网中主机的i p 地址都具有相同的 网络号，路由器在进行路由查找时只对网络号进行查找。随着i n t e r n e t 的快速发 展，初期定义的3 类i p 地址已经不能满足大量主机的要求。目前多采用子网编 码技术解决i p 地址的分配和管理问题川。它的主要思想是将3 2 位i p v 4 地址分成 网络号，子网号和主机号三个部分。其中网络号的定义基于i p 协议中a ，b ，c 三类地址的定义，具有确定的长度。子网号根据用户实际的物理网络规模来确定， 具有不确定的长度。路由器将根据报文中i p 目的地址中的网络号和子网号来确 定该报文的路由结果。考虑到子网号的不定长因素，路由表的每个表项需要包括 中国科学技术大学硕：i = 毕业论文 网络地址、子网掩码和路由结果等三部分内容。 当路由器从一个输入端口接收到一个i p 数据包时，它需要决定从哪个输出 端口转发此数据包。为此，路由器将数据包的目的地址和路由表进行匹配。如何 构造一个合适的数据结构存放路由表，基于这个数据结构我们能快速地找到转发 端口就是i p 路由查找的问题所在。 通常i p 路由查找都是进行最长前缀匹配【4 】【3 2 1 。当路由器接收到i p 包后，必 须从路由表中找到一个具有和目标i p 地址相同，且予网掩码( 前缀) 最长的表 项作为路由结果，即最长前缀匹配。例如，路由表中的三个表项分别为： p 1 ：1 0 0 0 0 1 1 00 1 0 1 0 1 0 10 1 0 1 0 0 1l 水 p 2 ：1 0 0 0 0 1 l o0 1 0 1 0 1 0 10 1 0 1 0 0 1 幸 p 3 ：1 0 0 0 0 11 00 1 0 1 0 1 0 00 1 术 那么根据最长前缀匹配规则，目标i p 地址1 0 0 0 0 1 1 00 1 0 1 0 1 0 10 1 0 1 0 0 1 1 1 1 0 0 1 0 0 1 的匹配结果应该是p 1 ，1 0 0 0 0 1 1 00 1 0 1 0 1 0 00 1 0 1 0 0 1 l1 1 0 0 1 1 1 1 的匹配 结果应该是p 3 。 人们对骨干路由器上的路由表进行了许多测试和分析3 1 ，得到以下规律： 路由表的表项数目一般为3 0 k - 1 2 0 k 左右，基本按平方方式随时间增 长。 路由表更新的频率大约为1 0 0 - - 一1 0 0 0 次秒。 表项前缀从8 位到3 2 位都有分布，但超过2 4 位的情况比较少。在8 位 到2 4 位一般呈递增趋势，并主要集中于1 6 到2 4 位之间，另外在8 ，1 6 ， 2 4 位上都有更多的分布。 对于o c 4 8 的数据传输率，应能满足每秒钟8 m 次的i p 路由查找速度，即 在1 2 5 n s 内应能得到一个路由查找结果。除了上述查找速度的要求外，路由表更 新的开销、能否支持i p v 6 的1 2 8 位i p 地址路由查找、实现成本等也是评价i p 路由查找技术的重要方面。 1 3 研究现状 对于网络处理器存储系统，很重要的一部分就是能够支持快速i p 路由查找。 下面简单介绍目前的一些存储器的组织方式和快速i p 路由查找策略。 中国科学技术大学硕二l = 毕业论文 1 3 1 存储器的组织方式 在片内存储容量受限的情况下，为了提高i p 查找速度和数据存取速度，e t 前常用的是c a c h e 缓存i p 地址以及片上s r a m 和片外d r a m 相结合的方式。 基于c a c h e 的存储器设计有三种主要形式：( 1 ) 直接缓存目标i p 地址的 c a c h e h a c ；( 2 ) 缓存i p 地址范围的c a c h p 一h a r c i h a r c ；( 3 ) 缓存i p 地址前缀的c a c h e 。这些方式能够获得一定程度的性能提升。但是也有研究表明， 由于网络上数据包之间并没有太多的关联性，在我们的设计中是否使用c a c h e 还有待进一步研究。而且上述的c a c h e 技术都是基于平均查找时间优化的，并没 有对最坏情况作保证。 另一种方式是利用片上s r a m 来存储路由表或者数据队列的索引结构，而 片外d r a m 存储具体的数据。有研究者已经提出了按照这种思想设计的i p 路由 查找技术( b i tp a t t e r n ) 1 9 】和数据队列管理存储器( d q m ) 1 2 0 l 【2 l 】【2 2 】。一次或多 次片上访存可以得到数据在d r a m 中的位置，然后通过一次片外访存即可得到 结果。这样的片上s r a m 和片外d r a m 相结合的方式能够很有效的提高访存速 度。 1 3 2 快速i p 路由查找策略 路由表项是一个三元组( i pa d d r e s s ，m a s k ，p o r t ) ，路由查找的基本概念是 “最长前缀匹配”将子网掩码( 前缀) 最长的表项作为路由结果。原来路由 器中的i p 路由查找一般基于二进制树的软件查找方法。但是随着高性能的需求， 采用专用硬件来实现路由查找功能是n p 设计的主流。有两个主要的设计途径： 经典软件算法的直接硬件化或者利用特殊器件加速。下面简单说明现有的一些路 由查找技术 4 1 。 1 、二进制树查找 软件路由查找的基本方法是用二进制树【7 】( b i n a r yt r i e ) 来表示路由表项 的前缀。各路由表项按照其前缀的二进制编码放置在二进制树中：从第0 级到第 l 级的路径表示了该前缀的高l 位二进制编码。在进行路由查找时，将从树的根 节点出发，按照目的i p 地址的二进制编码的从高到低的顺序依次查找二进制树 的各级节点。当树中没有更低一级的子树与目的i p 地址的相应位匹配时，最后 中国科学技术大学硕士毕业论文 一个匹配的路由表项即为查找结果。 为了进一步提高二进制树的查找效率，还可以使用路径压缩的方法将只有一 个前缀信息的子树变成一级节点。典型的例子是b s d 中使用的p a t r i c i a 树。 2 、基于h a s h 表的二进制树查找 w a l d v o g a l 6 】提出了基于h a s h 表的二进制树查找算法。它的主要思想是：将 具有相同前缀长度的表项分别组织成相应的h a s h 表，而且h a s h 表项中还包含了 具有与本表项相同前缀但长度更长的其他h a s h 表项的双向指针。查找过程从中 间前缀的h a s h 表开始，如果没有发现到相应的表则回退到具有一半前缀长度的 h a s h 表查找；否则要么继续增加前缀长度进行查找，要么就获得结果。另外，作 者还针对路由查找的特点，进一步优化二进制树结构和查找过程以减少查找中访 问存储器的平均次数以及存储容量。该算法对于3 2 位地址长度的i p v 4 路由表只 需要5 次h a s h 查找，软件的执行时间大约为8 0 n s ，存储器容量大约为1 5 m b 左 右。 3 、分层结构查找 d e g e m a r k 8 】提出，根据i p 路由表的特点可以采用分层结构查找。其中第一 层对应前缀长度小于等于1 6 的路由信息，第二层对应前缀长度从1 7 到2 4 的路 由信息，第三层对应前缀长度从2 5 到3 2 的路由信息，并根据子树中结点的数目 组织成不同的数据结构，以减少存储容量。该算法的主要特色在于路由表所占用 的存储器容量小，对于典型骨干路由器的路由表一般占用1 6 0 - - 一2 8 0 k b ，可以放 置在通用处理器的二级c a c h e 和三级c a c h e 中，以获得更好的路由查找性能，其 最坏查找时间需要4 0 0 5 0 0 n s 。 4 、存储器直接访问 基于存储器直接访问的i p 路由查找方法 9 1 是将路由查找过程分成两次存储 器访问。第一次直接将目标i p 地址的高2 4 位和路由表项比较，若此地址的前缀 小于或等于2 4 ，则直接得到结果；否则根据存储器访问的指针和低8 位i p 地址 合成新的存储器地址，进行第二次比较，以获得最终结果。 如果两次访存按照流水线方式组织，则可以在一次访存周期中得到路由查找 结果。但是这种方法在路由表更新的时候会产生过多的访存。而且这种方法只对 中国科学技术大学硕士毕业沦文 i p v 4 的3 2 位i p 地址查找有效，难以处理i p v 6 下的1 2 8 位i p 地址查找，也难以 处理i p v 4 下的包分类。 5 、硬件直接实现p a t r i e i a 树的查找 i b m 公司研制的针对o c 4 8 的n p 4 g s 3 i ”j j 网络处理器，用硬件直接实现 了p a t r i c i a 4 q 树的数据结构。为了提高查找速度，它采用了由片内s r a m ，片外 s r a m 、d d rd r a m 构成的存储系统来分别存放p a t r i c i a 树中不同的部分。 查找过程分为查找和端比较两部分。首先查找片内的直接映射表，然后在存 储器中沿着树进行搜索，直至找到目标叶节点。之后，使用带屏蔽位比较或者范 围比较的端比较指令最终判断查找的结果是否符合要求。这种方法能通过统一的 查找引擎完成多种查找和分类过程，对外部器件要求也比较低。但是其复杂的多 外围存储器结构使得芯片引脚过多，从而增加成本。 6 、基于三态c a m 的路由查找 三态c a m ( t e r n a r yc o n t e n t a d d r e s s a b l em e m o r y ) i ：1 2 是一种特殊的c a m 硬件设备，其中每位都有三个逻辑状态：0 ，1 和x 。其中x 表示该位不需要比 较，而且t c a m 中多个表项的比较结果可以按照固定优先级选择优先级最高的 结果输出。 设置路由表的时候，将前缀长的】p 地址放在优先级高的地方，前缀以外的 部分用x 表示。当目标i p 地址送入t c a m 后，其所有表项都同时和目标i p 地 址进行比较，并根据优先级选择前缀最长的表项输出，该输出结果可以形成访问 存储器的地址以获得最终路由结果。 由于在路由更新时要保证前缀长的i p 地址具有更高的优先级，s t a b 0 4 研究 了该方法在路由更新时t e a m 表项分配的问题。其基本思想时将c a m 的空闲 表项集中于c a m 中部。每次加入新的表项时，首先确定其加入的位黄，然后按 相同i p 地址，前缀递增的方式将已有表项移动到空闲表项中。删除操作与之类 似。这样每次更新表项的数目就只有d 2 ( d 为塌长前缀长度) 。 基于三态c a m 的i p 路由查找可以达到很高的速度，同时也司灵活的扩充 到i p v 6 查找和包分类。但不幸的是价格昂贵，且路由表受限于c a m 容量。 7 、i f l o w 寻址处理器 中国科学技术大学硕士毕业论文 i f l o w 寻址处理器川是s i l l i c o n a c c e s s n e t w o r k s 公司推出的一种快速i p 路由 查找处理器。它集成了约5 2 m b 的d r a m 和1 2 m b 的s r a m 。这些存储器足以 容纳1 2 8 k 个3 2 位i p 地址表项。整个路由表按照b 树的方式组织，大致上可以 分成三个部分：查找前端、查找后端和相连数据三部分。 查找前端由三级s r a m 构成，其中l 0 包含了3 1 个前缀，l 1 包含了3 2 1 5 个前缀，l 2 包含了5 1 2 1 5 个前缀。当目标i p 地址进入l 0 后，将并行读出和 比较3 1 个前缀的数据。根据5 位比较结果从l 1 存储器的3 2 个行中选择一个， 并行读出和比较其中1 5 个前缀的数据。l l 的比较结果和l 0 的比较结果可以合 成一个9 位的结果以从5 1 2 个l 2 的行中选择，并行读出和比较其中1 5 个前缀 的数据。上述三次存储器访问和比较操作构成流水线，即可以同时处理三个路由 查找请求。由于每次从存储器中读出最多3 1 个前缀，所以存储器数据总线高达 2 31 0 位。 查找后端由2 4 m 位d r a m 构成，并组成8 1 9 2 行，每行包括最多3 2 个前缀。 由l 0 ，l 1 ，l 2 的比较结果形成的1 3 位结果从中选择一个并行读出和比较。虽 然d r a m 访问和比较需要5 个周期，但可以通过流水线方式获得并行。查找结 果中包含了1 8 位的指向相连数据的指针。 相连数据也分为l 4 和l 5 两级d r a m 。l 4 容量为2 5 6 k 9 6 b ，其中包涵两 个递增计数器域和一个1 3 位的l 5 指针。l 5 的容量为8 k 5 1 2 b ，其中也包含了 两个计数器域。 由于采用了高带宽片内存储器和流水线操作，i f l o w 的查找性能可以和直接 存储器访问技术相比。而b 树的数据结构也减少了更新路由表项的访存开销。 8 、利用c a c h e 提高i p 路由查找速度 利用c a c h e 的前提就是数据流中存在着局部性。目前，c a c h e 技术主要分为 直接缓存i p 地址、缓存地址范围和缓存路由前缀三种。 ( 1 ) 直接缓存目标i p 地址的c a c h e 这种方案称作h a d l 7 1 ( h o s ta d d r e s sc a c h e ) ，类似于一个普通c p u 中使用 的c a c h e ，目标i p 地址被用作存储器地址。h a c 中直接缓存单独的i p 地址，试 图利用连续数据包之间的i p 地址局部性来提高性能。 ( 2 ) 缓存地址范围的c a c h e h a r c 和i h a r c 由于网络数据流的包转发中的局部性不够突出，因此可以通过提高i p 地址 中国科学技术大学硕士毕业论文 空间的“有效覆盖”( e f f e c t i v ec o v e r a g e ) 来提升处理性能。但是在树形结构查找 的最坏情况下，将进行3 2 次匹配。为了改善这一点，采用了n a r t ( n e t w o r k a d d r e s sr o u t i n gt a b l e ) 【i6 j 的数据结构。 h a r c 【l7 j ( h o s ta d d r e s sr a n g ec a c h e ) 利用了这样一个特性：每个路由表项 对应于一个连续范围的i p 地址空间。实际上，这是在h a c 的基础上将目标i p 地址右移x 位，也就是将最低有效的x 位忽略，然后再选择索引位进行查找。 i h a r c 1 7 1 ( i n t e l l i g e n th o s ta d d r e s sr a n g ec a c h e ) 在第二个设计的基础上进 行了优化。由于所有的路由查找结果都是有限个物理输出端口，端口的数目是很 小的。因此利用一个贪心算法的h a s h 函数，可以将多个脱节的地址范围组合成 一个大的地址范围，这将大幅度提高i p 地址空间的覆盖度。同时为了能适应各 种不同的路由表应用，h a s h 函数采取了可编程逻辑。 k a r t i kg o p a l a n 等人【1 8 】基于i h a r c 作出改进，提出了降低c o n f l i c tm i s s 的两 种方法：“平衡范围负载”和“可变的c a c h e 组映射机制”。同时针对频繁路由表 更新中的c a c h e 一致性维护提出了“可选择的c a c h e 失效”策略，相对完全失效 策略性能提升了近2 4 倍。 ( 3 ) 缓存路由前缀的c a c h e 斯坦福大学的h u a nl i u 1 9 】根据实际观测结果，提出路由前缀具有比单独i p 地址很好的局部性，因此提出了缓存路由前缀的c a c h e 技术。这个设计由 p r e f i x c a c h e 和p r e f i x - m e m o r y 两部分构成。p r e f i x c a c h e 采用全相联的组织方式， 路由表项为三元组( p r e f i x ，m a s k ，p o r t ) 。 在查询时，先将目标i p 地址和m a s k 相与，然后再和p r e f i x 比较。如果匹配 成功，那么就返回端口号；如果匹配失败，那么就在p r e f i x m e m o r y 的完整路由 表中查找。找到查询结果，则将完整的表项( p r e f i x ，m a s k ，p o r t ) 发送给p r e f i x c a c h e 进行缓存，同时返回端口号。 p r e f i x m e m o r y 的主要工作就是在c a c h e 失效时进行路由查找。在找到匹配 路由后，将结果返回给c a c h e 进行缓存。由于一个i p 可以匹配多个前缀，那么 如果只有其中一个前缀被缓存，则有可能出错。因此，如何选择合适的前缀进行 缓存是这个设计中的重要问题。 对于上面介绍的c a c h e 技术，都有不同程度的性能提升。h a c 的c a c h e 失 效率比缓存路由前缀的c a c h e 要高大约3 8 倍。而i a r c 的失效率是i h a r c 的2 9 1 7 0 9 倍，因此h a r c 的处理速度比i h a r c 要慢2 2 4 3 1 8 倍。同时相 中国科学技术大学硕士毕业论文 对于h a c ，i h a r c 的平均查找时间降低了5 倍。但是，上述的c a c h e 技术都是 基于平均查找时间优化的，并没有对最坏情况作保证。因此，c a c h e 技术是否可 以采用还有待需求分析的考证。但是对于其中有用的技术和思想，比如n a r t 数据结构，也可用于其他硬件实现的路由表。 9 、b i tp a t t e r n 查找方式 b i tp a t t e r n 2 3 1 采用片上s r a m 和片外d r a m ，将路由表的结构信息存储在 s r a m 中，非叶节点用一个l 表示，叶节点用0 表示，按树的层次存放，即所谓 的b i tp a t t e r n 。同时s r a m 中还保存了一个l e v e l 数组，存放了每一层的起始b i t 地址。叶子节点所具有的具体的路由信息存放在d r a m 中。根据这样的设计方 法，对于骨干路由器，只需要2 5 k b 左右的片上s r a m ，d r a m 也大约只需要 2 5 m b ，因此容易实现。 查找的时候，经过若干次访问s r a m 到达叶子节点，然后经过简单的加法 和移位操作即可得到路由信息在d r a m 中的地址。这样可以达到很好的i p 查找 速度。但是这种方式在路由表更新的时候会引起很多次的d r a m 访问，因而会 对性能有所影响。 从上述存储器的组织方式和快速i p 路由查找策略可以看出，高性能的获得 都是得益于高带宽的存储器系统以及流水线技术。实际上，各种实现方式之间可 以取长补短，比如说缓存路由前缀的c a c h e 方案中，它的p r e f i x m e m o r y 可用 t c a m 来实现高速查询。 1 4 研究内容 调研表明，国内的网络处理器市场主要集中在边缘路由器领域。因此，在今 后从i p v 4 向i p v 6 过渡的很长一段时期内，基于n p 技术的能同时处理i p v 4 和i p v 6 的路由器极具研究价值。国外，贝尔实验室的研究人员曾研究过如何将i x p 网 络处理器应用到i p v 4 i p v 6 共存网络中的网关上【2 州。在高性能路由器中，各种基 于硬件方法实现的i p 路由查找技术被广泛使用，如直接存储器访问、三态c a m 和c a c h e 等。目前i p 路由查找过程大多利用专用协处理器来实现，以希望达到 更好的i p 路由查找效率。 路由器的转发速率和选择路由的速度成正比，因此，i p 路由查找和更新的 方法是路由器进行包转发的基础和提高其性能的关键性技术，在路由器设计中至 中国科学技术大学硕士毕业论文 关重要。在片上存储器容量受限的情况下，路由器的存储系统必须达到很高的整 体存储带宽。快速i p 路由查找和路由表更新要求尽量少的访存次数和访存开销， 这些都是研究的重点所在。本文在详细分析现有n p 中常用技术的基础上，综合 考虑i p 路由查找速度、路由表更新开销、是否支持i p v 6 查找、是否易于硬件实 现以及成本等多个方面，提出了一种快速i p 路由查找和更新技术，主要的工作 在以下几个方面： 1 采用由片上s r a m 和片外d r a m 构成的硬件模型，结构简单且成本较 低，能够方便地实现网络协处理器； 2 将i p 路由查找时的最长前缀匹配等价为前驱查找，根据前驱查找的特 点采用b 树结构存储路由表，查找速度快，便于扩展到i p v 6 ； 3 利用“空间换取时问”的思想在片外d r a m 中存储了路由更新所需要 的数据信息，基于b 树结构能够完成快速的路由更新； 4 b 树结点中充分发掘数据的可压缩性，利用共享指针和端点数据压缩等 方式进行优化，节约存储空间的同时提升路由查找速度。 除了上述四个主要的方面之外，基于b 一树这样的平衡的多路查找树的存储 结构，每次i p 路由查找需要固定的访存次数，因此可以对本文所描述的i p 路由 查找方案进行流水化，这样可以提高查找过程的并行性，从而可以实现每一次存 储器访问完成个路由查找请求。 1 5 论文组织 本文后面的章节按如下方式组织：第二章描述一种快速i p 路由查找方案的 原理，介绍了基于片上s r a m 和片外d r a m 的存储结构硬件模型，并分析i p 路由查找中的最长前缀匹配如何等价为前驱查找，然后说明相应的基于b 树的 基本数据结构和针对快速路由更新的扩展数据结构；第三章详细分析地址前缀转 化、建立路由表、路由查找以及路由更新的算法，给出了算法的伪代码描述，并 介绍了对设计方案的两种优化策略端点数据压缩和查找过程流水化：基于前 面的分析和算法，第四章是实验和实验结果，并和几种现有技术作了比较；最后 是工作总结，并对未来的工作提出展望。 中国科学技术大学硕：i = 毕业论文 2 一种快速i p 路由查找方案的原理 本章在分析现有技术的基础上，描述了我们提出的一种快速i p 路由查找和 更新方法的硬件模型和数据结构。其基本思想是将i p 前缀匹配等价为地址范围 搜索【3 5 】 3 7 】，采用b 树结构存储路由表。这种方案对存储要求较低，仅由小容量 的片上s r a m 和片外d r a m 构成即可。后续章节的实验表明，该方案在简单的 硬件支持下就能够达到o c 4 8 的转发速率要求，在存储空间和查找更新时间上 达到了平衡。 2 1 现有查找技术的不足 1 2 2 节介绍的二进制树查找、w a l d v o g e l 的基于h a s h 表的二进制树查找和 d e g e r m a r k 的分层结构查找都是软件查找方式，这类算法比较适合在一般通用处 理器上由软件实现。如果由硬件直接实现，可能会增加设计的复杂程度，而且次 数不固定的存储器访问难以用流水线实现。他们的共同特点是： 数据结构复杂； 路由表占用的数据空间可以压缩到很小； 不需要专用的硬件设备； 存储器访问的次数多且不固定。 表2 1 六种硬件i p 路由查找技术比较 查找技术查找速度 更新开销是否支持i p v 6 查找 成本 直接存储器访问快 大不支持低 n p 4 g s 3 由 小 岛 三态c a m快小支持 同 i f l o w快小 品 c a c h e b 小支持 d j b i tp a t t e r n快大支持 低 表2 1 是1 2 2 节中介绍的六种硬件i p 路由查找技术的比较。从表中可以看 出，这些硬件i p 路由查找技术或多或少都存在一些不足。直接存储器访问、三 态c a m 、i f l o w 和b i tp a t t e r n 等都具有快速的i p 路由查找能力，但是直接存储 器访问和b i tp a t t e r n 的更新开销过大，三态c a m 和i f l o w 的成本过高。n p 4 g s 3 和c a c h e 技术虽然更新开销比较小，但是查找性能一般，成本方面也没有太大的 中国科学技术大学硕士毕业论文 竞争优势。综合比较来看，三态c a m 和n p 4 g s 3 的成本太高，c a c h e 技术由于 数据包之间的局部性不够突出导致查找速度不够，直接存储器访问不能支持i p v 6 路由查找，b i tp a t t e r n 由于采用静态数组存储树的结构而使得路由表的更新开销 太大。因此，综合考虑查找速度，更新开销、支持i p v 6 查找和成本等多个方面， 我们采用存储器成本较低的片上s r a m 和片外d r a m 相结合的形式，利用和 i f l o w 处理器类似的b 树结构存储路由表，同时用流水线技术对其优化。本章的 后续内容将详细介绍我们设计方案的硬件模型及其数据结构。 2 2 硬件模型 第一章介绍了目前快速i p 路由查找技术中常用的硬件模型，主要有利用 c a c h e 以及片上s r a m 和片外d r a m 相结合两种方式。正如前面所述，采用c a c h e 主要是利用相邻访问之间的存在的局部性，但是对于路由查找来说局部性并不是 特别突出。实际上，c a c h e 技术都是基于平均查找时间优化的，并没有对最坏情 况作保证。而采用片上系统的好处有两个：一是片上存储器的访存延迟很小，二 是片上系统的片上存储器的总线带宽比片外存储器高的多；但同时片上系统的存 储器不可能很大。因此，综合考虑查找效率和存储成本，本文的研究中采用片上 s r a m 和片外d r a m 相结合的方式，在现有技术的基础上加以改进，提升i p 路 由查找和更新的效率。 和b i t p a t t e r n 方式类似，将路由表分为结构信息和数据信息两部分。本文描 述的路由表存储结构硬件模型如图2 1 所示。图的左边是由p e 和存储系统构成 的芯片，存储系统采用片上s r a m ，用于存储路由表的结构信息；图的右边是扩 展的片外d r a m ，存放的是路由表的数据信息下一跳地址。基于上述硬件 结构，i p 路由查找过程可以简单描述成： ( 1 ) p e 从外部接收目标i p 地址，经过若干次访存，执行简单的逻辑、移 位操作即可得到输出结果： ( 2 ) 根据p e 输出的下一跳地址索引访问片外d r a m ，得到具有目标i p 地 址的l p 数据包的转发端口。 整个过程所耗用的时间主要是数次片上s r a m 访存和一次片外d r a m 访存 所占用的时问。假设i p 数据包的大小都是最小长度4 0 字节，那么单位时间内需 要处理的路由查找次数是最多的。对于o c 4 8 的应用需求来说，本文的设计方 案能够满足每1 2 5 n s 处理一个路由查找的要求。 中国科学技术大学硕：e 毕业论文 i l l i i l l l l i 疑l s r a m i l i l i i i i l i lfi il 。，。l 。 2 3 地址范围搜索 图2 1路由表存储结构硬件模型 路由表项是一个( i p 地址，掩码，端口) 三元组，i p 地址和掩码相与后得 到一个地址前缀。i p 路由查找的过程实际上就是查找和目标i p 地址匹配的最长 的地址前缀。下面先给出相关的几个定义，随后以一个简单的路由表为例进行说 明。 定义1 ：对于一个地址前缀p 下的所有地址i ，十进制表示时i 满足条件a i b ，定义非负整数区间 a ，b + 1 ) 为地址前缀p 的地址范围。在地址范围 a ，b ) 中，a 称为左端点，b 称为右端点。 定义2 ：对于一个地址范围 a ，b ) ，定义端口a 绑定到左端点a 上，意思是 在地址范围 a ，b ) 内的所有地址都映射到端口a 。 例如8 位地址的前缀0 0 0 1 慵电代表了0 0 0 1 0 0 0 0 和0 0 0 1 1 1 1 1 之间的所有地址。 十进制表示下，0 0 0 1 0 0 0 0 和0 0 0 1 1 1 1 1 分别是1 6 和3 1 。为了减少b 树中的结点， 前缀0 0 0 1 木的地址范围就是 1 6 ，3 2 ) ，1 6 和3 2 分别是前缀0 0 0