当前位置:首页 >> 建筑/土木 >>

快速流分类算法研究综述


科技文献检索

026194

李振强

快速流分类算法研究综述
李振强
(北京邮电大学信息网络中心 ,北京 100876)

摘要
本文对流分类算法进行了综述,包括流分类的定义,对流分类算法的要 求,以及各种流分类算法的分析比较。文章的最后指出了在流分类方面还没有 得到很好解决的问题,作为进一步研究的方向。

关键词
流分类;服务质量;IP

背景
当前的 IP 网络主要以先到先服务的方式提供尽力而为的服务。随着 Internet 的发展和各种新业务的出现,尽力而为的服务已经不能满足人们对 Internet 的要求,IP 网络必须提供增强的服务,比如:SLA(Service Level Agreement)服务,VPN(Virtual Private Network)服务,各种不同级别的 QoS (Quality of Service)服务,分布式防火墙,IP 安全网关,流量计费等。所有这 些增强服务的提供都依赖于流分类,即根据包头(packet header)中的一个或几个 域(field)决定该包隶属的流(flow)。典型的,包头中可以用来分类的域包括: 源 IP 地址(Source IP Address)、目的 IP 地址(Destination IP Address)、协议 类型(Protocol Type)、源端口(Source Port)和目的端口(Destination Port) 等。

流分类算法描述
首先定义两个名词:规则(rule)和分类器(classifier)。用来对 IP 包进行分 类的由包头中若干域组成的集合称之为规则,而若干规则的集合就是分类器。 构成规则的域(我们称之为组件 component)的值可以是某个范围,例如目的 端口大于 1023。流分类就是要确定和每个包最匹配的规则。表 1 是由 6 条规则 组成的一个分类器。我们说这是一个 5 域分类器,因为每条规则由 5 个组件构 成。我们假定分类器中的规则是有优先级的,越靠前的规则优先级越高,即规则 1 的优先级最高,规则 6 的最低。 表 1 4 域分类器 Rule Src IP Dest IP Protocol Src Port Dest Action Address/Mask Address/Mask Number Port Number Rule1 86.118.168.192/ 26.145.168.192/ TCP any eq 21 Deny 255.255.0.0 255.255.255.25 5

1

科技文献检索

026194

李振强

Rule2 Rule3 Rule4 Rule5 Rule6

202.112.168.192/ 255.255.255.0 210.12.78.4/255.2 55.255.255 172.16.21.0/255.2 55.255.0 any 0.0.0.0/0.0.0.0

202.204.4.2/255 .255.255.255 202.112.168.0/2 55.255.255.0 202.112.168.0/2 55.255.255.0 202.112.168.0/2 55.255.255.0 0.0.0.0/0.0.0.0

TCP TCP UDP ICMP Any

any any any Any any

eq 21 gt 1023 range 55-1023 Any Any

Permit Permit Deny Deny Deny

分类器中的每条规则有 d 个组件。R[i]是规则 R 的第 i 个组件, 它是包头第 i 个域的一个通用表达式。如果对于任意 i, 包头的第 i 域满足 R[i]的表达式,那 么该包就匹配规则 R。实际中,规则组件常常用地址/掩码或者操作符/数字的方 式表达。在地址/掩码方式中,如果掩码的某位是 0,表示我们不关心地址中的 对应位,如果掩码为 1,则反之。操作符/数字表达方式是指如下的形式:等于 21,范围 55-1023。 传统路由器中查中下一跳 IP 地址所使用的最长匹配算法其实就是一维流分 类的一个特例。我们可以认为所有去往同一个网络(network prefix)的包都属 于一个流。包应该转发往的下一跳的 IP 地址就是规则的行为(action),而前缀的 长度决定的规则的优先级,前缀越长优先级越高,即特定主机路由具有最高优 先级。

对流分类算法的要求
流分类算法具有位数宽、多维(multiple dimension)和允许范围匹配等特 性,这就决定了流分类算法的复杂性。高速路由器对快速分组转发能力的需求 又要求流分类算法必须具有很高的吞吐能力(具有“线速”的流分类能力)。 这使得流分类算法的设计具有较高的难度。一个好的流分类算法应该具有如下 的特征: 查找速度高:随着网络链路速度的提高,流分类必须具有较高的匹配速 度。 内存消耗少:算法需要的内存少,就可以使用价格较高的但速度较快的 存储技术,例如 SRAM,CACHE 等。 能够适用于实际中的规则较多的分类器 容易实现:算法应便于采用软件和硬件的方式进行实现,要便于采用流 水线结构和并行逻辑进行实现。 预处理时间短:在应用算法进行实际流分类之前,初始化数据结构需要 的时间要尽量短。 能够快速更新:动态性好,预处理完成后能够容易的从分类器中删除和 向分类器中添加规则。 用于流分类的域具有可扩展性:算法能够对 5 域(源 IP 地址、目的 IP 地址、源端口、目的端口和协议类型)的任意组合进行分类。 规则的任意性:一个好的算法应该能够支持不同形式的规则,包括前 缀,操作符(大于, 等于, 小于,范围等),统配符等。

