基于范围元组搜索的在线包分类方法

摘要

本发明公开了一种基于范围元组搜索的在线包分类方法，包括数据结构构建方法、数据包分类查找方法和分类规则更新方法；本发明利用哈希函数保证了规则更新常数级的时间复杂度，实现了分类规则的快速更新；本发明将规则映射到少量范围元组上，在保证规则更新速度的同时大大提高了数据包的分类速度；本发明能够很好的将数据结构存储于片上存储器中，从而减少片内存储内容的切换，提高方法的性能。

权利要求

1.一种基于范围元组搜索的在线包分类方法，其特征在于，包括数据结构构建方法、数据包分类查找方法和分类规则更新方法；

所述数据结构构建方法包含以下步骤：

1)按照规则的每个维度，分别计算随着某一维度字段长度的增长规则数量的累计分布曲线；并根据该曲线斜率定位聚类点；

2)连接每个维度中相邻的聚类点，相邻的连接聚类点称为一个小范围；若某一聚类点没有相邻的聚类点，则该聚类点自身称为一个小范围；

3)合并每个维度中相邻的两个小范围；

4)向后对齐合并后的小范围成为一个范围，确保所有范围的并集覆盖规则集中所有的规则；

5)根据每个维度划分的范围，组成若干个范围元组，所述范围元组满足：a)所有范围元组无交集，b)所有范围元组合并能覆盖整个规则集的空间范围；

每个范围元组对应一个哈希表，用于存储映射其中的规则；

所述数据包分类查找方法包含以下步骤：

1)根据匹配规则，在每个维度抽取数据包头信息；

2)将上述信息在每个哈希表中进行哈希查找；

3)比较所有匹配规则的优先级，选取优先级最高的规则，对数据包执行相应操作；

所述分类规则更新方法包含以下步骤：

1)根据待更新规则的每一维度的长度确定该待更新规则所属的哈希表；

2)在该哈希表中更新该待更新规则。

2.根据权利要求1所述的基于范围元组搜索的在线包分类方法，其特征在于，向后对齐合并后的小范围成为一个范围的方法为：如果两个小范围之间的间隔差距不超过D，并且合并后范围跨度小于S，则合并该两个小范围。

3.根据权利要求2所述的基于范围元组搜索的在线包分类方法，其特征在于，D＝2；S＝

8。

说明书

基于范围元组搜索的在线包分类方法

技术领域

[0001] 本发明涉及数据包分类技术，特别是一种基于范围元组搜索的在线包分类方法。

背景技术

[0002] 包分类是交换机、路由器和其他网络设备中用于支持安全性、QoS和高级功能的基本操作之一，其中数据包在分类器中根据多字段规则集进行匹配。在传统的网络应用中，规
则保持相对静态。因此，离线构建的分类器通常拥有设计精良的数据结构，这类分类器可以
实现高效的数据包分类，且由于规则更新不频繁，分类器可以离线构建。

[0003] 软件定义网络(SDN)的出现为网络创新提供了巨大的机会，以使网络支持新的特性和增值功能。这些功能包括流量工程、网络功能虚拟化(NFV)和高性能云计算的支持。然
而，这些新功能除了依赖于基本的快速包分类外，还依赖于分类器中规则的动态更新能力。
一方面，网络应用必须对大量的用户和请求进行即时响应，使得分类器规则必须频繁更新，
以满足不同的需求。另一方面，网络功能的常规迁移或变更总是会改变拓扑结构和策略，从
而分类器的规则必定会有相应的更新。因此，快速的规则更新对于当前的分类器是绝对必
要且有意义的。

[0004] 尽管包分类非常重要，并且已经吸引了很多研究者的关注，但是现有的算法往往不能同时满足上述两个要求，即快速包分类的同时支持快速规则更新。基于决策树的算法，
如HyperCuts、EffiCuts和SmartSplit，都能实现快速的包分类，但不能实现快速的规则更
新。基于哈希的算法，如在Open vSwitch(OVS)中使用的元组空间搜索(TSS)，可以实现快速
更新规则但不能实现高速包分类。PartitionSort(PS)和TupleMerge(TM)可以提升包分类
的速度但都牺牲了规则更新的性能。同时实现快速的包分类和规则更新是满足先进的网络
管理和高性能云计算的新需求和基本挑战之一。

[0005] 现有的高性能数据包分类方法由于复杂的数据结构，不利于分类规则的快速更新，从而无法满足当前大量网络应用在线频繁更新策略或规则的需求。

[0006] 现有的支持规则快速分类的数据包分类方法，虽然可以提供分类规则的在线更新，但是其数据包分类速度达不到大部分网络功能的需求。

[0007] 包分类模块通常会被部署在FPGA、TCAM或其它专用芯片上。而这类芯片的片上存储器大小往往比较小。现有包分类方法所设计的数据结构占有较大的运行内存，或者运行
内存非常不稳定(随规则的种类有较大波动)。

发明内容

[0008] 本发明所要解决的技术问题是，针对现有技术不足，提供一种基于范围元组搜索的在线包分类方法，实现分类规则的快速更新，在保证规则更新速度的同时大大提高数据
包的分类速度。

