（系统工程专业论文）基于网络处理器的报文分类算法研究.pdf

北京科技大学硕士学位论文 摘要 i n t e r n e t 网络应用的发展要求下一代路由器必须有能力支持q o s 、网络入侵检 测、传输测量与审计、负载平衡、拥塞控制等一系列功能，因此要求用不同的机制 来实现这些功能。虽然实现的技术可能不尽相同，但它们都有一个公共的要求，即 路由器应能够基于报文头部的某些字段对报文进行分类，因此报文分类是许多网络 关键技术的基础，它涉及到网络的控制、性能、安全、管理等多方面内容，报文分 类速度的快慢、功能的强弱都直接影响这些网络技术的性能。 已有的研究表明，实现高速多维报文分类算法是非常困难的，要么要求的内存 空间过大无法满足低成本的要求，要么分类的速度较低无法满足高速网络环境的应 用需求，它已成为路由器的新的瓶颈，随着网络的发展和i p v 6 的出现，这种情况会 更加突出。这种矛盾促使报文分类成为网络技术研究的一个重要热点，近年来吸引 了许多研究人员的注意。 本文第一部分系统地论述了报文分类的相关技术，包括分类的模型、可能分类 的字段，评价分类的基本标准等等，通过对现有报文分类算法的分析和性能比较， 并结合分类规则所具有的特性，提出了设计报文分类算法所应遵循的原则和思路。 论文的第二部分提出了一种报文分类的空间优化方法，该方法主要针对软件实 现方面，利用规则的互补表示，有效的节省了空间，对分类算法效率的提高有重要 意义。 论文的第三部分分析了网络处理器平台，它是介于通用处理器和专用处理器 ( a s i c ) 芯片之间的一种可编程处理架构，网络处理器采用了许多优化技术如：多 内核结构多线程技术，优化的内存管理和d m a 单元，优化的运算逻辑单元a l u ，集 成网络专用的协处理器( c o p r o c e s s o r s ) 等。 论文的最后部分主要讨论了算法的实现过程，首先提出了一种基于信息熵原理 的决策树算法，并在网络处理器上进行了测试，效果比较满意，但因为是一种启发 式方法，在实际应用中的效果还有待进一步分析和研究。 关键词：报文分类，网络处理器，信息熵，决策树 北京科技大学硕士学位论文 r e s e a r c ho na l g o r i t h mo fp a c k e tc l a s s i f i c a t i o nb a s e do n n e t w o r kp r o c e s s o r a b s t r a c t t h ed e v e l o p m e n to fi n t e m e ta p p l i c a t i o nn e c e s s i t a t e sn e x t - g e n e r a t i o nr o u t e r sa b i l i t yt o s u l y p o r tt h o s ef u n c t i o n ss u c ha sq o s ( q u a l i t yo fs e r v i c e ) ，n e t w o r ki n t r u s i o nd e t e c t i o ns y s t e m s ( n i d s ) ，m e a s u r e m e n to f 位d f f i c , a c c o u n t i n ga n db i l l i n g , l o a d i n gb a l a n c ea n dc o n t r o l c o n g e s t i o ne t c t h o u g hi m p l e m e n t a t i o n so ft h e s ef u n c t i o n sv a r yt r e m e n d o u s l y , t l l e ya l ln e e d p a c k e tc l a s s i f i c a t i o n s op a c k e tc l a s s i f i c a t i o nh a se x t e n s i v eb e e na p p l i e di nn e t w o r kt e c h n o l o g y f i e l d i tp r o v i d e st h ef o u n d a t i o nf o rm a n yi m p o r t a n tn e t w o r kt e c h n o l o g i e sa n di sc l o s e l y a s s o c i a t e dw i mm a n ya s l ：n x t k qo fn e t w o r kf i e l d , s u c ha sn e t w o r kc o n t r 0 1 n e t w o r ks e c u r i t y , n e t w o r km a n a g e m e n ta n dn e t w o r kp e r f o r m a n c e e s p e c i a l l y , i ti si n d i s p e n s a b l et on e x t - g e n e r a t i o nr o u t e r t o s u p p o r tm a n yn e wa p p l i c a t i o n s t h es p e e da n df u n c t i o no fp a c k e t c l a s s i f i c a t i o nd i r e c t l yi n f l u e n c et h ep e l f o l l t l a n o go f t h o s en e t w o r kt e c h n o l o g i e s b u ts t u d yh a ss h o w nt h a ti ti sd i m c u l tt od e v e l o paf a s ta n dm u l t i - d i m e n s i o n sp a c k e t c l a s s i f i c a t i o na l g o r i t h m ，p a c k e tc l a s s i f i c a t i o nh a sy e tb e e nan e wb o t t l e n e c ko f r o u t e r w i t ht h e d e v e l o p m e n to ft h en e t w o r ka n da p p e a r a n c eo fi p v 6 ，t h es i t u a t i o nw i l lb e c o m ew 0 1 ，3 e o nt h e o n eh a n d ，s 0 1 t i en e t w o r ka p p l i c a t i o n sr e q u i r ed e e pp a c k e ti n s p e c t i o n , w h i c hl e a d st om o r e c o m p l e xc l a s s i f i c a t i o nm e c h a n i s ma n ds l o w e rp a c k e tc l a s s i f i c a t i o ns p e e d o nt h eo t h e rh a n d , h i g h - s p o e dn e t w o r kr e q u i r e sah i g h e rp a c k e tc l a s s i f i c a t i o ns p e e di nt h ef u t u r e t h ed i l e m m a m a k e sp a c k e tc l a s s i f i c a t i o nb eo n eo fi m p o r t a n tr e s e a r c hi s s u e si nn e t w o r kf i e l d s oi ta t t r a c t s m a n yr e s e a r c h e r s a t t e n t i o ni nr e c e n ty e a t s t h ef i r s tp a r to ft h ed i s s e r t a t i o ns y s t e m a t i c a l l yi n t r o d u c e st h eb a c k g r o u n da n dc u r r e n t r e s e a r c ha d v a n c eo f p a c k e tc l a s s i f i c a t i o n , i n c l u d i n gt h em o d e lo f p a c k e tc l a s s i f i c a t i o n ，c r i t e r i at o e v a l u a t ec l a s s i f i c a t i o na l g o r i t h ma n ds oo n b ya n a l y z i n gt h ee x i s t i n ga l g o r i t h ma n d c h a r a c t e r i s t i co f c l a s s i f i e r , t h ea u t h o rd i s c u s s e st h ep r i n c i p l ea n da p p r o a c ha b o u th o wt od e s i g n p 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 t h es e c o n dp a r tg i v e san e wm e t h o dt or e d u c et h er u l es p a c ew i t h o u tc h a n g i n gt h er u l e m e a n i n g ，w h i c h h a st h ei m p o r t a n ts i g n i f i c a n c ei ns o f t w a r ei m p l e m e n t a t i o n t h et h i r dp a r ti n t r o d u c e st h en e t w o r kp r o c e s s o r , w h i c hi sap r o c e s s o ra r c h i t e c t u r eb e f w e a l t h eg e n e r a lc o m p u t e r sa n dt h ea s i c ( a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t ) a n dt a k e sm a n y o p t i m i z e dt e c h n o l o g i e sf o rt h eh i g h 哪旧e dr e q u i r e m e n to ft h en e t w o r ka p p l i c a t i o n s ，t h e s e - 北京科技大学硕士学位论文 t e c h n o l o g i e si n c l u d em u l t i c o r ea n dm u l t i t h r e a d , o p t i m i z e dm e m o r ym a n a g e m e n ta n dd m a u n i t , o p t i m i z e da l uu n i t , i n t e g r a t i n gw i t ht h es p e c i f i cc o - p r o c e s s o r s t h el a s tp a r to f t h ed i s s e r t a t i o np r e s e n t st h ei m p l e m e n t a t i o n , c o n c l u d i n ga l lt h eo t h e r p a r t s o ft h ed i s s e r t a t i o r lw ep r o p o s ean e n va l g o r i t h mc a l l e dt h ee n t r o - t r i ea l g o r i t h mb a s e do nt h e i n f o r m a t i o ne n t r o p ya n di m p l e m e n ti to nt h en e t w o r kp l d c 沱s s o l , o b t a i n i n ga s a t i s f a c t o r yr e s u l t h o w e v e rt h i si sah e u r i s t i ca l g o r i t h m , i tn e e d st h ef u r t h e rr e s e a r c ha n dt h e o r e t i c a la n a l y s i st o f u l f i l lt h ec o m m e r c i a la p p l i c a t i o n k e yw o r d s ：p a c k e tc l a s s i f i c a t i o n ，n e t w o r kp r o c e s s o r ，i n f o r m a t i o ne n t r o p y ，d e c i s i o n t r e e i 北京科技大学硕士学位论文 图清单 图2 1 规则的几何解释一8 图2 2t c a m 中规则匹配过程1 0 图2 32 4 1 阶层树一1 2 图2 4 集合删减树1 3 图2 5 网格树一1 3 图2 6 a ) b i n a r y t r i o , b ) p a t h - c o m p r e s s e d t r i e , 曲l c - t r i e 一1 5 一 图2 7b v 与a b v 分类实例2 0 图2 8b l o o mf i l t e r s 分类算法结构一2 2 图2 9 单步分类与递归式分类的比较2 4 图2 1 0r f c 算法结构图2 5 图2 1 1 对表2 3 几何图的切割2 6 图2 1 2h i c u t 决策树的构造过程2 7 图2 1 3h i c u t 与h y p e r c u t 的比较2 8 图3 1 曲规则互补表示3 2 图4 1 i x p 2 4 0 0 硬件结构图一3 7 图4 2 邻接寄存器操作示意图4 1 图4 3s r a m 中的队列操作4 1 图4 4s c ra t c m ，a d 中的队列操作4 1 图4 5i x a 编程的一般结构 图4 6i x a 应用的逻辑构成4 6 图4 7 线程保序模型一4 7 图5 1 某b g p 表中的前缀分布情况一5 2 一 图5 1 递归分析示意图5 3 一 图5 2 可变长t r i e 递归关系图5 4 图5 4 平均访存次数与规则数目的关系( 时间衡量) 一6 2 图5 5 最大访层次数与规则数目的关系一6 3 一 图5 6 规则数目与树结点数目( 空间衡量) 的关系( 位长= 5 阀值= 1 0 ) 6 3 图5 7 给定规则数2 0 4 8 ，决策位长度对树结点数的影响( 阀值- 2 0 ) 一6 4 图5 8 给定规则数2 0 4 8 ，叶结点阀值对树结点数的影响( 位长= 5 ) 一6 4 一 i v 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 北京科技大学或其他教育机构的学位或证书所使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表 示了谢意。 签名臣止日期：j 竺p 关于论文使用授权的说明 本人完全了解北京科技大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。 ( 保密的论文在解密后应遵循此规定) 签名：童三一吐导师签名：聋幸扯日期：竺孚l 兰 北京科技大学硕士学位论文 引言 计算机网络正处于蓬勃发展的时期，网络速度不断提高，用户数量急剧增长同 时，i n t e r n e t 服务也开始由原先的尽力服务( b e s t e f f o r ts e r v i c e ) 向q o s ( q u a l i t y o fs e r v i c e ) 发展，网络设备( 路由器、交换机等) 的功能必须由原先单纯的转发分组 提升到具有内容知晓( c o n t e n t a w a r e n e s s ) 的能力，而分组分类则是其中重要的一环 许多网络关键技术，如虚拟专用网( v p n s ) 、网络地址转换( n a t ) 、防火墙、网络入侵 检测( i d s ) 、q o s 、拥塞控制、组播以及未来的i p v 6 流标识等都涉及到分组分类因 此，分组分类速度的快慢、功能的强弱将直接影响到许多网络技术的性能，并且对下 一代网络及其服务质量有关键性的影响因此，分组分类是现今网络研究的重要议题 之一。 报文分类的本质是快速查找，它的困难在于分类的多维性( 报文分类的字 段) ，匹配形式的多样性，( 例如精确匹配，前缀匹配，范围匹配) ，所以直接套用 快速查找的算法是行不通的，必须研究分类规则的特性及其相互之间的关系等诸多 因素才有可能找到有效的解决方案，从而为各种网络技术的发展奠定坚实的基础。 网络处理器是在网络速度继续提高、网络应用和服务同益多样化的情况下，为同 时满足高速处理、高灵活性和短研制周期而出现的一种新兴技术它被认为是推动下 一代网络发展的核心技术基于网络处理器平台的算法实现可以轻松地扩展服务类型 或移植到其他系统上，这对于开发商和用户而言，无疑都是一个很好的选择网络处理 器具有很好的发展前景，其相关技术的研究同益成为一个热门课题。 当前的高速分组分类通常用硬件( 例如t c a m 和f p g a ) 来实现，但是，这类的硬件 成本非常高( 特别是在比特长度和容量都很大的情况下) 、功耗大，因此，业界都希望 能用软件的方法达到高速分组分类的效果因此，在网络处理器这种新技术平台上设 计和实现高速分组分类算法，无论是从技术角度还是从市场角度都具有十分重要的意 义。 北京科技大学硕士学位论文 1 绪论 1 1 报文分类背景及意义 计算机网络正处在蓬勃发展的时期，网络速度不断提高，用户数量急剧增长， 各种网络应用不断涌现，计算机网络需要支持包括w e b 服务、多媒体服务等在内 的多种服务。i n t e r n c t 的高速发展要求底层能够提供足够的带宽，这不但需要高速的 通讯链路，还需要高速的网络路由设备即路由器。随着光纤通讯技术的发展，通讯 链路以g 比特乃至更高的速度进行数据传输已可以实现。相比较而言，路由器正在 成为网络数据传输的瓶颈。在路由器的转发过程中，主要有三个瓶颈：查找、交换和 输出调度。近年来，在解决路由器瓶颈方面取得了一些进展【1 脚3 】：首先是体系结构 的突破，交换系统方面出现了快速总线和交换点阵列( c r o s s b a o 等交换设备。多数路 由器的生产厂商认为，在网络视频得到广泛应用之前，对输出队列调度的要求还不 是很高。在过渡阶段，一些较简单的方案，如改进的轮询策略( r o u n dr o b i n ) 就能够 有效地满足输出调度的要求。因此，当前路由器的瓶颈主要表现在路由器的查找效 率上。 当前的i n t o - n e t 只提供先到先服务的( b e s t - e f f o r t ) 转发机制。无法为用户提供高质 量的声音、图像等多媒体传输服务。将来的i p 网络服务要求与商业挂钩，要考虑用 户的不同要求及其付费行为，对用户提供因人而异的全方位i p 网服务，支持全方位 i p 网服务是通过采用报文头综合处理方式进行的，其中报文分类、流标识是其设计 中关注的重点之一。 近年来兴起的一些网络应用希望路由器能够提供相应的功能支持【4 】【5 】f 6 】，这些功 能包括防火墙、基于策略的路由( p o l i c y - b a s e dr o u t i n g ) 、区分服( d i f f e r e n t i a t e d s e r v i c e s ) q o s 、流量计费等。在上述各种情况下，都需要将到达的数据包归类为不 同的数据流，根据不同的数据流来决定诸如是否转发该数据包、向哪星转发数据 包、数据包应该得到什么样的服务或者相应流量数据包该收取多少费用等一系列问 题。这些功能都是以报文分类技术为基础。分类速度的快慢、功能的强弱都直接影 响到这些网络技术的性能，关系到网络的控制、性能、安全、管理等诸多内容，特 别是在未来的网络中要满足不同网络应用的要求，报文分类更是必不可少。 1 2 报文分类背景及意义 本文余下部分安排如下： 第二章讨论了报文分类的相关技术及当前进展，首先介绍了报文分类的基本概 北京科技大学硕士学位论文 念、几何解释、可用作分类的字段等，之后对目前几个重要的报文分类算法进行较 为详细的讨论，主要包括线性查找算法( l i n e a r ) ，h i e r a r c h i c a lt i l e 算法，c r o s s p r o d u c t i n g 算法，h a s h 算法，t u p l es p a c es e a r c h 算法，和r f c 算法，为设计新算 法提供一定的思路。同时将这些报文分类算法的性能进行了比较，便于了解各种算 法的优缺点。 第三章分析了一种规则空间优化的方法，在范围匹配转化成前缀匹配时，采用 了规则互补的方法，有效的节省了空间。 第四章结合i n t e l 公司的i x p 2 4 0 0 网络处理器，主要讨论了网络处理器技术的 软硬件环境以及在算法实现中如何利用i x p 2 4 0 0 网络处理器的微引擎并行性和线程 并行性来提高性能。 第五章主要设计了一种新的基于i x p 2 4 0 0 网络处理器的报文分类算法，并在网 络处理器平台上作了实现。 本文的主要贡献如下： 对现有的几个重要的报文分类算法的机制进行较为详细的分析，并对这些 算法的性能进行了比较和总结，同时详细讨论了i x p 2 4 0 0 网络处理器的软 硬件体系结构。 给出一种规则库优化的方法，从而提高了报文分类的速度，因为报文分类 算法的性能都与规则规模有关，分类问题本身就集中在如何于时空复杂度 之间灵活平衡并且整体性能有所优化。 设计了一种新的基于i x p 2 4 0 0 网络处理器的快速报文分类算法，该算法具 有直观灵活，易于实现的特点，并且对中小规模的规则库有很高的分类速 度。若与a b v 算法进一步结合，能解决可扩展性问题，适用于大规模的规 则库。 北京科技大学硕士学位论文 2 报文分类算法综述 目前报文分类算法从实现的角度可分为两种一种是硬件算法( h a r d w a r e - b a s e da l g o r i t h m s ) ，一种是软件算法( s o f t w a r e b a s e da l g o r i t h m s ) 。硬件算法。如 t e r n a r y - c a m s ( c o n t e n t - a d d r e s s a b l em e m o r y ) 算法 4 】【5 】【6 1 ，此算法将所有规则用t c a m 硬件实现，利用硬件并行对报文进行分类，并报告最高优先级匹配规则。这种方法 分类速度较快，但它要求大量的逻辑元素，它受到功率消耗的限制，不能扩展到大 规模的分类器上，因此这种方法有维数少，扩展性差，价格比较昂贵等缺点。同时 不能直接支持一些运算符，内存数组的利用率也不是很有效，对基于p c 机的路由 器来说不实用。 现有的软件算法一般只具备特定维数的分类能力，特别是单维分类和二维分类 的算法较多( 例如b i n a r yr a n gs e a r c h 7 1 算法、g r i d o f - t r e e 算法【s 】、a q t 算法【9 1 等) 。 能够提供对高维分类支持的算法但在空间复杂度和时间复杂度上都不能很好满足应 用要求，例如r f c 算法【l o l 、h i e r a r c h i c a lc u t t i n g 算法( 1 l 】等在最坏情况下空间复杂度 很大，另一些算法，如基于位向量的算法、回溯算法时间复杂度较大。而基于 c a c h e 的报文分类方法【1 2 】因命中率较低、流持续时间较小等原因在实际使用中也不 能很好满足要求。一些相关问题仍未解决，例如分类如何在i p v 6 中实现，如何设 计通用的具有可扩展性的分类算法，如何解决分类与网络安全问题等等。以下部分 具体分析了各种算法原理及优缺点。 2 1 术语表 为了便于后面的论述，我们先定义一些将要用到的符号术语。 分类器：是规则的集合，也称策略数据库、流分类器等。规则的个数记为 这些 规则的排列具有一定的顺序关系，当一个报文同时匹配多个规则时，许多算法默认 排在前面的规则具有较高的优先权，即，报文优先匹配在所有匹配的规则中排在前 面的规则。 字段：字段域r 是一个连续的位的集合，它可以是报文的一部分也可以是与报 文相关的信息，例如，时白j 戳或者进入报文的端口号。 报文头：报文头日是k 个字段的集合，这些头字段分别表示为- 1 1 。 研2 】 研团，这里每个字段都是一个位串。 精确匹配：精确匹配是对规则字段i 的值的说明，一个报文头字段h i 0 与一个 规则字段r o 是一个精确匹配是指，任给一个i ，当且仅当n q = r o 。 北京科技大学硕士学位论文 前缀匹配：前缀匹配是对规则字段i 的前缀说明，一个报文头字段研f 】与一个 规则字段r 明是一个前缀匹配是指，任给一个i ，当且仅当埘司是研f 】的一个匹配前 缀。 范围匹配：范围匹配是对规则字段i 的范围的说明，是指一个报文头字段h o 落在规则字段r i o 的范围之内。 优先级函数：每一个规则联系一个优先级函数，记为p r i o r i t y ( r ) ，以便当一个 报文同时匹配多个规则时，通过寻找最高优先级的规则作为最终匹配规则来解决规 则的冲突问题。 动作：每一个规则联系一个动作，记为彳门对，当一个报文匹配一个规则时，就 按照彳俾) 对报文进行处理。 一维分类：假定一个有个规则的分类器，每一个规则只有一个在 1 “】范围 内的字段，且每个规则联系一个代价函数，一维分类是指在分类器c 中查找一个包 含点q 1 “】且具有最小代价函数的规则的过程。 多维分类：多维分类的含义与一维分类的含义相似，只不过每个规则中可以包 含两个或多个字段。 2 2 报文分类背景及意义 分类器包含n 条规则，每条规则有3 个部分：j 下则表达式r j i 】，规则的优先 级砸( r j ) ，以及规则对应的动作a c t i o n ( r j ) 。这表示每个规则可以有自己的分类字 段、分类方法，以及对应的执行动作。每个规则有不同的优先权，当到达分组同时 满足多个规则的正则表达式时，选出优先权最高的规则为分类的结果，并进而执行 该规则的动作。分类字段可以是报文头( p a c k e th e a d e r ) 字段，也可以是负载 ( p a y l o a d ) 的部分f ”】。 过去路由器的i p 地址查找其实就是一种报文分类分类字段是目的地址( 一 维分类) ，规则是口前缀集，优先级是最长前缀匹配最高，而动作是报文转发。当 分类字段变多( 一维分类专多维分类，如：源地址，源端口，目的端口，负载) 、分 类的运算符( o p e r a t o r ) 变多( 见表2 1 ) 、动作的选择变多( 如：d e n y - o f s e r v i c e ，l o a d b a l a n c i n g ) ，报文分类的能力就大大地增强，应用范围也更广泛，从第二层交 换，第三层报文转发，第四层的i n t s e r v 、d i f f s e r v 甚至第七层的负载平衡、入侵检 测都属于报文分类的应用( 见表2 2 ) 。 表2 1 分类规则的运算符 北京科技大学硕士学位论文 运算符例子 算术运算 m a s k 逻辑运算a n d ，o r , n o t 大小关系 ，一 通配符 表2 2 报文分类在网络各层中的应用 o s i 层应用速率分类字段数目分类类型 规则举例 2 s w i t c h i n g , m p l s o c 4 8 c s i n g l e精确匹配 s e n d p a c k e t s w i t l l d m a c = ：= 6 a 1 0 0 i a b l 2 7 a d i r e c t l y t o e n d h o s t s 3 f o r w a r d i n g 0 c 4 8 c s i n g l e 最长前缀匹 s e n da l lp a c k e t s 、析t l ld i p 1 9 2 1 6 8 t ot h ei s p s 配 r o u t e r 4i n t s e r v , f i o wo c 4 8 c m u l t i p l e精确匹配 g i v ep a c k e t s 、“ms i p i d e n t i f i c a t i o n 叫p s p ，d p 一( 1 9 i ， 2 0 0 1 8 ，2 3 ，1 0 3 0 ) h i g h e s t p d o d t y 5f i l t e r i n g ，d i f f s e r v o c 4 8 c m u l t i p l e前缀或范隔 d r o pa l lp a c k e t s 、纠ls i p 一1 9 2 1 a n ds p 1 0 2 3 匹配 a n dd p 3 的多维空间点定位问题( 就像报文分类问题) ，可接 受的算法的时间和空间复杂度介于，时间最优( 空白j 可接受情况下) 为：时间复杂 度o ( i o g n ) ，空间复杂度o ( n 4 ) ；空间最优( 时间可接受情况下) 为：时间复杂度 o ( 1 0 9 “1n ) ，空i 日j 复杂度d ( ，z ) 。 对于其它的几项性能指标，更多的是根据实际应用的需求来进行取舍。例如规 则的更新速度，在较大的边缘路由器中同时可能存在1 2 8 k l m 个流( f l o w ) ，而且这 些流变化极快，因此这些路由器中的微流( m i c r o f l o w ) 标的更新速度也要极快；与之 相反在防火墙的应用中，通常每个端口只有不到2 k 条规则，而且这些规则很少更 新，通常只在系统启动重启时进行配置，这时候我们就可以应用那些查找速度快更 新速度较慢的分类算法了。又如，路由器中的i p 地址查找可以不考虑分类算法是否 可以扩展到多维分类的情况，也不必考虑算法的灵活性，完全可以用硬件来高速完 成这种简单的分类操作；而在内容路由器中，即便是应用层的复杂数据也需要分类 模块进行处理，算法的灵活性就显得尤为重要了。 2 2 2 报文分类的几何解释 报文分类可以用几何的方式进行解释【1 4 】f 阍，我们知道前缀可以用来表示线段上 连续的间隔，那么两维的规则在二维欧几里得空间上就表示为2 一x 2 w 2 的矩形，其 北京科技大学硕士学位论文 中尻。熙分别表示每个维的宽度。类似的，三维的规则在欧几里得空间上表示一个立 方体，一般地，一个d 维规则在d 维空间上表示为一个d 维超立方形。一个分类器 就是一个具有优先级的超立方形集合。报文头表示d 维空间中的一个点，这个点的 值就是对应的报文头d 个字段的值。 对一个报文的分类相当于寻找一个包含报文点，且具有最高优先级的长方形， 图2 1 是表2 3 分类器的几何解释，点p ( 0 1 1 ，1 l o ) 由规则5 来分类。 注意：高优先级的规则可以覆盖低优先级的规则，例如，在图2 1 中，规则4 被 规则1 和规则2 所覆盖。 表2 3 一个二维分类器的例子 规则字段1字段2 r 10 0 0 0 r 20 术0 1 r 3l 术 o 爿c r 40 0 o 术 r 5o 爿c1 乖 图2 1 规则的几何解释 北京科技大学硕士学位论文 2 3 报文分类的硬件解决方案：基于c a m 、t c 舢订的解决方案 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 ) 【4 】【1 6 1 是一种可以进行精确匹配的硬件。 c o n t e n ta d d r e s s a b l e 指的是这种存储器的运作特性，它可以根据内容进行寻址，输入 内容之后可以在一个时钟周期之后就得到包含该内容的存储单元地址。它是如何做 到的呢? c a m 技术使得定位一个规则条目的内存访问时间得以最小化，在输入一个 查找值之后，c a m 设备并行的将其和所有的存储器之进行比较，因此，c a m 的一 次有效查找只需要1 个时钟周期。 虽然c a m 技术在精确匹配操作上效果很好，并且在某些严格划分层次的路由 查找方案中有所应用，但是，由于地址聚合技术( 例如：无类域间路由c i d r ) 的 广泛应用，使得任意长度的前缀都有可能出现，精确匹配技术就显得不够用了，需 要一种能够对任意长度前缀进行匹配的硬件技术来满足这样的应用需求。于是， t c a m 技术应运而生。 t e r n a r yc o n t e n ta d d r e s s a b l em e m o r y ( t c a m ) 【4 】【1 6 1 在基于内容的寻址上与c a m 完全一致，亦是并行比较，并在下一个周期给出结果。而 t e r n a r y 是指不同于一般 二进制( b i n a r y ) 的存储器，t c a m 能纪录三种状态，分别是0 ，1 ，( 无关位，也 就是任意值，不论是0 ，l 都可以) ，因此t c a m 可以完成精确匹配和前缀匹配两 种模式。 t c a m 时如何应用在解决报文分类问题上呢? t c a m 将规则依照优先级顺序 关系存储起来，并以输入的关键词( 例如i p 地址) 跟所有条目的内容比较。因为同 时可能有多条符合结果的规则，所以输出一组记录着与各条目比较结果的位向量， 交给紧接其后的优先级编码器来进行选择优先级最高者，并依此结果到内存里找到 对应的处理动作。因为这三个硬件处理模块式彼此独立的，所以可以用流水线的方 式来运作，带来性能上的不少提高( 见图2 2 ) 。 北京科技大学硕士学位论文 图2 2t c a m 中规则匹配过程 t c a m 的最大而且最卓越的优点是它的简易性与运算速度快，目前t c a m 的时 钟周期约为1 0 1 6 n s ，也就是说每秒钟能执行6 6 m 1 0 0 m 次分类查询。对于目前核心 4 0 g b p s 的高速网络，即便是每一帧都是最短的以太帧6 4 字节，每秒钟到达的分组 也不过是0 7 8 1 0 8 个，t c a m 每秒钟1 1 0 8 的报文分类处理能力对这样的高速网来况 也是有过之而无不及了。而且主频为2 5 0 m h z 的t c a m 也在研发中，不久将会投放市 场。 但相对优点来说t c a m 的缺点也不少。因为是硬件设备，所以制作成本高，价 格昂贵。据调查，主频为1 0 0 m h z 的2 m b 大小的t c a m 市价在2 0 0 2 5 0 美元之 间。此外，由于t c a m 的并行计算的能力，相应的电路也复杂，因此它花费的电力 也相当惊人，如果每秒钟执行1 0 0 m 次查询的话，消耗的电能大约在1 5 - - - 2 0 瓦之 间。同时，t c a m 的电路密度也不能做得很大，目i j i 可用到的t c a m 最大也只有 2 m b ( 例如：1 2 8 kx1 2 8 ，可层叠) 。最后，t c a m 只支持l j 缀匹配不支持范围匹 配，这也是它的一个小缺点。 最后值得一提的是t c a m 的内容更新( 如新增删除修改规则等操作) 速度也 较差。主要原因有下面两点： 第一：为了使后端的优先级编码器( p r i o r i t ye n c o d v r ) 容易制作，通常t c a m 里存 放的规则是按照其优先级顺序从高到低排列的，也就是说，t c a m 里存放的是一组 北京科技人学硕士学位论文 “已排序”的规则。在已排序的数据中加入或删除任何一项数据，同时还要保证数据 仍然是有序，这样的操作复杂度不低。如只有相同前缀的规则才需要维持顺序，可 以提高增量更新( i n c r e m e n t a lu p d a t e s ) 的速度。 第二：为了使规则占用存储器空间减小，通常逻辑上极小化的规则合并动作。例 如：原来的t c a m 中有这条规则“0 0 * - ) r u l e l ”，如果之后接到更新请求要求增加 “0 1 专r u l e l ”，此时t c a m 可以用2 个存储空间来存储，分别记录“0 0 - - r u l e l ”与 “0 1 * - - ) r u l e l ”，可是如此规则所占空间会较大，所以可以做逻辑化简，合并规则为 “0 * - - ) r u l e l ”。当然，这个额外的化简动作要花费不少时间开销的 2 4 报文分类的软件解决方案 2 4 1t i l e 树 t i l e 树切是一种通用的用于存储和查找字符串的数据结构。它的思想非常简单：每 一个字符串都可以用一棵树的某个叶结点来表示，而且这个串的值可由根到叶结点的路 径来确定。这种串的存储和查找方式被广泛的应用在各个领域，其中也包括了报文分 类。 2 4 1 1 阶层树 基于后面的分析需要，我们先建立一张规则表，并以此表作为各算法的规则集示 侈 i 。 表2 42 小l 前缀表 规则 目的地址原地址 r 1o 宰1 0 幸 r 2o 0 l r 3o 奉 l r 40 0 l 奉 r 50 0 1 l + r 61 0 事1 r 7 0 0 北京科技大学硕士学位论文 图2 32 小l 阶层树 根据规则表2 4 中目的地址前缀建立d e s t t r i e 树，构造的方法与普通二叉t r i e 树相同。对于每一个在d e s t - t r i e 树中的前缀p ，递归构造s o u r c e - t r i e ，前缀p 通过 n e x t t r i e 指针链接到s o u r c e - t r i e 上。整个过程完成之后，我们就得到了d e s t - s o u r c e - t r i e 这棵阶层树【l 刀，如图2 3 所示，其中黑色部分为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 e - t r i e 阶层树在查找的时候却出现了问题。例如：某一 到达分组的( d s t , s r c ) 为( 0 0 1 ，0 1 1 ) ，首先针对d e s t t i l e 进行搜索，将追踪到 d e s t t i l e 的最左端，但是该节点下的s o u r c e - t r i e 却无一符合，所以算法就必须回 溯，这导致阶层树的时间复杂度较高。 阶层树的存储器复杂度为o ( n w ) 其中为规则数目，矽为每一条规则字串的宽 度；由于回溯的存在，阶层树的搜索时间复杂度为d ( 胪) 。 2 4 1 2 集合删减树 为了解决阶层树的回溯问题，vs r i n i v a s a n 等人又提出了集合删减树【1 8 1 ( s e t p r u n i n gt r i e ) 。在前面的例子中我们可以看到r