（通信与信息系统专业论文）基于ixp2400的改进rfc算法的研究与设计.pdf

中文摘要中文摘要摘要：计算机网络应用的多样化和宽带化已经成为当今网络的发展趋势。在应用多样化的趋势下网络设备不再仅是简单地对数据包进行转发，还需要为不同用户提供有差别的服务，而流分类技术是差别类服务的技术基础。多维流分类问题在实现上是比较困难的，在网络宽带化的趋势下，网络设备渐渐成为网络的瓶颈，因此需要有高速的流分类方案，才能实现对数据包的线速分类转发。本文通过对常用算法的性能分析，选取了流分类算法中可以软件实现的最快算法之一r f c ( r e e u r s i v ef l o wc l a s s i f i c a t i o n ，递归流分类) 算法。r f c 流分类算法的优点是查询速度快，而且算法在实现过程中存在分布式思想，各个表项可以独立并行地进行查询，为此，本文采用了多核多硬件线程的网络处理器i x p 2 4 0 0来实现算法。r f c 算法的缺点是随着规则库规模增加，算法的占用空间会骤增。因此，本文采取压缩规则库和压缩交叉乘积表两项措施对算法进行改进。规则库压缩算法是将原来以每条规则为划分单位的规则库重新组合为以处理结果为划分单位，在有相同的处理结果的规则组内查找邻接规则并将其进行合并，r f c 算法在每个阶段都要合并一些域，所以规则库压缩在r f c 算法预处理的每个阶段开始之前都会产生压缩效果。交叉乘积表压缩主要采用比特向量压缩算法，将原表中连续重复出现元素占用的空间压缩掉。本文针对以上两种措施对r f c 算法的综合改进方案作了数据结构设计、流程设计、代码实现。硬件资源的分配方案是改进算法能否在多核多硬件线程的网络处理器上充分利用多核多线程硬件资源，实现数据包线速转发的关键。本文对微引擎、硬件线程和存储器的分配做了详细设计。本文在网络处理器的软件开发平台上对改进算法进行了仿真试验和分析。仿真结果显示：r f c 算法占用空间会随着规则库规模的增大急剧增加，改进算法相对于原r f c 算法空间的压缩率会随着规则库规模的增加而提高，对算法的空间占用情况有极大改善，最多能够实现5 4 的空间压缩。关键词：流分类，网络处理器，r f c ，i x p 2 4 0 0分类号：t n 9 1 9 2 1t p 3 9 3 0 5a bs t r a c ta b s t r a c t ：i nm o d e mc o m p u t e r sn e t w o r k ，t h e r ew i l lb em o r ek i n d so fa p p l i c a t i o ns e r v i c e sa n dm o r eb r o a d b a n da c c e s s t h en e t w o r k se q u i p m e n ts h o u l dn o to n l yf o r w a r dt h ep a c k e t su n d i s t i n g u i s h e d ，b u ta l s op r o v i d e dd i f f e r e n t i a t e ds e r v i c e sf o rv a r i o u su s e r si nt h et r e n do fm u l t i p l es e r v i c e s p a c k e tc l a s s i f i c a t i o ni st h eb a s et e c h n o l o g yf o rt h ed i f f e r e n t i a t e ds e r v i c e s c l a s s i f y i n gp a c k e t so nm u l t i p l ed i m e n s i o n si sad i f f i c u l tp r o b l e m ，t h en e t w o r ke q u i p m e n tb e c o m et h eb o t t l e n e c ki nt h et r e n do ft h eb r o a d b a n d s ow es h o u l dl o o kf o rab e t t e rm e t h o dw i t l ll l i g hs p e e d t h er f c ( r e c u r s i v ef l o wc l a s s i f i c a t i o n ) c h o s e nb yt h ep a p e rh a sh i g h e s ts p e e di nt h es o f t w a r em e t h o d sa f t e rt h ea n a l y s i so ft h ep a c k e t sc l a s s i f i c a t i o nm e t h o d s t h el l i g hq u e r ys p e e di st h ea d v a n t a g eo ft h er f c ，a n dt h e r ea r em a n yd i s t r i b u t i o n si nt h em e t h o d ，s op a r a l l e lq u e r y i n gc a ni m p l e m e n ti nr f c t h eh i g h s p e e dm e t h o di si m p l e m e n t e do nt h em u l t i - c o r em u l t i t h r e a dn e t w o r kp r o c e s s o ru n i t ( n p u ) i x p 2 4 0 0 t h ed i s a d v a n t a g eo fr f ci se x c e s s i v es t o r a g ew i t hi n c r e a s i n go ft h en u m b e ro fr u l e s s o ，t h er u l es e tc o m p r e s s i o na n dt h ec r o s s p r o d u c t i n gt a b l ec o m p r e s s i o ni su s e di nt h i sp a p e r i nt h er u l es e tc o m p r e s s i o n ，t h er u l es e t ，i nw h i c ht h er u l ei st h eb a s ee l e m e n t ，i sr e a r r a n g et oas e tb a s e do nt h ea c t i o n s 硼1 ea d j a c e n c yr u l e sc a nb em e r g e di nt h es a m e - a c t i o n - g r o u p i ne a c hp h a s eo ft h ep r e p r o c e s s i n go fr f c ，t h e r ea l es o m ef i e l d sc o m b i n e d ，s or u l e sc o m p r e s s i o nc a l lb ea c h i e v e di ne a c hp h a s e t h eb i t - v i c t o rc o m p r e s s i o ni su s e di nt h ec r o s s p r o d u c t i n gt a b l ec o m p r e s s i o nt od e c r e a s et h em e m o r ys p a c eb e l o n g i n gt ot h ec o n t i g u o u ss a m ee l e m e n t s 们1 cd a t as t r u c t u r ed e s i g n i n g , f l o wc h a r td e s i g n i n g , a n dt h ec o d i n gf o rt h et w oc o m p r e s s i o ns c h e m e sa r ea c h i e v e db yt h i sp 印e r o nt h en p u ，t h ea s s i g n m e n to ft h ep r o c e s s o r sa n dt h et h r e a di st h ek e yf o rt h es u f f i c i e n tu s et h eh a r d w a r er e s o u r c ea n dt h el i n es p e e df o r w a r d i n g t h ea s s i g n m e n tf o rm e ，t h r e a d s ，m e m o r yi si l l u s t r a t e di nd e t a i li nt h ep a p e r 1 1 1 es i m u l a t i o ni si m p l e m e n t e do nt h en p ud e v e l o p m e n tp l a t f o r m a c c o r d i n gt ot h es i m u l a t i o nr e s u l t s ，t h es t o r a g es p a c ew i l li n c r e a s ee x c e s s i v e l yw i t ht h er u l es e ti n c r e a s e a l s o ，t h es t o r a g es p a c eh a sb e t t e ri m p r o v e m e n tw i t hi n c r e a s eo ft h er u l es e t i nt h eb e s tc o n d i t i o n5 4 c o m p r e s s i o nr a t ec a nb ea c h i e v e d k e y w o r d s ：p a c k e tc l a s s i f i c a t i o n , n p u ，r f c ，i x p 2 4 0 0c i 。a s s n o ：t n 9 1 9 2 1t p 3 9 3 0 5学位论文版权使用授权书本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。( 保密的学位论文在解密后适用本授权说明)学位论文作者签名：景匿导师， i o z 签字日期：p o 暑年彳月眩日签字日期：p o 急年占月独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名：景医签字日期：加i ) 了年乡月je l7 4致谢本论文的工作是在我的导师张宏科教授的悉心指导下完成的，张宏科教授严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢两年来张宏科老师对我的关心和指导。张宏科教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都给予了我很大的关心和帮助，在此向张宏科老师表示衷心的谢意。苏伟老师对于我的平时的科研工作和毕业论文都提出了许多的宝贵意见，在此表示衷心的感谢。感谢研究生期间给过我帮助和支持的秦雅娟老师、周华春老师等实验室的各各位老师，感谢武勇、郭华明、李昀晖等各位同学和朋友。感谢和我一起工作和学习过的所有同学，没有他们的帮助和鼓励，也就没有我的进步。另外，也感谢我的父母，他们的理解和支持使我能够在学校专心完成我的学k 。绪论1 绪论1 1 选题背景近年来，随着因特网的快速发展和网络用户数骤增，网络应用的多样化成为了网络发展的一种趋势，尤其是随着宽带多媒体业务日益普及，用户对因特网的要求也不再仅仅满足于简单的文件传输，而是要求网络提供更加安全、快速和多样化的服务。在网络应用多样化的趋势下，计算机网络必须要为用户提供更多的服务类型和更好的服务质量，而其中的许多关键服务，如防火墙包过滤( f i r e w a l lp a c k e tf i l t e r i n g ) 、网络入侵检测( 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 ，m s ) 、虚拟专用网( v i r t u a lp r i v a t en e t w o r k , v p n ) 、策略路i 扫( p o l i c y - b a s e dr o u t i n g ) 、服务质量( q u a l i t yo fs e r v i c e ，q o s ) 、区分服务( d i f f e r e n t i a t e ds e r v i c e s ，d i f f s e r v ) 、网络地址转换( 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 ) 、拥塞控制、传输测量与记账、资源预留( r e s o u r c er e s e r v a t i o np r o t o c o l ，r s v p ) 、负载平衡、收集统计数据、交换机的设计、m p l s ( m u l t i p r o t o c o ll a b e ls w i t c h i n g ) 通道的流合并、传输整形以及p v 6 流标识、异步传输模式( a s y n c h r o n o u st r a n s f e rm o d e ，a t m ) 信元交换等，都需要对到达的或者转发的数据包进行分类，归类为不同数据流，以采取相应的操作，从而提供以上对应的服务。这些服务都是以流分类( p a c k e tc l a s s i f i c a t i o n ) 技术为基础的，需要根据预设的规则库对数据包做不同的分类处理。所以，流分类技术是现代网络种多样化服务的基础。而多于两维空间的流分类问题是比较困难的，流分类处理部分一般都会成为网络设备的瓶颈【1 1 。所以流分类已成为路由器、防火墙等网路关键设备中最为关键的技术，会直接影响到网络的控制、性能、安全和管理。在网络宽带化的趋势下，网络带宽的增长速度逐渐超过了网络设备处理能力的增长速度，而且这种差距有加大的趋势，这使得网络系统的瓶颈由传输设备的带宽转化为网络设备的处理能力；在网络应用的多样化的趋势下，新的网络应用不断出现，网络设备需要支持的协议数目越来越多、协议内容也越发复杂，网络设备需要具有高度的灵活性来满足新协议和新业务的升级，并为不同用户和业务提供不同的q o s 性能保障。所有这一切都要求网络设备能够高速、灵活地完成各种协议上的包处理任务。针对网络的宽带化和应用的多样化人们设计出了专门用于处理网络数据处理的网络处理器( n e t w o r kp r o c e s s o ru n i t ，n p t o 。在网络处理器中，专门为网络处理而进行优化设计的硬件结构提供了高速强大的网络处理平台，以适应网络处理宽带化的趋势，完全可编程的网络处理模式提供了灵活多样的网络处理功能，以满足网络业务综合化的要求。网络处理器弥补了通用处理器( g e n e r a lp r o p o s ep r o c e s s o r ，g p p ) 和专用集成电路( 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 s i c ) 在传统网络处理及应用方面的不足。它综合了通用处理器的可编程j 量立交通盔堂亟量论塞性与专用集成电路和高速度，可以适应不同功能的网络设备的需要，大大降低了研发成本，缩短了产品进入市场的时间。而且由于网络处理器大都是多核多硬件线程架构的，这为解决流分类性能瓶颈开辟了一条新途径。1 2 选题意义流分类的本质是准确快速的查找，它的困难在于保证在达到准确分类条件下分类的多维性、分布式环境下分类规则的一致性和分类的高效性。在多于两维空间上的流分类是比较困难的，一般是需要o ( 1 0 9 卜1 ) 的空间复杂度和线性时间复杂度或者l o g n 的空间复杂度和d ( x ) 的时间复杂度【l 】。直接简单套用快速查找的算法或者传统的通用查找分类算法是不符合现代流分类要求的，只有研究分类规则的特性及其相互关系等诸多因素，才有可能找到有效的解决方案，从而为各种网络技术的发展奠定坚实的基础，在当前形势下研究流分类技术，无论是在实用价值还是在理论上都具有重要意义。而本文所选取的r f c ( r e c u r s i v ef l o wc l a s s i f i c a t i o n ，递归流分类1 算法是流分类算法中可以软件实现的查询速度最快的算法之一，算法中存在很多可以并行处理的部分，例如处于同一阶段的预处理表或者交叉乘积表都可以被并行查询，处于不同阶段的表项也能够被互不干扰地查询。i x p 2 4 0 0 属于i n t e l 公司的第二代网络处理器产品。由于采取了多处理、多线程、分布式处理、分布式缓存等技术，使得i x p 2 4 0 0 具有强大的网络处理性能和灵活的网络处理功能，常用于构架防火墙、核心路由器、安全网关等网络设备。在网络处理器上可以充分地利用多处理器、多硬件线程并行地查询r f c 算法中缩减树中的多个表项，把较长的存储访问时延隐藏起来，实现对数据包的快速分类。此外，本文得到了“北京交大i n t e l 网络处理器联合实验室的资金和技术的资助，本文所研究的内容是“i n t e l 大学合作计划 在北京交通大学中的研究项目，该项目致力于研究高速的流分类技术及其在多和多线程的网络处理器上的应用。对流分类技术进行深入研究，开发出一组符合市场需求、具有自主知识产权的新型基于网络处理器的流分类模型，有着十分广阔的市场前景和重要的科研意义。1 3 国内外研究现状实用化的快速包分类算法是近年来的一个热点研究，其目的是寻找具有合理的时间和空间复杂度、适应较大规则库且在最坏情况下也具有较高性能的包分类算法。其中比较典型的流分类算可以分为四类【2 】：以穷尽搜索为主要思想的线性2绪论查找和t c a m 算法；以决策树为主要思想的集合归并查找树，栅格查找树算法，h i c u t s 算法等；以划分元组空间为主要思想的元组空间算法一系列算法；以对数据处理过程分解为并行过程成为主要思想的交叉乘积、r f c 、并行比特向量算法等。这些算法按照应用场合划分也可以分为在硬件上实现的方案和在软件上实现的方案。目前最常见的硬件方案是使用t c a m 3 】【4 】，该方案所需的分类时间最短，只需要一个内存访问周期：但是由于t c a m 功耗大，内存密度小，价格昂贵，并且它能够处理的分类规则也十分有限，因此也不是一种理想的解决方案。除了硬件实现的算法之外，现有的大部分包分类算法基本上是基于通用处理器实现软件实现的。因为在多维上实现流分类算法本身是比较困难的，所以在通用处理器上软件实现的算法，大都查询并非很快。网络处理器是为数据包处理而优化设计的芯片，其多核多线程的体系结构非常适合支持线程级并行，可极大提高数据包的处理效率。本文正是基于r f c 算法的实现过程中存在很多的并行步骤，而网络处理器中对并行算法的实现提供了硬件支持。然而目前基于网络处理器多核多线程体系结构而设计的流分类算法并不多，在这个领域还有很大的研究空间。自从1 9 9 9 年g u p t a 和m c k c o w n 提出了r f c 算法【5 】之后，流分类领域有很多的学者对r f c 算法的应用和改进提出了自己的研究成果，比如g u p t a 在其r f c提出的文章当中就提出了利用邻接规则压缩规则库【5 】的思想，s p i t z n a g e l 提出了对交叉乘积表采用比特向量压缩的方法【6 】，并进一步提出了改进的措施，但是并没有对算法的数据设计实现。d u ol i u , b e ih u a 等提出了对交叉乘积表位图压缩算法的实现方案【7 】【8 】【9 】，并对算法在网络处理器上的实现作了积极的探索。k o u n a v i s等人对网络中规则库的分布规律作了总结，并提出了在网络处理器上利用软件硬件分别实现m 查询和剩余域查询两个阶段实现方案【1 0 1 ，并对这种两阶段实现方案进行了详细地分析【l l 】。本文的研究工作是基于以上前人提出的思想和算法，综合了压缩规则库和比特向量压缩交叉乘积表两种思想对r f c 算法进行了改进，并在网络处理器上进行了软件设计方案。1 4 本文的主要工作本文综合了前人提出的规则库压缩和交叉乘积表压缩的思想对r f c 算法进行了这两方面的改进，并对算法在网络处理器上进行了软件设计仿真，仿真结果显示，本算法能够对r f c 算法的空间占用情况有很大的改善。本文的内容由以下章节组成：第1 章，绪论，论述论文的选题背景，选题意3义，研究现状和论文的主要工作。第2 章，流分类算法综述与网络处理器i x p 2 4 0 0简介。流分类综述部分主要介绍了流分类算法的定义，常用的匹配方式，匹配字段，衡量标准，设计原则并对常用的流分类算法作了介绍总结。网络处理器简介部分主要对算法实现的硬件平台及软件开发架构作了简要介绍。第3 章，r f c算法的改进，分别对规则库压缩和交叉乘积表压缩两种改进措施进行了功能分析，数据结构设计，流程规划，代码实现。第4 章改进算法在网络处理器上的设计，主要对网络处理器上的维引擎、线程、存储区等资源作了详细的划分，并针对算法在网络处理的实现作了进一步的优化和改进。第5 章，改进算法的仿真和测试，给出了仿真环境配置情况，给出了仿真结果并进行了分析。4流分类综述与i x p 2 4 0 0 简介2 流分类综述与i x p 2 4 0 0 简介2 1 流分类综述2 1 1 流分类概述流是具有某种相同属性的网络协议报文的集合【1 2 】【1 3 】f 1 4 】【1 5 】，是具有某种相同属性的报文的集合，区分两个流的不同在于比较它们两者属性的差异。组成流的最小单位是报文。简单的说，流分类问题主要是基于报头的一个或多个域，根据事先定义的一定的策略和规则识别该报文所属的流。一个d 维的流分类问题可以描述如下：与流分类有关的事先定义好的策略和规则的集合称为分类器，对于给定n 条规则分类器，俾，) 笔，其中规则r ，由三部分组成：1 ) 一个规则表达式r 廖】，1 i d ，其中d 代表数据包头有d 个域。2 ) 一个数字，p r i ( r ，) ，指出了该条规则在分类其中的优先级。3 ) 一个操作，a c t i o n ( r ，) ，对于一个到达数据包p ，其数据包头是d 维元组( 暑，另) ，我们说它匹配规则尺，当且仅当匹配尺， i 1 ，其中1 i d ，并且p r i ( r j ) p r i ( r ，) 。简单地讲，流分类就是将到达的数据包包头与流分类设备中预设的规则库相比较来决定数据包所属数据流的过程，转发引擎将根据分类结果采用相应的方法来处理数据包。图2 1 为一个简易的流分类模型。流分类器i1 一图2 - 1 流分类模型f i g 2 - 1p a c k e tc l a s s i f i c a t i o nm o d e l在流分类的过程中起关键作用的是规则库 弓) 二。，它是流分类的依据，由n5条规则构成，如表2 1 所示。每条规则r ，0 = 1 ，2 ，n ) 都关对应于一种特定的处理结果( a c t i o n ) 。若一个到达的数据包p 匹配了某条规则尺，p 就应该作相应的处理( a c t i o n j ) 。所以，流分类过程实质上就是对特定的数据包p 在俾，慢规则库中搜索与之匹配的规则，确定p 的流类别，对p 做相应的处理。流分类的过程是根据p 包头中的d 个域h 【1 】，h 2 】，h d 】进行，此时的规则库称为d维规则库。其中任一规则码也可以用一个d 维向量r ，= ( r i l l ，r j 2 ，尺， d 】) 来表示，b 中第i ( i - 1 ，2 ，d ) 个分量尺】是一个与h 【i 】相对应的表达式。表2 - 1 规则库实例t a b l e2 - 1e x a m p l eo f r u l es e t s规源口目的p协议类源端口目的端口处理结则型果号o2 1 1 7 1 7 1 1 2 8 2 52 0 2 1 1 2 1 4 4 0 ，2 4t c pg t l 0 2 38 0p e r m itl2 1 1 7 1 7 1 1 2 8 2 52 0 2 1 1 2 1 5 4 o 2 4t c pg t l 0 2 32 1p e r m it22 1 1 7 1 7 1 1 2 8 2 52 0 2 1 1 2 1 5 4 o 2 4t c pg t l 0 2 32 3p e r m it32 1 1 7 1 7 1 1 2 8 2 50 1 0 2 3d e n y42 0 2 11 2 1 5 4 0 陀40 1 0 2 3d e n y52 0 2 1 12 1 4 4 0 2 40 1 0 2 3d e n y6p e r m it数据包p 匹配规则r i 被定义为：对于任意的i ( i _ 1 ，2 ，d ) ，p 包头中的第i 个域h i 】匹配规则r ，的第i 个分量r 】。一般r ，的任一个分量尺 定义整数集上的一个范围，p 匹配r ，意味着对任意的i ( i _ 1 ，2 ，d ) 有h 【i 】属于r 】。因此，任一规则的流分类可以转化为在多维空间中点的定位问题：d 维空间中有n 个d 维长方体( 规则r ，) ，流分类问题是确定给定点( 数据包p ) 位于哪个长方体中。由于p 可能匹配规则库皿，) 羔，中的多条规则( 即规则冲突) ，需要对每条规则赋予一个代价或优先级以解决多重匹配的问题，这样流分类过程实际上就是在但，迕中搜索匹配p 的代价最小的规则r ，的过程。6流分类综述与i x p 2 4 0 0 简介路由查找是流分类的一个特例，它根据数据包头中的目的口地址查找路由表( 一般采用最长前缀匹配) 得到下- - 跳( n e x th o p ) 地址，因而是一个一维流分类问题。数据包头与规则的匹配有三种方式【1 2 】【1 3 】【1 4 】：1 ) 精确匹配：数据包头中的每个域都恰好等于某一规则的对应域的值( h i 】= r j i 】) 。2 ) 前缀匹配：某一规则的每个域都是报头相应域的前缀，一般应用最长前缀匹配( r 廖】是h i 的前缀) 。3 ) 范围匹配：报头每个域的值都在某一规则相应域指定的范围内( h i 】属于r 廖 所限定的范围) 。理论上，报头中七个域可以用于规则库中【1 2 1 1 3 】【1 4 】：4 个字节的目的源口地址、2 个字节的传输层目的源端口号、1 个字节的服务类型、1 个字节协议类型和1 个字节传输层标志。另外，由于应用的需求，数据链路层6 个字节的源地址和目标地址，以及报文净负荷都可以用于分类。国6 bl b4 1 3牾i bl b2 b2 bm a c 源m a c 目的l 3 协议目的m传输层源传输层目上层数据i地址地址类型源i p 地址l 4 端口号t o a净荷地址端口的端口图2 - 2 常用流分类字段f i g 2 - 2t h ep a c k e tc l a s s i f i c a t i o nf i e l d分类器是分类规则和分类策略的集合【1 7 】，是为了对规则库进行快速查找，对原规则库进行优化而构建的。它是实现分类设计的关键依据，分类器构建的好坏将直接影响到流分类查找的速度以及算法的更新速度。分类器的形成是建立在一定标准之上的，这些标准通常与网络应用直接相关，因此依据网络应用将包分类器划分为以下几种类型：1 ) 基于包转发应用的分类器，即单域流分类器。基于这些应用的分类器通常只需对包头中的一个域进行操作。这种应用的例子包括：基于第二层的m a c 地址交换、a t m 信元交换、多协议标签交换m p l s 、第三层的p 转发等。2 ) 基于包过滤应用的分类器，或者称之为多域分类器。基于这些应用的分类通常需要对包头的第二三四层的多个域进行检查，进行精确匹配、前缀匹配或范围匹配操作。目前多域分类器的分类规则一般涉及5 个域：源i p 地址、目的i p地址、协议、源端口和目的端口。这种应用的例子主要有防火墙的包过滤、v p n实现、q o s 应用( 集成服务和差分服务) 等。3 ) 基于内容己知型应用的分类器。这是一个新的应用类型，不仅需要对包7头的域进行检查，还要对包的内容进行扫描和分类。例如服务负载平衡，入侵检测和病毒扫描等。流分类算法是实现线速分类查找的关键，流分类技术发展到现在对包分类算法的评价标准很多，对于不同的应用，其衡量的侧重点也不同。我们一般从以下几个方面来进行衡量【1 6 1 1 7 】：1 ) 分类速度。即分类处理一个数据包所需要的时间复杂度，这是评价分类算法的最重要指标。一般考虑三种情况的时间复杂度：最坏情况、平均情况和统计情况。考虑到计算机中c p u 的计算速度比内存的访问速快得多，因此当计算量大小在可接受的范围内时，一般使用查找中访问内存的次数来衡量一个算法的时间复杂度。为避免成为网络性能瓶颈，包分类速度应能达到线速f 数据包到达流分类器的速度) ，且算法性能不应依赖于特定的业务流量特性。2 ) 空间复杂度。算法的空间复杂度，包括分类器本身和为保证高速的分类查找而建立的各种数据结构所占用的存储空间。分类算法占用的空间越小越好，小的存储空间可以使用较昂贵的高速存储器，例如s r a m ，从而进一步提高分类查找的速度。3 ) 更新复杂度。当规则库发生增量变化时，比如增加或删除一条规则，算法的数据结构需要更新，包括完全更新、增量更新和重组或平衡更新等。4 ) 预处理时间。数据结构初始化所需的时间。预处理时间的长短直接和算法的更新复杂度是相关的。5 ) 可扩展性。目前最大的规则库包括几千条规则，但是动态的资源预留协议可以使规则库膨胀到数十万条。因此对大规则库的可扩展性也是包分类算法的关键特征。可扩展性主要是指对分类的包头字段( 域) 数目和分类器尺寸的扩展可以总结为以下三方面的内容：a ) 分类个数上的可扩展性，指分类器的规则个数n可以很大，而不是限定在固定的一些规则数目上；b ) 分类维数上的可扩展性，指分类规则可以包含任意多个分类字段，而不是限定在固定的某几个字段上：c 分类层次上的可扩展性，指分类可包含多个网络层次的分类，理想的算法应该是能够容许匹配任意层内的字段，包括数据链路层、网络层、传输层，在一些特殊的情况下可能还要包括应用层的内容。6 ) 规则的适应性：一个好的包分类算法应能支持各种形式的规则匹配，包括数据包头各个域的精确匹配、前缀匹配和范围匹配，同时还要能适应不同的规则库规模、规则空间分布及分类域的多少等。目前的大多数解决方案都比较重视前两个因素，即分类查找的时间效率和空间效率，而这两个因素往往互相制约，或者说他们之间存在一种权衡。因为对于一般的应用，规则库都由系统管理员管理【l 】，更新频率很低，所以往往忽略更新8流分类综述与i k p 2 4 0 0 简介速度。流分类算法的研究和发展与目前网络应用的发展息息相关，近年来随着网络的高速发展，各种新的网络应用不断出现，对流分类算法也提出了新的要求，因此我们在研究流分类算法或进行流分类设计时也要遵循一定的原则。现对目前设计流分类算法应该依据的几种原则做如下总结【1 2 】【1 7 】：1 ) 满足线速转发。包分类必须以线速转发数据包，要求网络设备能够及时转发从线路进入的最小数据包，这对基于包分类的各种应用来说是非常重要的，否则网络设备有可能在不知道分组的重要性之前，就将一些重要的包丢掉。2 ) 满足实际要求的情况下，在各性能中进行折衷。如上所述评价分类算法的标准有很多方面，这些方面往往是相互矛盾、相互冲突的，设计满足所有标准的高效算法非常困难，因此要根据分类的具体应用在速度、内存、规则更新等各方面进行折衷。例如分类的速度和所需的内存是一对矛盾，在不可能两者兼顾的情况下，就要根据实际需求或以速度换取空间，或以空间换取速度。3 ) 遵循算法简单和执行的灵活性。过分复杂的分类算法不仅会导致算法实现上的复杂，而且算法本身的运行要消耗一定的资源和时间。在理论上提出了好多“高效”分类算法，在实际中却根本不实用。因此所提出的算法应该尽量简单，在执行上，转发引擎依据系统的需要应该能够用软件或硬件执行。4 ) 尽量利用各种分类算法的优点，依据分类规则的不同字段( 域值) 特点，设计高效的混合分类算法。2 1 2 流分类算法分类文献从解决流分类问题的思想入手，将流分类设计方法划分为如下四个区域【2 1 7 】：1 ) 穷尽搜索( e x h a u s t i v es e a r c h ) 。检查规则库里的所有条目，获得最佳匹配规则。这是最简单和最直观的一类算法。主要有线性搜索( l i n e a rs e a r c h ) 和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 ) 两种算法。2 ) 决策树( d e c i s i o nt r e e ) 。根据规则库里面的规则创建规则树，然后利用数据包的各个字段遍历决策树。这种类型的算法的特点是利用了树这种数据结构。代表算法有格栅查找树( g r i d o f - t r i e s ) 、e g t ( e x t e n d e dg r i d o f - t r i e s ) 、h i c u t s ( h i e r a r c h i c a li n t e l l i g e n tc u t t i n g s ) 、m o d u l a rp a c k e tc l a s s i f i c a t i o n ，h y p e r c u t s ，f i s ( f a ti n v e r t e ds e g m e n tt r e e s ) 等。3 ) 分解( d e c o m p o s i t i o n ) 。将多个域的搜索分解到单个域上进行，首先在单个域上独立搜索，然后再将搜索结果组合起来。这类算法可以将各维的查找并行9执行，利于硬件实现。此类算法有交叉乘积算法( c r o s s p r o d u c t i n g ) 、r f c 算法( r e c u r s i v ef l o wc l a s s i f i c a t i o n ) 、b v ( p a r a l l e lb i t - v e c t o r s ) 、a b v ( a g 目e g a t e db i t v i c t o r ) 、p 2 c ( p a r a l l e lp a c k e tc l a s s i f i c a t i o n ) 、d c f l ( d i s t r i b u t e dc r o s s p r o d u c t i n go f f i e l dl a b e l s ) 等。4 ) 元组空间( t u p l es p a c e ) 。根据规则库指定的字段长度将规则进行分类，然使用简单的精确匹配检查每一部分或者一个子部分。这种算法中间要用到哈希函数，如果有好的哈希函数的话，算法的执行速度比较快。此类典型算法有：t u p l es p a c es e a r c h t u p l ep r u n i n g 、矩形查找( r e c t a n g l es e a r c h ) 、c o n f l i c t - f r e er e c t a n g l es e a r c h 。流分类技术的许多突出的特征是综合采用不同思想的方法来解决的。各种流分类算法都有其优越性和不足，未来的流分类算法一方面将追求较高的速率，另一方面，更加追求可扩展性和可移植性，尽量做到在较小的硬件( 内存、处理速度等) 需求下提高处理速度，并且使得算法尽量不受或少受规则个数、维数和匹配长度等参数的影响。因此设计流分类算法不再是采用单独的某一种算法，而是综合多种分类方法，来实现高效的流分类。图2 3 是这种划分方法的表示图【2 】，邻近的算法是相关的，图中算法的底色为阴影的表示这个算法有很多的改进措施，有一系列的算法与之相关，比如r f c算法就有一系列的改进措施，有很多基于r f c 的改进算法。很多算法并不属于某一个区域，很多算法出于两个区域的边界上。事实上，很多的方法是在各个域之间交叠的。而且现在网络领域学者们对流分类算法的研究也不再局限于单一的查询手段，而是复合使用多种方法，比如文献【1 1 】中就是采用了交叉乘积和元组空间算法。流分类算法的使用也要看具体的实现环境。上述算法中有很多适合软件应用比如交叉乘积算法。也有很多适合硬件上适用，比如t c a m ，也有的算法软硬件上都能使用，比如r f c 算法。而且一般情况下同样的算法在硬件上实现肯定是要比在软件上速度要快一些，但是费用会高一些。i o流分类综述与i x p 2 4 0 0 简介图2 - 3 常用流分类的分类f i g 2 - 3t a x o n o m yo ft h em u l t i p l ef i l e dp a c k e tc l a s s i f i c a t i o n2 1 3 常用的流分类算法p 地址查找算法只检查报头的一个域【1 5 1 ，即p 目的地址域。而流分类可能需要检查报头的多个域，因此说p 查找是流分类的一个特例。在i p 地址查找中，关键字是一种特殊的p 地址表示形式一前缀，查找的目的是为了发现最长匹配前缀。在流分类中，不仅仅允许前缀形式还允许任意范围，这里所指的范围是连续的整数集。在介绍具体的分类算法前，先介绍一下前缀和任意范围之间的转换。例如，一个范围 4 ，5 ，6 ，7 ) 通常被记为 4 ，7 】或者 4 ，8 ，称4 和8 是该范围的两个端点。为了方便起见，也称最大口地址为一个端点【1 5 1 。明显地，每个前缀都能转换为两个端点，因而也就很容易用范围表示。例如前缀o l o * ( w = 5 ) ，它的两个端点为0 1 0 0 0 ，0 1 0 1 1 ，因而可以区间表示为 0 1 0 0 0 ，0 1 0 1 1 ，n 个前缀的集合最多能被转换为2 n 个端点。同样，一个范围也很容易转换为前缀。一个范围 0 , 2 w - 1 ，最多能转换为2 n 一2 个前缀。例如，假定w = 4 ，范围 1 ，1 4 1 可以表示为前缀0 0 0 1 ，0 0 1 ，0 1 料，1 0 ，1 1 0 和1 l1 0 0 。前缀和范围之间的这种关系是非常重要的，因为这样所有的前缀算法都能用来解决范围问题，反之亦然。在介绍算法时，方便起见在允许情况下，都用了前缀表示。1 ) 穷尽搜索。搜索问题最直观地解决方案就是查找规则库中的每一项，当然也可以把规则库分为若干个子库，然后在每个子库中并行搜索。两种极限情况就是在规则库中逐条线性查找或者并行查找规则库中的每一条规则。这两种情况恰好代表了查找速度的下限情况不对规则库划分子集的线性查找和查找速度的上限情况将规则库中的每条规则划分为一个子库的t c a m 。a ) 线性查找【2 】。线性查找是最简单的一种数据结构，它按照优先级升降顺序把分类规则存储在一个数组或者链表中。对于一个到达报文的报头，逐条查找规则，直到匹配为止。这种方案不适用于有大量规则的分类器。该算法实现简单，但是算法的扩展性差，查找时间随规则数的增加而线性增加。b ) t c a m t 3 】【4 】【1 8 1 是将所有的规则按照优先级降序排列存储于t c a m 的内存阵列中，对于到达的数据包并行与所有的规则进行比较匹配，输出n 位的比特向量，然后再通过一个优先级判决的逻辑电路即可得到最佳的匹配规则。t c a m 采用了并行处理，理想情况下一个时钟周期内就可以完成数据包的流分类匹配。但是t c a m 在工艺上没有r a m 密集，t c a m 的价格远远高于r a m ，是一种高端存储器件，而且由于t c a m 采用了并行查询，导致t c a m 的功耗过大，另外，从t c a m 的存储方式和匹配方式可以看出，t c a m 不支持范围匹配，如果规则库中涉及端口的范围匹配，则必须将端口转化为前缀。对于w 比特的端口范围，在最坏情况下可能转化为w 2 个前缀，这将大大地浪费t c a m 的宝贵存储空间，所以t c a m 只适用于小规则库的情况。2 ) 决策树【2 1 。这类流分类算法都需要在预处理阶段构造一棵决策树，决策树的叶子节点上市规则库的子库。流分类查找前，需要将数据包头构造成一个查找关键字。查找时，利用查找关键字的每一个或者几个比特在决策树中进行每一步的遍历，直到找到某个页子节点，包含一个或者几个规则，挑选优先级最高的做相应的处理。在每个节点上作决策时，前缀、范围、精确匹配的混合方式是难以作决定的，必须将它们转化为一种匹配方式，而规则中存在任意范围的情况，这样在转化为比特向量时，就会导致一条规则可能在多个叶子节点中出现。而决策树算法中大都是想办法解决规则在叶子节点中的重复出现问题。决策树算法的查找时间复杂度大都为o ，w 为决策树的深度。1 2流分类综述与i x p 2 4 0 0 简介a ) 分层查找树【1 2 】【1 5 1 ( h i e r a r c h i c a lt i l e s ) 是对一维查找树的一种简单扩展，采用递归方式生成。假设分类器c = r ，) 有d 个域，如果d 大于l ，首先构建第一维查找树，称为f 1 t d e ，它对应分类器中所有规则的第一域前缀集 只，。) 。f i h i e 中的每个结点表示一个前缀p ，在p 处递归的构建一个( d 一1 ) 维的分层查找树。