数据包的分类

刘杰 111220065 引言：

传统上，网络路由器通过同样的方式处理到来的数据包来提供最大努力地服务。随着新应用的出现，网络服务供应商希望路由器向不同的应用提供不同的服务质量（QoS）级别。为了满足这些服务质量(QoS)需求，路由器需要实现新的机制，例如许可控制，资源预约，每个数据流的排队，和均衡调度。然而，要实行这些机制的先决条件是路由器要能够对进入的数据流量进行甄别并分类成不同的数据流。我们称这些路由器为流量感知的路由器。一个流量感知的路由器与传统路由器的区别是，它能够持续地跟踪通过的流量并且针对不同的流量应用不同级别的服务。

所有的流量通过不同的规则来加以指定，每一条规则都是由一些通过用特定的值与分组字段进行比较的操作组成。我们称一个规则的集合为分类器。它的形成主要基于一些标准，而这些标准将要用来将不同的数据包分类到一个给定的网络应用。既然一个分类器要定义数据包的属性或者内容，那么数据包分类就是一个识别某个规则或者一个数据包符合或匹配的规则集合的过程。为了详细说明一个具有数据包分类能力的流量感知路由器所提供的各种各样的服务，我们运用了一个在表3.1中展示的示例分类器。假设在图3.1中显示的示例网络中，这个分类器被安装于路由器R中。

  在示例分类器中只有四条规则，路由器X提供以下的服务：

数据包过滤：规则R1阻塞所有从外部进入网络A的远程登录连接，其中A可能

是一个私有的用于研究的网络。

策略路由：在网络B到D的通过图3.1底部的ATM网络的应用层中，规则R2

能够利用实时传输协议（RTP）让路由器传送所有的实时通信量。

流量监管：规则R3由C到B的所有传输协议（TCP）的流量速率不超过

10Mbps。

有关规则、分类器和包分类的正式描述是在Lakshman 和Stiliadis的工作中给出

的。我们将在整章中运用这些符号和名词。

1、一个分类器C由N条规则组成。Rj, 1 ≤ j ≤ N，在这里Rj由三部分组成：

(a)一个正则表达式Rj[i], 1 ≤ i ≤ d,位于每一个包的d个头部字段中。 (b)数字Pri(Rj)，指明了分类器中相应规则的优先级。 (c)一个功能说明，以Action(Rj)的形式出现

2、一个到来的带着头部报文的d元组数据包P(P1,P2,...,Pd)被称为是与Rj相匹配的，当且仅当Pi和Rj[i]匹配，1 ≤ i ≤ d。

3、考虑一个到来的包P和这个d元数组，这个d维的包的分类问题就是要在所有与这d元组匹配的规则Rj中，找到一条具有最高优先级的规则Rm。正如图3.2所示，一个包的头部由32位的IP源地址，32位的目标地址，16位的源端端口号，16位的目的端口号和8位的协议类型组成。包的头部是用来与分类器中的规则匹配的，具有最高优先级的规则将被选择并且相应的行为会被施加于这个包。

在表3.1的示例分类器中，每条规则在从网络层到应用层的包头部域中有5条正则表达式。每个表达式可以是一个前缀/长度或运算符/号码格式的说明。这个前

缀/长度的说明与在IP查找中有相同的定义。然而这个操作符/号码可能会更加的通用，比如等于23，它的范围是从256到1023，并且大于1023。并且允许插入一个通配符来匹配任何值。注意在表3.1中的R4将会匹配任何进入的包，因为它的全是通配符的说明。这意味着当一个包同时匹配R4和其它的规则时，这些规则的优先级说明都会生效。

假设有一个规则的集合C= Rj(1 ≤ j ≤ N)，并且每个规则Rj都有d个不同的域。这些域被标记为Fi(1 ≤ i ≤ d)并且Rj被表示成{Rj1,Rj2,...,Rjd}。表3.2展示了一个在4个域中带有7条规则的分类器的例子。开始的两个域，F1和F2是在前缀部分规定的，最后的两个域，F3和F4是在范围部分说明的。最后一列展示了与规则相对应的行为。F1和F2通过运用树或者第二章中的TCAM而被更加高效的处理，通过将数字映射到不同的范围然后进行范围检查，这将在本章的

后面几节中描述。这7条规则按照优先级递减的顺序列出，也就是说，R1具有最高优先级。这个规则集将会被用来阐明稍后描述的一些算法。

几个性能的度量将会被用来比较和分析数据包分类算法：

搜索速度：高速的链接需要快速的分类。例如，假设一个最小长度为40字

