高速路由器中TCP/IP数据流的分类技术

文章编号：1009－6868(2001)04－0015－04 文献标识码：A 中图分类号：915.05

　　IP流分类(Flow classification)技术是在TCP/IP网络的节点中，根据业务流的特征对其分类，目的是为不同业务流提供不同的处理方式。在Internet中，对流的分类实际上是对分组的分类(Packet classification)。IP流分类一个最简单的例子是IP分组的路由选择过程：即根据路由表和目的地址对IP分组进行分类处理(即选择不同路由)。随着Internet的发展和新业务需求的涌现，业务流分类处理已成为保障网络及应用的服务质量(QoS)及安全性的重要手段，为此也引入了更为复杂的多字段分类技术。当前流分类技术的一个主要应用是在IP网络QoS模型(如DiffServ/IntServ模型)中，对不同等级的业务流进行分类和调度，以提供不同级别的服务质量。此外在众多的网络安全方案中，IP流分类技术也大量应用于具有防火墙功能的网络节点上，用于区分和过滤非法的或不安全的数据流。网络节点的高速分组处理速率意味着在业务要求日趋复杂和分类规则不断膨胀的情况下，分类算法仍然具有极高速度。然而针对任意规则的快速分类在理论上仍然是一个难题。因此，近年的研究热点都集中在IP网络中对实用化的快速流分类技术的研究。

　　1 流分类技术描述

　　流分类器的核心部分是规则库R，它是分类的依据，由一组策略或规则(Rule/filter)构成。每条规则r都定义一个业务流类型(Class)。每个流类型都具有唯一标识，并且对应于一种特定的处理方法。若一个分组p匹配了某规则r，p就应被划分为r所对应的类。故分类过程的实质即：对特定p，在R中搜索与之匹配的规则，确定p的类别，并将相应的处理方法应用于分组p。分类过程必需利用分组p头的k个控制字段h[1],h[2],…,h[k]，此时分类器称为k维分类器，其中任一规则r也可用一个k维向量r=(r[1],r [2],…,r [k])来表示。分组p匹配了规则r就被定义为：对任意i(i=1～k)，p分组头的第i个字段h [i]都匹配了规则r的第i个分量r [i]，其中，h [i]匹配r [i]的形式有精确匹配(h [i]=r [i])、前缀匹配(r [i]是h [i]的前缀)和范围匹配(h [i]属于r [i]所定义的范围)等。一般r的任一分量r [i]定义整数集上的一个范围， p匹配r意味着对任意i有h [i]∈r [i] 。因此，任意规则的流分类可归结为在多维空间中点的定位问题：k维空间中有N个k维长方体(规则r)，问题是确定给定点(分组p)位于哪个长方体中。显然，p可能匹配规则库R中的多条规则(即规则冲突Conflict)，而流分类实际上是在R中搜索给定分组p的最佳匹配规则r的过程。

　　研究表明：通常情况下若规则库规模为N，在k > 3时，时间复杂度最低限为O(logN)，此时空间复杂度为O(Nk)；空间复杂度最低限为O(N)，时间复杂度为O(logk-1N)。N较大时算法很难同时达到较低的时间/空间复杂度。通常的研究方法是根据特定环境，利用规则库中的某些特征来提高算法的效率。在IP环境中的流分类器维数一般为6～7维(根据应用可能更多)。不同应用的规则库R规模也差别很大，从数十到数万条规则。

　　一般来说，IP流分类在节点的输入端进行；节点根据分类结果对不同流作不同的处理。为保证整体性能，流分类算法也必须满足一定的性能要求，包括在最坏情况下(非平均情况下)，算法最大的分组处理速率一般不能低于线路分组的到达速率，算法性能不依赖于某种特定业务流量特性，即性能与业务流特性无关。算法设计时的另一个问题是规则修改的复杂度。通常分类规则的修改频度较小；为提高分类性能可在一定程度上牺牲规则修改的性能和复杂度。但某些动态规则分类器对规则的修改性能也有很高的要求。

　　2 高速IP流分类技术

　　实用化的快速IP流分类技术的研究是近年来的一个热点，其目的是在有限的空间条件下，根据IP流分类的特点来设计算法，使其能用较大IP分类规则集对分组进行快速分类处理，且在最坏情况下也具有较高的性能。目前已经提出了若干算法，在一定的限定条件下(分类器的维数、存储空间和规则库的规模)，依赖特定的设备和环境，实现高速的IP流分类。

　　2.1 三重内容寻址存储器方案

　　这是一种采用硬件的高速分类实现方案。其规则按照优先级存储于内容寻址存储器(CAM)中；CAM能够将IP分组的控制字段同时与所有规则进行并行比较，选出优先级最高的匹配规则。由于采用硬件实现，方案具有极高的分类速度；但其成本过高，只适用于小规则库，且不能直接支持范围匹配。