国内外研究现状
2

科技文献检索

026194

李振强

目前流分类算法主要应用了三种数据结构:线性表,树和 Hash 表。这三种 方法都是在预处理时建立相应的数据结构,流分类时通过一次或多次查找建立 的数据结构和一些简单的处理获得最终的分类结果。使用线性表数据结构的算 法包括:Linear Search、Ternary CAM、Crossproducting、Recursive Flow Classification 等。使用树数据结构的算法包括:Hierarchical Tries、Set-Pruning Tries、Grid of Tries、Hierarchical Intelligent Cuttings、Aggregate Bit Vector 等。 使用 Hash 表数据结构的算法包括:Tuple Space Search 等。下面对每一种算法 进行简要的分析,指出各自的优缺点。 Linear Search 这种算法采用的数据结构最简单,规则以链表的方式降序存储。分类时数 据包从表头开始依次和链表中的各个规则进行比较,直到找到一条匹配的规则 或者达到链尾。尽管该算法存储效率高,简单,但是查找时间长,并且查找时 间随规则数的增加而线性增加。 Ternary CAM Ternary CAM 算法具有最快的分类时间,只需要一个内存访问周期。但该 算法只能由硬件实现,需要的 CAM 存储器的容量为 dNW(d:分类器的维数,N: 分类器中规则的个数,W:每一维的宽度,下同)。CAM 存储器价格高,耗电量 大,不能直接支持范围匹配,因而对 d, N, W 的扩展性均较差,只能用于较小 的流分类问题。 CrossProducting[6] CrossProducting 算法将多维的流分类问题建立在多个一维流分类基础上, 利用多个一维流分类的结果查找 CrossProducting 表获得最终的流分类结果。该 方法便于实现,时间复杂度是 dW,空间复杂度为 Nd,对规则维数和数量的可 扩展性较差。 Recursive Flow Classification[1] RFC 是由 Pankaj Gupta 和 Nick McKeown 提出的一种适合多域流分类问题 的算法,具有流分类速度快,直接支持范围和前缀匹配等优点。但当 d, N, W 增加时,所需存储空间太大。如果该算法所基于的特征在所用的分类器中不具 有或不明显,每一维长度的压缩量将很小,这将严重影响流分类的性能。该算 法的另一个缺点是动态性差,添加一条新规则在最坏的情况下需要重建整个数 据结构,因而不适合规则频繁变化的流分类器。 Hierarchical Tries Hierarchical Tries 是对一维查找树的一种简单扩展,它从 d 维中任选一维生 成第一级查找二叉树,对该二叉树中的每一个与分类器中第一维匹配的结点, 按分类器中规则的第二维建立另一个二叉树,反复上述过程直到完成每一维的 处理,就构成了多维分层查找树。该方法简单、直接,也便于硬件实现,但查 找时间较长,对 d 的扩展性差,也不直接支持范围匹配。 Set-Pruning Tries[7]

3

科技文献检索

026194

李振强