节的IP数据包，10Gbps的链路能够携带31250000个数据包每秒。这个

分类器的时间被在32ns以内。

存储需求：小的存储需求意味着快的内存访问速度和较低的能量消耗。这对

于基于缓存的软件算法和基于SRAM的硬件算法来说是很重要的。

分类器大小的可扩展性：分类器的大小由应用所决定。对一个开展短流程识

别的地铁/边缘路由器，流量的数量在128k到1百万之间。连接速度增加这个值也会增加。

头部域数量的可扩展性：随着更多复杂的服务被提供，更多的头部域需要被

添加进来。

更新时间：当分类器改变时，例如一个条目被删除或加入，这个数据结构就

需要被更新。一些服务比如说短流程，需要较短的更新时间。否则分类器的性能就会降低。

规范的灵活性：算法解决宽范围规则说明的能力，比如说，前缀/长度，操

作符/号码和通配符，让它能够运用在不同的情形中。

线性搜索对于包的分类来说是最简单的算法。规则集能够按照成本递增的 方式被组织成数组或链表。考虑一个到来的包的头部，这些规则将会被一个接一个的检查，直到某个匹配被找到。对于一个有N条规则的分类器，它的存储和查询时间复杂度都是O(N)，使这种方案对于大的规则集来说是不可实行的。

许多有效的包分类方案已经被提出来并且将在接下来的几节中描述。 3.2基于树的分类 3.2.1分层查找树

分层查找树是一维树结构到树结构的简单扩展，每一维都代表了一个域。它也被叫做多级树，回溯查找树，特里结构树。

规则的存储组织 。一个代表了表3.2中规则集C的头两个域的二叉分层查找树如图3.3所示。在这里我们只考虑F1和F2，因为它们是前缀部分并且能够利用树来简单的处理。其中椭圆形的结点属于F1的树，圆形的结点属于F2的树。粗体的弯曲的箭头代表了下一棵树的指针。要说明的是这里有4个F2的树结点因为我们在C的F2域中有4个不同的前缀。每个灰色的结点用一个规则Rj标示，它意味着如果这个结点在搜索中被搜索到了，那么Rj就被匹配了。总的来说，分层查找树能够按照以下的方式被构造：一个二进制的根树，被称作F1的结点为所有规则中的F1域的前缀集合{Rj1}而被首先构造。第二步，对任一个在F1结点中的前缀p，一个d-1维的分层超找树Tp为那些在F1域中精确指定p的规则所递归的被构造。也就是一个规则的集合{Rj|Rj1= p}，树Tp通过一个存储在p中的指向下一颗树的指针而被连接到p。

分类方案。对进入的带有头部(v1,v2,...,vd)的数据包的分类应该按照以下的步骤执行：查找算法查找基于v1的F1树；如果遇到指向下一颗树的指针，算法就沿着这个指针然后递归的查找接下来的d-1维的树。

对于上述的规则集C，考虑一个到来的包（001,110），搜索过程将从F1树开始来找到与“001”匹配得最好的前缀。在到达F1树中的“D”结点之后，指向下一颗树的指针将被用来引导算法进入F2树来找到所有与“110”匹配的前缀。很显然R1和R2都被找到了；然而，只有R1被记录了，因为它具有最高优先级。现在搜索过程回溯到结点“B”，它是F1树中结点“D”的最低一级的祖先。再

一次，我们将利用指向下一颗树的指针来搜索F2树。这个过程一直重复直到再也没有“D”的祖先结点可以被用来搜索。在这个例子中，搜索过程在结点x处结束，并且在图3.3中整个行进路径都用虚线描绘出来了。在遍历中，共发现3个匹配的规则，R1，R2和R6。R1作为匹配到的具有最高优先级的规则被返回。回溯过程是需要的因为进入的包中的“001”可能在第一个域中与多个前缀相匹配，并且我们也无法提前知道哪一个F2树包含与“110”匹配的前缀。此外，所有的匹配都必须找出来，以确保返回的是具有最高优先级的规则。

性能评价。分层查找树是最能节省存储空间的算法之一。对一个具有N条规则的集合，其中的每一个规则都有d个子域，并且每个域的最大长度是W，那么存储复杂度就是O(dW)。这个数据结构是简单的并且容易在较长的搜索时间开销中保持稳定。遍历树的过程中会带来回溯来找到所有相匹配的规则，因为它们的优先级不能被这个数据结构很好的反映。它的搜索时间复杂度是O(Wd)，Fd树具有W的深度，因此需要花费O(W)来搜索。Fd-1树也具有W的深度，在这里每个