　　2.2 基于比特向量的多维范围匹配

　　基于比特向量的多维范围匹配方案也需要硬件辅助[1]。该方案定义一种比特向量，每条规则唯一对应于向量中的一位。在进行搜索时，可并行在多个字段上进行一维匹配搜索。各维的搜索结果均是一个比特向量，其中包含了分组可能匹配规则。各个结果向量进行比特与运算后，就可找到分组的最佳匹配规则。算法需要N比特向量的与操作，只能用硬件实现，这限制了规则库的扩展性，其空间复杂度为O(Nk)。

　　2.3 有向非循环图DAG算法

　　该算法采用有向非循环图[2](DAG)来搜索最佳的匹配规则。规则表采用DAG的形式存储，被划分为多个层次，每层对应于规则中一个字段的查找(如第一层目的IP地址、第一层源IP地址……)。一个层次搜索成功后，可根据DAG中指定的通路转移到下一层次继续搜索，直到规则中的所有字段均搜索完毕。在各层中可采用不同一维匹配算法。如IP地址可采用快速的最长前缀匹配算法；端口号可采用范围匹配等。DAG算法的主要数据结构是DAG规则表。为了提高搜索速度，算法还设计了一个流表，实际是规则表的高速缓存，采用哈希表方式存储。DAG算法的基本过程是：对每个到达分组，先利用哈希方式在流表中进行查找；若查找失败，则在规则表中搜索，并把搜索到的匹配规则添加到流表中。DAG算法的搜索时间在一定程度上只与分类器的维数k有关，而与规则数N无关，但在各层次的搜索中对不同字段的匹配算法往往可能与N相关。从空间复杂度上来看，对于大部分的实际规则库，其空间要求接近于O(N)；但其在最坏情况下(如规则冲突度很大时)，其空间复杂度将达O(Nk)。DAG算法的实现不依赖于硬件。

　　2.4 交叉乘积算法

　　交叉乘积(CP)算法[3]可实现对多维的任意规则的快速匹配，其基本思想是以牺牲空间为代价换取时间复杂度的降低。CP算法先在每一维上分别进行匹配，把结果连接起来形成交叉乘积，在乘积空间中直接映射到最佳匹配。CP算法查找时间很短，但最坏情况下乘积空间巨大(O(N k))，如50条规则需约1.5M空间。一种改进的On－Demand CP算法采用了缓存(Cache)技术降低空间的需求，使之能用于更大规模的规则库，但其最坏情况下的搜索时间得不到保证。

　　2.5 Grid of Tries算法

　　Grid of Tries(GOT)算法[3]是一种基于二叉树的二维前缀匹配的算法，由于其查找速度快、空间要求小且能用于很大的规则库,因此非常适用于源－目的地址的二维地址前缀匹配的快速搜索。这里的Trie是一个二叉树，分支分别标记为0和1。树上节点对应的前缀是从根节点到该节点的路径上所有比特的串结。这种结构有利于处理二维的源地址－目的地址的规则。这种结构对每个到达分组，首先在目的树(DT)中搜索匹配，其结果是最长目的地址前缀；然后在与该目的地址前缀相关的源树(ST)中搜索源地址的匹配前缀。若在ST中搜索失败，则将导致回溯，需在DT中再次搜索一个次最长的目的地址前缀匹配，在新的ST中重复上述搜索过程。

　　从以上的算法过程中可见GOT算法的时间复杂度为O(w2)，其中w为IP地址的长度。为减少回溯，算法通过预处理在ST中增加引入转移关联指针。当在ST中搜索匹配失败时，不需回溯，直接通过关联指针转移到其他ST。改进后搜索时间复杂度为O(w)，最大搜索次数为2w，空间复杂度为O(Nw)。

　　GOT算法还可改进。由于DT仅用于一维最长匹配前缀搜索，因此可采用更高效搜索方法。实际中可将总搜索次数降低到logw ＋w。另一种改进是采用多比特树替代单比特ST树，使ST的深度从w减少到w/m(m为比特数)，故查找时间可降为O(logw＋w/m)。但所需空间将从2Nw增加到Nw2m/m，因此m需折衷选择。此外，算法需要较多的预处理时间。通过扩展，GOT还可支持范围匹配，与CP算法结合也可实现多维的分类[3]，但最坏情况下的性能无法保证。

　　2.6 Tuple空间搜索算法