Set-Pruning Tries 通过对多维分层查找树中某些结点进行多次复制,减少多 维分层查找树的层次,提高查找效率。但所需存储空间增加较多,对规则维数 的扩展性差。 Grid of Tries[6] Grid of Tries 的主要思路是将 Set-Pruning Tries 中重复的子树删去,只保留 一颗子树,这样存储空间的需求量由 NddW 降为 NdW,时间复杂度仍为 dW, 但该方法动态性差,减少规则需要对整个树进行重建,并且只适用于 d=2 的情 况。 Hierarchical Intelligent Cuttings[2] Hierarchical Intelligent Cuttings 的基本思想是以规则的每一字段为一层次将 分类器中所有规则按范围空间进行循环分组,直到每一组中都只有少于 NUM 条的规则,查找时在少于 NUM 条规则中通过线性匹配来找到匹配规则。在 HiCuts 中,整个分类器只建立一棵树:根节点表示整个 d 维空间,树中每个节 点代表了查找空间的一部分,叶结点存储了位于这个查找空间的 B 条规则, B<=NUM。HiCuts 能够根据分类器本身的特征自动调节流分类算法使用的数据 结构,最大限度的利用优化数据结构、减少冗余,降低算法的存储容量要求, 提高流分类的速度。该算法对存储容量要求低,直接支持范围匹配,动态性 好,规则的增删容易:产出规则时,只要把该规则打上“删除”标记即可,不 用修改 HiCuts 树;增加规则时,在相应空间的叶结点加上该规则号,如果叶结 点增加后的规则数大于 NUM,则对该叶结点执行空间划分过程。 在规则空间均匀分布的情况下,HiCuts 有很好的性能,但由于构造 HiCuts 树时是循环依次对每一维进行空间划分,如果一个 d 维分类器中的大部分规则 只通过某一维来划分,而其他维的值相似或相同,HiCuts 树的深度和结点会大 大增加,预处理时间和占用的内存空间都会成倍增加,大大影响算法的性能。 Aggregate Bit Vector[8] ABV 的基本思想是“分割-合并”, 它将一个 d 维的流分类问题分割为 d 个 1 维匹配的子问题,然后将子问题的结果进行合并得到最后的匹配规则。 ABV 为每一字段建立一棵非完全二叉树,二叉树的每个节点都表示了一个范 围,二叉树的最高高度不大于该域的比特位数 W。ABV 利用比特向量记录符合 该结点范围的规则,然后根据归并参数 A 对比特向量进行 A 位一组的逻辑或操 作。通过归并 ABV 算法减少了访存次数,当分类器维数较大,规则较多时,采 用多层归并可以大大减少算法的访存次数,提高匹配速度。但是归并带来的好 处是受条件限制的。当规则无序排列使得归并后的向量为全 1 时,并不会减少 访存的次数。所以,在 ABV 的预处理阶段需要对分类器中的规则按字段进行排 序,但这会大大增加预处理时间。 ABV 算法具有较好的动态性,对分类器中规则的增删改比较容易。删除规 则时,只需遍历二叉树把向量中对应的比特位置 0;修改与删除类似;增加规 则时,可以占用被删除规则的位置或加到最后比特位的后面,并且能够较好的 实现规则的冲突检测,这是 ABV 算法一个突出特性。 Tuple Space Search[10] Tuple space search 算法使用 Hash 表将一次匹配分解成几次严格匹配查询。 该算法将一个 d 维规则映射成一个 d 元元组,d 元元组的每个组件存储规则相应

4

科技文献检索

026194

李振强

域前缀的长度。该算法的时间复杂度是 M(M 是分类器中 d 元元组的个数),存 储复杂度是 O(N),因为每一个规则只在一个 Hash 表中存储。该算法支持规则 的动态更新,在 d 元元组较少时有良好 MF 分类性能。但是该算法只支持前缀 匹配,并且 Hash 算法的使用使得匹配和更新的时间具有不确定性,在最坏情况 下,M= O(Wd)。

进一步研究方向
新算法的设计和验证 通过对已有流分类算法的研究和分析,借鉴其优秀的设计思想,对已有算 法的不足进行改进,提出新的算法并进行验证。 IPv6 流分类 以上所述各种算法都只适用于 IPv4。对于 IPv6 的流分类问题现在很少有论 文论及。IPv6 的流分类和 IPv4 的流分类有些不同。首先,每一个地址域变成了 128 比特。一个典型的 5 域分类器用于分类的关键字将长达 296 比特。其次,确 定 TCP/UDP 端口号需要顺着扩展头列表进行解析,直到分类器确定了 TCP/UDP 净荷的开始位置或确定了分组不属于这两个协议。 对于 IPv6 流分类可以考虑利用 IPv6 包头中的流标号域。一个可能的用法 是分组的发送源对所有要求网络给予同样排队和调度处理的分组分配一个随机 但唯一的流标号值。这样分类关键字仅仅需要覆盖流标号和源地址域就能实现 流层次上的分组隔离,而不需要检查目的地址域和 TCP/UDP 端口号。 但是流标号加源地址的分类方法限制了路由器将几个流进行汇聚的能力。 产生分组的源负责为分组分配流标号并且可能为属于不同应用的流分配相同的 流标号。由于流标号仅仅标识要求特殊排队和调度处理而没有其他附加语义, 路由器就区分不出共享同一个流标号的不同的流,相反,由于不同的应用采用 不同的 TCP/UDP 端口号,明确的端口号分类允许路由器从相关的应用中识别 流。 分段后的流分类 MF 分类的一个局限是分段的 IPv4 分组仅在第一段承载 TCP/UDP 端口号。 因此,察看 TCP/UDP 端口号的 MF 分类器很可能遗漏同一个分组的后面的段 (除非分类器使后面的段和承载端口号的第一个段关联)。 加密报文的分类 端到端的净荷加密给分类算法提出了挑战性的问题。网络加密隐藏尽可能 多的信息以防止被窃听,而同时保留足够的信息以使路由器能正确的转发分 组。如果 IP 的净荷被加密,则 TCP 和 UDP 端口号不能被识别。更复杂的情况 是,应用的 IP 分组被全部加密且以隧道方式通过网络。网络内部的路由器将基 于隧道的分组头分类,这意味着很少关心共享隧道的单个流的信息。

