（信号与信息处理专业论文）流分类技术的研究和硬件实现.pdf

北京邮电大学硕士学位论文 摘要 流分类技术的研究和硬件实现 摘要 流分类就是在路由器中把相同类型的报文归为一类流的操作。路 由器会对属于同一个流的所有报文中按照同样的规则进行相似的处 理。流分类主要用于防火墙，q o s 业务保证等领域。 随着因特网的发展，人们对于业务质量的要求不断提高。传统的 基于尽力服务架构的因特网无法有效满足现在网络的需求，这就会导 致越来越多的网络设备逐渐采用基于流的报文处理方法：首先对到达 的报文进行分类，然后根据分类的结果进行相应的调度、处理、统计、 流控，从而保证不同用户、不同业务的报文可以得到预约的服务质量 ( q o s ) 。 报文分类可以通过软件实现，但是随着网络速度的提高，很难达 到线速处理的要求，所以硬件分类器技术成为研究热点。 本文首先对路由器的发展的现状和将来的发展方向进行了一个 概述，将来的路由器，会提供更大的容量和更高的端口速率、有o o s 的保证、还将具有支持综合业务迅速成长需求的能力。 然后本文从时间复杂度，空间复杂度等方面对比了多种分类算 法，分析了各自的优劣。还针对硬件的实现结构进行了分析，并提出 了一个好的分类算法要达到的要求。 接着，本文重点介绍了基于d - l e f t 算法和片内c a m 的硬件哈希表 解决方案。此算法可以通过一次查表操作获得结果，解决了一般哈希 表存在的最坏访问时间的问题。利用片内c a m 使哈希表的加入失败 概率降到可以忽略的程度，同时提高了存储器的利用率。在实现方面， h a s h 函数我们采用c r c ，还可以按照设计需要折中考虑存储器利用 率、加入失败概率、占用片内c a m 资源多少以及硬件实现复杂度等 因素，具有很好的灵活性和可扩展性。将之应用到基于哈希表的硬件 报文分类算法中，可以有效的提高其处理性能。仿真和应用证明其有 很好的可行性和实用性。 最后，介绍了一下我在实验室的工作情况，着重介绍了双光口千 兆以太网接口板的原理图设计。 关键词：路由器流分类d - l e f tc r c 硬件实现c a m 北京邮电大学硕士学位论文 t h er e s e a r c ha n dh a r d w a r i m p l e m e n t a t l o no fp a c k e t c l a s s i f i c a t i o na l g o l u t h m a b s t r a c t t h ep r o c e s so fc a t e g o r i z i n gp a c k e ti n t o f l o w s i na l li n t e r a c tr o u t e ri s c a l l e dp a c k e tc l a s s i f i c a t i o n a l lp a c k e t sb e l o n g i n gt ot h es a m ef l o wo b e y ap r e d e f m e dr u l ea n da r ep r o c e s s e di nas i m i l a rm a n n e rb yt h er o u t e r p a c k e tc l a s s i f i c 撕o ni sn e e d e df o rn o n - b e s t - e f f o r ts e r v i c e s ，s u c h a s f i r e w a l l sa n dq u a l i t yo fs e r v i c e s w i t ht h eb u r s to fi n t e m e t ，p e o p l ea l er e q u i r i n gh i g h e rq u a l i t yo f s e r v i c e s t r a d i t i o n a lb e s t - e f f o r ts e r v i c e sc a l l tm e e tc u r r e n tr e q u i r e m e n to f n e t w o r k ，a sar e s u l tp a c k e tc l a s s i f i c a t i o na l g o r i t h m sa r eb e i n ga d o p t e db y m o r ea n dm o r en e t w o r ke q u i p m e n t t h er e a c h e dp a c k e t sa r ec a t e g o r i e d i n t od i f f e r e n tf l o w sf i r s t l y , t h e ne v e r yf l o ww h i c ho b e y sp r e d i f i n e dr u l e s w i l lb es h e c d u l e d , p r o c e s s e da n ds t a t i s t i c e db yt h er u u t e r h e n c ei tc a n a s s u r ed i f f e r e n tu s e r sd i f f e r e n tl e v e l so fq o s p a c k e tc l a s s i f i c a t i o nc a nb ei m p l e m e n t e di ns o f t w a r e ，b u tw i t hr i s i n g o f t h en e t w o r ks p e e d ，i ti sb e c o m i n gm o r ea n dm o r ed i f f i c u l tb e c a u s ei ti s s oh a r dt op r o c e s sa tl i n e s p e e d t h e r e f o rh o wt oi m p l e m e n ti nh a r d w a r e i st h ek e yp o i n to f p a c k e tc l a s s i f i c a t i o nt e c h n o l o g y f i r s t l yt h i sp a p e ri n t r o d u c e st h eb a s i ck n o w l e d g eo fr o u t e ra n di t s d e v e l o p m e n to r i e n t a t i o n w et h i n kt h a tf u r o r er o u t e r sw i l lp r o v i d eb o t h l a r g e rc a p a c i t ya n dh i g h e rp o r t s p e e d ，a n da tt h es a n l et i m ei t w i l ls e c u r e q o sa n ds u p p o r ti n c r e a s i n gi n t e g r a t e ds e r v i c e s s e c o n d l yt h i sp a p e rc o m p a r e ss e v e r a lc l a s s i f i c a t i o na l g o r i t h m sa n d a n a l y z e st h e i rp r o sc o n si nt i m ea n ds p a c ec o m p l e x i t y f i n a l l y , t h i s p a p e rp r e s e n t s a n a p p r o a c h f o r o b t a i n i n g 北京邮电大学硕士学位论文a b s t r a e t h i g h - p e r f o r m a n c eh a r d w a r e h a s ht a b l eb a s e do nd l e f ta l g o f i t h ma n d o n c h i pc a m h a s ht a b l e ，w i t hi t sl o w e rc o s ta n db e r e rs c a l a b i l i t y , i s w i d e l yu s e di nm a n yr o u t i n ga n dp a c k e tc l a s s i f i c a t i o na l g o f i t h m s t h i s p a d e ra d o p t sc r ca so u rh a s hf u n c t i o ni n o u rp a c k e tc l a s s i f i c a t i o n a l g o r i t h m t h et i m ec o m p l e x i t yo fi n s e r t i o na n dl o o k - u pt i m eo fh a s h t a b l ei s o n l y 廿( b yu s i n gd - l e f ta l g o r i t h m b e n e f i t i n gf r o mf a s t e r o n c h i pc a m t h ef a i l u r ep r o b a b i l i t yo fi n s e r to p e r a t i o nd e c r e a s et ou l t r a 1 0 w1 e v e l ，a tt h es a m et i m e t h ea v a i l a b i l i t yr a t i oo fm e m o r yi si m p r o v e d d r a m a t i c a l l y t h er e s u l t so ft h ee x p e r i m e n t a la n da p p l i c a t i o ns h o wt h a ti t i sp r a c t i c a la n de 蚯c i e n t a d d i t i o n a l l y , t h i sp a p e rr e c a l l st h ew o r k su n d e r t a k e ni nl a ba n d m a i n l yf o i c u so nt m ad u p l e xg i g a b i te t h e m e ti n t e r f a c eb o a r d k e yw o r d s ：r o u t e rp a c k e tc l a s s i f i c a t i o nd l e f tc r cc a mh a r d w a r e 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所 知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢 意。 申请学位论文与资料若有不实之处，本人承担- - t , l 相关责任。 本人签名：孟窑二缸卜日期：丑西二3 工石l 一 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生在校 攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国家有关部 门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论 文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 她篡裟鬣鬟竺 本人签名： 匕聋、盘蟠 刷谥铄贯一 ，l 适用本授权书。 日期：邀：王盔 日期： 北京邮电大学硕士学位论文流分类技术的研究和硬件实现 第一章绪论 1 1 路由器概述 路由器是互联网络的枢纽、”交通警察”。它的主要作用就是在源节点和目的 节点之间为数据交换选择路由，主要功能有： 1 网络互连，路由器支持各种局域网和广域网接口 2 数据处理，提供包括分组过滤，分组转发，优先级，复用，加密，压缩 和防火墙等功能。 3 网络管理，路由器提供包括配置管理，性能管理，容错管理和流量控制 等功能。 1 2 路由器基本功能介绍 路由器是构架因特网的核心设各之一，从因特网出现之初，路由器经历了数 十年的发展，系统容量不断增加，体系结构也发生了多次变化，但其所包含的基 本功能并没有发生太大的变化，如图1 - 1 所示。 j a 面。h 二二二= 玉_ 图1 - 1 路由器功能模决图 下面我们依次介绍路由器中的各个基本功能模块。 一 i p 查表 路由器的主要任务是完成报文转发，即根据报头中的目的p 地址，将到达 输入端口的口报文转发到正确的输出端口。为此，在路由器中通常需要运行一 定的路由协议软件，通过路由协议软件，以及用户的手工配置，在路由器中生成 第1 页 北京邮电大学硕士学位论文 流分类技术的研究和硬件实现 一个转发表，该转发表中包含不同目的d 地址对应的下一跳输出端口信息。口 查表过程即根据报文的目的m 地址，查找路由器中的转发表，得到报文的下一 跳输出端口的过程。 随着因特网的发展，1 9 9 3 年，基于c i d r ( c l a s s l e s s i n t e v d o m a i n r o u t i n g ) 的地址分配和路由方案被采纳。c i d r 一方面有效抑制了转发表大小的指数增长 趋势，提高了i p 地址的利用率，但同时也增加了查表实现的复杂度。此时 的转发表中包含一系列的口前缀( 口p r e f i x ) ，每个前缀对应一定的前缀长度和 下一跳输出端口，对于一个目的p 地址，它可能与多个前缀同时匹配，此时需 要按照匹配的最长前缀对应的输出端口进行报文转发，这样的查表过程称为最长 前缀匹配( m a x i m u mp r e f i xl e n g t hm a t c h ) 查表。 报文处理 报文处理即按照协议的要求，对报文的内容进行相应的修改。例如对于口 协议，需要修改的内容通常包括：报头中的t 1 工域，如果需要对报文进行拆分， 则需要修改报头中的d f 、m f 、c h e c k s u m 、f m g r n e n to f f s e t 域。对于m p l s ， 可能的报文处理操作包括标签( l a b d ) 的替换，标签堆栈的压栈以及弹出等等。 交换 交换功能主要存在于包含多个输入输出端口，尤其是包含多块接口板的路由 器中。交换功能的主要任务是：根据坤查表得到的报文的下一跳输出端口，将 报文传送到相应的输出端口或者接口板。交换功能通常可以采用总线、交换芯片、 交换背扳、或者专用的交换板实现。交换功能通常具有一定的交换容量、交换延 迟等参数。对于高速交换，现在通用的方法是：在交换之前，首先将报文分割成 固定长度的短数据块，然后交换这些短数据块，在交换完成之后重组短数据块得 到报文。这样的结构可以大大简化交换功能实现的复杂度。由于交换阵中短数据 块的丢弃将会导致组成整个报文的若干个短数据块的失效，同时也会增加缓冲功 能重组短数据块的难度，此外，在交换阵中很难执行细致的丢弃策略，因此，对 于交换功能通常要求能够提供足够大的交换容量，使得在交换阵中的报文丢弃可 以忽略不计，报文丢弃主要在缓冲和队列调度模块中执行。 第2 页 北京邮电大学硕士学位论文 流分类技术的研究和硬件实现 - - i 一一一一，二二：歹- - ：，-，一，：)。t - - 卜 - - - - - - - 图i 一2 交换功能示意图 缓冲与队列调度 如图1 2 所示，在具有n x n 交换阵系统的路由器中，由于到达n 路交换 阵输入端口的报文经过交换阵后可能输出到同一路交换阵输出端口，因此交换阵 输出端口流量的突发性将有可能增加。为了容纳交换阵输出端口报文的突发性， 降低因此而产生的报文丢弃概率，通常需要在交换阵输出端口之后设置一定容量 的报文缓冲，报文缓冲通常包含一定的报文丢弃策略。队列调度功能主要用来保 证不同优先级的报文能够按照对应的优先级进行转发，以及同一优先级报文转发 的公平性。 一网络设备管理 网络设备管理完成路由器的管理功能，通常包括路由器的配置管理、故障管 理、性能管理、安全管理和计费管理5 个管理功能域。管理功能通常通过特定 的管理接口实施，如通过网络进行的s m v 口( s i m p l e n e t w o r k m a n a g e m e n t p r o t o c 0 1 ) 网管接口，通过控制台实现的c l i ( c o m m a n d l i n e i n t e r f a c e ) 管理接 口等等，此外，由于客户端i n t e m e te x p l o r e 非常普及，因此，基于h t t p 协议的 网络管理接口也为众多用户所青睐。 路由软件 路由软件的主要功能是运行一定的路由协议，如r i p ，o s p f ，b g p 等，由 路由协议生成一定的转发表，作为报文转发的依据。 1 3 路由器体系结构的发展历程 因特网出现之初的路由器通常由一台拥有多个网络接口的工作站，运行相应 的协议软件完成报文转发功能。随着因特网的蓬勃发展，人们对路由器的性能提 出了越来越高的要求，导致路由器在结构上发生了多次变化。纵观路由器结构的 几次变化，我们可以发现，这些变化主要遵循如下两条主线： 第3 页 北京邮电大学硕士学位论文 流分类技术的研究和硬件实现 第一，控制通道由软件处理，数据通道依靠软件和硬件协调完成，并且随着 路由器体系结构的发展，越来越多的数据通道功能更大程度的依靠硬件完成，即 硬件化程度不断提高。 第二，随着路由器体系结构的发展，越来越多的路由器功能模块由独立的软 硬件实体完成，即功能实现的专一化程度不断提高。 下面我们依次简要介绍在路由器发展过程中出现的几种典型结构。 单( 主从) 处理器共享总线结构 单处理器共享总线型路由器结构如图1 3 中( a ) 所示。这种路由器与安装 了多块网络接口卡的计算机在结构上非常相似，所不同的是，为了提高系统的实 时处理性能，这种结构的路由器通常采用实时操作系统。在这种结构的路由器中， 各个端口报文的收发、口查表、路由协议的处理、报文的缓冲与队列调度、网 络设备管理等功能均由运行在中央处理器上的软件完成。 ( & ) 单c p u 器由嚣结构( b ) 主占k p u 菇由嚣结梅 图1 - 3 单( 主从) 处理器共享总线型路由器结构 这种路由器结构的主要优点是：( 1 ) 主要功能实体均由软件实现，各个接口 卡主要完成底层的报文收发功能，因此接口卡成本较低，并且通过软件移植，可 以比较方便的提供对于不同协议类型的支持；( 2 ) 成本低，比较适合低速接入应 用。这种单处理器共享总线结构路由器主要存在以下缺点：( 1 ) 中央处理器需要 完成几乎所有的报文处理操作，因此成为系统的瓶颈，导致这种结构路由器的系 统容量非常有限；( 2 ) 这种路由器结构的扩展性很差，无论是支持的接口速率还 是支持的接口数目都较难提高；( 3 ) 系统容错性能较差，软件或者硬件故障将导 致整个系统完全瘫痪；( 4 ) 共享总线有可能也会成为系统性能的瓶颈。作为这种 结构的改进，可以采用图1 - 3 ( b ) 所示的主从处理器结构，将路由器各个功能模 块在不同处理器上实现，但其性能的提高通常比较有限。 _ 对称式多处理器共享总线结构 对称式多处理器共享总线型路由器结构如图1 _ 4 所示。每个接口板都包含一 个独立的处理器，完成该接口板特定的报文处理功能，如物理接口报文的收发， 第4 页 北京邮电大学硕士学位论文 流分类技术的研究和硬件实现 报文的处理，报文的坤查表，报文的缓冲和调度等操作。主处理器接收各个接 口板转发过来的路由协议控制报文，运行一定的路由协议软件，生成各个接口板 对应的转发表，此外，各种网络设备管理软件通常也运行在主处理器上。 图1 _ 4 对称式多处理器共享总线型路由器结构 采用这种路由器体系结构，完成了路由器功能专一化的第一步。各个接口板 的处理能力大大增强，同时，采用处理能力更强的处理器，可以进一步提高接口 板的处理能力，因此其容量扩展性较单( 主从) 处理器共享总线型路由器结构有 所增加。但在一定程度上，共享总线制约了其系统容量的迸一步提高。 _ 基于交换阵结构的路由器 采用硬件交换阵结构的路由器如图l - 5 所示。 图1 5 基于交换阵的路由器结构 第5 页 北京邮电大学硕士学位论文流分类技术的研究和硬件实现 由于采用了硬件交换阵结构，因此系统的交换瓶颈得到了很大程度的缓解。 从而促使接口板采用各种新的技术提高支持的端口容量，如各种高速硬件口查 表结构，高速报文缓冲结构等等。当前商用的端口速率为o c 1 9 2 ( 1 0 g b p s ) 的 接口板技术已经比较成熟，进一步的端口速率为o c 7 6 8 ( 4 0 g b p s ) 的接口板也 在一些路由器厂商的开发计划之中。 下一代t 级路由器 在基于交换阵结构的路由器中，通常采用高速背板连接交换阵和接口板，高 速背板的容量通常有限，当路由器容量达到数百g 甚至t 级时，交换背板便成 为系统的瓶颈，此时，更多采用如图1 6 所示的结构。 图l - 6 基于交换阵的路由器结构 数个接口板机架通过光纤连接到一个大容量的交换核心，这种结构同时也有 利于采用更加复杂的交换核一i i , 以提高系统的交换容量。 1 4 路由器的发展方向 1 4 1 提供更大的容量和更高的端口速率 受以下一些因素的驱动，路由器需要不断提高其所能提供的系统容量和端i s i 速率： 第一，个人计算机处理能力的不断增强和局域网技术的迅猛发展使得广域网 成为互联网容量进一步提高的主要瓶颈。 第二，传输技术得到了迅猛发展，w d m 和d w d m 技术将单根光纤的可利 用传输带宽提高到t b p s 级，但是，受到诸多技术因素的制约，路由器的容量和 第6 页 北京邮电大学硕士学位论文 流分类技术的研究和硬件实现 端口速率的提高相对滞后，导致路由器成为广域网容量提高的主要瓶颈。 第三，大容量路由器可以简化网络互连，降低设备和维护成本。 1 4 2 业务质量q u a l i t yo f s e r v i c e ，q o s ) 支持随着如p 电话、i p 视频等流媒体业务被加入到因特网中，人们发现， 因特网最初的尽力服务( b e s te f f o r t ) 模式严重阻碍了这些应用的顺利开展。同 时，因特网在其商业化过程中也遇到对其所提供业务质量等级化的需求，以满足 - 不同用户的多种需求，因此，如何在统一的因特网中提供多种不同的业务质量成 为因特网研究的一个热点，相应的，如何在路由器中有效支持业务质量也成为路 由器发展的一个方向。 1 4 3 未来路由器将具有支持综合业务迅速成长需求的能力 未来个性化路由器功能会更多，同时将向模块化方向发展，便于用户根据需 要，对模块进行取舍。一般来说，单一化功能的路由产品已经不能满足行业应用 的需要，路由器提供商需要根据应用环境为用户量身定制，功能化、安全化、定 制化、服务化的产品成为应用趋势。在关键的p 业务流程处理上采用了可编程 的、专为p 网络设计的网络处理器技术。网络处理器通常由若干微处理器和一 些硬件协处理器组成，多个微处理器并行处理，通过软件来控制处理流程。对于 一些复杂的标准的操作( 如内存操作、路由表查找算法、q o s 的拥塞控制算法、 流量调度算法等) 采用硬件协处理器来提高处理性能。这样实现了业务灵活性和 高性能的有机结合。 第二章流分类( 报文分类) 算法 2 1 硬件分类技术出现背景 i n t e m e t 的发展，要求对业务流分类处理。最初的因特网只能提供尽力服务 ( b e s t 2 e f f o r ts e r v i c e ) 类型的业务，即到达的报文以相同的优先级进行口查表、 报文处理、交换、报文缓存以及队列调度等操作，当路由器发生拥塞时，随机的 对报文进行丢弃，由端到端的上层协议对其进行处理。上述结构的优点在于：简 化了报文的处理过程，从而降低了路由器的实现复杂度。 然而随着因特网的发展，对于业务质量( q u a l i t yo f s e r v i c e ，q o s ) 的需求不 断提高，上述结构逐渐暴露出以下一些问题：首先，基于尽力服务架构的因特网 第7 页 北京邮电大学硕士学位论文 流分类技术的研究和硬件实现 不利于如口话音、i p 视频等多媒体业务的开展。由于多媒体业务不同于等传统 的数据业务( 例如：e m a i l 、f t p 、w w w ) ，对于传输信道有着较高的要求，而 在基于尽力服务架构的因特网上很难保证其所需的传输带宽需求，因此很难在其 上顺利开展多媒体业务；其次，基于尽力服务架构的因特网不利于其走上商业化 道路。商业化的因特网需要向用户提供有保证的服务，同时需要根据用户申请提 供不同等级的服务。 显然，基于尽力服务架构的因特网无法有效满足以上需求，这就会导致越来 越多的网络设备逐渐采用基于流的报文处理方法：首先对到达的报文进行分类， 然后根据分类的结果进行相应的调度、处理、统计、流控，从而保证不同用户、 不同业务的报文可以得到预约的服务质量( q o s ) 。 数据包分类的依据视具体应用可以非常灵活，如可以根据“源口+ 目的p ” 对报文进行分类，也可以根据“源口+ 源端口+ 目的i p + 目的端口+ 协议类型” 对报文进行分类，甚至可以包含h t t p 请求部分内容。我们将上述报文分类字段 组合称为流标识( f l o w i d ) ，具有相同流标识的报文序列称为流。判断到达数据 包属于何种流的过程，称作报文分类( p a c k e tc l a s s i f i c a t i o n ) 。在基于流的报文处 理中，不同流标识对应不同的处理参数，如流量管理参数、统计参数、优先级参 数等等，这些参数通常是事先申请好的，或者是通过信令建立的，保存在设备的 流表( f l o w t a b l e ) 当中。此时的报文处理过程如下所述：报文到达后，首先对 报文进行分类，即根据报文的流标识在流表中查找该报文所属的流，取出流表内 保存的该流对应的处理参数，然后根据这些处理参数对报文进行相应的处理。 报文分类可以通过软件实现，但是随着网络速度的提高，很难达到线速处理 的要求。硬件分类器技术成为研究热点。 分类的基本概念 从数学上看，报文分类问题与计算几何中的一些问题很相似。在计算几何中 有一个多维空间的点定位问题：给定多维空间中的一些互不相交的区域，找出包 含指定点的区域。一般说来，报文分类问题比多维空间的点定位问题复杂。假定 不同区域互不相交时，对n 条过滤规则和k ( k 3 ) 个分类域的情形，计算几何的 结果给出的最好结果是：在空间复杂度为o ( n 。) 时，时间复杂度为o ( 1 0 9 n ) ；或 者是在空间复杂度为o t n ) 时，时间复杂度为o ( ( 1 0 9 ) “) 。也就是说，对1 0 0 条 过滤规则，每条规则4 个域的情况，空间大概为1 0 0 m b ，时间大约是访存3 5 0 次。 这种效率显然是不可接受的。 但是数据流的分布和特定数据库中过滤规则的分布都有一定的规律性，或者 说有内在的结构。所以很多好的报文分类问题的解决方案都是考察到它们分布的 某一点规律性提出的。此外，二维的p 分类问题( 即针对目的口一源碑对的分 第8 页 北京邮电大学硕士学位论文流分类技术的研究和硬件实现 类) 相对简单，而且二维的报文分类在m u l t i c a s t 和v p n 中都有广泛的应用，具 有实际的意义，因此对二维的婵分类问题的研究较成熟，有一些优秀的算法作 为基础。所以，报文分类问题的解决的一个重要的思想，就是降维，将高维问题 转化为二维乃至一维的问题。在下一部分中，我们将介绍报文分类问题的几个典 型的算法，这些算法很清楚地体现了这些思想。 2 2 解决方案评价原则 报文分类问题的核心是高效的查找算法。一般来说，一个好的查找算法，必 须满足以下 三个条件： -速度快：这是评价一个报文分类算法中最重要的标准。通常要求p 查找能 够以线速进行，报文分类速度至少达到l g b p s 。网络上充斥着相当一部分的 短包，这很大程度是因为大量的数据都与w w w 服务有关，因此，通常都是 考虑最短包长( 如4 0 字节) 的情况下，折算成报文分类处理的比特率。在 算法的时间复杂度上有三种评价指标：( 1 ) 最坏情况：对一个包进行报文分 类的查找时间的最坏可能情况；( 2 ) 平均情况：在随机情况下，对一个包进行 报文分类的查找时间的平均值：( 3 ) 统计情况：在符合某种预先指定包或过滤 规则匹配率的分布下，对一个包进行报文分类的查找时间的平均值。考虑到 计算机的c p u 的计算速度比访问内存的速度快得多，因此当计算量大小在 可接受的范围内时，也可以使用查找中的访存次数来衡量一个查找算法的速 度： _占用内存少：在查找过程中，一个算法所需要占用的内存大小也是需要考虑 的重要因素。这个占用的内存不仅仅指容纳过滤规则数据库本身所需要的， 还指算法为了保证高速度的查找建立的各种数据结构所消耗的内存； 易于更新：共有三种可能的更新：( 1 ) 完全更新：是指初始化过程中从过滤规 则数据库中建立查找数据结构，或者是以后的重新建立全部查找数据结构的 过程：( 2 ) 增量更新：在查找数据结构中增加或删除一条过滤规则；( 3 ) 重组或 平衡：随着过滤规则的不断增加或删除，可能会造成查找的数据结构效率降 低。因此在适当地时候需要进行重组使其恢复原来的效率。 目前的大多数解决方案都比较重视前两个因素，即查找的时间效率和空间效 率，而这两个因素往往互相制约，或者说它们之间存在一种权衡( t r a d e - o f f ) 。 为阐述各种算法，定义以下概念： 定义1 一个地址d 是一个长度为w 比特的比特串( 这里是指二值比特串， 第9 页 北京邮电大学硕士学位论文 流分类技术的研究和硬件实现 各比特取0 和1 两个值，后面我们还会介绍三值比特串，每个比特还可以取值 为”，类似c a m ) ： 定义2 一个前缀p 是长度介于0 到w 问的一个比特串，l e n g t h ( p ) 表示前 缀p 的以比特数为单位的长度： 定义3 如果d 开始的l e n g t h ( p ) 个比特与p 相同，就称前缀p 与地址d 匹配： 定义4 包头h 是有k 个域实体，包头的各个域分别表示h 1 】，h 2 ，h i k 】， 其中每个域都是比特串； 定义5 一条过滤规则f 也具有k 个域。与过滤规则的一个域f i 相关联的 有一个匹配方式，它可以是下面三种匹配方式中的任何一个：精确匹配( e x a c t m a t c h ) ，前缀匹配( p r e f i xm a t c h ) 或范围匹配( r a n g em a t c h ) ： 定义6 域f i l 通过一个数值来指定，如果包头h 的域h i 与过滤规则f 的 域f 【i 】满足h i 】= f i ，那么就称h i 与f 【i 】精确匹配： 定义7 域f i 】通过一个前缀来指定，如果包头h 的域h i 】与过滤规则f 的 表示前缀的域f 嘲匹配，那么就称h 田与f 【i 】前缀匹配； 定义8 域f 脚通过一个范围指定，也即f 【i = v a l l - v a l 2 ，如果包头h 的域h i 】 与过滤规则f 的域f 曲满足v a l l h i 】v a l 2 ，那么就称h 【i 与f i 】范围匹配； 定义9 我们称过滤规则f 与包头h 匹配，当且仅当对h 的每个域h i 】都与 f 相应的域f i 】匹配。h i 】与f 【i 的匹配方式由f 嘲的形式指定，可能为上述匹配 方式中的任何一种。 定义1 0 报文分类定义：一个分类器( c l a s s i f i e r ) 包含n 个规则，r j ，1 ，n ， 每个规则有3 个部分： i r e g u l a re x p r e s s i o nr j 【i 】， i i p r i o d t yo f t h er u l ep r i ( r j ) ， i i i a c t i o n ( r j ) ， 这表示每个规则可以有自己的比对字段、比对方法，以及对应之执行动作 ( a c t i o n ) 。每个规则有不同的优先权，当输入报文同时满足多个规则的r e g u l a r e x p r e s s i o n 时，选出优先权最高的规则为分类的结果，并进而执行该规则之 a c t i o n 。比对字段可以是报头( p a c k e t h e a d e r ) 字段，也可以是净荷( p a y l o a d ) 的部分。 p 分类问题是最佳过滤规则匹配问题的一个实例。从这个定义中也容易看 出，口查找是报文分类的一个特例，它对应报文分类中单个域的情形。p 分类 问题中与每条规则相联系有一个a c t i o n ，它用来表示对满足相应过滤规则包的 相应的处理动作。另外，由于c i 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 ) 的存在，掩 码表示的i p 地址范围不一定是连续的，在口查找和口分类中的i p 范围也不一 第1 0 页 北京邮电大学硕士学位论文 流分类技术的研究和硬件实现 定是用前缀来表示的，但是总是可以用若干前缀来表示相同的m 范围。 2 3 分类算法 2 3 1s e t - p r i m i n gt r e e 集合删减树算法 集合删减树是首先发展出来的树结构算法，其主要原理是将由d e s t i n a t i o n a d d r e s s 及s o u r c ea d d r e s s 合成起来的检索条件，分别建立d e s t t r i e 及s o u r c e t r i e 后，再运用搜寻该d e s t - s o u r c et r i e 进行匹配。这个方法的基本好处是，运用树 这种数据结构进行搜寻匹配，其效率要比传统之线性检索( l i n e a rs e a r c h ) 或是 二分法检索( b i n a r ys e a r c h ) 均好得多。以图2 1 表示的前缀匹配条件表为例说 明集合删减树建立步骤如下 r u l ed e s t i n a t i o ns o u r c e a d d r e s sa d d r e s s r 1o +1 0 + r 20 +0 l r 3 0 l + r 40 0 1 + r 50 0 l l r 6l o +1 r 70 0 图2 - i 示例过滤规则数据厍 1 先依据表d e s t i n a f i o n a d d r e s s 建立d e s t t r i e ，作法说明如下： 由r 1 ( 0 + ) 开始，因r l 的第一个字符为0 ，因此由向左画一实线，标示 为0 ，接着第二字符为( 代表d o n t c a r e ，郎0 或1 均无所谓) ，即向下方画一 虚线；r 2 、r 3 因与r 1 相同，因此树和r 1 相同：接着看r 4 ( 0 0 ) ，因r 4 的 第二字符为0 ，因此延续r 1 往下，再向左画一实线，标示为0 ，第三字符为+ ( 代 表d o n tc a r e ) ，因此向下方画虚线，r 5 ( 0 0 + ) 亦同；再看r 6 ( 1 0 ) ，第一字 符为1 ，因此由树根开始向右画一实线，标示为1 ，第二字符为0 ，因此向左子 树画一实线，标示为0 ，最后为，因此向下方画一虚线( 代表d o n tc a r e ) ；最 后看r 7 ( + ) ，因+ 表示0 或l 均无所谓，因此由树根直接向下画一虚线，即告 完成。至此为止，已完成了d e s t i n a t i o n a d d r e s s 的d c s t - t r i e 。 2 再依据表- - s o u r c e a d d r e s s ，在d c s t - t r i e 的下方，建立s o u r c e t i l e ，作法说明 如下： 第1 1 页 北京邮电大学硕士学位论文 搋分类技术的研冗和坦件实现 由r l 之s o u r c e a d d r e s s ( 1 0 + ) 开始，因d e s t - s o u r c e t r i e 的原理是将同一 组规则( r u l e )的d e s t i n a t i o n , 及s o u r c e n 以配对，这里r 1 的d e s t i n a t i o n 为 0 + ，因此 , s o u r c et r i e 须由0 + 处往下画，而r l 之s o u r c e a d d r e s s 为1 0 ，因此 应延续! r 1d e s t i n a t i o n - 子树再往下画，首先由向右子树画一实线，标示为1 ， 接着向左子树画一实线，标示为0 。同理可将r 2 至r 7 之s o u r c e a d d r e s s 逐 项画出，而完成s o u r c e t r i e 之建置。 3 至此为止，一个基本的d e s t - s o u r c et r i e 已建立。 粤、 。步 ；、t r 1 ，7 7 1、 r 1 ，固，j - 崤，少7 ! ：。墨墨墨嚣肌霉 j 垂r 。幽竭蕊盈盈 毒 i 、苔 手o f 薹蒜踊露 r u uu ” 9 r bo 000 r 5r 2 r i r 7 圉2 - 2d e s t - s o u r c et r i e 然而，以这样的d e s t - s o u r c et i l e 来作实际运算，却发生了问题，说明如下： 假设有一i n c o m i n g p a c k e t ，其( d s t , s r c ) 为( 0 0 1 ，1 0 1 ) ，首先针对d e s t - t r i e 进 行匹配，依据最长前缀匹配( t h el o n g e s tp r e f i xm a t c h i n g ) 原则，将追踪到r 4 的 位置，然而接下来在比对s r ca d d r e s s 时，发现r 4 下面之s o u r c e t r i e 无一符 合，因而算法必须回溯( b a c k t r a c k i n g ) 到r 1 的位置，再往下比对s o u r c e a d d r e s s 。 然而，因为r id e s t ( 0 + ) 本身即是r 4d e s t1 1 0 0 * ) 的前置( p r e f i x ) ，因此只要是能 够到达r 4 节点，一定能够到达r 1 节点( 因为r 1 条件较宽) ，那么以此例而言， 既然树追踪都已经走到r 4 了，严格来说已经比r 1 还要满足匹配条件( 其本身 已是r l 的一种可能选择) ，那又何必再回溯至r l 点，何不继续往下搜寻，如 果能够将r 1 下面的s o u r c et r i e 复制到r 4 下面，就可以解决回溯之问题。再 者，如以原演算方法作树追踪，因常需要作回溯动作之故，将耗费大量搜寻时间， 而违背了最佳匹配问题中，对于处理的时间要快的要求。基于这种想法：何不将 整个d e s t s o u r c e t i l e 中，凡d e s t a d d r e s s 具有p r e f i x 关系者，则将其s o u r c e - t d e 第1 2 页 北京邮电大学硕士学位论文 流分类技术的研究和硬件实现 全部往d e s t - t d e 更严谨之节点下方复制一份，如此可确保任何一个报文匹配， 一定由d e s t s o u r c e st i l e 之树根开始往下搜寻，而且保证如果匹配符合，一定是 一通到底，而绝对不会有回溯( b a c kt r a c k i n g ) 的情况发生。依这种方法，以图 2 3 所举实例而言，建置起来之树如下图所示，红色部份即为复制之项目。而因 其将减少搜寻状态之集合总数，因而命名为集合删减树( s e t p r u n i n g t r e e ) 。 辔o r 。 o r 7r 二r ： r j 为戛 00 3 3 固固 r 6 o r 7r ：r 1r 1r 7 露 图2 3s e t - p r t m m gt r e e 然而，集合删减树( s e t p r i m i n g t r e e ) 算法执行起来仍然有问题，其内存复杂 度为o ( n 2 ) ，而搜寻时间复杂度为o ( 2 w ) ，显然内存复杂度太大了，当比对条 件一增加，路由器内存将被耗尽，甚至不足。文献 6 】提出了改良的方案，即阶 层树( h i e r a r c h i c a lt r i e ) 算法。 其实阶层树( h i e r a r c h yt h e ) 就是指尚未进行s o u r c et d e 复制之 d e s t - s o u r c e t r i e ，其概念为：如需要回溯就回溯