（电路与系统专业论文）网络树形搜索引擎的设计及其验证.pdf

浙江大学硕上学位论文 摘要 随着i n t e m e t 的迅猛发展，网络处理器的接口速率已经达到了2 5 g b p s 到 1 0 g u p s 。这一速率要求网络处理器能快速地进行地址查找，所以说网络处理器 中搜索引擎已经成为实现包快速转发的关键。 笔者结合网络处理器的本身架构，从网络处理器的整体性能和性价比出发， 对多个网络处理器的搜索算法进行横向和纵向比较，如，p a t r i c i a 树，内容可 定址c a m ，缓存策略，二进制t r i e 树，多分支t r i e 树和地址前缀长度的二分 查找法等，然后提出了基于p a t r i c i a 树的树形搜索引擎的设计原理和设计方 法。树形搜索引擎支持精确的全匹配搜索( f m ) ，也支持最长前缀搜索( l p m ) ，还 支持用于自定义树的搜索( s m t ) ；它支持二进制p a t r i c i a 树结构，同时也支持多 分支( m u l t i b i t ) 的搜索方法：它支持缓存( c a c h e ) 策略搜索，也支持哈希( h a s h i n g ) 辅助搜索；它还支持专门为t r u n k i n g 设计的二进制搜索( b i n a r ys e a r c n 算法。 笔者结合网络处理器的整体框架和性能，提出了树形搜索引擎的实现方案， 从三个主要执行模块阐述了搜索引擎的命令操作过程。 笔者更从工程的角度出发，提到了芯片验i 正( v e r i f i c a t i o n ) 是设计实现的保证， 所以论文从验证方法、验证流程、验证环境和验证结果四个方面，阐述了树形搜 索引擎模块的验证。 关键字： 网络处理器树形搜索引擎t s ec a m 验证 浙江大学硕士学位论文 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 f i n t e m e t ，t h el i n es p e e do f n e t w o r kp r o c e s s o r ( n p ) h a sr e a c h e d2 5 g b p sa n de v e n1 0 g b p sb e y o n d t h i ss p e e do r d e r sn p t ob ea b l et o s u p p o r t f a s ti pa d d r e s s s e a r c h i n g ，s o s e a r c h e n g i n e i st h e k e y t o p a c k e t f a s t f o r w a r d i n g b a s e do nt h ea r c h i t e c t u r e ，p e r f o r m a n c ea n dc o s to fn e t w o r kp r o c e s s o r ，a u t h o r c o m p a r e d a l lt h es e a r c h a l g o r i t h m s i n n p , i n c l u d i n g p a t r i c i at r e 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 ) ，c a c h e c a s c a d e ，b i n a r yt r i et r e e ，m u l f i b i t t r i ea n d b i n a r ys e a r c hb a s e do n t h el e n g t ho fa d d r e s sp r e f i x ，e t c t h e nat r e es e a r c he n g i n e b a s e do np a t r i e i at r e ew a sp r o p o s e d ，a n dt h ep r i n c i p l eo ft s ew a s p r e s e n t e di nt h i s p a p e r t s es u p p o r t se x a c tm a t c h i n gs c h e m e 【f u l lm a t c h ) ，l o n g e s tp a r e mm a t c h i n g ( l p m ) a n ds m tf o ru s e rd e f i n i t i o n ；i ts u p p o r t sb i n a r yp a t r i c i at r e e a n dm u l t i b i t p a t r i c i at r e e ；i ta l s os u p p o r t sc a c h e c a s c a d ea n dh a s h i n ga l g o r i t h m ；i na d d i t i o n ，i t s u p p o r t sb i n a r y s e a r c hf o r t r u n k i n g c o n s i d e r i n gt h en pp e r f o r m a n c e a u t h o ri m p l e m e n t e d t h et s ew i t hr t lc o d e t h r e em a i nb l o c k sp e r f o r m i n gt h et s ec o m m a n d sw e r ed e s c r i p t e di nt h i sp a p e r , s u c h a sf m l p m ，f m s m ta n dm i s c i no r d e rt oa s s u r et h ec o l t e c t n e s sa n dt om e e tt h ef u n c t i o n a l t e s t i n g a n d v e r i f i c a t i o n ，av e r i f i c a t i o np l a t f o r mo ft s e w a s p r e s e n t e d i na d d i t i o n ，t h ep a p e r a l s o i n t r o d u c e do u rv e r i f i c a t i o nm e t h o d o l o g y , v e r i f i c a t i o nf l o wa n dv e r i f i c a t i o nr e s u l ti n t h i sp r o j e c t k e y w o r d s ： n e t w o r kp r o c e s s o r ( n p ) ；t r e es e a r c he n g i n e 汀s e ) ；c a m ；v e r i f i c a t i o n 浙江大学硕士学位论文 1 1 研究背景及意义 第一章绪言 在过去的几年里，不论是因特网还是电信通信网，其带宽都呈爆炸性增长。 这对我们生活的方方面面都带来了极大的影响。目前，微电子技术、光通信技术 和各种系统理论带来的革新造成的这种高指数规律的信息科学技术的增长还将 持续发展下去。与此同时，人们使用带宽的费用却在不停的下降，由此使得我们 可以充分享用i s p 为我们提供的因特网网络服务。然而这将带来更多的带宽饥渴 现象和计算的密集型应用，例如因特网上的语音服务( v o i p ) 、音频和视频流业 务、p 2 p ( p e e r t o - p e e r ) 应用、虚拟专用网v p n ( v i r t u a lp r i v a t en e t w o r k s ) ，还有很多 其他我们现在所想不到的新业务。 为了能有效的处理这些应用业务，网络就得支持新的协议和利用新的技术。 比如新的网络设备需要支持差分服务( d i f f e r e n t i a t e ds e r v i c e s ) 、流量工程t e 、主动 网技术。此外，新设备要能支持各种网络管理功能。这些要求说明，在要求网络 设备有很高的吞吐量的同时，还需要它有一定的灵活性去支持新的协议与应用。 另外，网络设备变化带来的各种解决方案要尽可能快的面市。这些网络技术的发 展表现在： 1 更高的带宽：o c 1 9 2 已用于骨干网中，o c 7 6 8 正在发展o c - 4 8 已推 广到接入端； 2 更强的功能：更复杂、更具深度的分组处理。例如，具有u r l 交换功 能、安全处理功能和记账功能等； 3 可编程型：增加新功能，适应协议更新。 现在，传统的网络应用都是基于现场可编程门阵列f p g a ( f i e l d p r o g r a m m a b l e g a t ea r r a y s ) 来实现较低层的处理，而通过通用处理器g p p ( g e n e r a lp u r p o s e p r o c e s s o r ) 来实现高层的处理。这两种解决方案中的任意一种都无法满足网络处 理的各种需求。对此人们提出了各种办法，我们来看一下当前出现的这些方法： a s i c ( a p p l i c a t i o ns p e c i f i ci n t e r g r a t e dc i r c u i t ) 专用集成电路解决方案这 是一种全硬件系统解决方案； 浙江人学硕士学位论文 a s i p ( a p p l i c a t i o ns p e c i f i ci n s t r u c t i o np r o c e s s o r ) 专用指令处理器解决方案 这是一种专门为特定应用域设计的指令集处理器方案； 协处理器( c o p r o c e s s o r ) 方案协处理器实质上也是一种硬件，但是与 a s i c 不同的是，它有一定的接口编程能力； f p g a 方案这是一种可在门级进行再配置编程的设备； g p p ( g e n e r a lp u r p o s ep r o c e s s o r ) 方案这是一种实现通用目的的可完全编 程的处理器解决方案，实际上也就是原来的通用c p u 加上r a m 的简 单方案。 曼 话 性 g p p j 一 任墨 图表1 系统应用范围示意图 正如图1 中所示，a s i c 是尽可能使用硬件，基本上没有什么灵活性，但却 能够提供最优的性能；作为另一对立面，g p p 具有最大的灵活性，但性能也最低： f p g a 提供的解决办法比较有效，那就是在缺少a s i p 或协处理器的情况下，他 们的综合性能要高于g p p 或a s i c 。 考虑到各个方面的权衡，我们可以看到，a s i p 在绝大多数网络系统应用中 都是一种最好的解决办法。一个为网络设计的a s i p ，事实上也就是现在所称的 网络处理器n p ( n e t w o r kp r o c e s s o r ) ，充分体现了硬件与软件的平衡，并满足了 前面所提到的网络发展的所有要求，即： 性能通过在硬件中执行关键的可计算核，n p 能在线速度下满足许 多应用的性能要求； 灵活性n p 的软件系统是其重要的系统组成部分，这样通过校正软 件，可以很灵活的适应协议标准和应用的变化； 更快的t t m ( t i m e - t o m a r k e t 卜与设计同功能的硬件系统相比，设计软 浙江人学硕士学位论义 件在设计时间与设计售价上都要少很多； 功耗n p 可能不被嵌入到能耗敏感的设备中，比如手提设备，因此 它们的功耗更多地需要考虑的是售价的原因，比如说封装。 网络处理器n p 是系统设计从全定制专用集成电路设计转向可编程应用系统 设计中出现的产物。在网络通信应用的很多领域的大量趋势表明，通信系统的设 计在采用a s i c 系统存在很多困难，这主要体现在： 1 深亚微米d s m ( d e e ps u b m i c r o n ) 效应加剧了电路设计的困难性； 2 大量的片上设备的指数增长； 3 片上不同设备单元的增长； 4 缩短t t m 的要求。 以上这些因数的组合压力导致系统应用设计更多地朝可编程性解决方案方 向考虑。网络处理器的概念从提出到现在仅四五年的时间就受到如此广泛的注视 并出现爆炸性的增长，充分说明了系统设计可编程性的需求之旺。 1 - 1 1 什么是网络处理器 网络处理器( n e t w o r kp r o c e s s o r , n p ) 是为网络应用领域设计的专用指令处理器 a s i v , a s i p 具有自己的结构特性和专门的电路设计以适于网络分组处理，同时它 又是一块软件可编程的芯片。具体定义如下： n p 是具有以下功能的i c ： 1 它具有软件可编程能力； 2 它是对分组处理流程的优化，以满足线速处理要求： 3 它可以接管很多原来主c p u 完成的控制与管理功能。 1 1 2 什么是搜索引擎 在网络处理器中，主要包括如下六大核心功能模块：模式匹配、查寻、计算、 数据操作、排队管理、控制处理。而本论文主要讨论的就是查寻功能模块，即搜 索引擎。它的功能就是根据一些关键值完成数据查找功能。它常与模式匹配相结 合，以便在表中找出所需的条目。查找中所使用的数据结构和算法依赖于查找类 型的要求以及关键字的大小。对于a t m 和m p l s ，这个用于查找的域很小，而 浙江人学硕士学位论文 且映射是一对一的，所以通常对a t m 和m p l s 也只需要查找一次。然而对于i p v 4 和i p v 6 的路由，由于它们有很大的地址域，使得我们不太可能在一次存储器的 存取中就发现目的地址。 随着路由表迅速增大，网络交换日趋频繁以及更高速连接，特别是向着 i p v 6 ( 1 2 8 位) 的发展，网络地址查找变成个巨大的挑战。搜索的主要工作是在 路由数据库中找到i p 包的目的地址( 数据链路桥( d a t al i n kb r i d g e )1 0 0 m b p s 的速度在好几年的时间很好的胜任了这个工作) ，但是这些传统的搜索方法，包 括h a s h i n g 、二进制搜索、c a m s ，已经不能适用当前的搜索要求了，因为当前 的搜索需要最长前缀匹配，而不是简单的精确匹配。当然我们也可以通过软件的 方法来实现数据搜索，但是明显它不能满足互联网线性的搜索速度。所以，必须 要求我们有更强有力的硬件搜索算法或者改进的传统搜索方法来满足地址查找 的需求。 前缀匹配是在9 0 年代初提出来的，当时它就预见了网络终端数及查找信息 将会迅速膨胀。网络传统分类分为a 类，b 类，c 类，但是这种分类方法逐渐被 认识到太不灵活也太浪费地址空间。为了更好的利用地址空间，特别是b 类的 地址空间，我们可以把几个c 类地址捆绑在一起来代替个b 类地址，但它并 不是一个真正的b 类地址，这将会导致路由表的大小变得更为庞大。于是就产 生了一种技术，称为无类别域间路由选择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 ) ， 它允许网络地址任意的分割以减少路由表的大小。如今一个i p 路由表的数据库 包括很多个地址前缀，当一个i p 路由器接收到一个包时，它需要去找到哪个前 缀跟它目的地址最长匹配，随后这个包就传给最长前缀对应的输出链路。例如， 前缀p 1 = 0 1 0 1 ，p 2 0 1 0 1 1 0 1 和p 3 = 0 1 0 1 1 0 1 0 1 0 1 1 ，如果一个地址的前1 2 位是 0 1 0 1 0 1 1 0 1 0 1 l ，那么它找到的最长前缀是p 】。如果前1 2 位是0 1 0 1 1 0 1 0 1 0 1 1 ，那 么它找到的最长前缀是p 3 。所以说，最长前缀匹配是可以实现地址层次查找， 而h a s h i n g 等传统搜索只能是全匹配查找。 基于p a t r i e i a 树的各种树形查找方式能实现这个最佳前缀匹配，它被实现在 各种网络处理器中。本文介绍的网络处理器中所用到的搜索引擎也是一个基于 p a t r i c i a 树的搜索算法。 浙江大学硕士学位论文 1 2 研究方法及过程 笔者从实际的网络处理器项目出发，更从工程的角度出发，对多个网络处理 器的搜索算法进行横向和纵向比较，特别是结合整体性能和性价比等因素，然后 提出了树形搜索引擎的设计原理和设计方法。之外，笔者还提出了树形搜索引擎 的实现方案及其验证方法和验证环境。 论文也将根据这个思路，将在下面的章节逐一阐述笔者所参与的网络处理器 项目的框架结构，树形搜索引擎的原理，设计实现及其验证。 浙江大学碗上学位论文 第二章网络处理器及其树形搜索引擎介绍 2 1 网络处理器介绍 本论文所涉及的n p 采用的是多处理器解决方案，其中有8 x 1 1 个专门的协 处理器和1 个p o w e r p c 核。它支持4 个千兆网端口、4 0 个快速以太网m a c 或 p o s ( p a c k e t o v e rs o n e t ) 口，其处理目标定于第2 5 层分组。 2 1 1 网络处理器模块框图 我们的网络处理器由e p c ( e m b e d d e d p r o c e s s o rc o m p l e x ) 、专门的帧处理硬件 和外围设备接口等组成，如图2 所示： ! 巫匦匦亚亟凸 图表2 网络处理器整体框图 物理m a c 复用器( p h y s i c a lm a cm u l t i p l e x e r ) ：它是网络处理器的外部接 口，接收和发送外部物理层和网络处理器的数据。它包括两部分：i n g r e s sp m m 和e g r e s sp m m 。p m m 包括五个数据转移单元( d m u s ) ，其中四个d m u s ( a ，b ，c ，d ) 能被独立的配置成外接以太网的m a c 或s o n e t ( p o s ) m a c 端口。交换数据 转移单元( w r a pd m u ) 把数据从出口e d s 传送到入口e d s 。它支持4 g i g a b i t 以太网或2 5 g i g a b i tp o s 速率。 入口进列出列调度( i n g r e s se n q u e u e r d e q u e u e r s e h e d u l e r ) ：i - e d s 是p m m ， e p c 和s w i 的接口，它从p m m 的d m u 接收数据，存储在内部的存储单元里， 浙江大学硕士学位论文 当接收到一定的数据以后，它就会送给e p c 进行处理。在这里，i - e d s 不一定 要接受所有的帧数据然后再交给e p c ，它可以接受帧的一部分，如帧头，就可以 送给e p c 进行处理了。一旦e p c 处理完帧以后，帧需要重新移交给i - e d s ，i - e d s 随后进行流控制，抛弃一些无用的帧，并重新安排帧的顺序送给s w i 。 出口进列出列调度( e g r e s se n q u e u e r d e q u e u e r s e h e d u l e r ) ：它的功能跟i - e d s 的功能差不多，包括数据传输、数据存储、流控制、缓冲器管理、q o s 管理等操 作。 交换接口( s w i t c hi n t e r f a c e ) ：通过s w i 可以连接外部的交换接口板，形成多 个n p 的互联。它支持u t o p i a - 3 和c s i x 的总线协议。在交换接口模块中，帧需 要增加分组头，以及重新调整帧的内容。 内嵌p o w e r p c 核：它可以替代外面的控制单元( c p ) ；控制存储接口提供最 多1 g b p o w e r p c 编程空间： 内嵌处理单元e p c ( e m b e d d e dp r o c e s s o rc o m p l e x ) ：提供整个网络处理器的 处理功能；实现网络处理器的编程能力等等。总的来说，e p c 接受来自i - e d s 和e e d s 的数据，经过微码( p i c o c o d e ) 控制和硬件协处理器的协同处理，最终 决定进来的数据该进行什么样的处理，有可能被送往目的地址，也有可能被丢弃。 e p c 主要由下面几部分组成：8 个协议处理器( d p p u ) ：中断调试单步控制；指 令内存空间：控制存储器仲裁器：帧发送器；完成单元；硬件辅助分类器；入口 数据和出口数据存储、仲裁；控制总线仲裁器以及一些协议处理器内部协处理器 所对应的管理模块。 协议处理器( d p p u ) 是e p c 实现微码控制和协处理器的数据处理模块，它 由2 个c l p ( c o r el a n g u a g ep r o c e s s 0 0 ，11 个协处理器( c o p r o c e s s o r ) 和一个8 k 的共享内存组成。其中树形搜索引擎t s e 协处理器被两个协议处理器共享，这 将在下面的章节进行重点讨论。 2 1 2 网络处理器数据流程 浙江大学碗_ 上学位论文 1 s 一一”r a b t i c l 高昌 一：塑 ：一一一一一11 1 l 卜一 4 i n g r o s 6e d 8 ；。卜一 e a r j e o s 3 p c 。m m 。r。j 【一 2 1 曼匡圣吒 g l 1 一l 1 1 一 | 图表3 网络处理器数据流示意图 1 入口帧首先进入到输入物理m a c 复用器p m m ( i n g r e s sp h y s i c a lm a c m u l t i p l e x e r ) ，在这里完成帧的c r c 检查，之后被存储于缓冲器里。 2 i n g r e s se d s 会传递帧的一部分到协议处理器。 3 硬件分类器帮助协议处理器识别帧格式，以完成查询功能。树形搜索引 擎t s e ( t r e es e a r c he n g i n e ) i $ 过完成驻存在控制存储器中的路由表的查 找辅助完成搜索。控制存储仲裁器用于管理从属于不同协议处理器的多 个存储器查找。c o m p l e t eu n i t 完成在帧被送到交换结构板之前的排序 工作。 4 e p c 把处理好的帧传重新传给i n g r e s se d s ，完成q o s 和流控制( f l o w c o n t r 0 1 ) 功能。同时选择要传送的帧，把数据送到入口交换接口s w i ( s w i t c hi n t e r f a c e ) 。 5 入口交换接i ：1 完成必要的帧变换，例如增加m p l s 标签。 6 输入的出口帧以相反的方式进行处理。出口交换接口接受从s w i t c h f a b r i c 得到数据。 7 e g r e s se d s 把进来的帧传送给e p c 。一旦e p c 线程发现他接受到的帧 不是属于他所处理的范围时，e g r e s se d s 必须重新组织帧，并重新发送 给e p c 其他的线程。 8 e p c 处理。包括分类，查找，更新，抛弃等操作。 浙江大学颤士学位论文 9 e p c 把处理完的帧送给e g r e s se d s ，在出去之前进行流控带u ( f l o w c o n t r 0 1 ) $ 1 流量整形, ( s h a p e ) 。 1 0 p m m 完成最后送到对应端口的工作并完成其他一些功能，如加上 c r c 。 2 1 3 内嵌处理单元e p c e p c 有一个p o w e r p c 核和1 6 个可编程的微码处理器。每一对微码处理器共 享一个硬件协议处理器，以加速树形搜索和帧操作的速率。 图表4 协议处理器内部结构框图 当n p 内部需要实现一些固定的算法和特定的任务时，我们可以考虑使用协 处理器来实现，( 当然我们用软件方法也可以实现，但是可能需要花费更多的时 间，降低了n p 的性能) 。 协处理器硬件有两种工作方式一旁路调用与数据通路。以旁路调用方式工作 的协处理器类似于过程调用，由主处理器根据需要调用。而数据通路上的协处理 器则以流水线方式处理数据，在数据通过它时对数据进行修改。后者有两个问题。 首先，为了避免成为瓶颈，数据通路上的协处理器必须以线速度工作；第二，由 于这些协处理器更紧密地集成在设计中，很难进行改变。以旁路调用方式工作的 协处理器有着模块化的优势，可以根据需要扩展，增加新的协处理器，不需要对 浙江人学硕士学位论文 体系结构作太大改动。但是，旁路调用时主处理器与协处理器之间大量数据传输 产生的开销将影响性能。我们采用的是旁路调用这种工作方式。 在我们的协议处理器中有1 1 个协处理器( c o p r o c e s s o r ) ： 1 数据存储( d a t as t o r e ) ：它是到帧缓冲器的接口，可以提供d m a 能力； 2 校验和处理( c h e c k s u m ) ：计算头的校验和： 3 排队( e n q u e u e ) ：它与c o m p l e t i o nu n i o n 对接，用于将帧送到目的端口 4 5 6 7 8 9 1 0 1 1 的正确队列： 控制总线接e i ( c a b ) ：为协议处理器提供存取内部寄存器、计数器和存 储器的通道； 串拷( s t r i n gc o p y ) ：在e p c 内实现高效的数据搬移； 计数器( c o u n t e r ) ：维护协议处理器中计数器，包括读，写及更新； 策略管理( p o l i c y ) ：检查流控制信息，以校验它是否与先前预先分配的 带宽保持一致； 标签( s e m a p h o r e ) ：标志一个实体是否获得所有权或者被锁住； 外部设备接口( q d r ) ：从外部的q d r 存储器中读取数据； 带宽分配( b a t ) ：为每个线程解决带宽的分配问题； 树形搜索引擎( t s e ) ：从控制存储器中的表中查找，并完成必要的搜 索。 2 2 搜索引擎比较 查找路由表的目的就是为了找到个最能匹配给定目标的特定地址。我们称 这个给定的目标为查找键( s e a r c hk e y ) 。所谓最能匹配的地址，也就是说，最长 长度匹配的地址。 路由查找算法可以分为两类：基于地址前缀值的路由查找算法和基于地址前 缀长度的路由查找算法。基于地址前缀值的路由查找算法是通过对整个地址前缀 空间进行地址关键字穷举来消除地址前缀长度对查找的影响，而基于地址前缀长 度的路由查找算法是在前缀长度空间内进行查找，与基于地址前缀值查找相似。 下面介绍几种传统的路由沓找算法： 浙江大学硕士学位论文 2 2 1p a t r i c i a 树 p a t r i c i a ( p r a c t i c a la l g o r i t h m t or e t r i e v ei n f o r m a t i o nc o d e di na 1 p h a n u m e r i c ) 是1 9 6 8 年提出的，它提供了一种在大文件里存储、检索和重新得到信息的很好 的方法。i p 的查找，它每次处理一位地址，所以这种算法的效率是比较低的。 在一个3 0 0 m h z 的系统内，一个2 4 位p r e f i x 的查找，平均要花费1 5 0 0 n s ，最差 的情况要花费2 5 0 0 n s 。 2 2 2 精确匹配的改进算法 前面说到，因为当前的网络路由不仅需要进行全匹配的查找，而且还要进行 最长匹配的查找，所以像h a s h i n g 和二进制搜索等传统的快速查找技术已不能直 接应用于当前的搜索。 b u t l e rl a m p s o n 提出了一个改进的二进制搜索方法，但是这种方法进行一次 搜索要地、仃z - l o g ，z ”步，n 是指路由表的e n t r y 的个数。随着当前路由表越来越大， 最差的情况可能需要1 7 步数据查找，也就是要1 7 次访问存储器，这就需要很长 时间。任何二进制搜索算法的平均访问次数为l o g ：。效率也不是很高。 另一个线性搜索方法，就是把每个可能长度的p r e f i x 都进行精确匹配，然后 挑出最长的。那么这个它要进行w 次精确搜索。w 指输入地址的长度，如i p v 6 ， 则w = 1 2 8 。 2 2 3 二进制t r i e 树( b i n a r yt r i o 用二进* i j t r i e 结构来表示地址前缀是一个常用的方法，t r i e 采用一种基于树的 数据结构，它通过前缀中每一位比特的值来决定树的分支。图表5 就是用二进制 t r i e 结构( 树中每一个内部结点最多包含两个子结点) 来表示的地址前缀表。 浙江大学硕士学位论文 。 一 一 l0 j ( d 廷， u ( i 、 图表5 二进制t r i e 树结构 在t r i e 树中，处于第l 层的结点代表了一类地址前l 比特均相同的地址空间， 并且这前l 个比特串就是由从根结点到这个结点路径上的l 比特组成。例如图5 中 处于第三层的结点c ，它就代表了所有前3 个比特为0 1 1 的地址族，而且比特串0 1 1 就是根结点到结点c 路径上的比特按照遍历顺序构成。图5 中带阴影的结点表示该 结点对应着一个地址前缀，因此这些结点中包含了该地址前缀相关的转发信息。 图5 中的阴影结点既可以是叶子结点( 如结点b ) ，也可以是中间结点( 如结点a ) 。 2 2 4 路径压缩t r i e 树( p a t h - c o m p r e s s e d t r i e ) 月i 、。 ” - 3 ， h 0 7 t吵，1 p r e f i x e s b0 1 0 0 0 dl 十 e 1 0 0 f1 1 0 0 + 9 1 1 0 1 h l l l 0 i1 】l h 图表6 路经压缩f r i e 树结构 图5 中t r i e 树经过路径压缩之后得到的t r i e 树如图6 所示。比较图5 和图6 ，可以 看到，结点b 的前两个父结点已经被删除，结点a 从原来单分支结点处移动到了二 分支结点处，原来的单分支结点被删除。由于删除的单分支结点可能包含多个地 址前缀信息，所以路径压缩t r i e j 瞄结点中可能包含多个地址前缀。t r i e 树搜索过程 由于某些结点被删除，所以可以忽略目的地址中某些比特位的匹配操作，因此结 点处需要维护一个变量指示下一个需要检查的比特位。另外与二进带r j t r i e 树相比， 路径压缩t r i e 树前缀结点处需要保存地址前缀的比特串。查找过程与二进带l j t r i e 树 类似，但是在结点选取分支时考虑的是比特位变量所指示的比特位。当查找过程 遇到前缀结点时，需要进行前缀匹配操作。当到达叶子结点或者是前缀匹配操作 浙江大学硕士学位论文 失败时，查找过程终止，查找结果是查找过程中已被记录的最长匹配前缀。 路径压缩的思想最初在被称为p a t r i c i a 算法中提出，但是该算法不支持最 长前缀的查找。s k l o w e r 对该算法进行了改进，使之能够适应最长前缀的查找， 并且在b s d ( b e r k e l e ys o f t w a r ed i s t r i b u t i o n ) u n i x 中实现了这个算法。 简单二进s u t r i e 树和路径压缩t r i e 树的不足之处在于查找过程需要大量的存储 器访问操作，对于i p v 4 地址来说最差情况需要3 2 次存储器操作。实验表明，使用 b s d 路径压缩t r i e 树来表示典型路由器中4 7 ，1 1 3 表项数目的前缀表，最大搜索深度 为2 6 ，平均搜索深度也达到了2 0 。使用简单二进n t r i e 树来表示同样的地址前缀 表，它的最大搜索深度为3 0 ，平均搜索深度为2 2 。 2 , 2 5 多分支t r i e 树( m u l t i b i tt r i e ) 2 2 5 1 基本算法 一种提高t r i e 树查找效率的方法就是查找的每一步检查地址中的多个比特，而 不仅仅是一个。例如，如果我们每次查找检查地址的4 个比特，那么i p v 4 地址查 找最多只需要8 次存储器访问操作就可以了。我们把每一次查找中需要检查的比 特数称为查找步宽( s t r i d e ) ，查找步宽可以是固定的，也可以是可变的。二分 支t r i e 树实际上就是查找步宽为l 的t r i e 树。我们把查找步宽大于1 的t r i e 树称为多分 支t r i e 树( m u l t i b i tt r i e ) ，因此对于查找步宽为k 的多分支t r i e 树来说，每个结点的 最大分支数为2 。 在多分支t r i e 树中，同层中不同子树的步宽可以是一样的，也可以是不一样 的。一般来说，固定步宽的多分支订i e 树实现简单，但是会浪费较多的存储空间； 而可变步宽的多分支t r i e 树实现上复杂一些，但是可以节省定的存储空间。 多分支t r i e 树查找过程的每一步需要检查多个比特，因此它不能支持任意长度 的地址前缀。为了能够用多分支t i l e 树来进行前缀查找，前缀表中的地址前缀需 要转换成多分支t r i e 树查找能够允许的地址前缀才行。 多分支t r i e 树的查找过程与二分支t r i e 树的查找过程类似，在每次结点访问过 程时，记录下到目前为止已经匹配上的最长地址前缀，直到到达叶子节点搜索过 程结束。尽管多分支t i l e 树的查找也是基于地址前缀长度的线性遍历法，但是因 为多分支t r i e 树采用的步宽大于1 ，所以它的搜索效率大大提高了。 浙江大学硕士学位论文 2 2 5 2 多分支t r i e 树的优化算法 多分支t r i e 树设计的关键是步宽的选择，也就是如何在算法查找速度和算法消 耗的存储空间两个尺度上进行折衷。在极端情况下，可以使用一层步宽为3 2 的多 分支t r i e 树，显然在这种t i l e 树结构下每次查找只需要访问一次存储器操作就可以 了，但是需要耗费2 3 2 个表项存储空间。 一种较合适的方案就是根据实际地址前缀的分布来选择合适的步宽，即根据 二分支t r i e 树结构来构造多分支t r i e 树。例如，在图5 中前缀d 的右分支子树就是一 棵满二叉树，显然我们可以用一棵1 层4 分支t r i e 树来代替这棵2 层二分支t r i e 树， 这种情况下进行前缀扩展转化是很直接的想法，但是在其他情况下我们如何来进 行步宽选择就需要我们使用一些特殊的优化策略，s r i n i v a s a n 等人提出了一种多 分支t r i e 树的优化算法。他们算法的出发点是在多分3 t r i e 树搜索深度固定的情况 下，如何来选择合适的步宽来使得整个t r i e 树的存储空间达到最小，在算法设计 中他们根据实际地址前缀的特点使用了动态编程( d y n a m i cp r o g r a m m i n g ) 的思 想来达到优化算法存储空间的目的。 2 2 5 3 多分支t r i e 树的压缩算法 多分支t r i e 树需要通过前缀扩展的方法来建立，在前缀扩展的过程中，前缀的 转发信息被扩展到了t r i e 树的多个结点中，因此信息的冗余度非常高。不少研究 者试图通过数据压缩方法来降低这种冗余度，从而达到降低算法占用存储空间的 目的。 r u n - l e n g t h 压缩法是一种很简单的压缩方法，并且它能够很好的应用于地址 前缀查找问题。r u n 1 e n g t h 压缩的做法是将一系列连续的、拥有同一信息的地址 范围表示为该信息和记录该信息出现的次数。 2 2 6 地址前缀长度的二分查找法 为了能够减少查找的时间，w a l d v o g e l 等人提出了在地址前缀长度空间内进 行二分查找的算法。如果能够在前缀长度空间内实现二分查找，那么整个查找性 能就可以从o ( w ) 提高n o ( 1 0 9 w ) 。但是我们不能简单的将二分查找法直接 应用到前缀长度空间内，例如，假设有三个地址前缀0 ，0 0 + 以及1 1 1 + 。假设现 在需要查找111 ，二分查找法首先从前缀长度为2 的h a s h 表开始查找关键字11 ，因 1 4 浙i 工大学硕士学位论文 为h a s h 表中只有表项o o ，所以查找失败，而实际上在长度为3 的h a s h 表中具有匹 配关键字。为了解决这个问题，我们在前缀长度2 的h a s h 表中添加一个表项1 1 ， 这种表项被称为m a r k e r 。现在查找关键字l 1l ，首先在前缀长度2 的h a s h 表中查找 就会查找成功，然后二分查找法将会在前缀长度空间的下半部分继续查找 前缀长度的二分查找法将大大提高查找的效率，对于i p v 4 地址来说，查找过 程最多需要l o g ：= 5 次存储器访问，对于今后将会使用的i p v 6 地址来说，查找过 程最多需要l o g = 7 次存储器访问。 2 2 7 缓存策略 在路由查找中，可以使用缓存策略，把最近查找过的目的地址路由存放在高 速的路由缓存表( r o u t ec a c h e ) 中，只有当路由缓存表中查找失败的时候，我们才 需要进行真正完整的前缀查找匹配过程。 为了能够在查找性能上获得较大的提高，缓存的命中率就需要有一定的保 证，假设缓存查找速度是路由前缀查找速度的2 0 倍，经过计算可以得出，为了 能够使平均查找性能达到原来的1 0 倍，缓存的命中率需要达到9 5 左右。随着 i n t e m e t 的不断发展，网络用户的不断增加以及业务数据量的多样化，数据的时 间局部性变得越来越不明显，从而大大的降低了缓存的命中率。所以缓存的大小 应该能够随着网络用户或者网络数据业务量的增加而相应线性的增加。 2 2 ，8 内容可定址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 ) 一般的存储器技术是收到一个地址，然后根据地址取出所对应的存储内容。 而c a m 则采取了相反的设计原则，它的输入就是已存在m e m o r y 里面的数据， 而得到的结果是数据的地址。输入的数据，我们称之为s e a r c hk e y 举个简单的 例子，我们要从路由表中查找下一跳的地址，它的输入就是目的地址，得到的地 址将成为下个搜索必要信息。 c a m 一般分为二态c a m ( b c a m ) 和三态c a m ( t c a m ) ，二态c a m 用于 低层的应用，例如，m a c 表，2 层v p n 。三态c a m 可以用于高层协议，如q o s 和c o s 等，也是应用最广泛的。 浙江大学硕士学位论史 一c o n t r ( 1 1 & s t a c u 5 。一 一 5 。 图表7 c a m 内部体系结构 下面来看看c a m 的一些特性： 1 c a m 的响应时间很短，大概只需要一个时钟的时间； 2 它可以实现多块c a m 的级联，从而增大路由表的容量： 3 搜索的宽度和深度可配置，这样就允许多个搜索并行执行： 4 ，学习功能 c a m 也存在着很多不足的地方，以至于现在很多新的n p 设计厂商都已经 不用c a m 来进行搜索，而是利用本身自己的搜索引擎。例如，a g e r e ，e z c h i p 。 还有就是我们要介绍的这个树形搜索引擎，它是一个完全独立于c a m 而进行搜 索的搜索引擎。它的缺点体现在如下几个方面： 1 费用昂贵，一片c a m 至少需要几百美元。 2 它占用芯片上的很大一块面积： 3 它的功耗很大； 4 很难在查找同时更新路由表 因为s e a r c hk e y 是不定长的，3 6 ，7 2 ，1 4 4 都有可能，而大多数c a m 都被 设计为7 2 位长的s e a r c hk e y 。这样的话，很多操作，如对于3 6 位的搜索需要由 软件的协调才能正常进行，这样性能肯定会降低很多。有的c a m 厂商可能会提 供两种长度的搜索，而且效率也不会降低，但是价格也会贵很多。 维护和路由表管理是另外一个大的问题。我们刚才讲到，c a m 在更新的同 时是不能进行搜索操作的。这样就会降低整个系统的性能数据交换变慢，当 前的包必须暂存起来直到数据更新结束，然后再继续搜索。再进一步我们可以看 到，路由表的维护不仅仅是我j f i n u 才提到的表的更新，它还可以包括表格单元甚 6 浙江人学硕士学位论义 至整个表格位置的从定位，因为c a m 中各个子表可能由于几次更新而产生了很 多新的空间。当一块空间满了，整个路由表就需要重组，这就需要额外的操作来 实现。对于每一个重定位的单元，我们需要一个读，写过程，如果是整个表格的 开始地址需要重新定位的话，那么m a s k 字节也必须要重新定位，这样又要增加 一个读写过程。站在用户的立场来看，如果仅仅因为表要更新而要影响搜索的 过程的话，这是不允许的。 可配置性不够强大，当前很多c a m 都会碰到这种问题，因为不同的系统公 司有着不同的要求：有的公司需要不同大小的路由表，但是买不起支持这些结构 的c a m ：有的公司在系统初始化的时候灵活性强一些而在运行过程中则可以少 一些灵活性，等等 2 2 9 树形搜索引擎 基于上面介绍的搜索引擎的优缺点，我们设计了基于p a t r i e i a 树的树形搜索 引擎t s e ( t r e es e a r c he n g i n e ) 。树形搜索引擎支持精确的全匹配搜索，也