参考文献
1.Gupta P. and McKeown N., “Packet Classification on Multiple fields”, Proceedings of ACM Sigcomm, September 1999, pp. 147-160

5

科技文献检索

026194

李振强

2.Gupta P. and McKeown N., “Classification Using Hierarchical Intelligent Cuttings”, Hot Interconnects, August 1999 3.胡光岷,李乐民,“流分类算法研究综述”,通信技术,第一期,2002 4.Gupta P. and McKeown N., “Algorithms for Packet Classification”, IEEE Network, March/April 2001 5.隆克平,龚向阳等译,Grenville Armitage 著,IP 网络的服务质量—多业务互 联网的基础,机械工业出版社,2001 年 1 月 6.V. Srinivasan et al., “Fast and Scalable Layer four Switching,” Proceedings of ACM Sigcomm, September 1998, pp. 203–14. 7.P. Tsuchiya, “A Search Algorithm for Table Entries with Non-contiguous Wildcarding,” unpublished report, Bellcore. 8.Florin Baboescu, George Barghese, “Scalable Packet Classification”, Proceedings of ACM Sigcomm, 2001 9.Anja Feldmann, S. Muthukrishnan, “Tradeoffs for Packet Classification”, Proceedings of IEEE Infocom, 2000 10. V. Srinivasan, S. Suri, and G. Varghese, “Packet Classification using Tuple Space Search”, Proceedings of ACM Sigcomm, September 1999, pp. 135–46. 11. 申震生,龚向阳等,“具有高速过滤算法的 IP 防火墙”,计算机应用, Vol. 21, No 5, May 2001

6


相关文章:
文本分类中的特征提取和分类算法综述
文本分类中的特征提取和分类算法综述 摘要:文本分类...算法进行了论述,并通过实验的方法进行了深入的研究。...相对于特征抽取方法,特征提取方法因其快速、简单、...
车辆调度算法研究及其应用文献综述
车辆调度算法研究及其应用文献综述_教育学/心理学_人文...(Vehicle Routing Problem)问题描述及其分类 VRP 问题...图像分析技术以及计算机网络和信 息处理技术的快速发展...
数据流概念漂移分类和挖掘研究综述
流概念漂移处理方法的发展趋势,最后概括了 数据流概念漂移挖掘和分类研究现状。...流概念漂移分类研究进入了快速发展期,研究人 员开始考虑更加接近实际状况的数据流...
网络拥塞控制算法研究综述
网络拥塞控制算法研究综述 [导读]在本文中,作者着重阐述了 TCP 拥塞控制和 IP ...当某 个流的数据包到达过时,其队列就会很快占满,属于这个流的新到的包就会...
国内外文本分类研究计量分析与综述
国内外文本分类研究计量分析与综述 国内外文本分类研究计量分析与综述* 计量分析 [摘要 运用文献计量分析方法、计算机统计分析技术、社会网络分 摘要] 摘要 析软件对...
基于结构挖掘的排序算法研究综述.doc
基于结构挖掘的排序算法研究综述.doc_专业资料。龙源...很好地帮助用户快速从 搜索结果中锁定对自己真正有用...HITS 【 中图分类号 】 TP3 【 文献标识码 】 ...
网络流量分类国内外研究现状
分类方法以及算法的研究现状,据此以望 给相关领域的...基于“网络流”统计特征和机器学习的方法因为能够 ...提出一 种基于数据挖掘技术——概念自适应快速决策树...
聚类算法综述
后来,信息技术快速发展,新数据的出现呈井喷趋势,其...二、聚类算法分类及国内外发展现状根据中国知网的搜索...它的基本算法流 程为:首先将待分类数据构成一个有...
2013标签传播算法理论及其应用研究综述
具有算法简单,运行效果好,执行速度,可扩展性强,...分类、标注、处理和社区发现等方面的应用研究,最后...第二, 相同流形结构上的点 能够拥有相同的标签。 ...
车型识别研究综述
化建设和城市化建设的快速发展, 越来越多的家庭以及...车型识别技术的研究现状当前已有的车型识别分类方法...可最终有 效改善道路拥堵,提高路网通流效率,优化...
更多相关标签: