（计算机系统结构专业论文）支持快速增量更新的包分类算法研究.pdf

摘要 摘要 随着i n t e r n e t 的迅速发展，网络服务日趋多样化，新的网络应用层出不穷。 包分类技术足网络服务多样化的基础，它使得路由器能够区分地处理网络流量。 随着一些实时性要求很高的新兴应用出现，服务质量( q u a l i t yo f s e r v i c e ) 保证 技术越来越重要，该技术通常需要频繁地更新分类规则集。然而，现有大多数 包分类算法主要关心分类速度和空间需求的改进，而不太重视更新性能。更新 操作过r 复杂，有的甚至需要重建整个数据结构，更新代价昂贵。这使得这些 算法不适合那些要求动态分类的新兴应用，动态分类必须在满足线速 ( l i n e r a t e ) 的同时快速地更新规则集。因此，研究如何实现一个支持快速增 量更新并且满足线速分类要求的包分类算法具有重要的实际意义。 本文先分析了现有典型的包分类算法。发现递归空间分解是目前更新性能 最好的二二维包分类算法，因为它具有非常好的更新局部性。并发现两阶段多维 包分类笄t i c 很好地利j j 了规则集特征，其第，一阶段采用r f c 缩减树，第二阶 段引入解释器方法。r f c 是目前分类速度最快的多维包分类算法，但其缩减树 不支持增量更新。t i c 相比r f c 极大地减少了存储消耗和预处理时间，并保持 了与r f c 相当的分类速度，但它仍不支持增量更新。 因此，本文利用递归空间分解来替换t i c 第一阶段的r f c 缩减树，提出了 一个支持快速增量更新的两阶段多维包分类算法t i c s 。但是，递归空间分解生 成的a q t 树中存在很多空结点，a q t 树路径过长导致查找性能不佳。通过两 种路径压缩技术来压缩树路径，以提高查找性能。利用树结构特点，采用局部 数据结构重建替换的方法，并结合对数据结构的内存管理，在多核平台上实现 了共享数据结构的尊写者多读者并行无锁实时规则集增量更新，消除了更新和 查找共享数据结构之间的同步开销，避免了更新导致的查找中断。 实验结果表明，t i c s 算法的更新速度比现有更新最快算法至少提升了一个 数量级。路径压缩技术既减少了存储消耗，又提高了查找性能。虽然t i c s 算 法相比t i c 算法绝对分类速度差距较大，但t i c s 算法具有优异的并行可扩放 性，可以通过提高并行度来达到线速分类要求，并且t i c s 的预处理时间较t i c 降低了3 个数帑级。t i c s 算法更新和查找并行同步进行时，二者的相互影响很 小。当更新频率不太高时，更新对查找性能几乎没有影响。尽管全速更新，查 找速度的下降也很少。 关键词：包分类；增鼋更新；动态分类：并行；无锁 a b s t r a c t a b s t r c a t w i t ht h er a p i dd e v e l o p m e n to fi n t e m e t t h e r eh a sc o m eo u tl o t so fn e wn e t w o r k a p p l i c a t i o n s a st h en e t w o r ks e r v i c e sb e c o m em o r ea n dm o r ed i v e r s e p a c k e t c l a s s i f i c a t i o ni st h ef o u n d a t i o no fd i v e r s i f j c a t i o no fn e t w o r ks e r v i c e s i ta l l o w st h e r o u t e rt op r o c e s sn e t w o r kt r a f f i cd if f e r e n t i a l l y w i t ht h ee m e r g e n c eo fn e wn e t w o r k a p p l i c a t i o n si n v o l v i n gh i g hr e a l t i m ed e m a n d ，t h ea s s u r a n c eo fq u a l i t yo fs e r v i c e ( q o s ) i sm o r ea n dm o r ei m p o r t a n t ，w h i c hu s u a l l yr e q u i r e sf r e q u e n tu p d a t e so ft h e c l a s s i f i c a t i o nr u l es e t h o w e v e r , t h em o s to fe x i s t i n gp 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 j u s th a v ep a i da t t e n t i o nt oi m p r o v i n gt h es e a r c hs p e e da n ds t o r a g er e q u i r e m e n t ，b u t h a v e n tt h o u g h tm u c ho ft h eu p d a t ep e r f o r m a n c e t h eu p d a t eo p e r a t i o ni st o o c o m p li c a t e d ，a n ds o m ee v e nn e e dt or e c o n s t r u c tt h ew h o l ed a t as t r u c t u r e t h eu p d a t e o p e r a t i o ni ss t i l lv e r ye x p e n s i v e t h u s ，t h e s ep 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 en o t s u i t a b l ef o rt h ee m e r g i n ga p p l i c a t i o n st h a tn e e dd y n a m i cc l a s s i f i a t i o n d y n a m i c c l a s s i f i c a t i o nh a st os a t i s f yt h el i n e r a t ea n df a s tu p d a t et h er u l es e ta tt h es a m et i m e t h e r e f o r e ，i th a si m p o r t a n tp r a c t i c a ls i g n i f i c a n c et or e s e a r c hh o wt oi m p l e m e n ta 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 mw i t hf a s ti n c r e m e n t a lu p d a t es u p p o r ta n ds a t i s f y i n g t h el i n e r a t ec l a s s i f i c a t i o nr e q u i r e m e n t a f t e ra n a l y z i n gt h ee x i s t i n gt y p i c 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 ，w ef i n d t h a tt h et w o d i m e n t i o n a la l g o r i t h mr e c u r s i v es p a c ed e c o m p o s i t i o n ( r s d ) h a st h e b e s tu p d a t ep e r f o r m a n c e ，b e c a u s ei th a se x c e l l e n tu p d a t el o c a l i t y a n df i n dt h a tt h e t w o s t a g em u l t i d i m e n s i o n a la l g o r i t h mt i cm a k e sg o o du s eo ft h ec h a r a c t e r i s t i c so f t h er u l es e t i tu s e st h er e d u c t i o nt r e eo fr f ci nt h e1s ts t a g e ，a n de m p l o y st h e i n t e r p r e t i n g m e t h o di nt h e2 n ds t a g e r f ci sam u l t i d i m e n s i o n a lp a c k e t c l a s s if i c a t i o na l g o r i t h mw i t ht h ef a s t e s ts e a r c hs p e e dt h u sf a r , b u ti t sr e d u c t i o nt r e e d o e s n ts u p p o r ti n c r e m e n t a lu p d a t e c o m p a r e dt or f c ，t i cg r e a t l yr e d u c e st h e s t o r a g ec o n s u m p t i o na n dp r e p r o c e s s i n gt i m e ，a n dr e t a i n sa l m o s tt h es a m es e a r c h s p e e do fr f c ，b u tt i c s t i l lc a n ts u p p o r ti n c r e m e n t a lu p d a t e t h e r e l b r e ，b yr e p l a c i n gt i c sr e d u c t i o nt r e ei nt h e1s ts t a g ew i t hr s d ，t h i s p a p e rp r o p o s e sat w o - - s t a g 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 mt i c s w i t hf a s ti n c r e m e n t a lu p d a t es u p p o r t h o w e v e r , t h e r ea r et o om a n ye m p t yn o d e si n t h ea q tt r e eg e n e r a t e db yr s d t h ea q tt r e eh a st o ol o n gt r e ep a t h ，w h i c hr e s u l t s i n p o o r s e a r c h p e r f o r m a n c e w ec o m p r e s st h e t r e ep a t ht h r o u g ht w op a t h a b s t r a c t c o m p r e s s i o nt e c h n i q u e s t o i m p r o v et h es e a r c hp e r f o r m a n c e b yu t i l i z i n g t h e c h a r a c t e r i s t i co ft h et r e e ，e m p l o y i n gt h em e t h o do fr e c o n s t r u c t i n ga n dr e p l a c i n gt h el o c a ld a t a s t r u c t u r e a n dc o m b i n i n gt h em e m o r ym a n a g e m e n to ft h ed a t as t r u c t u r e ，t i c s i m p l e m e n t st h ep a r a ll e ll o c k r f r e er e a l ，t i m ei n c r e m e n t a lu p d a t eo ft h er u l es e ta m o n g as i n g l ew r i t e ra n dm u l t i p l er e a d e r sw i t ht h es h a r e dd a t as t r u c t u r eo nm u l t i c o r e p l a t f o r m ，e l i m i n a t e dt h es y n c h r o n i z a t i o no v e r h e a db e t w e e nt h eu p d a t ea n ds e a r c ho f t h es h a r e dd a t as t r u c t u r e ，a n da v o i d e dt h ei n t e r r u p t i o no fs e a r c hc a u s e db yu p d a t e 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 t ，t i c sa c h i e v e sa tl e a s ta no r d e ro f m a g n i t u d eo fs p e e d u pw i t hu p d a t es p e e dt h a nt h ee x i s t i n gf a s t e s ta l g o r i t h m p a t h c o m p r e s s i o nt e c h n i q u e sn o to n l yr e d u c et h em e m o r yc o n s u m p t i o n ，b u ta l s oi m p r o v e t h es e a r c hp e r f o r m a n c e a l t h o u g ht i c s sa b s o l u t es e a r c hs p e e di sm u c hl e s st h a n t i c s ，t i c s h a se x c e l l e n t p a r a l l e ls c a l a b i l i t y i t c a ns a t i s f yt h el i n e - r a t e c l a s s i f i c a t i o nr e q u i r e m e n tb yi n c r e a s i n gt h ep a r a l l e l i s m a n dt i c s sp r e p r o c e s s i n g t i m ei sr e d u c e db y3o r d e r so fm a g n i t u d et h a nt i c s w h e nt i c s su p d a t ea n d s e a r c h o p e r a t i o ne x c u t ec o n c u r r e n t l ya n ds y n c h r o n o u s l y ，t h e t w oh a v el i t t l e i n t e r f e r e n c ew i t he a c ho t h e r w h e nt h eu p d a t ef r e q u e n c yi sn o tt o oh i g h ，t h eu p d a t e a l m o s th a sn oi m p a c to ns e a r c hp e r f o r m a n c e e v e nt h o u g ht i c su p d a t e sa tf u l l s p e e d ，t h ed e c li n eo fs e a r c hs p e e di sl i t t l et o o 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 ，i n c r e m e n t a lu p d a t e ，d y n a m i cc l a s s i f i c a t i o n ， p a r a l l e l ，l o c k f r e e i v 图h 录 图1 1 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图2 9 图2 1 0 图2 1 l 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图3 1 l 图4 1 图4 2 图目录 具有包分类功能的路由器模型1 一个两阶段r f c 缩减树l o 规则r 0 一r l o 对应的 二维区域1 2 规则r 映射到区域a 的三种情形1 2 根据规则r o r 1 0 构造的a q t 四叉树1 2 h i c u t s 算法构造决策树示意图1 4 t i c 算法的三种指令格式1 6 前缀扩展列表的构建步骤示意图l7 中序遍历树状层次链表构建前缀扩展列表1 8 前缀扩展列表的二分杏找过程一1 8 c l a s s b e n c h 工具集的工作流程图2 0 o p e n m p 程序的f o r k j o i n 并行执行模犁2 3 规则r 0 r l0 的前两个域对应的二维区域表示3 0 根据规则r 0 r l0 的前两个域构造的a q t 四叉树3 0 t i c s 算法结点a 的内部结构3l t i c s 算法基于a q t 树的预处理过程伪代码3 3 t i c s 算法基于a q t 树的查找过程伪代码3 4 p c 路径压缩示意图3 5 t i c s 算法基于p c 树的查找过程伪代码3 7 p q t 路径压缩方法构造的p q t 四叉树3 8 t i c s 算法基于p q t 树的查找过程伪代码3 8 向结点a 的源i p 前缀端点列表中插入新规则r 11 4 0 插入规则r 1 2 后的p c 四叉树- 4 1 d e l lp o w e r e d g e2 9 0 0 服务器体系结构示意图”4 5 t i c 与t i c s 算法平均分类速度的并行可扩放性比较5 2 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 表4 5 表4 6 表4 7 表4 8 表4 9 表4 1 0 表4 1 l 表4 1 2 表目录 典型包分类算法的性能比较6 个3 维示例规则集9 参i 包分类的5 个典型i p 包头域2 1 分类规贝u 的5 个典型域”2l 不同源目的端口号类型分布统计2 1 p t h r e a d s 常用编程接口简介2 4 一个5 维示例规则集2 9 3 种删叉决策树的路径长度和查找结点个数统计3 9 d e l lp o w e r e d g e2 9 0 0 服务器硬件参数4 6 i n t e lx e o ne 5 4l0 处理器参数”4 6 l lc a c h e 、l 2c a c h e 和主存的访问延迟4 6 3 个版本t i c s 算法的分类速度对比4 7 3 个版本t i c s 算法的存储消耗对比4 8 t i c 与t i c s 算法的存储消耗和预处理时间对比4 9 t i c s 算法全速更新而无查找时的更新性能4 9 b r p s 算法的更新性能4 9 t i c s 与b r p s 的分类速度对比5 0 t i c s 与t i c 算法的分类速度对比”5 l t i c s 算法全速更新和查找同时进行时的查找和更新性能5 3 t i c s 算法不同更新频率下的查找和更新性能5 3 v l l i 中国科学技术大学学位论文原创性声明 作者签名：一 签字日期：剖 中国科学技术大学学位论文授权使用声明 作为巾请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 叼公开 作者签名： 口保密( 年) 导师签名：经益 签字l j 期：! 社 签字日期：! 竺址 第1 章绪论 1 1引言 第1 章绪论 随着通信及计算机技术的迅猛发展，因特网上的应用越来越丰富。这些应 用要求特网提供安全和多样化的服务，例如基于策略的路由【2 】、流量计费【3 】、 防火墙包过滤 4 】、虚拟专用网【5 】、网络地址转换【6 】、区分服务 7 】等。传统的 网络路由器采用“尽力而为”的工作模式，按照先来先服务的顺序处理到达的 数据包，不对数据包加以区分，从而无法提供有差别的多样化服务。 新掣网络应用要求首先将到达的数据包进行分类，然后根据数据包所属的 类进行相应的处理，因此包分类技术成为新型网络应用的基础。图1 1 是一个 具有包分类功能的路由器模型。 图1 1具有包分类功能的路由器模型 分类器根据预没的分类规则集将到达的数据包指派给不同的流。分类规则 集是一系列规则( r u l e ) 的集合，每条规则对应个流( f l o w ) ，规则中包含与 包头巾卡【1 关域对j 照的匹配条件、一个流标识( f l o w i d ) 和相应的处理方式 ( a c t i o n ) 。当数据包头中的相关域满足某条规则的所有匹配条件时，称数据包 匹配该规则。 包分类技术在边缘路由器和核心路由器中正发挥着越来越重要的作用。随 着链路速度以及网络流蕈的不断攀升，路由器必须不断提高数据包的转发速度 以避免成为嘲络瓶颈，因此高速包分类算法成为实现高性能路由器的关键。除 了速度要求以外，部分实时应用还要求能够动态更新规则集，即动态分类 8 】 9 】 ( d y n a m i cc l a s s i f i c a t i o n ) 的要求。目前大多数包分类算法主要关注提高分类速 第1 章绪论 度和减小存储空间需求，添加或删除规则的操作很复杂，有的甚至需要重建整 个数捌结构，更新规则集的代价仍非常高。这使得这些算法不适合那些要求动 态分类的应用。 目前，实现高速数据包分类主要采用硬件的方法，但硬件方法成本高，灵 活性差。软件方法灵活性好，但是分类速度相对较低。随着多核处理器的广泛 应用，在多核处理器上利用软件实现高速包分类成为可能。本文研究能够支持 快速增量史新的包分类算法，并在多核平台上高效实现。 1 2包分类问题的定义 从数学_ l 石4 ，包分类问题与计算几何中的一些问题很相似。在计算几何中 存在一个多维空间的点定位问题：给定多维空间中的一些互不相交的区域，找 出包含指定点的区域。对应到包分类问题，每条规则对应了多维空间中的一个 区域，数据包头中域的组合对应多维空间中的一个点，包分类问题就是要找出 包含这个t i 的一个区域。 一股米说，包分类问题比多维空间的点定位问题复杂，一是规则的数量可 能很大，二：是区域之间可能有重叠。假设不同区域互不相交，对条过滤规则 进行k ( k 3 ) 维分类，计算几何给出的最好结果是：在空间复杂度为o ( 矿) 时， 时间复杂度为o ( i o g n ) ；或者在空间复杂度为o ( d 时，时间复杂度为o ( 1 0 9 缸。m 。 也就是说，埘1 0 0 条过滤规则、每条规贝04 个域的情况，需要1 0 0 m b 的存储空 间和大约3 5 0 次的访存。 以下是包分类问题的形式化描述。 设数据包头为p ，p 中有d 个域( f i e l d ) 参与包分类，则数据包头表示为p = 们，五力) ，1 5 i _ d ，f 是包头p 中的一个域。 r = f ，f 2 r 厅 是规则集中的一条规则，其中r 对应于包头中的域f 。 凡是一个范闹，用厅= 【l ，凰 表示，l s i d ，其中，为下界，为上界。如果对 于所乍的f ( 1 s 舀力都有l i 鄂i _ j - - i i 成立，称包头p 匹配规则j r 。 r s = r ，r 2 r f r ， 是包含条规则的集合，每条规则都有一个优先 级。包头p 可能i ! 蔓配规则集尺s 中的多条规则，包分类要选择多条匹配规则中 优先级最高的规则。 在实际的列络应用中，并不需要按照包头中的所有域进行分类。根据对若 干匝在运 j ：的i s p 的分类规则集的统计发现，1 7 的规则指定了1 个域，2 3 的规则指定了3 个域，6 0 的规则指定了4 个域 1 0 】。例如，路由查找【l l 】是包 分类的一个特例，路由查找根据数据包头中的目的i p 地址查找路由表( 一般采 第1 章绪论 用最k 前缀匹配) 得到下跳地址，是维包分类问题。对于多维包分类问题， 如粜菜条规则只关心多维中的一维，则其它维可以用通配符枣来表示。包分类算 法支持的分类维度越高，其通用性越好，但复杂度会急剧增加。目前典型的分 类规则要求匹配数据包头中的源目的i p 地址、源目的端口号和协议五个域， 称为五元组( 五维) 包分类。 1 3包分类算法的性能评价 通常从以下几个方面评价一个包分类算法的性能： 1 ) 分炎速度：每秒钟可以分类的数据包数量，单位为m p p s ( m i l l i o np a c k e t p e rs e c o n d ) 。这是评价包分类算法最重要的指标。为避免成为性能瓶颈，包分 类必须达到线速( l i n e r a t e ，数据包到达路由器的速度) 。 2 ) 存储空间需求：算法数据结构占用的存储空间。较小的空间需求不仅可 以降低硬件成本，还可以更好地利用处理器的存储层次。例如，空间较小的数 据结构i l 以放入较上层的片上存储器中，减少访存时间。 3 ) 预处理时间：构建分类数据结构所需的时间。为提高分类速度，通常需 要构建利于查找的数据结构，如表( t a b l e ) 、树( t r e e ) 等。 4 ) 更新时间：在分类数据结构中插入或删除一条规则所需的时间。有两种 更新数据结构的方式：全局更新和增量更新( i n c r e m e n t a lu p d a t e ) 。全局更新需 要重建整个数据结构，开销大，耗时长；增景更新则是在当前数据结构上进行 局部修改，为在线实时更新提供了可能。 5 ) 可扩展性：指分类算法适应不同维度及不同规模规则集的能力。算法能 够很好地适应从一维分类到多维分类的应用要求，并能适应规模越来越大的规 则集，不会冈规模的增大而出现较大的性能下降。 6 ) 并行可扩放性：算法能否有效地利用多核处理器来实现并行加速的评价 指标。实际中，并行算法若能在并行平台上具有较好的可扩放性，即使该算法 在单一节点上的绝对速度不佳，仍可能在算法并行度到达一定数量时具备最佳 的执行速度。 以上这螳性能指标往往会互相制约【1 2 ，一个算法无法在所有性能指标上 都达到最好。包分类算法必须根据具体的应用需求进jj i 权衡。 1 4包分类问题的困难 设计一个各项性能指标都很好的包分类算法是非常困难的，主要困难在于： 第1 誊绪论 1 ) 分类速度和存储空间的权衡：从理论上来看，要同时获得最快的分类速 度和最小的仃储宅问是不可能的，只能根据实际的应用需求在时间复杂度和空 间复杂度之1 1 j 权衡。通常的做法是在满足存储空间约束的条件下，尽可能地提 高分类速度。 2 ) 动态更新：一些提供q o s 保证的服务通常需要频繁地更新分类规则集， 全局更新的7 t - i i ! i 太大，而增量更新则会导致分类数据结构更复杂，并进而影响 分类速度。夼找速度和更新性能之间的权衡很困难。 3 ) 分类维度高：包分类是一个多维匹配问题，问题的复杂度随分类维度的 增加而指数级增长。 4 ) 降低并行化开销：对于动态分类问题，需要在查找的同时增量更新分类 数据结构。在多核平台上，更新和查找之间必须同步，否则会出现数据的不一 致。如何降低或消除并行化带来的同步开销也是一大难点。 1 5包分类的研究现状 目前包分类算法的实现方案主要有硬件和软件两种。最常用的硬件实现方 案是t c a m 9 i3 1 4 ( 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 不是一 种很理想的解决方案。近年来，多核处理器技术发展迅速，处理器的计算能力 越来越强大，片上资源越来越丰富，采用软件方法实现高速包分类成为可能。 e l 前，软件实现的包分类算法大致可分为四类： 1 ) 线，查找算法：这是最简单的一种分类算法。分类规则按优先级顺序由 高到低存储，查找时根据包头中的相关域从表头开始顺序查找。该算法存储效 率高，实现简单，且支持增量更新，但是查找时间长，查找时间随规则数线性 增长。该贸：法只适合小规模的规则集，实际中很少被单独采用。 2 ) 基予决策树的算法：这类算法通常根据规则集构造决策树，将规则集中 的规则映射( 保存) 到树中的相应结点，查找时利用数据包头中相应域的比特 位来选择树的分支。典犁的基于决策树算法有h i c u t s 1 5 】、h y p e r c u t s 1 6 】、 g r i d o f - t r i e s fl7 1 、e g t f l8 】( e x t e n d e dg r i d o f - t r i e s ) 和递归空间分解 1 9 】 ( r e c u r s i v es p a c ed e c o m p o s i t i o n ) 等。这一类算法均支持增量更新，但更新复 杂度差异很火。 3 ) 维度分解算法：将多维分类问题转换为对每个维度的独立查找问题，然 后综合各维的查找结果得出最终的匹配结果。典型算法有a b v 2 0 】( a g g r e g a t e d b i t v e c t o r ) 、c r o s s p r o d u c t i n g 17 】、r f c 【l0 】( 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 ) 和 4 第1 誊绪论 b i t m a p r f c 2 1 1 等。该类算法查找速度快，并具有内在的并行性，但存储空间 消耗大，并且不支持增量更新。 4 ) 瑟于哈希的算法：根据规则中域的关键值或指定比特位，将规则集划分 成若。f 个子规贝0 集，查找时根据域的关键值或指定比特位的哈希值定位到相应 的r 规则集。：于规则集的规模一般较小，可商接采用线性查找。若子规则集规 模较大，则还可采用前缀或范围的二分查找来获得更好性能。典型算法有： t s s 2 2 】( t u p l es p a c es e a r c h ) 和b r p s 2 3 ( b i n a r yr a n g e & p r e f i xs e a r c h ) 等。 该类算法的通j f j 性较好，支持各种形式的规则匹配，存储空间需求较小，并支 持增毓更新，算法在所有子规则集规模都较小的情况下能够获得较好的分类速 度，但算法的查找和更新性能受规则集特征的影响较大。 r f c 【l o 是目前除硬件方案之外分类速度较快的多维包分类算法，但其内存 消耗随规则集规模的增大而呈爆炸性增长，且更新规则集需要重建整个数据结 构，耗时儿个小时。t i c 2 4 】( t w o s t a g ei n t e r p r e t i n gb a s e dc l a s s i f i c a t i o n ) 结合 二二维r f c * l l f i l - 释器方法将分类查找分成两个阶段，极大地减少了内存消耗，并 保持了与r f c 基本相当的分类速度，数据结构重建时间平均减少8 0 ，但t i c 仍不支持增量更新。 目前，大多数的包分类算法主要关注提高分类速度和减小内存空间需求， 而不太重视更新性能，更新规则集的复杂度很大，有的甚至需要重建整个数据 结构。在支持增量更新的几种包分类算法中，e g t 【l8 、h i c u t s 【1 5 】和 h y p e r c u t s 1 6 1 是基于决策树的算法，树结点之间存在规则的冗余存储，更新涉 及多个结点，因而更新代价很高。b r p s 2 3 采用分层的范围和前缀扩展列表二 分查找方法，时空性能较前三者有较大提升，更新性能是目前多维包分类算法 中最好的，但每次更新仍需约1 0 万个时钟周期，这是因为b r p s 也存在规则的 冗余存储。递归空间分解 1 9 】( r e c u r s i v es p a c ed e c o m p o s i t i o n ) 是一种基于四 叉决策树的二维分类算法，不存在规则的冗余存储，更新只发生在一个树结点 中，更新性能非常好，但树路径过长，分类查找性能有待改进。 表1 1 给出了典型包分类算法的性能对比。其中r f c 的查找性能最好，因 为其访存次数少，但它的空间消耗非常大。两阶段的t i c 算法既保持了与r f c 相当的分类速度，其空间需求较r f c 也大大降低了，而使用了维度分解的算法 r f c 、b i t m a p r f c 和t i c 都不支持增量更新。前面五个基于决策树的算法和 b r p s 都支持增且t o 史新。 第l 章绪论 表1 1典犁包分类算法的性能比较 包分类算法查找复杂度空间复杂度分类维度更新类型更新复杂度 h i c u t s o ( d + l ) 0 ( ) 多维 增鼍 o ( n c o h y p e r c u t so ( 日+ )o c j ) 多维增鼍 o ( n d ) g r i d o f - t r i e s o ( d w )o ( n d w ) i ? 维 增镀o ( n 肌 e g t o ( d w + l )o ( n d w ) 多维增最o ( n w ) 递! j 1 卒i h j 分解 0 ( 口叨o ( 加 二维增最 0 ( 口刽) r f c o ( o ( 确 多维全局 b i t m a p r f co ( 奶o ( 帕 多维全局 t i c o ( 力o ( n 2 + 3 n w ) 多维全局 b r p s o ( a l o g h 0o ( 呐 多维增最 o ( n d ) 注：表t 1 ，址规则数最，是规则域： 长，d 是分类维度，l 是第二阶段待匹配规则 数黄。口是个川户，i j 凋参数。 1 6多核平台上的包分类研究 在多核处理器技术广泛应用的背景下，现有包分类算法已经做了一些多核 平台上的并行化研究工作，如b i t m a p r f c 2 l 】和t i c 2 4 等，都在多核平台上做 了高效的并行化实现。但这些工作只考虑了分类查找过程的并行化，还未讨论 规则集更新! j 查找同步进行的并行化问题。随着一些要求动态分类的新兴应用 的出现，动态分类需要频繁地更新规则集，规则集的实时更新问题亟待解决。 因此，在多核处理器平台上实现包分类算法面临新的困难，需要解决数据结构 的更新和硷找之间的同步问题，并且查找性能不能受到太大的影响。 然而，现仃支持增鼍更新的包分类算法，只是为在线实时更新提供了可能， 但这些算法鄙朱讨论更新和查找的并行同步实现问题。而更新涉及对分类数据 结构的修改，更新与查找的并行同步很难处理，处理不好就会对查找性能造成 较大影响。如果采用读写锁机制来同步更新和查找操作，更新会导致相关查找 的停顿。并且涮用读写锁原语会有较大的开销。因此，如何降低或消除更新和 查找之间的同步开销仍是研究难点，很值得深入研究。 1 7本文主要工作与内容安排 本文研究支持快速增量更新的多维数据包分类算法以及算法在多核处理器 上高效的实现。本文在保持t i c 算法两阶段分类的基础上，利用递归空间分解 第1 章绪论 实现t i c 的第阶段( 替换r f c ) 以支持增嚣更新，从而提高算法的更新性能， 然后通过路径压缩技术改进递归空间分解的查找性能，并通过数据结构的局部 重建替换方法和适当的内存管理，实现分类数据结构的实时更新和查找并行同 步进行，更新不会中断查找过程，从而获得一个支持快速增量更新的两阶段五 维包分类算法t i c s ( t w o s t a g ei n t e r p r e t i n g b a s e dc l a s s i f i c a t i o nw i t h s p a c e d e c o m p o s i t i o n ) ，并在i n t e l 多核平台上实现了t i c s 算法。仿真实验结果显示， t i c s 的更新速度比目前更新最快的b r p s 算法至少提升了一个数量级，且分类 速度具有很好的并行可扩放性，可以通过提高算法的并行度来提高分类速度。 本文剩余内容安排如下：第2 章介绍已有的包分类算法和相关技术基础； 第3 章详述t i c s 算法的设汁和优化，以及如何在多核平台上并行同步实现增 量更新和查找：第4 章给出算法在i n t e lx e o n 多核平台上的实验结果及分析： 第5 章总结全文，并指出未来的研究工作重点。 第2 章相灭研究工作与技术基础 第2 章相关研究工作与技术基础 近年来，有关包分类算法的研究成果很多 8 9 】 1 0 】 12 】【1 3 】 1 4 】 15 1 6 】 【1 7 1 【1 8 1 1 9 1 1 2 0 2 1 】【2 2 】【2 3 】 2 4 】【2 7 】【2 8 】【2 9 】 3 0 】 3 l 】 3 2 】【3 3 】 3 4 】 3 5 】 3 6 】，【2 5 2 6 】 对现仃的经典包分类算法作了详尽的介绍。本章主要介绍与本文工作相关的包 分类算法，以及在多核处理器平台上开展包分类研究的技术基础：规则集基准 c l a s s b e n c h 和多核平台上的多线程并行编程模型。 2 1 包分类算法 2 1 1r f c 算法 r f c 【1 0 ( 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 ) 是除硬件方案之外分类速度较快的 软件包分类算法。假设对包头中的d 个域进行分类，用s 表示由这d 个域所形 成的比特串的k 度，则该比特串的值应在 o ，2 s - 1 中，共有2 6 种情况。如果将每 种情况对应一个等价类( 用e q l d 表示) ，则分类问题可看成是根据包头中长为 s 的比特串来确定其对应e q l d 的问题。如果预先将2 5 个e q l d 计算好并存放于 一个线性表中，则在分类查找阶段使用数据包头中的比特串作为索引，通过一 次访存便可得出奁找结果。然而，在实际的多维包分类问题中，s 通常很大， 比如当d 为5 时s 为1 0 4 b i t ，需要约1 0 2 4 g b 内存，这显然是不现实的。 r f c 是一个典型的维度分解算法，其基本思想是将多维分类j u j 题转换为