（计算机软件与理论专业论文）快速包分类算法研究.pdf

摘要 摘要 包分类是下一代路由器、防火墙等设备的关键技术。包分类算法研究具有十分 重要的意义，是目前的热点之一。 本文介绍了常用的包分类算法，分析了它们的优缺点。从算法和体系两条主线 出发，对包分类问题进行研究。首先，针对多维包分类问题提出一种新的相联存 储器结构- m d r c a m ，支持多维范围匹配，其维数的设定具有灵活性。理论分 析表明，在该结构上实现包分类，算法时间复杂度为d ( 1 ) ，空间复杂度为d ( 聆) 。然 后，针对一个具体应用，提出一种动态多维硬件高速包分类算法。该算法采用决 策树作为快速查找的数据结构，每个叶结点存储一组规则，根据叶结点所处决策 树层次和最大查找时间要求来确定叶结点最大规则数，从而可界定最坏情况下的 分类时间；支持快速更新，借用一个限定长度的双向链表来更新决策树，可减少 临时空间；优化决策树并提出存储动态管理策略，适于在f p g a 上实现。仿真结果 表明，在5 0 m h z 的搜索频率下，该算法能够达到每秒处理2 5 m 个包头的速度，最 坏情况下的分类时间g 堋= 3 4 个时钟，空间复杂度为d ) 。 关键词：多维包分类内容可寻址存储器范围匹配决策树 优化 a b s t r a c t a b s t r a c t 3 一 p a c k e tc l a s s i f i c a t i o ni sak e y t e c h n o l o g yo fn e x tg e n e r a t i o nr o u t e r sa n df i r e w a l l s i t i so n eo ft h eh o t t e s tt o p i c s ，a n dr e s e a r c ho nt h ep r o b l e mi ss i g n i f i c a n t s e v e r a lr e p r e s e n t a t i v ec l a s s i f i c a t i o na l g o r i t h m sa r ei n t r o d u c e di n t h i sp a p e r ，w i t h d i s c u s s i n gw h i c ha p p l i c a t i o n st l l e ya r es u i t a b l ef o r r e s e a r c h e so nc l a s s i f i c a t i o na r e d o n eo nt w om a j o rt h r e a d s ，a l g o r i t h m i ca n da r c h i t e c t u r a l f i r s t l y , an e ws t r u c t u r eo f c o n t e n t a d d r e s s a b l em e m o r yi sp r e s e n t e d ，w h i c hs u p p o r t sm u l t i d i m e n s i o nr a n g em a t c h a n di sn a m e dm u l t i - - d i m e n s i o nr a n g ec a mw i t hm d r - c a mf o r s o r t , a n di t sp a r t i t i o no f d i m e n s i o n si sf l e x i b l e t h er e s u l t so ft h e o r e t i ca n a l y s i ss h o wt h a tt h ea l g o r i t h m sc a nb e d i r e c t l yi m p l e m e n t e do nm d r c a m s ，w i t ht h et i m ec o m p l e x i t y0 ( 1 ) a n ds p a c e c o m p l e x i t yd ( ，z ) t h e n ，ad y n a m i cm u l t i d i m e n s i o n a lh a r d w a r ea l g o r i t h mf o ran e t w o r k a p p l i c a t i o no nr o u t e r sw i t hs e v e r a la d v a n c e m e n t si sp r o p o s e d t h ea l g o r i t h mt a k e s d e c i s i o nt r e ew i t he a c hl e a fs t o r i n gas m a l lg r o u po fr u l e sa sd a t as t r u c t u r ef o rf a s t l o o k u p ，b o u n d st h ew o r s t c a s ec l a s s i f i c a t i o nt i m eb yc a l c u l a t i n gt h em a x i m u mn u m b e r o fr u l e si no n es m a l lg r o u pb yt h ed e p t ho ft h el e a fa n dt h em a x i m u ma v a i l a b l e c l a s s i f i c a t i o nt i m e ，s u p p o r t sq u i c ku p d a t ea n dr e d u c e st h eu s eo ft e m pm e m o r yb y e m p l o y i n gad o u b l el i n kw h o s el e n g t hi sr e s t r i c t e dt or e n e wt h ed e c i s i o nt r e e ，a n dc a l l b ei m p l e m e n t e do nf p g aw i t ht h eo p t i m i z a t i o no fd e c i s i o nt r e ea n das i m p l em e m o r y m a n a g e m e n ts t r a t e g y t h er e s u l t so fs i m u l a t i o ns h o wt h a tt h ea l g o r i t h mc a nc l a s s i f y a b o u t2 5m e g ap a c k e th e a d e r sp e rs e c o n do n5 0 m h zs e a r c hc l o c kw i t ht h ew o r s t c a s e c l a s s i f i c a t i o nt i m eg 姗= 3 4c l o c ka n dt h es p a c ec o m p l e x i t yd ( 疗) k e y w o r d ：m u l t i - d i m e n s i o np a c k e tc l a s s i f i c a t i o n c o n t e n t - a d d r e s s a b l em e m o r y r a n g em a t c h d e c i s i o nt r e e o p t i m i z a t i o n 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均己在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：盘查：磕 日期 矽d 多彩 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名：鱼量：壁 导师签名：日期2 d 酪2 2 分 第一章绪论 第一章绪论 1 1 引言 路由器的主要功能是将一个网络的数据包( p a c k e t ) 转发到另一个网络。传统路 由器根据数据包的目的地址对数据包进行转发，提供未加区分的尽力服务( b e s t e f f o r ts e r v i c e ) 。但是，随着因特网规模的不断扩大和应用技术的进步，越来越多 的业务需要对数据包进行快速有效的分类，因此路由器还需要对数据包进行进一 步的处理。最常见的是根据安全性需要，对包进行过滤，阻止有安全隐患的数据 包通过。因此，研究高速包分类算法具有十分重要的意义。 因特网是由许许多多的主机及连接这些主机的网络组成，主机间通过t c p i p 协议交换数据包。数据包从一个主机穿过网络到达另一个主机，其中就需要路由 器提供数据包转发服务。近年来，因特网己经从主要连接教育机构的低速网络迅 速成为重要的商业基础设施。现在，因特网正呈现两方面的新变化：一方面，因特 网上的用户正在呈现爆炸性增长，w e b 站点正在迅速增加，需要宽带网络的多媒 体应用正在日益普及，因特网的通信量也正在呈现爆炸性增长，因特网正日益变 得拥挤：另一方面，因特网上的用户正呈现许多不同的种类，从以浏览和下载资料 为主的普通家庭用户到经营电子商务的大型企业等等，这些用户从安全、性能、 可靠性方面对因特网的期望是不同的。人们希望路由器能够具有诸如数据包过滤、 区分服务、q o s 、多播、流量计费等额外功能。所有这些处理都需要路由器按某 些规则将数据包进行分类，分类后的数据构成许多“流，再对每一个流分别进 行处理。 对于网络流量的不断增长问题，由于光纤技术和d w d m 技术的发展使得链 路的速率不再成为瓶颈，已经满足了大流量传输的需求，这就使得路由器的处理 速度成为网络整体速度的一个瓶颈。这主要由于路由器需要对每个输入包执行许 多操作，包括十分复杂的分类操作。例如，它们需要对每个输入包执行最长前缀 匹配以发现其下一跳地址：需要对每个输入包执行多维包分类以便在执行缓冲器 管理、q o s 调度、防火墙、网络地址翻译、多播服务、虚拟专用网、速率限制、 流量计费等任务时区别对待不同的包。同时，由于无线网络、移动网络等的不断 发展，因特网上的设备越来越多。更多的设备就意味着需要更多的地址，也就是 说在路由器上需要更多的存储空间。因此，为了满足服务快速性和服务多样性这 两方面的需要，就必须研究相应的快速包分类算法以应用到实际路由器中。 2 一 快速包分类算法研究 1 2 包分类问题 数据包分类就是根据网络上传输的数据包的包头信息，将数据包按照一定规 则进行分类。在网络分层模型中，要传输的数据被各层协议的包头依次封装，每 层的包头都包含若干个域( 字段) ，它们分别表示该层协议的特征数据。一个分 类器( c l a s s i f i e r ，也称为规则集) ，含有条规则( r u l eo rf i l t e r ) ，规则r 如1 9 剑由 三部分组成：( 1 ) 与域( f i e l d ，又称字段或维) 有关的表达式r ， z 1 ，l i d ，d 为域数， 表达式一般是d 元组形式以；励，其中石是前缀( p r e f i x ) ，也可以是范围 ( r a n g e ) ，或者是一个精确值( v a l u e ) ；( 2 ) 优先级例，声明规则尺，在分类器中 的优先级；( 3 ) 处理动作a c t i o n ( r ) ，如果输入的数据包与规则r ，匹配，则根据 a c t i o n ( r ) 对数据包处理。一个输入包经过解析后得到一个关键字p ，p 为d 元组 仞i , p 2 , 枷，p f 是精确值，d 维包分类问题就是在分类器中找到与p 匹配的具有最 高优先级的规则尺妇( 最佳匹配) 。 以经典五元组规则( 目的地址，源地址，协议，目的端口，源端口) 为例，一 般i p 地址( 3 2 位) 为前缀( i p 地址采用c i d r 记法) ，端口( 1 6 位) 为范围，协议( 8 位) 为精确值。一条规则对应一个数据流，例如，规则r = ( 1 9 2 2 0 0 2 2 3 2 1 0 1 1 0 0 2 2 ，t e p ，2 3 ，3 ) ，它对应的数据流，由子网2 1 0 1 1 0 0 2 2 出发，协议为 t c p ，源端口为3 ，流向子网1 9 2 2 0 0 2 2 ，目的端口为2 3 。在进行数据包和过滤 规则的匹配时，根据字段( 域) 类型的不同，允许三种匹配方式：精确匹配，前缀匹 配和范围匹配。包分类过程如图1 1 ，包分类算法将左边输入的包与右边的分类规 则进行匹配，找到一个匹配的规则。当一个数据包与多条规则相匹配时，包分类 算法选出最佳匹配规则，将它作为匹配结果输出。 图1 1 包分类示意图 匹配结果 第一章绪论 1 3 包分类算法的评定标准 3 一 分类算法的评定标准主要有如下几种： ( 1 ) 速度快：物理链路线速日益增长，要求快速路由。例如，假设t c p i p 数据包最小为4 0 b y t e ，o c l 9 2 e ( 线速约为1 0 g b s ) 要求路由器的处理速度 达到3 1 2 5 m p p s ( m i l l i o np a c k e t sp e rs e c o n d ) 。通常要求算法在最坏情况下 仍表现良好。例如，分类速度应以线速进行，否则所有数据包需要排队缓 冲，这将导致路由转发延时难以控制，也不能提供有效的q o s ( q u a l i t i e so f s e r v i c e ) 。实际上，算法的平均表现对实际应用也是很重要的，一般平均 查找速度远高于最坏情况。例如，在一些应用中，对于o c l 9 2 c 链路，假 设平均数据包大小约3 5 4 b y t e ，算法的平均处理速度需要达到3 5 3 m p p s 。 ( 2 ) 易实现：搜索引擎可能用软件或硬件实现，这依赖于系统要求。因此， 一个分类算法，应既易于软件实现又利于硬件实现。为了达到最高的速度， 硬件实现往往是必须的，因此，算法应适于流水线实现。 ( 3 ) 占用内存小：通常期望算法在计算时采用的数据结构所占内存较小。 较小的内存需求可采用昂贵而快速的存储技术实现，例如s r a m s ( s y n c h r o n o u sr a n d o ma c c e s sm e m o r i e s ) 。一个内存有效的算法，如果软 件实现借助片上c a c h e 或硬件实现使用片上s r a m ，可大大提高查找速 度。 ( 4 ) 预处理时间少：预处理时间是算法建立初始数据结构所需时间。支持 增量更新的算法，其数据结构是动态的。对于静态算法，增加或删除一条 规则，整个数据结构需要重新计算。一般动态算法比静态算法更能接受较 大的预处理时间，其允许的时间大小随着应用而变。 ( 5 ) 快速更新：包分类问题中，不同的应用对更新速度的要求也大相径庭。 一般防火墙是规则的添加是手动的而且很少发生，对更新的速度要求很 低，然而，一个规则更新频繁的分类器对更新的速度往往要求很高。 1 4 本文的主要工作 ( 1 ) 第二章，首先介绍对真实规则集特征观测的结果；然后从包分类算法设计 所采用的高水平方法出发，将常见的包分类算法大致分成四类，并依次介绍这四 种方法，阐述其代表算法的优缺点；最后简单介绍一下高速缓冲技术。 ( 2 ) 针对t c a m 的存储效率低下，本文于第三章提出一种可设定各字段宽度 且支持多维范围匹配的m d r c a m 结构，从理论上证明了该结构能够支持灵活的 4 一 快速包分类算法研究 范围匹配运算，有待进一步研究开发。 ( 3 ) 第四章，从路由器中一个多维包分类问题特定需求出发，提出了一种适用 于该问题的算法。该算法采用决策树作为快速查找结构，能够界定最坏情况下的 查找时间；提供建树，添加，删除等操作，支持快速更新；借用一个限定长度的 双向链表来更新决策树，可减少临时空间；优化决策树并提出存储动态管理策略。 该算法能在保证分类速度的基础上大大节省存储空间和可编程器件硬件逻辑资 源，非常适用于对分类速度和硬件资源要求都比较高的应用。 ( 4 ) 用c 语言编程实现了改进算法，使用v e r i l o gh d l 完成了该算法在f p g a 上实现的电路描述。 ( 5 ) 对改进算法进行了软件测试验证和仿真。 第二章概述 第二章概述 2 1 规则集特征概述 为了更好地鉴别包分类算法，首先着眼于真实规则集的特征。在常见多维查 找问题的下届已经被确定的情况下，近来对规则集特征的观测为提高分类算法的 平均性能提供了新的可能性。 g u p t a 和m c k e o w n 颁布了一系列关于真实规则集特征的观测结果，已被广泛 地引用f 。其他学者也对真实规则集合进行了分析，并颁布了他们的结果 8 砧5 矧。 下列是真实规则集的若干规律： ( 1 ) 目前的规则集规则数目一般较小，从几十条到几千不等，一般不超过 5 0 0 0 条。如果不清楚规则集的规则数目极限，将会导致限制算法性能或 增加解决问题的代价。 ( 2 ) 协议域的值域很小。在大多数规则集中，t c p 、u d p 和w i l d c a r d 是协 议类型最常见的取值，其他的取值包括i c m p 、i g m p 、( e ) i g r p 、g r e 和i p i n i p 。 ( 3 ) 运输层的取值十分广泛。一般端口用范围表示，例如“g t1 0 2 3 ”( g r e a t e r t h a n1 0 2 3 ) ，这意味着把范围转化成前缀的效率将会十分低下。 ( 4 ) 与输入包相匹配的规则个数一般是5 或更小。 ( 5 ) 不同的规则之间往往有一些值相同的字段。 这些特征的出现是由于管理策略驱使着规则的构成。以如下规则构成模型为 例，管理程序首先指定通信主机或子网( 一对地址前缀，源地址和目的地址) ，然 后指明应用( 运输层说明) 。管理程序必须使用策略确保同一个应用的地址对不重 复，从而，产生的若干有相同运输层说明的规则。同样，对于同一个地址对，管 理程序也可能使用若干不同策略，这将产生具有相同地址对的若干规则。一般地， 观测结果表明查找的中间结果源于各字段独立查找和字段之间的组合。根据这一 观测结果，提出了一个网络处理器包分类问题的方法f n 】。 2 2 算法分类法 应包分类问题巨大的需求，众多的算法和体系结构已被提出。d a v i de t a y l o r 提出了一种分类法( 仫o n o m y ) 18 1 ，根据所采用的高水平方法( h i 曲1 e v e la p p r o a c h ) 将算法设计空间划分成四部分，而并非根据算法的性能。将包分类算法显著的特 5 一 6 一 快速包分类算法研究 征和性质归结为高水平方法，这种分类法是十分有用的，我们可以利用下列四种 高水平方法之一或其组合来设计和改进包分类算法。 ( 1 ) 穷尽查找( e x h a u s t i v es e a r c h ) ：检查规则集中所有规则。 ( 2 ) 决策树( d e c i s i o nt r e e ) ：根据规则集构造一棵决策树，让输入包穿越决 策树。 ( 3 ) 分解( d e c o m p o s i t i o n ) ：把多维查找分解为各维独立查找，然后合并各 维结果。 ( 4 ) 元组空间( t u p l es p a c e ) ：根据规则指定的位将规则集分区，在各区及 其子集上精确查找。 该分类法如图2 1 所示。若干包分类算法，包括几个最有前途的，采用了多种 方法。图2 1 中，相关的算法其椭圆邻接，混合的算法覆盖分界线，种子算法用 ”标示。 图2 1 多维包分类查找技术分类法 2 3 穷尽查找 查找问题最基本而简单的解决方法是在所有规则中进行查找。讨论这种方法 的意义在于，假设规则集已被分成许多子集，每个子集的独立查找往往可以选择 该方法。穷尽查找法中具体两个最常见的算法是线性查找和大规模并行查找。二 者恰好代表穷尽查找法的两种极端，线性查找对规则集不进行分割，其性能最低， 而t c a m ( t e r n a r yc o n t e n ta d d r e s sm e m o r y ) 将规则集划分成每个子集只有一条 规则，其性能最高。本节将详细讨论这两种算法，不直接讨论每个子集中包含多 条规则的中间选择。 第二章概述 一般根据并行程度的线性比例来计算穷尽查找法的资源需求，同样实际吞吐 率亦与并行程度成比例。在计算时，线性查找需要资源最少而t c a m 需要最多。 一旦规则集确定，穷尽查找法具有最理想的空间性能，空间复杂度为d ，其中 为规则数目。 根据上一节所述规则集的第五条特征，可以利用编码技术来减少冗余，从而 减少规则集所占存储空间。设规则以劫的第i 字段彳有b i 位，可得条规则 的集合所占内存大小用公式表示为： d b i ( 2 1 ) - 一 、， 现在，设r 1 , , 2 , u a 分别代表各个域独一无二值的个数。通过有效的编码，理 想情况下，所有唯一字段值所占存储可以从线性级降低到对数级。图2 2 的例子 中，8 条规则都是唯一的，然而每个字段只有两个唯值，这些字段值只须存储 一次亦可将所有规则表示清楚。如图2 2 所示，为每个唯一的字段值贴上标签， 则第f 域只需钗“f ) 位，所有规则都可以用字段值对应的标签表示。使用该编码技 术，存储需求公式变为： ( 包) + k 嘶 ( 2 - 2 ) 该式第一项代表所有唯一字段值所占空向，第二项代表所有规则经过编码后 所占空间。将公式( 2 1 ) 和公式( 2 2 ) 相比可以得到存储节约因子，为了简单，假设 对于任意f 有b f b 且u f u ，该因子用公式表示： n b ( u b + n l g u ) ( 2 3 ) 为了让存储节约因子大于1 ，下列关系式必须成立： u n + l g u b l ( 2 - 4 ) 由于 q 6 且“列必成立，该因子随规则数目和规则极限规模( 2 t h e n u m b e r o f b i 捃o f 删如) 相对唯一字段值数目的增大而增大。 s a d 爿p r o t l l + o o l 幸t c p 1 l 0 0 l u d p l l l o l t c p l l l o l u d p 1 1 1 0 0 1 0t c p 1 1 1 o o l 哪 1 1 l o1 0 l t c p 1 l l 1 0 l 宰u d p 胡胡商 图2 2 对唯一字段值编码以减少存储的例子 ) q l t e r s ( n ，a ，口) ( a x t 。6 ) t a 。b 。口) ( 口，b 。6 ) ( 6 ，乜，口) ( 6 a b ) ( 6 ，6 算) ( 6 6 。6 ) 快速包分类算法研究 2 3 1 线性查找 线性查找的空间复杂度是d ，时间复杂度也是d 。若把查找过程分为 若干小步，并采用流水线技术，可以将平均查找时间降低一个常数因子，令k 代 表流水线的阶段个数，平均查找时间变为o ( n k ) ，但是计算所需资源也将增加k 倍。线性查找相对较慢，但是，当根据其它算法将所有可能与输入包相匹配的规 则数目已经缩小到一个常数后【2 2 6 9 1 ，往往将线性查找作为查找的最后阶段。 2 3 2t c a m 作为一种全相联存储器( f u l l a s s o c i a t i v ec a c h em e m o r y ) t c a m ( t e r n a r y c o n t e n ta d d r e s sm e m o r y ) 设备可以在所有规则中执行全并行查找【刀。t c a m 不 但能存储“0 、“1 ”状态，而且能够存储“杪( d o n tc a r e ) 状态。输入关键字与 每个存放在t c a m 中的规则相比较，因此对于任意位掩码匹配( a r b i t r a r yb i tm a s k m a t e h ) 能够保证一个时钟完成查找。t c a m 有以下几个主要的缺点：( 1 ) 成本高： ( 2 ) 存储利用率低；( 3 ) 功耗高；( 4 ) 输入关键字较长时缺乏灵活些。目前，t c a m 的价格大约是普遍d d rs r a m 的3 0 倍，将来t c a m 的价格会下降，但是它们 不大可能像s r a m 和d r a m 那样应用广泛。 导致t c a m 规则存储利用率低的原因有两个。第一，范围需要转化成前缀。 最坏情况下，一个w 位的范围，例如一个端口，需要2 ( w 1 ) 个前缀。如果一个规 则包含两个端口范围，则该规则最坏情况下会转化成2 ( w 1 y 2 条规则。文酬1 8 1 中， 根据1 2 个真实规则集转化成前缀而计算得到的膨胀因子( e x p a n s i o nf a c t o r ) ，平均 为2 3 2 ，一般最小1 0 ，最大6 2 。这意味着设计者应至少为每条规则准备7 个存 储条目( e n t r y ) 。第二，存储第三状态“ 需要额外的硬件资源。存储一位二进制 数需要6 个晶体管( t r a n s i s t o r ) ，一个标准t c a m 单元还需要额外的6 个晶体管以 存储掩码位，并且匹配逻辑需要4 个晶体管，因此一个标准t c a m 单元共需要 1 6 个晶体管，约是一个标准s r a m 单元【7 】的2 7 倍。根据表2 1 对状态值的编码， 图2 3 显示了一个标准t c a m 单元的电路图。也有一些已申请专利的t c a m 单 元结构只需1 4 个晶体管【5 】【6 1 。 表2 1 使用两个寄存器a l 和a 2 对存储状态值( o ，1 ，d o n tc a r e ) 编码 状态值 a la 2 d 0 1 1 tc a r eo0 101 01o 未定义 1 1 第二章概述 m 口t c hl i n e v r r t ea r a b 如 一 t 一：奇：一 i o 譬配 图2 3 标准t c a m 单元 t c a m 结构具有大规模并行的性质，这是其功耗高的根源。每个匹配逻辑单 元必须驱动匹配结果的一根线( 一位) 。额外的逻辑和电容负载导致其访问时间大 约是s r a m 的3 倍【1 9 】。此外，每位存储的功耗正常情况下是3 m w ( 微瓦特) 【2 0 】， 而s i a m 的一位存储功耗是2 0 3 0 n w ( 纳瓦特) 。总之，每位t c t u m 的功耗约是 s p m 的1 5 0 倍。 s p i t z n a g e l 、t a y l o r 和t u r n e r 近来提出了e t c a m ( e x t e n d e dt c a m ) ，在硬件 上直接实现范围匹配，比标准t c a m 节约9 0 的功耗【1 0 】。e t c a m 是以硬件体 系结构为研究线索的典型代表，将在以后章节中详加讨论。 2 4 决策树 多维包分类另一种比较流行的解决方法是构造一个决策树，其叶结点包含一 条规则或一个规则子集。为了使用决策树执行一次查找，首先从输入包的包头解 析得到一个查找关键字。根据关键字的一位或若干位在每个内部结点选择分支， 以横穿决策树，直到一个叶结点，其存储了最佳规则或一个规则子集。决策树的 构造过程复杂，因为事实上规则可能包含几个不同的查找类型( 匹配类型) 。最长 前缀匹配、范围匹配和精确匹配的混合使决策树分支决策更加复杂化。该问题的 一般解决方法是将规则所有域转化成一种类型的匹配。有几种方法将所有字段转 化成带任意掩码的位向量( b i tv e c t o r sw i t h a r b i t r a r yb i tm a s k s ) ，例如位向量可能是 1 、0 或幸( d o n tc a r e ) 。然而，规则中的范围不易映射成任意位掩码，因此，该 转化过程会导致规则的复制。同样，通配符( w i l d c a r d ) 的使用会导致一条规则 被存储在多个叶结点中( 规则的复制) 。 为了更好地阐述这个问题，本文提供了一个简单的决策树结构的例子，见图 2 4 。图2 1 ( a ) 例示的规则集中包含5 条规则，每条规则由3 个字段构成：3 位的 地址前缀、可转化成3 位任意位掩码的范围、以及2 位精确值或通配符。首先将 所有字段转化成位向量，规则由5 条变成了8 条。图2 1 ( b ) 以深度优先方式构造 9 一 1 0 快速包分类算法研究 决策树，决策树的分支不断膨胀，直到决策树的结点只包含一条规则或用尽所有 的位向量。如果规则之间存在相互交叠的关系，叶结点上可能包含多条规则。考 虑到决策树的规模，图中只画出了一部分。该数据结构的效率并不高，需要引入 一些优化方法。 1 0 【0 ：2 】 o l o 宰 【3 ：7 】 0 1 1 1 l 【0 ：7 】 1 1 _ 【o ：2 】 1 0 簟 【0 ：7 】 1 0 转化成位向量 a 1 0 0 0 0 1 b1 0 0 1 0 0 1 co o l l0 l d0 幸 1 0 1 e1 1 1 宰 f1 1 幸0 0 1 0 g 1 1 0 l o1 0 h1 1 摩0 1 01 0 图2 4 ( a ) 规贝og a3 个字段构成，首先把所有字段被转化成任意位掩码 图2 4 一个简单的决策树结构 第二章概述 有几种使用了决策树方法的包分类算法被称为“切割( c u t t i n g ) 算法。这些 算法将d 个字段的规则视为d 维空间中的一个d 维矩形，而多维空间的一次“切 割”等同于一个决策树的分支。切割算法的分支决策比在位向量中检查一位更为 复杂。e t c a m 算法中也使用了切割算法的变种，但包含不同部分规则集的几个 决策树之间的是并行查找的。因此，本文只将切割算法视作放松了约束的决策树。 由于决策树方法有很多自由度，不同算法的表现和资源需求很不相同。一般， 查找时间复杂度为d ( 聊，其中形是规则的位数。标准五元组( s t a n d a r d5 - m p l e ) 至 少1 0 4 位，可行的方法是必须使用一些优化方法以提高吞吐能力。对于简单的决 策树结构，内存复杂度是o ( 2 w + 1 ) 。一般，内存需求依赖于分支决策所使用的数据 结构。基于决策树的分类算法的共同特征是依赖于内存访问。换句话说，决策树 查找是顺序的，找到一条匹配规则必须从根结点出发走到叶结点。决策树的该性 质排除了其完全并行实现的可能性。如果一个算法能够界定决策树的高度，然后 采用流水线结构实现，仍然可以得到高吞吐率，但每个阶段需要独立的内存访问 接口。 2 4 1g r i d o f - t r i e s 文献【3 j 介绍了种子算法g r i d o f - t r i e s 和c r o s s p r o d u e t i n g 算法。这节主要介绍 g r i d o f - t r i e s 算法，应用决策树方法解决关于源地址和目的地址前缀对的包分类 问题。对于根据地址前缀定义的规则，该算法在有向非循环图( d i r e c t e da c y c l i c 研a p h ) 技术【l2 】的基础上做了改进。有向非循环图技术也被引用到s e t p r u n i n gt r e e s 算法，因为冗余的子树可以通过增加结点之间的边剪除。然而，这种优化只能消 除多余的子树，不能彻底消除规则的复制。g r i d o f - t r i e s 算法采用了以下优化方 法，把一条规则只存储一个结点中，然后用转换指针( s w i t c hp o i n t e r ) 指向潜在可 能匹配的规则或子集，可消除规则的复制。 图2 5 根据表2 2 中的规则例示了s e tp r u n i n gt r e e s 和g r i d o f - t r i e s 的不同之处。 该例只根据规则中的两个字段目的地址和源地址进行分类。假设当前输入包的目 的地址和源地址都等于0 0 11 ，正在为之查找最佳匹配。在g r i d o f - t r i e s 算法的数 据结构中，找到最长目的地址前缀为0 0 ，并且跟随指针到达源地址树，由于该 树根结点没有0 分支，跟随转换指针( 图中绿色箭头) 到达目的地址树o 木对应的 源地址树，该树无0 0 分支，跟随转换指针到达目的地址宰对应的源地址树0 0 结 点，找到规则r 7 ，即为输入包的最佳匹配。 g r i d o f - t r i e s 算法界定空间复杂度为0 ( 聊，时间复杂度为d ( 功，其中是 规则数目，形是用于说明源地址或目的地址的最大位数。对于p v 4 版本的源地址 和目的地址前缀查找，比较好的解决方法是使用多叉t r i e s 。构造目的地址t i l e 1 2 快速包分类算法研究 每层取8 位，而构造每个源地址t r i o ，第一层取1 2 位，第二层取5 位。 表2 2 规则集举例，端口号为精确值或通配符 r u l ed a s a d ps pp r ( f i l t e r )( 目的地址)( 源地址) ( 目的端口) ( 源端口)( 协议类型) r 1o 幸1 0 t 8 0t c p i 也o 0 1 8 0t c p i b0 宰1 1 71 7u d p r 40 0 1 r 50 0 1 1 事 蠢t t c p r 61 0 幸1 幸 1 7 1 7u d p r 7 0 0 奉 章 r 8o 木1 0 木 1 0 0t c p r 90 幸1 球 1 7 4 4 u d p r 1 0 0 1 0 簟8 0 木 t c p r 1111 1 0 0 0 幸 4 4 u d p s e tp r u n i n g r 7 r 2r 1r 5 r 8 r 1 0 图2 5 根据表2 2 计算所得s e tp r u n i n gt r e e s 和g r i d o f - t r i e s 第二章概述 2 4 2e g t e g t ( e x t e n d e dg r i d 。o f - t r i e s ) 算法，对g r i d o f - t r i e s 的数据结构稍加改进，支持 多域查找f 8 】。e g t 本质上将转换指针( s w i t c hp o i n t e r ) 改变为跳转指针0 u m p p o i n t e r ) ，直接指向所有可能匹配的规则而不仅是与最长匹配对应的规则。如图2 6 所示，一开始e g t 根据表2 2 中规则的地址对构造标准的g r i d o f - t r i e s 。源地址树 的结点中存储的并不是规则，而是指向一个规则列表( 一个规则子集) 的指针， 该列表中规则仍包含除地址对外其它字段的信息。该算法的提出者认为，对于经 典的核心路由器( c o r er o u t e r ) 规则集，最后的列表很小，因此可以在该列表中 选择线性查找。而源地址t i l e 之间的跳转指针( 图中绿色箭头) 指向所有可能匹 配的规则。 图2 6e g t 数据结构图，根据表2 。2 e g t 算法，在最坏情况下访问内存次数是d ( 沪) ，其中形是地址长度。仿真 结果表明，对于核心路由器上8 0 - 2 7 9 9 条规则，e g t 平均每次查找需要访问内存 次数为8 4 1 3 7 。对于5 k 1 0 k 条模拟规则，仿真表明，平均每次查找访问内存次 数为1 2 1 - - - 2 1 3 ，平均每条规则的内存需求为3 3 字节到5 7 字节【1 8 】。 2 4 3h i c u t 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 ) 算法【2 1 由学者g u p m 和m c k c o w n 提 出，切割( c u t t i n g ) 的概念来源于从几何学角度观察包分类问题。该算法适于范 围类型的规则，将其它字段统一转化成范围。h i c u t s 采用了一棵决策树作为快速 1 4 快速包分类算法研究 查找的数据结构，其内部结点包含适当的分类导向信息，但不存储任何规则，其 叶结点( 或外部结点) 存储一个小型的规则子集。当收到一个输入包，该分类算 法横穿决策树，直到一个叶结点。然后在这个子集中进行线性查找，直至找到最 佳匹配。在构造决策树时，限定其所有叶结点上存储的规则数目小于一个常数， 该常数称为b i n t h ( f o r b i n t h r e s h o l d ) 。决策树的外形特征，例如高度( d e p t h ) 、 每个结点的度等，在预处理时根据规则集的特征决定。 表2 3 二维规则集例子，每个字段都是8 位范围 r u l e x - r a n g ey - r a n g e r 10 3 1 0 2 5 5 i 也0 2 5 51 2 8 1 3 1 r 36 4 7 11 2 8 2 5 5 r 46 7 6 70 1 2 7 r 56 4 7 1o 1 5 r 61 2 8 1 9 14 1 3 1 r 71 9 2 1 9 2o - 2 5 5 表2 3 例示了一个简单的规则集，其共有7 条规则，每条规则有2 个8 位范围 字段。从几何学的角度出发，其切割如图2 7 所示。根据二维空间中的递归分区， 并限定b i n t h = 2 ，构造的决策树如图2 8 所示。该树的根结点代表完整的二维空间， 其大小为2 8 2 8 。h i c u t s 算法x 维将完整空间等分为四，根结点的四个子结点代 表这四个子空间。这四个结点，除a 结点，包含的规则数目不大于b i n t h ，因此， 算法继续对a 结点进行分割。a 结点空间大小为2 6 2 8 ，根据】，维将此子空间再 进行二分，产生两个子结点，每个结点包含两条规则。由于所有叶结点包含的规 则数目不大于b i n t h ，决策树的构造过程结束。 ； 三 i 荔 磊 ，加i 鼬 j罐 臻 羹 ii 缓 ；晶魏驻翻荔麓黝 缓猫嘲绷强鞠掰黝 r 6 ， i r 4 笔i 二 睡 l 爹篱 i 澄e 曩一r 5 o 图2 7 二维空间切割图，根据表2 3 规则 概括地描述d 维h i c u t s 算法如下。每个内部结点v ，代表几何查找空间的一 5 l_ii r 攒姒t y 第二章概述 个分区。例如根结点代表完整的d 维空间，根据其中一维可将1 ，结点空间分割成 更小子空间，每个子空间为v 结点的每个子结点所表示。子空间被递归地分割直 至每个空间包含的规则数目不大于参数b i n t h ，此时给叶结点分派规则。公式化描 述内部结点v 如下： ( 1 ) 一个超矩形( h y p e r - r e c t a n g l e ) b ( v ) ，是一个范围类型的d 元组 ( 【z l ， l 】，【如，蝴，【t d , h a ) 。该矩形定义了一个子空间，存储于，结点。 ( 2 ) 一次切割c ( d ，包含两个实体。意= 疣m ( q d ) ，切割空间b ( v ) 所依据 的维的编号。印( c ( v ) ) ，空间曰( 们被分成的份数，等于内部结点v 的孩 子结点个数。 ( 3 ) 所包含的规则子集c r s ( v ) ，如果v 是内部结点w 的子结点，则c r 双 是c r s ( w ) 的一个子集。每个c r s ( w ) 中的规则，如果跨入( 或被切入) 空 间曰( 们，也即成为c r s ( v ) 中的一员。c r s ( r o o t ) 是包含所有规则的集合。 c r s ( v ) 的规则数目记作n u m r u l e s ( v ) 。 图2 8 一个可能的h i c u t s 树，b i n t h = 2 。图中椭圆代表内部结点，存储一个三元 组陋( 功，d i m ( c ( v ) ) ，印( c ( 力) ) 。正方形表示叶结点，包含一个规则子集。 以二维矿位为例，根结点代表完整空间2 w 2 ，超平面切割轴在二维中是简 单的直线。如果对空间的b 切割被描述成对二维平面的等分，并假设某内部结点 根据第一维切割产生了j d 份区间( i n t e r v a l ) ，该结点则有d 个子结点，每个子空 间大小为( 2 w d ) 2 。 然而，为一个规则集构造一棵决策树有许多方法。在预处理阶段，h i c u t s 算 法在几个启发公式引导下，在限定可用内存的情况下最小化决策树的高度，从而 能够构造出一棵比较合理的决策树。 h i c u t s 是一个表现杰出的动态软件算法。在最坏情况下的查找时间可用公式 表示为t ( d e p t h ) + t ( b