[0009] 为解决上述技术问题，本发明所采用的技术方案是：一种基于范围元组搜索的在线包分类方法，包括数据结构构建方法、数据包分类查找方法和分类规则更新方法；‑

[0010] 所述数据结构构建方法包含以下步骤：

[0011] 1)按照规则的每个维度，分别计算随着某一维度字段长度的增长规则数量的累计分布曲线；并根据该曲线斜率定位聚类点；‑

[0012] 2)连接每个维度中相邻的聚类点，相邻的连接聚类点称为一个小范围；若某一聚类点没有相邻的聚类点，则该聚类点自身称为一个小范围；

[0013] 3)合并每个维度中相邻的两个小范围；

[0014] 4)向后对齐合并后的小范围成为一个范围，确保所有范围的并集覆盖规则集中所有的规则；

[0015] 5)根据每个维度划分的范围，组成若干个范围元组，所述范围元组满足：a)所有范围元组无交集，b)所有范围元组合并能覆盖整个规则集的空间范围；

[0016] 每个范围元组对应一个哈希表，用于存储映射其中的规则；

[0017] 所述数据包分类查找方法包含以下步骤：

[0018] 1)根据匹配规则，在每个维度抽取数据包头信息；

[0019] 2)将上述信息在每个哈希表中进行哈希查找；

[0020] 3)比较所有匹配规则的优先级，选取优先级最高的规则，对数据包执行相应操作；

[0021] 所述分类规则更新方法包含以下步骤：

[0022] 1)根据待更新规则的每一维度的长度确定该待更新规则所属的哈希表；

[0023] 2)在该哈希表中更新该待更新规则。

[0024] 向后对齐合并后的小范围成为一个范围的方法为：如果两个小范围之间的间隔差距不超过D，并且合并后范围跨度小于S，则合并该两个小范围。

[0025] 与现有技术相比，本发明所具有的有益效果为：

[0026] 1)本发明利用哈希函数保证了规则更新常数级的时间复杂度，实现了分类规则的快速更新；

[0027] 2)本发明将规则映射到少量范围元组上，在保证规则更新速度的同时大大提高了数据包的分类速度；

[0028] 3)本发明能够很好的将数据结构存储于片上存储器中，从而减少片内存储内容的切换，提高方法的性能。

附图说明

[0029] 图1为本发明范围元组划分流程图；

[0030] 图2为本发明包分类流程图；

[0031] 图3为本发明规则更新流程图；

[0032] 图4(a)为与表1中的规则相对应的长度元组；图4(b)为范围元组划分图；

[0033] 图5为规则中源地址和目的地址前缀长度的累计分布函数。

具体实施方式

[0034] 范围元组是一种特殊的元组，其每个元素代表的是规则相应字段的长度范围。相较于TSS中的元组(a,b,c,…)中每个元组代表的是相应字段的比特长度，本发明中的范围
元组(A,B,C,…)中的每个元素则是代表了一个长度范围。每一个范围元组对应一个哈希
表，哈希表存储该范围元组能覆盖的所有规则。为了用哈希函数来索引规则，每一个哈希表
都需要规定其哈希键的长度。一种自然的方法是连接规则所有的匹配域作为哈希键。然而，
不同的规则可能对应于不同长度的匹配字段，而实际中一个哈希表中的规则需要相同长度
的哈希键。为了解决这个问题，本发明进一步引入了基元组的概念。更具体地说，对于范围
元组中的每个范围，选择其下界作为基元组的分量，用于限制连接哈希键时相应字段所截
取的长度。因此，当每个哈希表与一个范围元组相关联时，它必定也与一个基元组相关联，
而该基元组实际上就是该范围元组包含的规则长度的下界。

[0035] 为了实现快速的包分类。首先我们将规则集映射到范围元组，因此需要先将规则集划分为少量范围元组(步骤见图1所示)，并将规则存储在范围元组对应的哈希表中。

[0036] 建了数据结构之后，就可以用来进行分类数据包了(具体步骤见图2所示)。在分类过程中，可能会存在需要更新的规则，包括增加规则或删除规则(具体更新规则的步骤见图
3所示)。

[0037] 图2中，当接收到数据包时，分类器需要搜索每个哈希表以找到最佳匹配规则。一个数据包可能与多个规则相匹配，此时就需要根据规则的优先级来确定最终的匹配规则。
在初始化时，每一个哈希表都会设置一个优先级为0的傀儡规则。作为基本方案，所有的范
围元组哈希表按照顺序被搜索，并记录具有最高优先级的匹配规则。在搜索完所有哈希表
之后，分类模块要么返回具有最高优先级的匹配规则，要么报告没有匹配规则。

[0038] 图3中，当更新分类规则时，首先根据待删除或插入的规则确定其映射到的哈希表。然后，计算根据连接成的哈希键计算其哈希值，找到规则应该删除或插入的相应位置，
并删除或插入该规则。