　　Tuple空间搜索(TSS)算法[4]用于前缀匹配的搜索，其出发点是利用实际规则库的特性来提高搜索的速度。一般来说，尽管在实际规则库中存在大量不同的前缀，但前缀长度的取值范围很小(在0～32之间)，因此各字段的前缀长度组合的数目较有限。根据这个特点，TSS算法对于规则中各字段的前缀长度的每一种不同组合分别定义一个Tuple；每个Tuple只保存特定前缀长度的规则。显然在一个Tuple中，规则的各字段具有固定的前缀长度，故采用Hash方式可以非常快捷地找到匹配规则。通过划分，规则库按各字段的前缀长度的组合构成一个Tuple的集合空间(Tuple space)。这样，大规则空间的搜索就转化为较小Tuple空间的搜索，从而提高效率(即使采用线性搜索)。当分组到达时，依次检查每个Tuple空间中是否有分组的匹配项(采用Hash方法：根据各字段的长度从分组取出对应前缀串作为参数)，并从搜索到的匹配项中确定最佳匹配。算法的时间复杂度与Tuple空间大小成正比。

　　对Tuple空间的线性搜索将影响搜索的速度，为此TSS算法也有一些改进方案，其中主要方式是在搜索过程中逐步缩减被搜索Tuple空间以提高算法效率。例如，若在Tuple Ti中找到了匹配项，那么根据最长前缀匹配的原则，所有各字段的前缀长度均小于Ti的Tuple就可从搜索空间中裁减掉。由于利用了规则库的结构特性，TSS算法搜索规则空间缩减为较小的Tuple空间，提高了搜索效率。TSS算法空间很小，搜索时间仅与规则库结构(Tuple空间大小)有关，而与规则数量无关。

　　2.7 递归流分类算法

　　递归流分类(RFC)算法[5]采用递归方式来分步骤解决任意规则的流分类问题。RFC算法把多字段分类问题看作为分组头控制字段取值空间(S)到类标识(Class ID)空间(T)的映射问题(T=logN，N为规则数，且T<<S)。该映射最快捷的实现方法是预先计算出2S个不同的分组头取值所对应的类标识，存于一个线性表中；在搜索时只需一次内存访问就可查找到结果。但S空间一般很大，内存需求使其不能实用。RFC算法的基本思想就是分阶段递归实现上述的映射，各阶段搜索采用可并行的哈希运算，因此速度很快。逐步进行空间压缩，最终得到分类结果(即类的标识)。

　　RFC算法的实现与基于比特向量的多维范围匹配类似。但是，为了消除搜索过程中所需的大量比特向量逻辑与运算带来的开销，RFC算法将该过程移到预处理过程中进行，把查找过程中需要的中间数据(非比特向量)通过预处理保存下来。尽管增加了预处理复杂度，但大大简化了搜索过程，其代价是牺牲了预处理过程在时间和空间上的复杂度。

　　RFC算法在预处理阶段需要进行大量运算，得到如图1的数据流结构。算法性能通过阶段数和树形状两个参数来调节。当阶段数目增加时，所需的总内存空间减小，但是在搜索过程中会增加内存访问次数和时间。在图1中的各级向量表在预处理阶段生成；每一级向量表的内容被作为下一次递归搜索的关键字。

图1 RFC算法的数据流图

　　RFC算法搜索过程非常简单，在阶段0，从到达分组的分组头中提取关键字，并分别作为索引在相应的向量表(各关键字段均对应一向量表)中查找该字段的阶段0的类标志，通常类标志空间已经大大缩减。然后按照树的形状将不同字段的类标志结果合并，作为阶段1的一个关键字进行阶段1的搜索。通过这样的递归过程，将可在最终阶段的向量表中查询到分组对应的类标志。由于在搜索过程中向量表均采用索引方式查找，不需额外计算，只需若干次内存访问(图1中访问13次)，因此查找的速度非常快。据报道，采用硬件流水线的RFC算法处理速度可达30Mpps。

　　RFC算法可以适用于任何形式的规则，包括前缀匹配和范围匹配。RFC算法搜索的时间复杂度可用少数几次内存访问来表示，与字段数k和规则数N无关，而且不存在最坏情况下的性能下降。由于利用了实际规则库中的结构化和冗余性，故算法所需的空间难以用表达式来描述，其大小与规则库结构有关。规则数N增加时，所需空间可能相当大，特别是当阶段0中空间收敛不够快的情况下。此外算法为了提高搜索速度，使预处理过程十分复杂(不论在时间和空间上)，因此不适用于规则修改频度很高的应用中。

　　2.8 其他的快速分类算法

　　除了以上快速流分类技术外还有一些相关的技术可用于快速分类算法中，包括用于检测和解决规则冲突的快速冲突检测算法[6](Fast Conflict Detect Algorithm)等。许多最长前缀匹配搜索算法也常被用于快速分类算法的实现中。其中，分级二叉搜索(Binary Search on Levels)算法[7]的时间复杂度仅为O(logw)。经常被采用的最长前缀匹配搜索算法还有受控前缀扩展的快速地址搜索[8](Fast Address Lookups Using Controlled Prefix Expansion)和多路多列搜索的IP搜索[9](IP Lookups Using Multi－Way and Multi－Column Search)等。

