（计算机系统结构专业论文）基于位向量的流分类算法研究.pdf

基于位向量的流分类算法研究 摘要 随着网络技术的发展和应用范围的扩大，人们越来越依赖于网络进行信息 的处理。为了提高信息检测的处理速率，适应网络的高速发展，流分类技术应 运而生，成为路由器、防火墙等网络设备的关键技术之一。 本文阐述了流分类技术的研究现状，介绍了经典流分类算法，分析了各个 算法的主要思想和优缺点，重点研究了a b v 算法，针对该算法在多维、大规 模规则库的情况下，内存占用空间过大的问题，提出了改进的流分类算法。改 进算法采用交叉存储b v 位图与聚合位图的策略，保证了规则与位图的对应关 系，减少b v 位图中连续“o 串的存储，有效的降低了算法的空间消耗。 在l i n u xn e t f i l t e r 架构下，设计并实现了基于改进算法的流分类器，并对改 进流分类算法的性能进行了测试分析。试验结果表明，与a b v 算法相比，改 进算法具有良好的时空性能，适用于多维大规模规则库的环境。 关键词：流分类，a b v ，位图，交叉存储，n e t f i l t e r t her e s e a r c ho ff l o wc l a s s i f i c a t i o na l g o r i t h m b a s e do nb i tv e c t o r a b s t r a c t w i t ht h ed e v e l o p m e n ta n da p p l i c a t i o no fn e t w o r kt e c h n o l og y ，p e o p l e i n c r e a s i n g l yd e p e n do nn e t w o r kt op r o c e s si n f o r m a t i o n t h e f l o wc l a s s i f i c a t i o n e m e r g e sa so n eo fk e yt e c h n o l o g i e sf o rn e t w o r kd e v i c e ss u c ha sr o u t e ra n df i r e w a l l i no r d e rt o i m p r o v et h er a t eo fd e a l i n g w i t hi n f o r m a t i o na n da d a p tt ot h e d e v e l o p m e n to fn e t w o r k t h i sd i s s e r t a t i o nd e s c r i b e st h ec u r r e n tr e s e a r c h e ds t a t u so f f l o wc l a s s i f i c a t i o n ， i n t r o d u c e st h em a i ni d e a so fc l a s s i c a la l g o r i t h m sa n da n a l y z e st h e i rr e l a t i v em e r i t s t h et h e s i ss t u d i e sa b va l g o r i t h mm a i n l y ，a n dp r e s e n t sa ne n h a n c e da l g o r i t h mt o r e s o l v et h ep r o b l e mo fs p e n d i n go ns p a c ei nt h ee n v i r o n m e n to fm u l t i d i m e n s i o n a l a n dl a r g e s c a l er u l e sd a t a b a s e t h ei m p r o v e da l g o r i t h me n s u r e st h ec o r r e s p o n d i n g r e l a t i v eb e t w e e nr u l e sa n db i t m a pa n dr e d u c e st h ec o m p l e x i t yo ft h es t o r a g eb y i n t e r s e c t i n gs t o r a g ew i t ha g g r e g a t e db i t m a pa n db vb i t m a pa n dn e g l e c t i n gt h e s e r i a t ep a r to fz e r oi nb vb i t m a p t h ed i s s e r t a t i o nd e s i g n sa n di m p l e m e n t saf l o wc l a s s i f i c a t i o nb a s e do nt h e i m p r o v e da l g o r i t h mi nt h ef r a m e w o r ko fl i n u xn e t f i l t e r ，a n dt e s t st h ep e r f o r m a n c e o ft h ei m p r o v e da l g o r i t h m t h er e s u l t si n d i c a t et h a tt h ee n h a n c e da l g o r i t h mh a s g o o de f f i c i e n c y o ft i m ea n d s p a c ec o m p a r e d w i t ha b va l g o r i t h mi na m u l t i d i m e n s i o n a la n dl a r g e s c a l er u l e sd a t a b a s e k e y w o r d s ：f l o wc l a s s i f i c a t i o n ；a b v ；b i t m a p ；i n t e r s e c t i n gs t o r a g e ；n e t f i l t e r 插图清单 图2 1 流分类器的结构3 图3 1h i e r a r c h i c a lt r i e 算法查找示意图一7 图3 2s e t p r u n i n gt r i e 算法查找示意8 图3 3g r i d o f - t r i e s 算法查找示意图一8 图3 4b v 算法示意图1 l 图3 5h i c u t s 算法示意图1 2 图3 6r f c 算法流程1 3 图3 7t c a m 分类方案1 3 图4 1f i e l d l 字段的t r i e 树1 6 图4 2f i e l d l 和f i e l d 2 的t r i e 树1 7 图4 - 3 改进算法的预处理2 0 图4 42 5 6 叉t r i e 树2 0 图4 5 源端口值域坐标轴及区间位图2 1 图5 1n e t f i l t e r 在l i n u x 内核结构中的位置2 4 图5 2n e t f i l t e r 的工作流程2 5 图5 3 节点中的块结构2 7 图5 4i p 地址预处理成2 5 6 叉t r i e 树的流程图一2 8 图5 5i p 地址的2 5 6 叉t r i e 树节点与交叉位图的映射2 9 图5 6 链表节点中的结构2 9 图5 7 链表节点中的结构2 9 图5 8 端口值映射到坐标轴上的区间分割3 0 图5 9 端口值区间与交叉位图的映射31 图5 1 0 协议号与交叉位图的映射3 2 图5 11 数据包在规则库中查找匹配流程3 3 图5 1 2 测试平台示意图3 4 图5 13 算法的位图空间消耗一3 5 图5 1 4 算法的平均分类时间一3 5 表格清单 表2 1 五维分类规则集4 表3 1 规则集6 表3 2 规则集对应的元组9 表3 3 元组空间与规则对应关系一1 0 表3 4 算法比较14 表4 1 二元组规则库示例1 5 表5 1 钩子函数2 5 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得 金b 里王、业态堂 或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论支作者签字：嚼狐匆 签字日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解 金g 曼王些太堂 有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被 查阅或借阅。本人授权 金目曼王些太堂 可以将学位论文的全部或部分论文内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇 编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：调级忽 签字同期： 年月同 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 签字同期： 电话： 邮编： 致谢 历时两年半的研究生学习生涯即将过去，在这段日子里，留下了我们美好 的回忆。值此论文完成之际，对曾经帮助和关心过我的老师和同学们致以衷心 的感谢。 首先，衷心的感谢我的导师侯整风教授。侯老师渊博的知识、严谨求实的 态度以及不断进取、精益求精的精神，严谨的治学态度和诲人不倦的师长风范， 是我今后的学习、工作的榜样。在研究生学习期间，侯老师对我思想上、学习 工作上的循循善诱和谆谆教诲，以及生活上的关怀和照顾，使我终身受益。在 侯老师的指导下，我顺利完成了论文的研究和撰写，在此，再一次对恩师致以 崇高的敬意和衷心的感谢! 其次，感谢网络与信息安全实验室的同学。在研究生学习和撰写论文期间， 我们经常就学术问题进行交流和探讨，大家给予了我很大的帮助，在此一并致 谢。 最后，更要感谢我的家人，他们的无私的关爱是我完成此论文的前提，也 是我未来前进的动力。 衷心的感谢所有关心和帮助过我的人们! 作者：胡茂福 2 0 10 年0 4 月 第一章绪论 1 1 研究背景 随着i n t e r n e t 应用的迅猛发展，网络用户数急剧膨胀，应用的类型越来越 丰富。这对网络的带宽、提供服务的能力提出了巨大的挑战。网络流量的高速 增长，对网络实时数据检测提出了更高的要求。如何提高信息检测的处理速率、 适应网络的高速发展成为一个亟待解决的问题。 流分类技术将数据包按过滤规则分类成特定的数据流。流分类技术不仅应 用于防火墙【1 1 、统一威胁管理系统l 2 】【3 】等网络安全领域，区分和过滤非法数据流， 而且还应用于q o s 、流量计费、s l a 等网络服务，对不同的业务要求进行分类 和调度，为用户提供不同级别的服务。 总之，流分类技术是路由器、防火墙等网络设备的关键技术之一，也是 q o s 、流量计费等网络扩展业务进一步发展的基础。流分类问题的研究有助于 扩展网络的应用领域，为i n t e r n e t 用户提供更加完善的服务。 1 2 研究现状 自9 0 年代中期流分类问题被提出以来，流分类算法的研究取得了很大的 进展。目前已经出现了多种不同类型的流分类算法。早期的研究主要集中于包 含源目的i p 地址的二维分类，主要算法都是由路由查找算法扩展而来，包括 a q t 算法( a r e a - b a s e dq u a d t r e e ) 4 1 、f i s 树( f a ti n v e r t e ds e g m e n tt r e e ) 算法【5 1 和 g r i d o f - t r i e s 算法【6 1 等。 随后，研究人员从不同的角度对多维流分类问题进行了研究，提出了一些 高效的流分类算法，如空间查找算法【7 】、c r o s s p r o d u c t i n g 算法【8 1 、元组d a g 算法i9 1 、递归流分类( 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 0 】和基于查找空间分割 的h i c u t s 算法】等。此外，随着路由器转发速率的提高，出现了基于硬件的流 分类方案。常见的硬件方案使用t c a m 存储器【1 2 1 【l3 1 ，分类时间短，但存储器 价格昂贵，不直接支持范围匹配，且处理的分类规则数有限。 1 9 9 8 年，t v l a k e s h m a n 和d s t i l i a d i s 提出位并行算法【l4 1 。它是一种高效 快速的流分类算法，主要解决多维范围匹配的问题，能够对数据包进行线性处 理，但随着分类规则数量的增加，该算法的空间和时间性能将会随之降低。位 向量( b v ，b i tv e c t o r ) 算法【1 4 】通过引入t r i e 树【1 5 】结构，适用于多维前缀匹配和多 维范围匹配，但随着规则库规模的增大，算法的时间和空间复杂度大大增加。 随后，f l o r i nb a b o e s c u 和g e o r g ev a r g h e s e 基于b v 算法提出了聚合位向量( a b v ， a g g r e g a t eb i tv e c t o r ) 算法i l 引。a b v 算法通过位图聚合方式，改善了b v 算法在 平均情况下的执行时间，使其具有更好的扩展性；但算法极大的空间开销并未 得到改善。麻省理工学院( m i t ) 的l ij i 和l i uh a i y a n g 提出位向量折叠思想【1 7 】， 并应用到位向量折叠( a f b v ) 算法中，减少了算法的空间占用，但算法中的 冗余计算降低了时间效率。 目前，流分类研究主要集中在多维、大规模规则库下如何提高流分类的效 率。一些学者针对具体应用中分类规则库的特点，提出了启发式算法。此外， 规则动态更新、规则冲突检测等问题也是流分类技术的研究热点。 1 3 本文主要工作 ( 1 ) 本文阐述了流分类技术的研究背景和现状，介绍了流分类中的相关 问题，分析了经典流分类算法的基本思想和优缺点。 ( 2 ) 重点研究了a b v 算法，针对该算法在多维域、大规模规则库应用环 境下存储空间消耗过大的问题，提出了改进的流分类算法。改进算法综合考虑 了时间和空间性能，采用交叉存储b v 位图和聚合位图的策略，保证了位图与规 则的对应关系，保持与a b v 算法相同的时间性能，忽略b v 位图中连续出现的0 串，提高了算法的空间性能，克服a b v 算法在上述应用环境中的不足。 ( 3 ) 在l i n u xn e t f i l t e r 架构1 1 8 l i l 9 l 下，设计并实现了基于改进算法的流分 类器，并对改进流分类算法的性能进行了测试分析。 1 4 章节安排 论文的内容安排如下： 第一章绪论。阐述了流分类技术的研究背景，发展现，介绍了本文的主 要工作和章节安排； 第二章流分类问题概述。本章阐述了流分类问题，指出了流分类的定义 和流分类算法的性能衡量，并指出流分类算法研究的难点； 第三章典型流分类算法分析。本章分析了经典的流分类算法和各自的优 缺点； 第四章a b v 算法研究与改进。重点研究a b v 流分类算法，针对空间消 耗过大的缺点提出改进的流分类算法； 第五章改进算法在l i n u x 防火墙中的应用。对l i n u x 下n e t f i l t e r 内核框架 进行分析，设计并实现了基于改进算法的流分类器，并对算法的性能进行测试 分析： 第六章总结与展望。 2 第二章流分类问题 i n t e r n e t 以先到先服务的方式提供尽力而为的服务。随着网络的发展和各 种新业务的出现，该服务已经不能满足人们对网络的要求，一些新的服务应运 而生，如：v p n 服务f 2 们，s l a 服务，q o s 服务2 1 1 ，流量计费【2 2 1 和安全网关等。 这些服务都是以流分类技术为基础的。 2 1 流分类的定义 流的最初定义【2 3 】是“从一个源发送到一个目的的分组序列”，后来出现了 不同的含义：“具有相同的源地址的所有分组 、“具有相同的源目的地址的所 有分组 、“属于同一个t c p 连接的所有分组 等。现在通常把“具有某种相同 属性的网络协议分组的集合 定义为“流 。 流分类根据事先定义好的策略和规则，对包头的一个或多个域进行分析， 以识别该分组所属的流。与流分类有关的策略和规则的集合称之为流分类器， 它是流分类的核心。分类器的结构如图2 1 所示。 皖分类嚣 n 刘选的数据包p 虹第r 类藏 图2 1 流分类器的结构 假设一个规则库含有n 条分类规则r j ( 1 i n ) ，规则由3 部分组成【2 4 ： 正则表达式r i j 】( 1 j k ) 代表数据包头的k 个字段。每个字段可以 是具体的值、范围或前缀。 整数p r i o r i t y ( r i ) 代表规则优先级。当数据包匹配多条规则时，根据优先 级取最佳匹配1 2 5 1 。 操作a c t i o n ( r i ) 代表分组匹配规则后的动作。数据包p 可以看作k 维空 间的一个点( p l ，p 2 ，p k ) 。k 维分组分类问题就是在所有规则中查找与点相匹配 3 且优先级最高的规则。 流分类器中的每条规则根据包头的内容确定数据包所属的流类别，每一类 有一个类标识符。分类规则通常由k 个域构成，分别对应数据流的不同部分， 例如通常使用的5 维域流分类的5 个域 2 6 1 分别是源，目的i p 地址，源，目的端口 号以及协议类型字段。如表2 1 所示的五维( 源目的i p 地址，源目的端口号， 以及协议类型) 规则集。 表2 i 五维分类规则集 规则源l p 地址掩码目的i p 地址，掩码 协议 源端目的端口动作 口 r u l e l8 6 1 1 8 1 6 8 1 9 42 6 。1 4 5 1 6 ，1 9t c p 8 0 8 0 拒绝 r u l e 22 0 2 1 1 2 1 6 8 1 9 42 0 2 2 0 4 4 4t c p 2 l允许 r u l e 32 1 0 1 2 7 9 82 0 2 1 1 2 1 6 9 0t c p 1 0 2 3 允许 r u l e 41 7 2 1 6 2 9 0 2 0 2 1 1 2 1 6 9 ou d p 5 5 ，1 0 2 3拒绝 r u l e 5 毒 2 0 2 1 1 2 1 6 9 oi c m p 拳木 拒绝 r u l e 6 t鼍t 拒绝 2 2 流分类算法的性能评价 ( 1 ) 空间复杂度 该指标用于确定保存分类器和分类中相关数据结构所需要的空间o ( g ) ，g 是规则个数n 、域宽w 和维数k 的函数。 ( 2 ) 时间复杂度 该指标用于确定完成分类所需要的步骤o f f ) ，f 是规则个数n 、域宽w 和 维数k 的函数。 ( 3 ) 可扩展性 可扩展性包括以下3 种方式：分类规则的个数上具有扩展性。分类的 维数上具有扩展性。可以包含任意个字段；分类的层次上具有扩展性。 ( 4 ) 更新复杂度 该指标用于确定对分类规则进行插入、删除或更新所需要的步骤o ( h ) 。 一个高效的流分类算法希望具有较小的时间复杂度、空间复杂度和更新复 杂度，并且具有良好的可扩展性27 1 。 2 3 流分类的难点 ( 1 ) 分类速度与存储空间的权衡问题 从理论上来说，同时达到最大的分类速度和最小的存储空间的流分类算法 是不存在的，只能根据实际应用的需要在时间和空间之间进行权衡。 ( 3 ) 网络安全问题 4 防火墙、v p n 、入侵检测等系统使用的安全技术，如加密技术，它对分组 的信息进行加密，这使得流分类过程中难以提取所需信息，不利于分类。 ( 3 ) 规则冲突与优先级问题 规则冲突是指规则库中两个或多个规则重叠，从而导致一个模糊的分类问 题【2 引。给每个规则都赋予一个优先级是解决规则冲突的最基本方法。但随着规 则库规模的增大，优先级的设置变得越来越复杂，并且直接影响分类效率。如 何解决规则冲突，已成为流分类问题的一个难点。 2 4 本章小结 本章描述了流分类问题，主要包括流分类的定义、算法性能评价标准以及 流分类研究的难点。 第三章典型流分类算法分析 自流分类问题提出以来，流分类算法一直是人们研究的热点。目前已经出 现了很多不同类型的流分类算法，本章主要介绍几种典型的流分类算法。 3 1 基于线性表的算法 基于线性表的典型代表算法是l i n e a rs e a r c h 算法。线性查找算法按优先级 的高低以链表的方式降序存储规则。分类匹配时数据包依次与表中的各个规则 进行匹配找到合适的规则或者查找失败。该算法存储效率高、实现简单，但查 找时间随规则数的增加而线性增加，所以算法只适合小型分类规则库的环境。 3 2 基于t r i c 树的算法 数字查找树也称t r i e 树( 二叉查找树是最简单的t r i e 树) 。从根节点到某 个节点的所有位组成的位向量构成了t r i e 树上节点对应的前缀。t r i e 树的相关 算法是建立层次式的t r i e 树结构，这类算法在最坏情况下需要的访存次数为用 于分类的字段中比特位的数目。基于t r i e 树的算法对于一维查询比较有效，而在 多维查找中会耗费大量内存空间。采用t r i e 树结构的经典算法包括h i e r a r c h i c a l t r i e l 2 9 、s e t p r u n i n gt r i e l 3 0 】和g r i d o f - t r i e s 算法。 3 2 1h i e r a r c h i c a lt r i e 算法 该算法是基于t r i e 树的前缀查找算法。算法从d 维中选择一维生成第一级 t r i e 树，对树中的每一个与规则中第一维匹配的节点，按照规则中的第二维字 段建立第二个t r i e 树，以此类推，直到完成每一维字段的建树，就构成了多维 分层查找树。根据表3 1 的规则的h i e r a r c h i c a lt r i e 查找树，如图3 1 所示。 表3 1 规则集 规则目的i p 地址 源i p 地址 r l 0 0 0 0 r 2o 0 l r 3l 0 幸 r 40 0 0 r 50 l 幸 r 6 l + 6 图3 1h i e r a r c h i c a lt r i e 算法查找示意图 算法的查找过程：首先在第一层t r i e 树中对数据包的目的i p 地址做最长前 缀匹配：然后再对匹配成功的节点及其父节点所指向的第二层t r i e 树匹配查找， 得到最佳过滤规则。 根据以上的查找过程，对数据包p ( 0 1 0 ，o o o ) 进行处理。根据其目的i p 地址 前缀“0 0 0 ”按最长前缀匹配找到节点c ，继续查找节点c 指向的源地址t r i e 树。 源地址第一个比特位“0 ”找到节点r 4 ；然后回溯查找目的i p 地址t r i e 树，找到 节点r 2 。r 2 的优先级高于r 4 ，因此r 2 为最终的匹配规则。 该算法实现简单，便于硬件完成，但回溯查找时间长，因此算法对规则维 数的扩展性差，而且不直接支持范围匹配。设n 为规则总数，d 为规则维数，w 为域宽，则算法的时间复杂度是o ( w d ) ，空间复杂度为o ( n d w ) 。 3 2 2s e t p r u n i n gt r i e 算法 h i e r a r c h i c a lt r i e 算法查找时经常需要回溯，增加算法的时间复杂度，降低 了查找效率。s e t p r u n i n gt r i e 算法对多维分层查找树中某些节点进行复制，减 小分层查找树的层次，避免了回溯查找，提高查找效率。根据表3 1 的规则构建 查找树，如图3 2 所示，与图3 1 相比，增加了某些节点的拷贝。 7 图3 2s e t p r u n i n gt r i e 算法查找示意 s e t p r u n i n gt r i e 算法通过在t r i e 树上复制节点，增加节点数，查找时不需 要回溯操作，所以时间复杂度为o ( d w ) 。但算法的空间开销大，最坏情况下空 间复杂度为o ( n d ) ，同时对规则维数的扩展性差。 3 2 3gr i d o f - t r i e s 算法 g r i d o f - t r i e s 算法是对h i e r a r c h i c a lt r i e 和s e t - p r u n i n gt r i e 算法的改进。 g r i d o f - t r i e s 算法引入了交换指针，交换指针避免了h i e r a r c h i c a lt r i e 树中的回溯 需求，同时避免了s e t p r u n i n gt r i e 树中对节点的复制。根据表3 1 的规则构建 g r i d o f - t r i e s 查找树，如图3 3 所示。 图3 3g r i d o f - t r i e s 算法查找示意图 8 g r i d o f - t r i e s 算法的查找过程：首先在目的地址t r i e 树中对包头的目的i p 地址做最长前缀匹配；然后再对这个匹配成功的节点及其父节点所指向的源地 址t r i e 树，根据包头的源地址沿着0 、l 指针( 或交换指针) 进行源地址匹配查 找，得到优先级最高的过滤规则。 根据以上的查找过程，对数据包p ( 0 1 0 ，o o o ) 进行处理。根据其目的i p 地址 前缀“0 0 0 按最长前缀匹配找到节点c ，继续查找节点c 指向的源i p 地址t r i e 树。源i p 地址第一个比特位“0 找到酗点，然后再根据其第二个比特位“1 ” 找到节点r 2 。r 2 的优先级高，因此r 2 是其匹配规则。 g r i d o f - t r i e s 算法需要大量预处理时间建立数据结构，同时交换指针的使 用增加了更新操作的难度，不利于数据库规则的快速更新。此算法的空间复杂 度为o c n d w ) ，时间复杂度为o ( d w ) 。 3 3 基于元组的算法 基于元组的代表算法为元组空间查找算法( t u p l es p a c es e a r c h ) 。在规则数 据库中，每条过滤规则虽然含有不同的前缀或者范围( 如端口) ，但前缀长度 的数量是有限的，因此不同长度的交叉组合的数量也是有限的。元组空间查找 算法正是基于这种现象，对一个不同字段域的长度值组成一个元组，所有元组 集合组成元组空间。一个元组对应的字段域的比特位情况是已知的，将这些比 特连接组成h a s h 表的索引值，通过索引值查找与该元组对应的规则集合。当查 找数据包的匹配规则时，对每个元组查h a s h 表，得到该元组中匹配的过滤规则， 再通过元组空间查找获得最优的过滤规则。 以表3 1 所示的规则集阐述元组空间查找算法的处理过程。 ( 1 ) 根据规则集中所包含的规则，计算出每条规则所对应的元组，如表 3 2 所示。 表3 2 规则集对应的元组 规则集( f 1 ，f 2 )元组 r l( 0 0 ，0 0 )( 2 , 2 ) r 2 ( 0 | i ，0 l )( 1 2 ) r 3( 1 搴，0 卑)( 1 ，1 ) r 4 ( 0 0 o 事) ( 2 ，i ) r 5( o 幸，1 幸)( 1 ，1 ) r 6 ( 章，1 ) ( 0 ，1 ) ( 2 ) 将相同的元组合并，求出元组空间与规则对应关系如表3 3 所示： 9 表3 3 元组空间与规则对应关系 元组h a s h 条目 ( 0 ，1 )r 6 ( 1 ，1 )r 3 ，r s ( 1 ，2 )r e ( 2 ，1 )r 4 ( 2 ，2 )r l ( 3 ) 匹配数据包时，首先查找可能匹配该包头的规则所映射的元组，找 到匹配的元组，然后再利用从包头各域提取的信息查找h a s h 表，得到匹配的规 则。 元组空问查找算法平均查询时间性能好，而且规则改变时更新速度快，但 h a s h 表的使用使得查询匹配和更新时间具有不确定性。 3 4 并行搜索算法 并行搜索的代表算法为位向量( b v ) 算法。b v 算法是利用硬件逻辑运算 的并行性来实现分类。假设规则库中规则具有d 个字段域，b v 算法首先找到每 个字段域对应的值域空间，把它映射到坐标轴上：接着取规则中各维的值对相 应维的坐标轴进行分割，从而将d 条坐标轴分割成数目不等的小区间。然后对分 割后的d 条坐标轴计算每一条坐标轴上小区间对应的规则位图。 b v 算法为每条坐标轴上的分割小区间和对应的规则位图构建t r i e 树，t r i e 树中每个有效节点都用n 位位向量( 位图) 表示，当某个节点的前缀与规则r i 匹配，则该节点的位图中第i 位比特值设为“1 。根据表3 1 的规则集构建b v 算法的t r i e 树结构，如图3 4 所示。f 1 对应的t r i e 树中有三个节点，分别包含了 三个有效前缀1 幸、o 、0 0 。匹配数据包时，在每一个域的t r i e 树上做最长前缀 匹配查找，找到相应的节点，获得对应的位向量，然后对所有字段域的位向量 进行与运算，根据运算结果中“1 ”的位置找到数据包相应的匹配规则。 1 0 图3 4b v 算法示意图 p i b v 算法中与运算的时间复杂度为o ( n ) 。假设机器字长是w 比特，则与操 作需要访问( n * d ) w 次内存，由此可以看出算法的时间随着规则数目n 的增加而 线性增加，所以b v 算法在规则规模上扩展性低。 3 5 启发式算法 启发式算法如r f c 、h i c u t s 等都是依据规则集合的结构和冗余特点来进行 处理的。一般来说启发式算法时间效率很好，然而一些算法的空间性能却有待进 一步改进。 3 5 1h 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 ) 是以规则的每个字段为一层 将所有规则按范围空间进行循环分组，直到每组中只有少于n 条规则为止，查 找时在少于n 条规则的组中通过线性匹配来找到匹配规则。在h i c u t s 算法中， 只建立一棵决策树，根节点表示整个d 维空间，树中每个节点代表了查找空间 的一部分，每个结点下的所有子结点按某一维平均划分其父结点。子结点的维 数和个数按用户事先给定的约束参数b i n t h ( 叶结点对应的最大规则数) 和s p f a c ( 实验结果确定的常数) 选取。每个结点包含的规则是与该结点对应的d 维空间 相交的所有规则，如果某结点对应的规则数量超过给定的b i n t h ，该结点将被划 分成若干个子结点，直到所有子结点对应的规则数量不大于给定的b i n t h 为止。 图3 5 为根据表3 1 的规则构建的算法示意图，设b i n t h 为2 。 i 苎蔓查! 芝：。 日f l - 爵i 。 ：* 。l - - - - - 凹3 5h i c u t s 算法示意图 h i c u t s 算法支持范围匹配，对存储容量要求低，规则更新容易在规则空 b j 分布均匀时，h i c u t s 有很好的性能。但构造h i c u t s 树时需要循环依次对饵一 维进行空自j 划分。如果大部分规则只通过某一维来划分，而其他维的值相似， h i c u l s 树的深度和结点数会大大增加，预处理时间和占用的内存空间都会成倍 增加，大大影响算法的性能。 3 5 2r f c 算法 r f c 算法( r e e u r s i v ef l o w c l a s s i f i c a t i o n ) 是一种多维流分类算法。在对实际 规则数据库的观察中，发现过滤规则都具有内在的结构和冗余度，r f c 算法j f 是利用了这一特点进行算法设计。 r f c 算法是将流分类问题看成是一个包头中s 比特数据到t 比特( t = l o g n ，n 为规则总数) 的c l a s s l d 的一个映射。如果预先计算出包头的s 位，共2 3 种情况下 不同的c l a s s l d 值，那么每个数据包只需要检查一次，即访问内存一次。就可以 得到相应的c l a s s l d 。但可以看出，采用此方式会需要极大的空间丌销。r f c 的 思想是通过多个阶段柬完成映射，每个阶段是将一个较大的集合映射成个较 小的槊含。称为一次缩减。r f c 算法拭分几个个阶段，每个阶段由一系列并行 查找组成，每个查找的结果值要比查找的索引值短。图3 6 是种4 阶段的缩减 树。 阶段l阶段2阶段3 图3 6r f c 算法流程 r f c 算法具有极高的分类时间性能，但算法空间开销巨大，不适合大规模 规则库的应用。同时该算法预处理时间长，不支持规则的快速动态更新。 3 6 基于t c a m 的硬件实现方法 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 ) 是基于内容寻址存储器，它以 变量掩码的形式存储数据项，其中变量和掩码都是w 位比特长。若w = 6 4 ，对 二维流分类规则( 2 1 2 1 9 5 5 1 ) 、( 1 6 5 1 2 1 木) ，在t c a m 中将以( 2 1 2 1 9 5 5 1 0 ， 1 6 5 1 2 1 0 0 ，2 5 5 2 5 5 2 5 5 0 ，2 5 5 2 5 5 0 o ) 的形式存储。分类时，提取数据包相 应字段，然后连接各个值，组成t c a m 的输入，查询时只需在掩码置1 的位与变 量进行匹配比较。 图3 7t c a m 分类方案 日阪配规则 基于t c a m 的流分类方案如图3 7 所示。首先将规则库中所有规则按照优先 级的降序排列，存储于t c a m i 拘存储矩阵中。查找分类时，根据数据包的包头 并行匹配所有规则，输出n 位向量。该向量中的各位对应的规则已经预先按优 先级从高到低的顺序排列。这样，对输出的n 位比特向量只需要进行一个优先 级判断的逻辑电路的处理即可得到最佳匹配规则。 t c a m 算法具有最快的分类时间，只需要一个内存访问周期。但该算法需 要的t c a m 存储器的容量为d n w ( n 为分类器中规则总数，d 为分类器的维数，w 为每维宽度) 。t c a m 存储器价格高，耗电量大，且不直接支持范围匹配，因而 对规则的扩展性较差，适用于较小的流分类环境。 3 7 本章小结 本章介绍了几种经典的流分类算法，算法性能比较如表3 4 所示。 表3 4 算法比较 分类算法时间复杂度( 内存读 空间复杂度 取次数) l i n e a rs e a r c hnn h i e r a r c h i c a lt r i ew dn d w s e t p r u n i n gt r i e d wn d g r i d o f - t r i e sd wn d w t u p l es p a c es e a r c h l o g n n b vd n wn w d r f cdn d h i c u t sdn d t c a md n wd n 2 其中，n 为规则数，w 为域宽，d 为维数( 域的数目) ，n 为元组数( 其 大小与具体规则数据库有关，最坏情况下n 等于n ) 。 1 4 第四章a b v 算法研究与改进 1 9 9 8 年t v l a k s h m a n 等提出了位并行的思想，由此引出了b v 算法，a b v 算法是基于b v 算法的一种改进的快速流分类算法。该算法适合稀疏空间下的数 据分类，并且特别适合于网络数据的分类，被广泛应用于防火墙、路由器和i d s 系统中。 4 1a b v 算法 4 1 1a b v 算法的基本思想 网络数据流的分类属于多元分类方式，最典型的是通过源i p 地址、目的i p 地址、源端口、目的端口以及协议类型五维字段来构建数据分类的规则库。b v 算法分别针对每个字段进行匹配，最后根据各元组匹配的结果得到最终分类结 果，从而将所分析的数据划分到规则库中的某一类别中。b v 算法需要为字段建 立t r i e 树，树的深度与字段取值的长度有关。t r i e 树上的每个结点对应一个b v 位图m ，m 的长度l 与规则数相同，位图的第i 位对应规则库的第i 条规则，当该 结点匹配第i 条规则时，则位图的第i 位取值为“1 ”，否则为“0 。因此，匹 配规则库的过程是通过t r i e 树定位结点，然后匹配候选规则，即该结点位图中 为“l 的对应规则。 表4 1 为规则二元组，由此得到如图4 1 所示的f i e l d l 字段的t r i e 树，此时位 图m 的长度l = 9 。显然，规则库中规则数越多，位图m 的长度越大，b v 算法匹 配规则时间就越长。通过研究发现，在实际应用中一个结点匹配的规则很有限， 因此b v 位图m 是稀疏的，即m 中“1 的个数稀少。 表4 1 二元组规则库示例 r u l e s f i e l d lf i e l d 2 r 00 0 0 0 r l0 0 0 l 幸 r 2 1o 0 0 r 3ll 1 r 4 0 幸1 0 r 5o 幸 0 0 r 61 牛0 0 r 711 1 0 r 81 0 母1 1 5 图4 1f i e l d l 字段的t r i e 树 a b v 算法针对b v 位图稀疏性的特点，采用聚合b v 位图，创建聚合位图， 先运算聚合位图，再查找b v 位图，有效的提高了算法的时间性能。a b v 算法的 基本思想：将稀疏的b v 位图按照聚合因子a 进行聚合得到聚合位图，聚合因子a 决定了b v 位图中几个比特位聚合为聚合位图中的1 位；如果a 位中至少有一位 为“1 ，则对应的聚合位图中聚合位就是“1 ”，否则对应“0 ；分类时，先 对结点的聚合位图进行与操作，然后查找与操作结果中“1 ”的位置，找到该位 置对应的b v 位图部分，再对b v 位图做与操作，得到最终结果，结果中“1 所 处的位置就是该数据包的分类规则。 如图4 1 所示，聚合因子a = 3 ，位图m 的长度为3 ，位图m 长度小于b v 位图 m 。算法运算时首先匹配m ，当m 中匹配到为“l 的位时，再进一步匹配m 中对应的a 位。通过位聚合的方式，a b v 算法减少了读取位图的位数，从而加快 了算法执行，降低了匹配运算的复杂度。对于大规模规则库，有时候只进行一 次聚合是不够的。采取2 次聚合或多次聚合来压缩位串中的比特数目，可以减少 查找的难度，提高效率。 4 1 2a b v 算法描述 根据a b v 算法的基本思想，算法分两个部分：预处理过程和查找过程。 ( 1 ) 预处理过程 给定规则库f d ，假定它有n 条k 维规则，分别d f l f l f n 表示，f i ( j ) 表示规 贝, i j f i 的第j 维字段的值。a b v 算法的预处理过程如下： 对f d 的每一规n f i ( 1 i n ) ，将其源目的i p 字段分别建t r i e 树，对源 目的端口号和协议号投影到坐标轴上，最多形成2 n + 1 个不相交的区间，将区间 1 6 范围数值存储到表中。 为t r i e 树的非中间结点和表元素指派一个n 位的位图b ，b 中的每位代 表一条规则。 为t r i e 树的非中间结点和表元素映射一个聚合位图b 。通过位图b 按聚 合因子a 求出聚合位图b 。最后每个t r i e 树的非中间结点和表元素映射都同时映 射位图b 和聚合位图b 。 ( 2 ) 查找过程 设数据包为p ( e ，e 2 e ( e i 为