节点有一个Fd树。Fd-1树在最坏情况下的搜索时间也因此是Q(W2)。归纳起来，增加的更新能够被实现在O(d2W)以内因为每一个更时间复杂度就变成了O(Wd)。

新的规则都被精确的存储在一个最大深度为O(dW)的一个地方。 3.2.2集修剪树

集修剪树是分层查找树的一种修改版。在一个集修剪树的查找过程中回溯能够被避免。

规则的存储组织。在一个集修剪树中，每一个树结点（具有有效的前缀）复制它的祖先结点规则集的所有规则到它自己的规则集中然后基于新的规则集构造下一维的树结构。

一个表示集合C(表3.2)中规则的F1和F2域的二维集修剪树的例子如图3.4所示。要说明的是在图3.3中F1树的结点A，B和D的规则分别是{R7},{R4,R5,R6}和{R1,R2}。然而在图3.4中，它们是{R7},{R4,R5,R6,R7}和{R1,R2,R4,R5,R6,R7}，这里的规则已经被复制了。

分类方案。搜索过程对于一个由d个连续的最长的前缀组成的d元组来说，在集修剪树的每一维上都要匹配。考虑一个二元组，(001, 110)，在图3.4中查询路径用虚线描绘了出来。R1作为匹配到的具有最高优先级的规则而被返回。沿着这条路径会遇到许多规则并且具有最高优先级的规则会被记录下来。路径上的R2结点应该包含规则R2和R6，但只有R2被保存了因为它的较高的优先级。 性能评价。分层查找树需要回溯因为与F1树结点相关的规则集是彼此分离的。而集修剪树消除了这种需求并且以增加存储复杂度（O(NddW)）为代价把查询时间复杂度减少到了只有O(dW)，因为一条规则有可能被复制高达Nd次。而更新复杂度依旧是O(Nd)。

3.2.3网格查找树。

Srinivansan et al建议使用网格查找树来进行二维的分类。它能够减少存储复杂度到O(NdW)，就和分层查找树一样。然而通过提前计算和在一些F2树的结点中存储所谓的交换指针而仍然维持查找时间复杂度在O(dW)。在上面已经提到，集合修剪树的F1树的结点复制属于它的祖先的规则。这个过程也可以被解释成，F1的树结点融合了它的祖先的F2的树结点而变成它自己的F2树。例如，在图3.4中A结点的F2树的R7被复制了3次。假设属于结点B的F2树被表示成F2-B-trie，在图3.3和3.4中两个F2-B-tries的唯一的不同就是结点R7在集合修剪树中被复制了。现在取代结点复制的是一个用'0'标记的转换指针被包含到结点x，中并且在F2-A-trie中指向结点R7正如图3.5所示。这个转换指针用虚线的弯箭头描绘。事实上，这个在结点x，中用'0'标记的转换指针代替了在集合修剪树中的0-指针。

如果一棵分层查找树和一棵集合修剪树已经为一个分类器C建立好了，C的

网格查找树结构就能够通过与集合修剪树相比较而添加准换指针到分层查找树。一个标记为0或1的转换指针ps被插入到结点y，不管在何时只要它在集合修剪树中的副本包含了一个指向另一个结点z的0/1指针而y不包含这个副本。结点z或许在分层查找树中有好几个副本，但ps只指向在F2树中的一个结点，这个结点是离包含结点y的F2树最近的一个点。例如，在图3.4和图3.5中的x和x'结点都是图3.4中x''结点的副本。然而，在结点y中转换指针指向了x'因为结点B比结点A里结点D更近。如果把转换指针看做和0/1指针一样，那么这个查找过程就和集合修剪树一样了。

这个网格查找结构在查找事件和存储复杂度上都表现得很好，但是增量更新比较复杂因为几个指针可能指向一个结点。如果这个结点将要被删除了，一些新的结点就需要被创建并且这些指针也需要更新指向这些新增的结点。

3.2.4扩展的二维方案

Baboescu et al.为核心路由器介绍了一种新奇的分类方法EGT-PC。其核心思想就是充分利用他们在核心路由器中发现的规则数据库的特性来降低像2维查找那

样的查找的复杂度。通过观察来自Tier 1 ISP的核心路由器的统计数据，他们发现每个数据包最多匹配一些明显的在规则集中提供的源-目的前缀对(SIP, DIP)。换句话说，如果我们只将规则集运用于源和目标字段，不会有数据包匹配到很多的新的映射规则集合中的规则。要注意这对于单字段来说断然是不对的因为有通配符：当考虑到任何一个部分都是孤立的时，一个单独的包能够匹配成百上千条规则。基于这个特征，他们就发表了一个简单的有关2D分类方法的想法，正如图3.6所示。

