快速流分类算法研究综述

《快速流分类算法研究综述》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、科技文献检索026194李振强快速流分类算法研究综述李振强（北京邮电大学信息网络中心，北京100876）摘要本文对流分类算法进行了综述，包括流分类的定义，对流分类算法的要求，以及各种流分类算法的分析比较。文章的最后指出了在流分类方面还没有得到很好解决的问题，作为进一步研究的方向。关键词流分类；服务质量；IP背景当前的IP网络主要以先到先服务的方式提供尽力而为的服务。随着Internet的发展和各种新业务的出现，尽力而为的服务已经不能满足人们对Internet的要求，IP网络必须提供增强的服务，比如：SLA(ServiceLevelAgreement)服务，VPN(VirtualPriva

2、teNetwork)服务，各种不同级别的QoS（QualityofService）服务，分布式防火墙，IP安全网关，流量计费等。所有这些增强服务的提供都依赖于流分类，即根据包头(packetheader)中的一个或几个域（field）决定该包隶属的流(flow)。典型的，包头中可以用来分类的域包括:源IP地址（SourceIPAddress）、目的IP地址（DestinationIPAddress）、协议类型（ProtocolType）、源端口（SourcePort）和目的端口（DestinationPort）等。流分类算法描述首先定义两个名词：规则（rule）和分类器(classifi

3、er)。用来对IP包进行分类的由包头中若干域组成的集合称之为规则，而若干规则的集合就是分类器。构成规则的域（我们称之为组件component）的值可以是某个范围，例如目的端口大于1023。流分类就是要确定和每个包最匹配的规则。表1是由6条规则组成的一个分类器。我们说这是一个5域分类器，因为每条规则由5个组件构成。我们假定分类器中的规则是有优先级的,越靠前的规则优先级越高,即规则1的优先级最高,规则6的最低。表14域分类器RuleSrcIPAddress/MaskDestIPAddress/MaskProtocolSrcPortNumberDestPortNumberActionRule1

4、86.118.168.192/255.255.0.026.145.168.192/255.255.255.255TCPanyeq21Deny6科技文献检索026194李振强Rule2202.112.168.192/255.255.255.0202.204.4.2/255.255.255.255TCPanyeq21PermitRule3210.12.78.4/255.255.255.255202.112.168.0/255.255.255.0TCPanygt1023PermitRule4172.16.21.0/255.255.255.0202.112.168.0/255.255.255.0

5、UDPanyrange55-1023DenyRule5any202.112.168.0/255.255.255.0ICMPAnyAnyDenyRule60.0.0.0/0.0.0.00.0.0.0/0.0.0.0AnyanyAnyDeny分类器中的每条规则有d个组件。R[i]是规则R的第i个组件,它是包头第i个域的一个通用表达式。如果对于任意i,包头的第i域满足R[i]的表达式，那么该包就匹配规则R。实际中，规则组件常常用地址/掩码或者操作符/数字的方式表达。在地址/掩码方式中，如果掩码的某位是0，表示我们不关心地址中的对应位，如果掩码为1，则反之。操作符/数字表达方式是指如下的形式：等

6、于21，范围55-1023。传统路由器中查中下一跳IP地址所使用的最长匹配算法其实就是一维流分类的一个特例。我们可以认为所有去往同一个网络（networkprefix）的包都属于一个流。包应该转发往的下一跳的IP地址就是规则的行为(action),而前缀的长度决定的规则的优先级，前缀越长优先级越高，即特定主机路由具有最高优先级。对流分类算法的要求流分类算法具有位数宽、多维（multipledimension）和允许范围匹配等特性，这就决定了流分类算法的复杂性。高速路由器对快速分组转发能力的需求又要求流分类算法必须具有很高的吞吐能力（具有“线速”的流分类能力）。这使得流分类算法的设计具有较

7、高的难度。一个好的流分类算法应该具有如下的特征：Ø查找速度高：随着网络链路速度的提高，流分类必须具有较高的匹配速度。Ø内存消耗少：算法需要的内存少，就可以使用价格较高的但速度较快的存储技术，例如SRAM,CACHE等。Ø能够适用于实际中的规则较多的分类器Ø容易实现：算法应便于采用软件和硬件的方式进行实现，要便于采用流水线结构和并行逻辑进行实现。Ø预处理时间短：在应用算法进行实际流分类之前，初始化数据结构需要的时间要尽量短。Ø能够快速