（计算机科学与技术专业论文）高性能多维包分类算法的研究.pdf

高性能多维包分类算法的研究 摘要 随着网络技术的飞速发展以及网络应用的层出不穷，互联网用户对网络服务 的可靠性、安全性、多样性都提出了更深层次的要求。路由器需要提供有差别的 网络服务才能满足不同用户的需求，如包过滤防火墙、流量计费、流量控制、区 分服务、q o s 等。为了支撑这些新型的网络服务，传统的单独依据目标地址进行 匹配的单维包分类算法已经不能满足多样化的网络新需求，路由器需要根据数据 包头的多个域对数据进行分类处理，例如数据报文的5 元组( 源i p 地址、目的i p 地 址、源端口、目的端口、协议) 。研究表明，i n t e r n e t 持续迅猛的发展对多维包分 类算法提出越来越高的性能要求，不仅要求匹配速度快、空间占用少，且对算法 动态更新及扩展性能也有高的要求。研究高性能的多维包分类算法是大规模高速 网络发展的必然要求。本文提出两种高性能的多维包分类算法，一种属于软件范 畴，一种属于硬件范畴，如下所述： 软件算法方面，提出一种基于元组空间的高性能二维包分类算法t b ( j o i n t t u p l es p a c ea n db i t m a p ) ，该算法从维度分解思想出发，联合元组空间和位图设计 并实现。t b 算法首先分别对源i p 和目的i p 进行单维匹配后，运用交叉组合思想形 成访问元组空间的路线，并通过位图过滤技术进一步减少访问元组空间的个数。 相比传统的元组空间算法，t b 算法结构清晰简洁易于实现，时间和空间性能较为 优越，规则库更新较易，且算法扩展性能较好。实验证明，t b 算法平均访问内存 次数低于元组空间代表算法r s f r 约2 6 6 ，空间性能平均低于r s f r 算法3 5 1 。 硬件算法方面，提出一种基于计数布鲁姆过滤器的快速多维包分类算法 c b h t ( c o u n t i n gb l o o mf i l t e ra n dh a s ht a b l e ) ，该算法从数据包匹配规则的聚集特 性出发，结合计数布鲁姆过滤器和哈希表设计并实现。基于聚集特性，对于五维 包分类问题，c b h t 算法首先利用计数布鲁姆过滤器的过滤功能结合单域匹配获 得与前两维匹配的小规模规则集，而后在此有限规则集中对后三维进行匹配。 c b h t 运用数据包匹配的聚集特性对传统的硬件算法结构进行改进，同时通过计 数布鲁姆过滤器提高了包匹配速度并有效支持规则库的动态更新。在斯坦福大学 的p a l a c 实验平台中对c b h t 算法进行仿真实验，实验结果表明c b h t 算法较其它 算法匹配速度快，占用硬件资源少，并有效的支持了规则库动态更新。 关键词：包分类；计数布鲁姆过滤器；哈希表；元组空间；位图 i i 硕士学位论文 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 fn e t w o r kt e c h n o l o g ya n dt h ee m e r g i n gn e t w o r k a p p l i c a t i o n s ，i n t e r n e t u s e r sh a v em a d ed e e p e rd e m a n d so nt h en e t w o r ks e r v i c e r e l i a b i l i t y ，s e c u r i t ya n dd i v e r s i t y t h er o u t e r sn e e dt op r o v i d ed i v e r s es e r v i c e ss u c ha s f i r e w a l l s ，t r a f f i cb i l l i n g ，t r a f f i cc o n t r o l ，d i f f e r e n t i a t e ds e r v i c e sa n dq o st os a t i s f y d i f f e r e n tu s e r s i no r d e rt o s u p p o r tt h e s en e wn e t w o r ks e r v i c e s ，t h et r a d i t i o n a l o n e d i m e n s i o n a lp 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 mw h i c h m a t c h i n g t h e p a c k e t sb y d e s t i n a t i o na d d r e s sc a nn o tm e e tt h en e wv a r i o u sd e m a n d sa n dt h er o u t e r sn e e dt o p r o c e s sm u l t i - d i m e n s i o n a lp a c k e tc l a s s i f i c a t i o nb yt h em u l t i - f i e l di n f o r m a t i o nf r o m t h eh e a d e ro fd a t a ，s u c ha st h ed a t ap a c k e t so ff i v e - t u p l e ( s o u r c ei p , d e s t i n a t i o ni p , s o u r c ep o r t ，d e s t i n a t i o np o r t ，p r o t o c 0 1 ) t o d a y ，r e s e a r c hh a ss h o w nt h a tt h er a p i d p r o g r e s so fi n t e r n e ti sc o n t i n u o u s l yp o s i n gg r e a td e m a n d sa n dc h a l l e n g e so nt h e m u l t i - d i m e n s i o n a lp 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 mp e r f o r m a n c e i tr e q u i r e sn o to n l y h i g hm a t c h i n gs p e e d ，l o wm e m o r yo c c u p a t i o n ，b u ta l s o t h ed y n a m i cu p d a t ea n d s c a l a b i l i t y p e r f o r m a n c e f o r a l g o r i t h m s t h e r e f o r e ，t h e r e s e a r c ho nt h e h i g h - p e r f o r m a n c em u l t i d i m e n s i o n a lp 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 mi st h en e c e s s a r y r e q u i r e m e n to ft h el a r g e s c a l ea n dh i g h s p e e dn e t w o r k i nt h i sp a p e r , w ep r o p o s e dt w o h i g h - p e r f o r m a n c em u l t i - d i m e n s i o n a lp 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 s ，o n eb e l o n g st o s o f t w a r ea l g o r i t h m ，a n da n o t h e rb e l o n g st oh a r d w a r ea l g o r i t h m a sf o l l o w s ： a s p e c t s o ft h es o f t w a r e a l g o r i t h m ，w ep r o p o s e d ah i g h p e r f o r m a n c e t w o - d i m e n s i o n a lp 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 mc a l l e dt b ( j o i n tt u p l es p a c ea n d b i t m a p ) f r o md i m e n s i o n sd e c o m p o s i t i o ni d e a ，t bc o m b i n e dt u p l es p a c ea n db i t m a p t e c h n o l o g yt od e s i g na n di m p l e m e n t t bf i r s tp r o c e s s e do n e d i m e n s i o nm a t c h i n gf o r s i pa n dd i pr e s p e c t i v e l y ，t h e nu s e dc r o s s c o m b i n a t i o nm e t h o dt of o r mt u p l es p a c e a c c e s sr o u t e ，a n da l or e d u c e dt h en u m b e ro ft u p l es p a c et oa c c e s sf u r t h e rb yb i t m a p f i l t e r i n gt e c h n i q u e c o m p a r e dt ot r a d i t i o n a lt u p l es p a c ea l g o r i t h m ，t h es t r u c t u r eo ft b i sc l e a r ，c o n c i s ea n de a s yt oi m p l e m e n t ，h a sb e t t e rt i m ea n ds p a c ep e r f o r m a n c e ，e a s i e r t ou p d a t e ，a n da l s oh a sab e t t e rs c a l a b i l i t y t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt b s a v e s35 1 o ft h es p a c er e q u i r e m e n tt h a nr s f ra n dt h en u m b e ro fa v e r a g em e m o r y a c c e s s e sl o w e rt h a nr s f r2 6 6 a s p e c t so ft h eh a r d w a r ea l g o r i t h m ，w ep r o p o s e da ne f f i c i e n tm u l t i d i m e n s i o n a l 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 mc a l l e dc b h t ( c o u n t i n gb l o o mf i l t e ra n dh a s ht a b l e ) i i i 高性能多维包分类算法的研究 c o n s i d e r i n gt h ea g g r e g a t i o np r o p e r t yo ft h er u l e sw h i c hap a c k e tm a t c h e d ，c b h t c o m b i n e dc o u n t i n gb l o o mf i l t e ra n dh a s ht a b l et od e s i g na n di m p l e m e n t b a s e do nt h e a g g r e g a t i o np r o p e r t y ，f o rf i v e - d i m e n s i o n a lp a c k e tc l a s s i f i c a t i o n ，w ef i r s tg o tt h e s m a l l - s c a l er u l es e tw h i c hm a t c h i n gt h ei pa d d r e s su s i n gc o u n t i n gb l o o mf i l t e r i nt h i s l i m i t e dr u l es e tw ep r o c e s s e ds e a r c ho nt h eo t h e rt h r e ed i m e n s i o n s c b h ti m p r o v e s t r a d i t i o n a ls t r u c t u r eo ft h eh a r d w a r e a l g o r i t h mb yc o n s i d e r i n gt h ea g g r e g a t i o n p r o p e r t y ，a l s oi m p r o v e dt h es p e e do fp a c k e tm a t c h i n ge f f e c t i v e l ya n ds u p p o r t sr u l e s e t sd y n a m i cu p d a t e w eu s es t a n f o r du n i v e r s i t y sp a l a cp l a t f o r mt oa s s e s st h e p e r f o r m a n c eo fc b h ta l g o r i t h m ，t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tc b h th a sb e t t e r t i m ep e r f o r m a n c e ，s a v eh a r d w a r er e s o u r c e s ，a n ds u p p o ar u l es e t s d y n a m i cu p d a t e e f f e c t i v e l y 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 ；c o u n t i n gb l o o mf i l t e r ；h a s ht a b l e ；t u p l es p a c e ；b i t m a p i v 硕上学位论文 插图索引 图1 1包分类原理图2 图2 1包分类技术总分类一8 图2 2 二进制t r i e 结构1 0 图2 3分层t r i e 结构1 l 图2 4集合归并t r i e 结构1 1 图2 5g o t 算法结构1 2 图2 6e g t 算法结构1 4 图2 7e g t - p c 算法结构1 5 图2 8r s 算法结构l8 图2 9b v 算法和a b v 算法结构2 0 图2 10 h i c u t s 和h y p e r c u t s 2 2 图2 1 lt c a m 工作原理2 3 图2 1 2 布鲁姆过滤器原理2 4 图2 1 3l m p b l o o m 算法结构2 5 图2 1 4d c f l 算法结构2 6 图2 1 5d c f l 算法聚合结点结构2 7 图3 1t b 算法结构3 l 图3 2 规则编码实例3 2 图3 3t b 算法包匹配实例3 4 图3 4小规模规则库( 3 0 0 6 0 0 0 ) 性能测试3 7 图3 5大规模规则库( 5 0 0 0 1 0 0 0 0 0 ) 性能测试3 8 图3 6 运用r s f r 算法作者提供的规则库测试3 9 图3 7t b 算法更新图示4 l 图3 8r s f r 算法更新实例4 l 图3 9 不进行重编码的t b 算法4 3 图4 1计数布鲁姆过滤器4 7 图4 2c b h t 算法结构流程图4 9 图4 3c b h t 算法包匹配流程5 2 图4 4p a l a c 模块交互图5 3 图4 5p a l a c 应用层关系5 4 图4 6c b h t 算法和b 2 p c 算法总平均访问次数比较5 9 v i i 高性能多维包分类算法的研究 表1 1 表2 1 表2 2 表2 3 表2 4 表2 5 表3 1 表3 2 表4 1 表4 2 表4 3 表4 4 附表索引 包分类规则库( 其中代表通配符) 3 二维规则库实例1 0 e g t - p c 算法示例五元组规则库1 4 元组空间概念实例1 6 b v 和a b v 算法样例规则库1 9 包分类代表算法性能表2 8 t s 个数及最坏内存访问次数3 7 t s 个数及最坏内存访问次数3 9 c b h t 算法样例规则库5 1 哈希表的平均冲突5 7 c b f 假阳性概率及位引用率5 7 c b h t 算法平均内存访问次数5 8 v i i i 硕士学位论文 第1 章绪论 1 1 包分类算法研究的背景与意义 因特网的出现和发展使人们的生活发生了巨大的变化。伴随着网络技术迅猛 持续的发展，人们对网络服务的要求越来越高，服务类型也趋于多样化。从当前 数据通信网协议的应用情况来看，i p 协议己成为一个占绝对主导地位的网络层协 议。众所周知，传统的i n t e r n e t 是基于尽力传送( b e s t e f f o r t ) 模型，它只根据数据包 的目的地址决定下一跳地址，而且对于到来的数据包采取先来先服务的方式，并 不区分数据包的优先级，其服务质量无法得到保证，无法满足人们对网络服务多 样化的需求。为了解决q o s 问题，网络服务提供商( i n t e r n e ts e r v i c ep r o v i d e r ，i s p ) 对传统路由器“先来先服务 的工作方式进行了改进，提出了区分服务( d i f f s e r v ) 这一主流q o s 体系结构，其基本思想是在一个资源有限的网络中，通过适当的数 据分类和优先级处理，提供足够的质量保证，反应在应用层面上就是按照用户对 服务的具体要求和服务价格，向用户提供满意的服务。区分服务的基本方法包括 以下几种：流量区分；总量控制；核心简化；边界智能等。区分服务能够很好地 与i p 网络相适应，其可扩展性、实现的简单性和可操作性使得区分服务逐渐成为 目前主流的i pq o s 体系结构。而这一主流q o s 体系结构的支撑就是数据包分类 ( p a c k e tc l a s s i f i c a t i o n ) 技术。 包分类技术是路由器依据i p 包的包头信息，通过匹配规则库中的规则对数据 包进行归类处理的过程，如图1 1 所示。包分类可以分为单维包分类算法和多维 包分类算法，单维包分类指根据数据包头的某个域进行匹配的过程，是多维数据 包分类的基础。路由查找是典型的单维包分类算法，它通过查找i p 数据包头中的 目的地址来决定其下一跳地址。多维包分类提取i p 包头多个域的信息，一般为源 i p 地址、目的i p 地址、源端口、目的端i ：i 、协议，根据提取的信息在相应的规 则库中进行多维匹配，按照最终匹配规则对应的策略对数据包采取相应的措施， 以完成相应的新型服务。 目前的因特网日益趋于商业化，从用户需求和应用发展的趋势来看，近年来 兴起的一些网络应用希望路由器能够提供相应的功能支持。这些功能包括防火墙 ( f i r e w a l l s ) t 1 1 、基于策略的路由( p o l i c y b a s e dr o u t i n g ) t 2 1 、虚拟专用网络( v p n ) 【3 1 、 流量计费( t r a f f i cb i l l i n g ) t 4 1 、流量控制( t r a f f i cc o n t r 0 1 ) t 5 】以及区分服务【6 】等等。为 满足用户提出的诸如上述的这些新型的服务，路由器需要对到达的数据流进行识 别，并归类为不同的数据流，根据不同的数据流来决定是否优先转发、是否拒绝 高性能多维包分类算泫的研究 转发、应该分配多少相应的带宽或是相应的数据流应该收取多少费用等一系列问 题。然而只根据包的单个域无法对各种各样的数据流进行分类，数据包的识别和 分类需要对i p 数据包头的多个域进行匹配，以决定其归属于哪个类及采取的相应 措施。例如，防火墙是保护网络安全的一个有效手段，防火墙除了最基本的网络 包过滤功能外，包含了越来越多的安全功能：拒绝非法链接、抗d d o s 攻击、防 蠕虫病毒和垃圾邮件、支持入侵检测等等，这些都要求防火墙需要超强的包识别 分类功能。防火墙为了决定是否包过滤，需要对包头的源i p 地址、目的i p 地址、 协议类型、源端口、目的端口甚至i c m p 包头的消息类型、t c p 包头的标志位等 众多个域进行匹配。因此，多维包分类算法成为目前学术界研究的重点，也是网 络发展的需要。网络技术持续的发展，提出更多多样化的新型网络服务，例如防 火墙目前提出最新的深度包检测技术不仅依据网络层和传输层的信息进行识别分 类，还可以达到对应用层内容的识别。近年来，由于光纤技术的发展，通讯链路 传输速率已经基本解决，从已有的研究表明，实现高效多维包分类算法已经成为 影响路由器性能的新瓶颈，因此多维包分类算法是当前网络技术的研究热点，具 有重要的研究意义。本文的研究内容为：高性能的多维包分类算法。 i p 数据包 输入序列 分类规则库 发 弋上 卜、 包分类算法 卜决定对数据包j 拒绝通过 y l 的处理方式 带包分类功能的 n 过 路由器 图1 1 包分类原理图 规则库是包分类算法的核心部件，每条规则都定义了一种数据流类型和相应 的处理方式，表1 1 给出了一个典型的分类规则库实例。每条规则分为“匹配条 件”，“规则权重 和“匹配处理3 个主要的部分。“匹配条件 指示i p 数据包 匹配该规则的条件，条件的每个部分对应包头的一个域。“规则权重 指示当多条 规则同时被匹配时，进行最后选择的优先权重。“匹配处理指示当匹配发生时对 i p 数据包进行的相应处理。源目的i p 两个域为前缀匹配，规则的形式一般为( i p 地址前缀长度) ，如表中规则r l ，源i p 字段对应的规则为2 0 2 1 9 2 1 9 0 2 4 ，表示 到达的i p 数据包的源i p 地址只要前，2 4 位与2 0 2 19 2 1 9 0 匹配即可，即在 2 0 2 1 9 2 1 9 0 2 0 2 1 9 2 1 9 2 5 5 之间的源i p 地址均符合此匹配条件；源目的端口这 两个域一般为范围匹配，即规则给出一个匹配的端口范围，当要转发的i p 数据包 2 硕士学位论文 的对应端1 2 1 号落在这个范围内时，发生匹配，如 1 0 2 4 表示端口范围 1 0 2 4 6 5 5 3 5 ，通配符q 表示的范围为0 - 6 6 5 3 5 ；协议类型字段通常要求精确匹 配，只有当规则的协议类型字段和i p 数据包的相等时才满足匹配条件。分类器提 取待分类i p 数据包中相关维度的信息，并与规则库中的规则进行匹配查找，只有 当所有维度信息同时满足各匹配条件时，分类器才认为该规则和待分类数据包发 生匹配。当发生多匹配时，分类器必须根据各规则对应的“匹配权重”大小进行 选优，根据最优规则指示的“匹配处理 对该数据包采取相应的处理。例如当前 待匹配的i p 数据包为( 2 0 2 1 4 3 1 0 9 1 9 2 ，1 9 6 1 6 8 1 2 0 ，4 0 0 0 ，8 0 8 0 ，u d p ) ，经过 各维度的匹配后，可得出最终匹配规则为r 2 ，因此路由器根据该规则相应的处理 方式对其进行优先转发。 表1 1 包分类规则库( 其中+ 代表通配符) 多维包分类技术已经广泛应用于不同的场合【7 l ：应用在核心级路由器上，用 于区分不同的业务流和实现q o s 管理；应用在接入级路由器上，以实现基于策略 的路由：应用在边缘级路由器上，协助实现网络防火墙。综上所述，多维包分类 算法是支撑因特网服务的关键技术之一，是新型网络设备( 如m p l s 路由器、防火 墙、v p n 网关等) 及相应新型网络服务( 如差分服务、包安全过滤、流量记账、流 量限制服务等) 发展和实现的核心技术。 1 2 包分类算法性能指标及研究进展 包分类从9 0 年代开始逐渐成为网络技术研究领域的热点问题，随着网络向高 速大规模方向发展以及各种新型网络服务的产生，包分类技术不仅从最初的单维 路由查找发展到各种多维的数据包分组分类技术，而且性能方面要求也越来越高， 主要包括匹配速度快，占用内存少，支持规则库动态更新，算法扩展性能高等等。 通常从以下几个方面评价一个包分类算法的性能： 3 高性能多维包分类算法的研究 1 1 匹配速度：即分类处理一个包所需要的时间，这是评价包分类算法最重要 的指标，一般可以通过内存访问次数衡量。 2 ) 存储空间：算法占用的存储空间不仅仅指容纳分类规则本身所需的，还包 括算法本身进行查找所建立的各种数据结构所占用的存储空间。它同样是需要考 虑的重要因素。 3 ) 预处理时间：算法数据结构初始化所需的时间。 4 ) 规则库更新：当规则库增加或删除一条规则时，算法的数据结构需要更新。 有些算法在更新规则库时不能进行分类处理，因此包分类算法要求最好可以动态 的支持规则库更新。 5 ) 可扩展性能：可扩展性包括三个方面的内容：( 1 ) 分类算法需要对规则库的 规模大小具有可扩展性，分类规则的数目n 可以扩展，而不是限定在固定的数 目上。( 2 ) 分类的维数具有可扩展性。规则可以包含多个分类字段，而不是限定在 固定的某几个字段。( 3 ) 包分类算法需要考虑向i p v 6 的可扩展性能，虽然目前仍 然以i p v 4 为主要的i p 体系，但是以长远目光来看，i p v 6 将会逐渐发展壮大并用 于实践中，因此创新包分类算法时需要考虑i p v 6 的因素。 6 ) 最坏情况性能：最坏情况一般指某算法所处的环境对其优势没有任何的帮 助，例如采用路径压缩技术对数据结构中的单支进行压缩，最坏情况便是结构中 没有任何单支的存在，因此算法性能没有提升。一个好的包分类算法，不仅需要 高的平均性能，还需要保证最坏情况下的性能。 对于数据包分类算法而言，一般期望时间复杂度、空间复杂度和更新复杂度 越小越好，并具有良好的可扩展性，不仅平均性能好，而且在最坏情况下的性能 也良好。在许多情况下，数据包分类算法的全部指标无法同时达到最优，只能根 据算法的使用场合加以折衷。 调研分析包分类技术的研究进展，自从1 9 9 3 年包分类引起人们关注以来，大 概经历了如下几个阶段：1 9 9 9 年以前，包分类技术的研究重点主要为单维的路由 查找算法，期间多维的分组分类技术还不是很成熟和广泛。2 0 0 0 年至2 0 0 3 年， 网络技术的发展和网络新型服务的不断涌现，使得多维包分类算法被广泛重视和 采用，此阶段主要是基于通用处理平台实现的软件类算法，涌现出许多优秀的软 件算法。2 0 0 4 年以来，随着路由器接口速率的不断提高以及硬件技术的不断创新， 以硬件为基础设计包分类算法成为一个研究创新热点，许多新型、高速的存储器 被采用，最为著名的便是t 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 ，三态的基 于内容访问的存储器) 【】芯片，高速缓存等，t c a m 基于内容查找的特点和完全并 发进行的能力，可以实现0 ( 1 ) 的时间性能和o ( n w ) ( n 为规则数目，w 为位宽) 的 存储空间性能，一个时钟就可以完成一次匹配过程，有非常快的速度。但是人们 很快意识到t c a m 存在着明显的缺点：工作功耗相当大，集成度低，价格昂贵， 4 硕士学位论文 只能用于小型的规则库中。近年来，研究人员寻找出另一种硬件结构支持多维包 分类算法：布鲁姆过滤器( b l o o mf i l t e r ) 9 1 。布鲁姆过滤器结构简洁，查找效率高 并易于用硬件实现，需要很少的存储代价，就能以较快的速度得到匹配判断，且 误差可以控制得很小。因此以布鲁姆过滤器为基础设计包分类算法成为目前一个 研究热点和线路。由上可知，包分类主要分为软件范畴类和硬件范畴类，两类算 法各有优缺点，硬件算法分为纯硬件及软硬件相结合的算法。包分类算法发展至 今，已经发明了很多经典的算法，提出了很多包分类领域的新概念。然而，高速 大规模网络持续迅猛的发展要求我们继续研究更高效的多维包分类算法，使包分 类技术得到与时俱进的发展和创新。学术界已有的各类算法将在第二章详细介绍。 分析目前包分类研究的路线可以概述为以下几个方面：第一，各学术专家不 断提出新的算法设计结构和概念。第二，针对已有经典算法的缺点进行改进，使 得经典算法性能更为优越，适应新的网络环境继续发挥其优势，比如可以利用硬 件结合经典算法来提高其速度，改进其弱点，例如将t c a m 、b l o o mf i l t e r 、高速 缓存等应用于算法中，弥补其不足。第三，由于包分类技术的应用性较强，因此 对匹配规则库( 如路由表和分类规则库) 的分析调研、特性提取，并由此为具体算 法实现指导作用是包分类技术研究课题中一个非常重要的环节。例如将规则库分 为多个子规则库；分析规则库的匹配特征；分层特征；对规则库进行重编码等等， 这些思想不仅用于改进原有的高性能算法，也用于设计了许多新的算法。第四， 基于硬件设计，软件算法和硬件算法各有优缺点，软件算法在选择数据结构以及 处理存储空间和查找时间平衡上都有具有较大的灵活性，且不需要耗费额外的硬 件资源。比较起来，硬件算法具有较高的吞吐率，匹配速度较快。因此基于硬件 可以设计纯硬件算法，也可以和软件数据结构相结合进行设计。 包分类技术目前面临的困难和挑战为：需要跟随i n t e r n e t 增长的步伐符合 i n t e r n e t 接口带宽的增长需求，也就是要求快速的匹配效率，但不能以巨大的空间 为代价；由于各种多样化网络服务的提出，规则库规模逐渐增大，要求包分类算 法具有良好的扩展性能：支持规则库的动态更新，目前很多算法无法支持动态插 入和删除规则，需要重构数据结构；面临向i p v 6 过渡技术转变的挑战等等，另外 多维包分类算法必须根据多个i p 数据包头字段进行匹配，匹配的原则也根据不同 字段的特点有所不同。总之，高速大规模的网络以及多样化的网络服务要求设计 更为高效的多维包分类算法。 1 3 本文的研究内容及主要工作 目前，包分类算法日益被计算科学家及网络设备制造商所重视。多维包分类 技术是路由器实现差别服务的基础，也是避免路由器成为网络性能瓶颈的关键。 本文全面调研了包分类算法的研究状况和主要研究路线，总结分析各类包分类算 法的设计思想并进行深入学习，以设计高性能的多维包分类算法为核心，如匹配 5 高性能多维包分类算法的研究 速度快，支持动态更新，扩展性能好等。本文的主要贡献为：从软件和硬件范畴， 分别提出了两种多维分类算法，一种基于软件实现，一种基于硬件实现。由上节 分析可知，软硬件算法各有优缺点，根据性能需要适用于不同场景。 本文的主要研究内容如下： 1 ) 对包分类算法进行全面的调研学习。 调研当前包分类技术的研究情况，总结分析包分类发展至今的研究路线及发 展历程。对学术界已有的成果进行分类综述，并总结分析各算法性能及优缺点。 包分类技术可以分为软件算法和硬件算法两大类，本文第二章中对各类代表算法 进行详细介绍。 2 ) 软件方面，联合元组空间思想和位图设计高性能二维包分类算法 从维度分解思想出发，将元组空间和位图技术相结合设计并实现了一种高性 能的二维包分类算法t b ( j o i n tt u p l es p a c ea n db i t m a p ) 。t b 算法首先分别对源i p 和目的i p 进行单维匹配后，运用交叉组合思想形成访问元组空间的路线，并通过 位图过滤技术进一步减少访问元组空间的个数。相比传统的元组空间算法，t b 算法结构清晰简洁，易于实现，时间和空间性能较为优越，规则库更新较易。实 验证明，t b 算法平均访问内存次数低于代表算法r s f r 约2 6 6 ，空间性能平均 低于r s f r 算法3 5 1 。 3 ) 硬件方面，基于计数布鲁姆过滤器设计快速多维的包分类算法 分析以布鲁姆过滤器为基础的各代表算法的优缺点后，从数据包匹配规则的 聚集特性出发，将计数布鲁姆过滤器和哈希表相结合，设计并实现了种高效的 多维包分类算法c b h t ( c o u n t i n gb l o o mf i l t e ra n dh a s ht a b l e ) 。基于包匹配规则的 聚集特性，对于五维包分类问题，c b h t 算法首先利用计数布鲁姆过滤器的过滤 功能结合单域匹配获得与前两维匹配的小规模规则集，而后在此有限规则集中对 后三维进行匹配。利用计数布鲁姆过滤器提高了包匹配速度并有效支持规则库的 动态更新。在斯坦福大学的p a l a c 实验平台中对c b h t 算法进行仿真实验，实 验结果表明c b h t 算法较其它算法匹配速度快，占用硬件资源少，并有效的支持 了规则库动态更新。 1 4 论文结构 第一章给出了课题研究背景和意义。分析了当前网络技术的现状；说明了高 效多维包分类技术对于支撑高速网络和多样化网络服务的意义；给出了数据包分 类的定义，对包分类算法的研究状况进行总结；分析总结目前的研究路线和包分 类面临的挑战。最后介绍了本文的主要贡献以及组织结构。 第二章对包分类算法整体进行分类概述。阐述各类算法的主要设计思想及其 代表性算法。主要介绍的包分类算法有：基于数据结构t r i e 的算法、元组空间类 6 硕士学位论文 算法、多维分解类算法、智能分割类算法、基于硬件的算法。 第三章提出一种属于软件范畴的二维包分类算法t b ( j o i n tt u p l es p a c ea n d b i t m a p ) 。t b 算法在深入研究元组空间思想的各个算法的基础上，为了设计更高 效的包分类算法，从维度分解出发，并将元组空间和位图技术相结合设计并进行 实现。t b 算法结构简洁，易于实现，并采用位图技术减少内存访问次数时间性 能优越，空间上相比传统的元组空间算法无需插入伪规则，节省大量空间，扩展 性良好且支持规则库更新较易。仿真实验表明t b 算法具有良好的查询和扩展性 能。 第四章提出一种属于硬件范畴的多维包分类算法c b h t ( c o u n t i n gb l o o m f i l t e ra n dh a s ht a b l e ) 。c b h t 算法将计数布鲁姆过滤器和哈希表结构相结合进行 设计，c b h t 算法的主要思想是采用一个计数布鲁姆过滤器结合哈希表查询结构， 计数布鲁姆过滤器用来表示规则库的前两个域，哈希表用来存储具体的每条规则。 c b h t 算法根据规则库的聚集特征设计算法的结构，算法结构清晰且采用单层布 鲁姆过滤器提高了匹配速度，节省了硬件资源。为了验证算法性能，在斯坦福大 学的p a l a c 实验平台中对c b h t 算法进行仿真实验。 最后，总结本文的主要内容，并给出进一步的研究工作。 7 高性能多维包分类算泫的研究 第2 章包分类算法概述 本章对目前包分类算法进行总体概述，对其进行分类并介绍各类中最具代表 性的算法。包分类算法研究至今，计算机科学家们从各种不同的角度与视野提出 了各种适用性不一的包分类算法。从实现角度进行分类，包分类可以分为软件算 法和硬件算法两大类。用软件实现和用硬件实现各有优缺点，根据用户需求适用 于不同的场合。 软件实现 包分类技术 基本数据结构li 规则库几何分割 a q 乡每 p r u a e d i s )fr s c o n f l i c tf r e e r s ) ( r s f r 图2 1 包分类技术总分类 图2 1 为包分类技术的总分类图。如图中所示，软件包分类算法可以大概分 为如下几类【l 0 。1 1j ：基本数据结构算法，其中包括线性查找、分层t r i e 树、集合归 并t r i e 树i l2 1 、格栅查找树【1 3 】；规则库几何分割算法是指将所有分类域值构成的 集合看成一个空间，每条规则的匹配条件可映射成该空间中的某个子区域，而某 个关键字则对应空间中的一个点。查找时，通过判断i p 数据包代表的点落入的 子空间范围，逐步收拢得到最终匹配的规则，其中包括f i s 树【1 4 】、基于区间划分 的四树算法a q t 15 1 、智能分割的h i c u t s 算法【1 6 】和h y p c r c u t s 算法【1 7 l ：启发式算 法是指通过对实际网络中分类规则的考察，发现规则都有内在的结构和冗余度， 这些特点可以被启发式方法利用。其中包括递归流分类算法r f c 1 8 j 、元组空间算 法t s s 1 19 1 、多维分解算法b v 2 0 】、a b v 2 1 1 等等。t r i e 树结构算法最早发明，目前 最为优秀的基于t r i e 的算法为e g t - p c i 2 2 1 。规则库分割算法中以智能分割性能最 为优越，h i c u t s 和h y p e r c u t s 思想起源于决策树。启发式算法中r f c 算法出发点 为包分类过程实质上是一种映射过程，将数据包头中的s 比特映射到t 比特的规 则序号，s 远大于t ，但是提前计算2 s 种不同的数据包头所对应的规则号相当耗 8 删【、卜f一 曼芏爹未、(丌一k讯一饕 硕上学位论文 费内存，r f c 致力于以一种递归的方式将所需映射分为几个阶段进行，每个阶段 都将一个大的集合映射为一个小的集合，由于r f c 将包头的d 个域分为多个块进 行映射，因此从另一角度也属于多维分解算法。元组空间算法的出发点为尽管规 则库中不同前缀的规则数量很多，但是不同前缀长度的数量有限，基于此将一个 规则库分割为多个子规则库，因此元组空间也属于规则库分割类。维度分解思想 起源于分治法，也属于一种启发算法。具体思想是指将多维的包分类首先分为多 个较为简单的一维分类问题，而后再综合各维匹配结果得到最终结果。这些设计 思想均用于许多优秀的算法中。 硬件包分类算法可以分为两大类：基于三元内容寻址存储器( t e r n a r yc a m s ) f 8 】和布鲁姆过滤器( b l o o mf i l t e r ) 【9 1 。基于硬件的算法也包括将软件和硬件相结合 设计的算法，优势互补，效率更高。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 实现的包分类算法匹配速度较快，但其价格相当昂贵且容 量小，耗电量大，不能直接支持范围匹配，因而对规则数量，规则维数和每维宽 度的可扩展性均较差，只能用于较小的包分类问题【2 3 之4 1 。布鲁姆过滤器实质是一 种能够表示集合元素、支持集合元素查询的简