这个想法第一次利用任何2D的匹配方法来找到所有的和头匹配的明显的源和目的前缀对(S1,D1),...,(St,Dt)。对每一个特定的对(Si, Di)，都有一个线性数组或者链表，其中含有在源和目的字段包含了(Si, Di)的规则。如图3.6所示：

(S1, D1)包含规则R5,R6,R2和R4。注意每条规则只能和一个源-目的前缀对相关联。另一方面，在搜索过程中可能有一个会希望复制规则来减少考虑到的源-规

则前缀对的数量而最终减少搜索时间。当为一个给定的键查找一条规则，许多的源-目的规则能和这个键匹配。例如，(*, 000)和(1*, 0*)和前缀键(111, 000)相匹配。结果，规则当中每一个和(S, D)对匹配的将会被进一步的搜索而与键中剩下的部分相反。例如，如果(S1,D1)被匹配到了，它的所有规则R5，R6，R2和R4将会被搜索与例如键的端口号相反。 3.2.5字段级的特里分类(FLTC)

一个字段级的特里分类（FLTC）用一个字段级特里（FLT）结构，这个结构被一个字段一个字段地组织在分层结构中。这个分类的数据结构已经被优化了以便于TCAM和多路搜索像期望的那样被应用于前缀和不同的字段。这个查询过程也是一个字段接一个字段进行的。有了正确的实现，每一个查询平均只需要很少的内存访问，也因此能够达到非常高的分类速度。FLTC的内存需求也是非常合理的因为FLT的结点共享属性。尽管结点共享让更新进程前进得稍慢了一点，更新操作的复杂度却保持得很低，因为更新操作只影响数据结构的一小部分。这个FLTC方案能够很容易的支持大型的分类器。例如，具有100000到1000000的规则，也并没有影响查询性能。

这个FLT的数据结构把分类器分成多个字段，每一个用前缀或者范围的格式来说明。图3.7展示了由表3.2中的分类器构造的FLT。FLT被定义为具有如下的属性：

1、

它被一个字段一个字段的被组织在分层结构中。在图3.7中FLT的深度等于d字段的数字。这里由4个级别的结点，被组织成F1到F4。

2、

FLT中的每个结点都有一个规则集，它也是该结点的父亲结点的规

则集合的一个子集。FLT的根节点被定义来在分类器中包含所有的规则。

3、

第i级别的结点a根据它所包含的所有规则的Fi值在第i+1级别上生成它的子结点。根据Fi的说明，这里有两种子结点生成的过程： •如果Fi以前缀的格式说明，a的子节点的编码等于包含在a的规则集中的Fi字段的所有不同前缀数字之和。每个结点都和一个不同的前缀相关联。假设子节点b和前缀p相关联，包含在b的规则集中的规则r的Fi的值就和p一样或者是p的一个前缀。例如，图3.7中的根结点在F1字段中包含所有7条规则和4个不同的前缀，*, 0*, 00*, 和10*，因此4个子节点被生成了。和前缀0*相关联的结点x包含4条规则R4-R7。F4-F6的F1值都是0*，这是相关联的前缀，R7的F1值是*，它是0*的前缀。

•如果Fi用范围的格式说明，我们首先把所有的范围（来自a的规

则集合的Fi字段）映射到一个数轴上并且包含一组间隔。对每个间隔I，一个子结点b被生成，规则r被包含在b的规则集中，当且仅当r的Fi字段说明的范围覆盖了I。例如，结点y生成了3个子结点，结点y'具有间隔[10,10]，它是一个单独的点，结点y'''具有间隔[6,6]，和结点y''具有间隔[4,5]和[7,8]（实际上有两个指针都指向y''），正如图3.7所指出的那样。

4、

结点a在第i级的规则集是所有在第i级的结点的规则集中的唯一。如果在第i-1级的两个结点，b和c，有一个共同的子结点a，

那么只有一个结点a被生成，并且他们共享这个结点。图3.7展示了当一个结点被多个结点指向时结点共享发生的情况。

字段的前缀形式。既然一个字段够用前缀或范围的形式被正常的说明并且每一个说明都有它自己的被支持的数据结构和搜索算法。我们用同样的说明将这些字段组织起来。在大多数情况下，一个分类器有两组字段；第一组用前缀的形式，第二组用范围的形式。在表3.2中，F1和F2在第一组中，F3和F4在第二组中。FLT被组织起来以让第一组的字段出现在较高的级别，第二组的字段出现在较低的级别。