[0039] 虽然使用哈希函数进行包分类非常有效，但不同优先级的多个匹配规则的存在以及规则重叠和哈希冲突会严重影响性能。为了进一步提高分类性能，本发明提出了两种优
先级排序的优化方法：(1)哈希表优先级排序。首先定义哈希表的优先级为哈希表中包含规
则的最高优先级。其次，根据哈希表的优先级从高到低的顺序，对哈希表进行排序。在这种
顺序下，一旦数据包找到优先级不小于下一个哈希表优先级的匹配规则时，接下去的搜索
就没有意义，对于数据包的分类过程也可以终止。当两个哈希表具有相同的优先级时，则根
据它们的基元组的模从大到小排序。具有较大模的基元组的哈希表具有高优先级的规则一
般更多，因为其规则具有相对较长的前缀。(2)重叠规则优先级排序。由于哈希冲突或规则
重叠，一个哈希值可能对应于多个规则。为了减少进一步验证的时间，在规则插入期间根据
重叠规则或冲突规则的优先级将规则从高优先级到低优先级排序。在不需要检查所有重叠
规则的情况下，一旦找到匹配规则，验证就可以立即停止。

[0040] 将完整的规则集划分为多个范围元组空间，那么这些范围元组空间需要满足两个条件：1)所有范围元组空间的并集必须覆盖所有匹配规则，任何规则都可以映射到某个范
围元组空间里；2)每个范围元组两两互不相交，使得每个规则只能映射到一个范围元组空
间里。本发明的划分策略遵循如下原则：1)范围元组的数量应该尽可能少，2)哈希表中重叠
规则的数量应该尽可能少，3)映射到范围元组的规则的各字段长度应尽可能接近其相应的
基元组。

[0041] 本发明的划分策略，首先把规则按照每一个维度进行投影，在每一个维度上依据规则的分布进行单维的范围划分。每一个维度的划分主要有如下几个步骤组成：1)定位聚
类点，2)连接相邻聚类点，3)合并临近小范围，4)对齐范围。

[0042] 表1为一个样例规则集(分类器)。该样例分类器包含10个规则，每个规则由四个字段组成。其中源地址和目的地址是匹配域，假设每个字段的最大长度为5比特。优先级字段
在数据包与多个规则匹配时给出选择的标准，而指令字段是规定匹配该规则后需要执行的
操作。对于包分类，即是将数据包头域与规则匹配域匹配并执行相应指令的过程。在这个样
例分类器中，每个规则只有两个匹配域(源地址与目的地址)用于与传入数据包的匹配。

[0043] 表1样例分类器

[0044]

[0045] 图4(a)中绘制了与表1中的规则相对应的长度元组，每个长度元组都可以用一个点来表示。假设将范围元组划分为图4(b)所示，并用灰色矩形表示，每一个范围元组对应一
个哈希表，哈希表存储该范围元组能覆盖的所有规则。范围向量对应的哈希表信息如表2所
示。

[0046] 表2样例分类器的范围元组及包含的规则

[0047]

[0048] 以源地址和目的地址为例，观察规则匹配字段前缀长度组合的分布情况。图5是一个样例分布，根据图5，源地址字段可以得到如下范围划分。

[0049] 首先把规则按照每一个维度进行投影，在每一个维度上依据规则的分布进行单维的范围划分。还是以源地址和目的地址字段为例，首先将规则投影到源地址字段，然后沿着
源地址维度划分范围向量。在目的地址维度也是同样操作，先投影，再沿着目的地址维度划
分范围向量。每一个维度的划分主要有如下几个步骤组成。

[0050] 1)定位聚类点。所谓聚类点，就是大多数规则在该维度上长度的投影点。为此，本策略计算该维度对应的累计分布函数在每个可能的前缀长度处的导数，然后选择导数值大
于平均斜率(连接开始点和结束点的直线的斜率)的整数点。这些点代表的是在该维度上，
以该数值为长度的字段前缀对应的规则很多。换言之，规则集中的规则在该维度上的投影
主要集中在这几个点。以图5中的源地址为例，这些聚类点有12、14、15、16、17、23、24、25、
26、30、31和32。

[0051] 2)连接相邻聚类点。连接相邻的聚类点称为一个小范围，如果某个聚类点没有相邻的其它聚类点，那么它自成一个小范围。此处，还需要添加一个最小长度的范围，以覆盖
所有规则(根据规则集而定)。在本例子中，这些聚类点可以连接为如下小范围[12,12]、
[14,17]、[23,26]、[30,32]和最小长度范围[0,0]。

[0052] 3)合并临近小范围。合并两个相邻范围，如果它们之间的间隔差距不超过D并且合并后其范围跨度小于S。这些限制条件的目的是为了限制规则重叠的数量过高。在本例中，
策略设置D＝2以确保两个小范围尽可能接近，设置S＝8为了确保规则之间的重叠数量尽量
少。更多标准可以被引入来用于设置这些参数。因此，根据本例的参数设置，可以得到合并
后的范围[0,0]、[12,17]、[23,26]和[30,32]。

[0053] 4)对齐范围。对齐范围以确保整个范围空间能够包含规则集中所有的规则。在本例中，在对齐范围后得到最终的在该维度上的范围划分为[0,11]、[12,22]、[23,29]和[30,
32]。