　　3 流分类技术在实际应用中的问题

　　流分类技术在TCP/IP网络中主要应用于安全信息过滤和提供QoS保障。综合分析上述的各种技术，这些算法都是在某些限定条件下设计实现的，分别针对不同的应用场合。因此在实际应用中，需要根据应用特点来选择和设计自己的分类算法。对于二维前缀匹配来说，GOT算法无疑是一个很好的选择。在多维分类算法中，RFC性能是很好，也存在一定问题，如所需空间不可预测、预处理复杂等。通过分析可以得出以下结论：首先，实现大规模规则库的高速搜索有相当的困难，特别是规则数和时间复杂度增加都将会对算法性能造成影响。算法实现中通常采用的手段是以增加空间复杂度的代价来提高搜索速度。但是由于物理存储空间的限制，必须在时间和空间代价之间进行权衡。提高搜索速度的另一个手段是引入数据的预处理，将大量数据运算过程在预处理中进行，减少搜索过程中的开销，提高搜索的速度。但是增加预处理开销的方式不利于规则库的频繁修改和动态更新。而当前的许多应用都对分类算法的可修改性提出了较高的要求。其次，大多数的快速分类算法都利用了实际规则库中规则的一些结构性特点和统计特性，以进一步减少搜索所需的空间和时间。因此，分析和利用规则特性也是设计高速分类算法的重要手段。总之，一个实用的快速分类算法需要进行多方面的权衡，往往需要结合多种算法的设计思想。而分类算法要满足高速网络设备所需要的高速率，最终还要利用硬件来实现。

　　4 结束语

　　可以看到，每一个快速IP流分类算法都是在一定应用特定的前提下针对特定的应用场合而提出的。由于前提和应用场合的差异，没有统一标准来衡量各种算法的优劣。在应用中也很难找到现成的算法能直接应用于特定的应用系统；需要我们通过研究和综合各种算法思想，才能设计和实现适用于自身应用需求的算法。

　　参考文献

1 Lakshman T V, Stiliadis D. High－speed Policy－based Packet Forwarding Using Efficient Multi－dimensional Range Matching.In:Proceedings of ACM SIGCOMM'98.Vancouver Canada,ACM,1998
2 Decasper D,Dittia Z,Parulkar G,Plattner B. Router Plugins—A Software Architecture for Next Generation Routers.IEEE/ACM Transactions on Networking,2000,8(1)
3 Srinivasan V,Varghese G,Suri S,Waldvogel M.Fast and Scalable Layer Four Switching.In:Proceedings ACM SIGCOMM'98.Vancouver Canada,ACM,1998
4 Srinivasan V,Suri S,Varghese G.Packet Classification Using Tuple Space Search. In:Proceedings of ACM SIGCOMM'99.Cambridge USA,ACM,1999
5 Gupta P,McKeown N.Packet Classification on Multiple Fields.In:Proceedings of ACM SIGCOMM'99. Cambridge USA,ACM,1999
6 Hari A,Suri S,Parulkar G.Detecting and Resolving Packet Filter Conflicts.In:Proceedings of IEEE INFOCOM'2000.Israel, IEEE,2000
7 Waldvogel M,Varghese G,Turner J,Plattner B.Scalable High Speed IP Routing Lookups.In:Proceedings of ACM SIGCOMM'97.France,ACM,1997
8 Srinivasan V,Varghese G.Fast Address Lookups Using Controlled Prefix Expansion.In:Proceedings of ACM SIGMATRICS'98.Madison USA,ACM,1998
9 Lampson B,Srinivasan V,Varghese G.IP Lookups Using Multiway and Multicolumn Search.In:Proceedings of INFOCOM'98.San Francisco USA,IEEE,1998

[摘要] 文章介绍了几种实用化的快速IP流分类技术，如：三重内容寻址、基于比特向量的多维范围匹配、有向非循环图、交叉乘积和递归流分类算法等流分类技术，并根据各种流分类技术的不同应用场合，给出了设计分类算法的原则。

[关键词] 因特网 TCP/IP协议 数据流分类

[Abstract] Some practical high－speed TCP/IP flow classification techniques, such as the Ternary Content Addressable Memory, Multi－Dimensional Range Matching based on bit vector, Directed Acyclic Graph Algorithm, Cross Producting, Recursive Flow Classification Algorithm techniques etc., are described. According to the specific applications of different flow classification techniques, principles for designing relevant algorithms are presented.

[Keywords] Internet TCP/IP protocol Data flow classification