对于只有前缀字段存在的第一组，TCAM能够被用来存储前缀并且在他们之间展开搜索，既然TCAM能够同时适应多个字段，对于字段的第一组的查询能够在一次TCAM访问里完成。图3.8展示了由表3.2中的分类器得来的压缩的FLT。现在对于F1和F2只存在一个级别，在图3.7的第3级最初有根结点的7个子结点。每个第二级的结点都有一个和它相关的F1/F 2前缀对。每个这样的前缀对都是TCAM中一个项的内容。

这个前缀对是从图3.7中的特里结构中得来的。对于图3.7中第3级别的每个结点a，和图3.8中第二级的结点一样，我们找到一条从根结点到a的具有最小前缀长度和的路径。在图3.8中沿着这条路径的前缀形成了与a相关的前缀对。在TCAM中所有的前缀都被安排成按前缀的长度(两个前缀的长度和)降序排列。对于具有相同长度的前缀对，他们的相对顺序可以是任意的。对于在图3.8中压缩的FLT的的TCAM的内容在表3.3中展示。

通过在TCAM中以升序的方式安排前缀对（意味着相匹配的最长的前缀对会被找到），我们能够保证从TCAM得到的搜索结果是正确的。例如，在第二级中的一个适当的结点将决定继续整个查询过程。一个简单的证明如下：

当用一个键A/B来搜索TCAM时，如果两个带有前缀对A1/B1和A2/B2的项被匹配到了，这里就会有两种情形。不失一般性，我们假设A1≺ A2，意味着A1是A2的一个前缀。

•在第一种情形中，B1≺ B2，A2/B2的长度比A1/B1的大，因此，带有A2/B2项作为结果输出。它是正确的因为a（与A1/B1一致）中所有的规则都被包含在结点b（与A2/B2一致）中，这是被FLT的属性所保证的，并且结点b被选择。

•在第二种情形中，B2≺ B1，具有前缀对A2/B1的另一个项一定存在，这是FLT的产生过程所保证的。因为A2/B1的长度比A1/B和A2/B2的长度都大，

带有A2/B1的项将作为结果输出。它是正确的因为结点a和c的所有规则都包含在结点c（与A2/B1一致）中。

以上的结论能够很容易的被推广到具有超过两个的多个前缀字段。考虑一个将要被分类的数据包的报头，属于第一组的字段被提取出来并且提供给TCAM以供搜索。从TCAM的输出预示着在第二级的一个结点下次将被访问。因为TCAM已经顾及到了所有的前缀字段，所以剩下的查询过程完全依赖于范围字段。

范围说明的字段。对于在第二个或跟低级的结点，我们假设在每个结点用一个多路搜索树来组织数据结构。例如，在这个扁平的FLT的第i级的一个结点a，当在把a中的规则集中规则的Fi字段映射到一个数轴之后，7个间隔I1-I7，随着8个结束点E1-E8被包含。如图3.9a所示。如果我们用一个3路搜索树来组织这个间隔，结果如图3.9b所示。它是一个两层的树并且有4个块（在FLT中为了避免术语'levels'和'node'的混淆，我们在k路搜索树中用术语'layer'和'block'）。每一个快都包含至多k个指针和k-1个点，在内部块里的指针指向k路搜索树中的另一个块，同时在扁平的FLT中叶块中的指针指向第i+1级的结点。我们用一个例子来阐明在k路搜索树中的搜索过程。假设在间隔I3中存在着指针P，搜索过程

从根块x开始，通过比较P和存储在x中的结束点E3和E6，我们知道在他们中的顺序是E3< P < E6，一次第二个指针符合第二层中的块y。同样的，通过比较P和结束点E4和E5，我们知道和间隔I3相关联的指针应该指向FLT中下一层的某个节点。

这个多路搜索对于范围查找来说是一个很有效的算法。一个k路搜索树的层数能够由logkM决定，在这里M是间隔的数量。从实现指针的角度来看，在k路搜索树中的每一个块都是存储在内存中的一个基本单元，对于每次读/写都需要一次内存访问。因此在一个搜索过程中，内存访问的次数等于这个k路搜索树的层数，这里是logkM，这里的数字k被块的大小所，是由内存的宽度所决定的。

一个FLT的查找过程从所有前缀字段的TCAM开始。到了范围字段之后，这个查找过程一次开始一个级别（或一个字段），并且在每一级上，一个k路搜索都会被执行来找到下一级将要访问的结点。当到达一个叶子结点时搜索过程就会终止并且一个匹配到的规则（如果存在）将会作为结果返回。