数据包的分类刘杰 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(W d)，F d树具有W的深度，因此需要花费O(W)来搜索。

F d-1树也具有W的深度，在这里每个节点有一个F d树。

F d-1树在最坏情况下的搜索时间也因此是Q(W2)。

归纳起来，时间复杂度就变成了O(W d)。

增加的更新能够被实现在O(d2W)以内因为每一个更新的规则都被精确的存储在一个最大深度为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(N d dW)）为代价把查询时间复杂度减少到了只有O(dW)，因为一条规则有可能被复制高达N d次。

而更新复杂度依旧是O(N d)。

3.2.3网格查找树。

Srinivansan et al建议使用网格查找树来进行二维的分类。

它能够减少存储复杂度到O(NdW)，就和分层查找树一样。

然而通过提前计算和在一些F2树的结点中存储所谓的交换指针而仍然维持查找时间复杂度在O(dW)。

在上面已经提到，集合修剪树的F1树的结点复制属于它的祖先的规则。

这个过程也可以被解释成，F1的树结点融合了它的祖先的F2的树结点而变成它自己的F2树。

例如，在图3.4中A结点的F2树的R7被复制了3次。