报文ACL算法之HyperSplit Tree建树性能优化

个人介绍：

黄鹏，目前就职于某网络安全公司，主要工作内容是DPDK应用程序性能调优，从事过企业级路由器维护与开发；面对问题衷于也善于求真，探求事物本质。

1.引言

今天主要分享：基于超分裂树的包过滤算法，在建树过程的算法优化方案和成果分享。

最近一段时间，主要忙着工作上的事情去了，差点深陷爬不起来；想着目标与机会，任务是必须要站着完成的，当然最后还是给出了有效输出。但是呢，就是自己一直心心念念的那个小玩意儿，暂停了有两周多了。

接下来，接着上一次DPDK之__rte_cache_aligned代码调优文章的故事源起继续讲，小系统完成整体的控制面和转发面基本流程编码完成后，CPU相关打桩代码也完成后，然后就是加上ACL（access control list）功能到小系统中去。

ACL（access control list访问控制列表）是一种基于包过滤的访问控制技术，它可以根据设定的条件对接口上的数据包进行过滤，允许其通过、丢弃或者其他动作。访问控制控制列表被广泛的应用于路由器和三层交换机，借助于访问控制列表，可以有效地控制用户对网络的访问，从而最大程度地保障网络安全。

路由器、交换机或者传统防火墙设备上，报文经过设备时基本都有这些功能需求：

• 1、 支持基于目的MAC、源MAC

• 2、 支持基于源IP、目的IP

• 3、 支持基于源端口、目的端口

• 4、 支持IP报文协议类型

• 5、 支持vlan

• 6、 支持时间段

• 7、 或者以上的任意组合进行报文过滤

常见的标准ACL则是基于IP地址子网段进行过滤的，扩展ACL则包含更多的报文特征（MAC地址、IP地址、端口、协议等）。

路由器、交换机和传统防火墙设备，根据其放在网络拓扑中的位置不同，对应称谓也不同，一般有集中式、汇聚和核心三种称谓，设备的吞吐性能的要求也是递增的，抛开流平台后，在报文最短路径上，报文的转发效率很依赖于路由表和ACL的查询效率；其次，除了报文吞吐外还有ACL容量上的规格要求，客户当然是觉得支持越多越好。因此，评估一个ACL算法的好坏，主要有这几个维度：查询效率、插入/删除效率、内存占用率。

目前，相关知识网上，能够看到各种ACL算法主要有这些：

• 1、 WOO

• 2、 TSS

• 3、 基于空间划分的算法：HiCuts、HyperCuts、HSM以及它们的优化算法（本文即将要介绍的算法超分裂树就是基于空间划分的）

• 4、 基于trie树的算法

之前有幸接触到超分裂树算法，通过GitHub找到了算法思想的出处吧（应该没找错：Packet Classification Algorithms From Theory to Practice，相关链接附在文章末尾）。

2.HyperSplit 算法概要

在讲述算法优化内容前，还是有必要说下算法的主要思想和算法基本实现原理，有助于理解本次所要讲述算法优化的内容。

2.1. HyperSplit算法思想

数据包分类的目的是通过将一组规则应用于数据包的头字段来对数据包进行分类。每个规则R有F个分量，规则R的第f个分量，称为R[f]，是数据包头的第f个字段上的范围匹配表达式。一个数据包 P 被称为匹配一个特定的规则 R ，如果 f ∈[1, F]，P 的头的第 f 个字段满足范围表达式 R[f] 。如果报文P匹配多个规则，则返回优先级最高的匹配规则。

在数学上，数据包分类可以看作是计算几何中的一个点定位问题。一个包头的F域中所有可能的值形成一个F维的搜索空间S，每个包P可以看作是位于S中的一个点。规则 R 的表达式 R[f] 指的是搜索空间第 f 维中的一个范围，所有由 R 指定的范围组成一个 F 维超矩形。如果数据包 P 与特定规则 R 匹配，则 P 表示的点将落入 R 指定的超矩形中（以上两段均来自原论文翻译）。

2.2. HyperSplit算法策略

原论文在基于HSM和HiCuts这两大类代码算法研究下，提出了自己的报文分类算法——HyperSplit。其使用以下策略构建分类数据结构：

1、空间分解

给定搜索空间 S、字段 f 和一组规则 R 作为输入，HyperSplit 应用以下基于规则的分解策略：首先，将 R 中的所有规则投影到 f 域上，得到 M (2 ≤ M ≤ 2*N + 1) 个端点。然后以增量顺序对这些端点进行排序，并将它们存储在一个临时数组 Pt[i](1 ≤ i ≤ M) 中。每两个连续的端点组成一个范围段，总共有 M - 1 个段，记为 Sg[j](1 ≤ j ≤ M -1)。通过选定的 M 个端点之一与 f 场正交的超平面用于将当前搜索空间拆分为两个子空间（这就是我们使用 HyperSplit 作为所提出算法的名称的原因）。可以采用多种不同的启发式方法来选择终点，以下是其中的三种：

•  Heuristic-1：选择 Pt[M/2]，这种启发式表示段平衡分解，即每个子空间沿 f 字段包含相同数量的段。

• Heuristic-2：选择 Pt[m]， s.t. 与范围[Pt[1], Pt[m]]重叠的规则数为[|R| / 2]，即R中规则数的一半。这种启发式是规则平衡的，因为分解后，每个子空间中的规则数趋于相同。

•  Heuristic-3：假设 R 中有 Sr[j] 规则与段 Sg[j] 重叠。选择Pt[m]，其中m为满足∑m,j=1 Sr[j] ＞1/2∑M,j=1 Sr[j]的最小值。这种启发式被称为加权段平衡策略，因为 Sr[j] 可以被视为段 Sg[j] 的权重。与Heuristic-1相比，加权方案在空间分解中加入了R的重叠信息，因此更有效地平衡了每个子空间的空间复杂度（内存开销，相比于前两者减少约50%）。

2、递归方案

选择局部优化字段以在每个阶段应用分解是 HyperSplit 递归的关键问题。根据空间分解中使用的不同启发式方法，可以通过多种方式实现此目标：

• 对于 Heuristic-1 和 Heuristic-2，由于具有更多端点的字段为局部优化空间分解提供了更多的候选，我们可以选择最大（M 个端点）的字段在每个阶段应用空间分解。

• 对于 Heuristic-3，每个段都有一个权重，因此我们可以选择具有最小 1/M∑M,j=1 Sr[j] 的字段，即沿所选字段最小化所有段的平均权重。

在每个递归阶段，HyperSplit 将两个子空间中的每一个与与其重叠的规则子集相关联。然后将子空间以及规则子集设置为下一阶段递归的输入。当满足以下两个条件之一时，递归终止：

• 与当前搜索空间S相关联的规则集R包含少于T个规则，其中T是预定阈值。当 T > 1 时，使用线性搜索找到最终匹配项。

•  当前搜索空间 S 完全被 R 中的所有规则覆盖。在这种情况下，R 中具有最高优先级的规则是最终匹配（没想明白，为啥还有优先级这种玩意儿）。

2.3. 个人归纳总结

假定规则F域为报文的：源、目的IP，源、目的端口和协议；

假定规则集R为：

规则R	源IP	目的IP	源端口	目的端口	协议
R1	（1，1）	（100，110）	（22，22）	（800，900）	（17，17）
R2	（3，50）	（2，2）	（50，50）	（800，900）	（17，17）
R3	（10，100）	（90，105）	（22，22）	（119，119）	（0，255）
R4	（1，25）	（17，29）	（80，80）	（120，120）	（23，23）

1、 空间分解的主要流程：

• 将R中所有规则投影到某个f域，得到M（2 <= M <= 2*N + 1）个端点。

例如，将所有规则都投影到源IP这个f域上，我们将得到，如下端点。

1，1，3，50，10，100，1，25

总计7个。

注意：起始点1和终点1是代表两个点，同为起点算一个点（铭记）。

• 对这些点，进行升序排列，存储到Pt[i]（1 <= i <= M）数组中。

• 每两个连续的端点组成一个范围段，共有M-1个段，记为Sg[j] (1 <= j <= M-1)。

• 在当前这个f域中选择出一个端点Pt[m]，将当前f域空间拆分为两个子空间，拆分的方式采用Heuristic-3（端点加权，每个端点有对应的权重，权重值为有多少条规则包含当前这个端点【打个样，这个权重值计算方式是今天的主题】）。

2、 递归方案

在步骤1中，是在某个f域中优选出了拆分空间的优选端点，那么每次应该选择哪个f域来进行空间拆分，进而对所有规则进行递归二分拆分。

针对不同端点优选方式，维度的优选方式也不一样，这里主要讲述Heuristic-3对应的f域优选方式：选取1/M * (Sr[1]+...+Sr[M])最小的那个域f作为当前待分割的维度。

注：Sr[j]记录的是每个端点的权重，权重越小，代表当前f域的重叠规则数越少，越适用于分割。

当满足以下两个条件之一时，递归终止：

• 1、当搜索空间包含的规则数量小于T时，递归终止，T是预设的阈值；

• 2、当搜索空间可以覆盖其包含的所有规则时，递归终止。

3.HyperSplit 算法实现

论文的原作者已经给出来该算法的实现代码，并在Github上进行了分享（Github链接地址，在文章末尾附上），算法实现的核心就是构造这棵HyperSplit Tree。大致流程如下：

输入：

1、 本次迭代的规则集

2、 当前HyperSplit树节点

3、 当前HyperSplit树深度

输出：

1、整棵HyperSplit树

过程：

For( dim = 0; dim < DIM_MAX; ++dim)

1、遍历存储当前规则集，投影到dim这个域的所有端点

2、将这些端点进行升序排列

For (pnt_num = 0, i = 1; i < 2 * N; i++)

遍历这些端点，将相同的端点合并成一个端点（去重）

注：相同的端点是指端点的值相同且要么都是起点要么都是终点，如果值相同，但是一个是起点，一个是终点，这算作两个点。

3、通过遍历获取到当前dim域中确定的端点数量pnt_num

4、同当前max_pnt进行比较，如果大于则更新max_pnt（记录的是所有域中pnt_num最大值）

If (pnt_num < 3)

Continue; // 直接进行下一个dim域的映射

//计算去重后的每个端点的权重值

For (i = 0; i < pnt_num – 1; i++)

For (j = 0; j < N; j++)

If (R[j].dim[d][0] <= Pt[i] <= R[j].dim[d][1])

wegiht[i] += 1;

weight_all += 1;

weight_jdg = (float) weight_all / (pnt_num - 1)

if (weight_avg <= weight)

continue;//表示当前dim域不是最优分割域，继续寻找

For (I = 1; I < pnt_num -1; i++)

遍历查找，优选拆分点。

If (weight_sum > (weight / 2.f))

Break;

保存拆分点thresh

保存拆分维度dim

If (max_pnt < 3)

记录相关信息

终止递归

Return;

5、根据拆分点thresh和拆分维度dim，将输入的规则集拆分为左右子规则集，并进行下一步迭代，直到递归结束。

可以看出，为了寻找最优的dim域和最优的分割点，上述算法实现过程的必要的步骤：

• 1、 遍历规则集，初次存储所有端点，时间复杂度：O(n)

• 2、 对所有端点进行排序，时间复杂度：O(nlogn)

• 3、 遍历所有端点进行去重，时间复杂度：O(n)

• 4、 计算每个端点的权重，时间复杂度：O(pnt_num * rule_num)

如果将建树时间作为算法好坏的一个指标，那么该算法每次迭代建树的时间就主要消耗在：计算每个端点的权重。如果能够将其优化成O(nlogn)或者O(n)，那么从理论分析可以得出，建树消耗的时间将会大大减少（可能论文作者已经有了优化思路，只是未公开而已）。而我觉得将其时间复杂度优化成O(n)是可能的。

3.1. 初升

在自己首次实现论文的算法时，统计的是连续两个端点划分的一段的权重值。因为原文中写道：每两个连续的端点组成一个范围段，总共有 M - 1 个段，记为 Sg[j](1 ≤ j ≤ M -1)。然后，就在坐在那里“发呆”，我应该怎样才能做到O(n)的时间复杂度下计算出每个段的权重值（每个分段被多少条规则所包含）。

现假定规则集R在某个dim域上的范围段为：

（1，8）、（4，15）、（6，18）、（11，22）

得到对应排序后的端点集为：

表 1

1	4	6	8	11	15	18	22
0	0	0	1	0	1	1	1

注：0代表原端点为起点，1代表原端点为终点。

我们规定，生成的范围段（a，b）的规则如下：

• 1、 如果a对应原端点为起点，则值维持不变；如果为终点，则a = 原端点值 + 1；

• 2、 如果b对应原端点为起点，则b = 原端点值 – 1；反之维持不变。

因此，上面计算后应该获得如下范围段：

范围段	(1, 2)	(3, 3)	(4, 8)	(9, 10)	(11,15)	(16, 18)	(19, 22)
权重	1	2	3	2	3	2	1

我们可以再仔细观察一下表1中的0，1数值。可以发现：遍历端点的过程中，对“0”出现的次数进行累加，当遇到“1”时，进行累减，得到的序列便是每个范围段的权重，得出如下数据：

端点	1	4	6	8	11	15	18	22
标识	0	0	0	1	0	1	1	1
权重	1	2	3	2	3	2	1	—

瞬间，内心已经开始忍耐不住了，想要实现了，试一把，便有了如下结构的代码：

last = 0;

seg_weight = (Pt[last].flag == 0);

for (last = 0, pidx = 1; pidx < nb_pts; pidx++) {

if (Pt[pidx].flag == 0)

seg_weight += 1;

else

seg_weight -= 1;

if (Pt[last].value == Pt[pidx].value) {

处理pidx + 1 >= nb_pts的情况

continue;

}

···

segment[seg_cnt].start = Pt[last] or Pt[last] + 1;

segment[seg_cnt].end = Pt[pidx] or Pt[pidx] - 1;

segment[seg_cnt].weight = seg_weight;

···

}

结局，不用怀疑了，这个第一个想法，肯定是不对的，但是呢，也不完全是错的。

假定，我们现在拿到的R规则集在某个dim域上的范围段为：

（1，9）、（2，9）、（9，16）

按照之前计算原则，得出的结果如下：

表 2

端点	1	2	9	9	9	16
标识	0	0	1	1	0	1
权重	1	2	1	0	1	—
范围段	(1,1)	(2,9)	(10,16)

到这里，咋一看，感觉还行对吧。参照论文算法，优选的点应该为：

使得Pt[1].weight + ··· + Pt[m] > 1/2 总权重，最小m对应的Pt[m]。

我这里计算的是每个范围段权重，就感觉已经跑偏了。其次还有如下三个问题：

问题1：

总权重=1+2+1，1/2总权重 = 2；那么优选的范围段就是（2，9），这个范围段我应该是去2还是9呢？其实，怎么取都是不对的；因为在某些R规则集的情况下，最后分割左右子空间（a，b）会出现：a > b的情况。

问题2：

对于范围段（2，9），其实应该是包含三个规则集：R1、R2、R3（包含了R3中9这个点），权重应该是3，不是2。

问题3：

前面其实有一直在强调一件事，那就是：何为不同端点。值不同，必定为不同端点，而值相同，就是同一端点吗？不对。一个是起点一个是终点算两个点。因此，范围段还少了一个（9，9）。

接下来，继续胡思乱想，当然也参考了原论文中提供的算法源码。就想着，要不先把范围段划分正确和每个范围段的权重计算正确。

3.2. 云起

对比上述表1和表2中的规则集的差异就是：一个规则集中含有相同值的点，而另外一个没有。解决这个端点权重O(n)的时间复杂度的关键就在于，如何处理规则集中相同值的点，对应的权重值，应该进行怎样校验以及每步计算过程中端点信息如何“传递”。

对应端点值相同的情况下，端点是起点还是终点的情况大致有以下三种情况：

• 1、 均为起点

• 2、 均为终点

• 3、 一个为起点、一个为终点

为了应对上述三种情况，我的思路如下：

• 1、 算法的基调仍然是遇到端点为起点权重+1，遇到终点权重-1；

• 2、 针对情况1，权重+1

• 3、 针对情况2，权重-1

• 4、 针对情况3，我们设定一个标记flag，记录我们在线性搜索所有端点的某个时刻发生过这个情况。

当发生这种情况后，我们首先是记录下Pt[last]和Pt[idx]组成的范围（这是在Pt[last].value == Pt[pidx].value的情况），且临时将权重+1处理，但不更新权重值

那么我们怎么用标记flag来补偿权重值呢？

答：当线性搜索端点集到不满足Pt[last].value != Pt[pidx].value时，我们就开始对权重进行补偿，补偿逻辑是：

• 1、 如果Pt[last]为起点，对权重进行负向补偿：权重值 - = flag

• 2、 如果Pt[last]为终点，对权重进行正向补偿，权重值 += flag

上述给出的处理流程，起始都能很容易的想到，并且是“正确的”（但不完全是）；

• 针对情况1，将权重加1，遇到又一条规则以该端点为起点，当然得加一哇；

• 针对情况2，进行加一，又一条规则以该端点为终点，权重当然得减一；

• 针对情况3，进行更具Pt[last]起止标记不同，进行权重不同的补偿也是对的，Pt[last]为终点；但是，突然又来一条以该端点为起点，当然得对该端点的权重进行加1补偿。

注：至此，我们的算法中端点排序都是只考虑端点值来排序的。

代码实现后，在自我设定的测试用例集下，算法运行正常；且把原论文中核心算法摘取出来进行做对比，端点/范围段的权重值，也都是正确的。

然后，顺利成章的将这个实现移植到具体的HyperSplit整个算法中去了。

设定规则数为50条，域：源、目的端口、协议。

结局：分裂树，确实是生成成功了；但是，但是，不是我想的那样子。50条规则，竟然给我分裂出20K个节点，树的深度都超过了规则数了。

就这···，论文原算法，100条规则：深度15，叶子节点数600多，节点数600多。这个差距，咋就不谈论占用多少内存了，一言难尽。

图 1 修正权重算法后的结果

图 2 论文源码100条规则分裂结果

3.3. 云散

第一反应，当然不用说了。这个权重的算法不普适，仅仅是针对某些情况是正确，这必定导致优选出来的分割端点与域，同原论文中最优的方式出入很大，可能和另外两种（Heuristic-1，Heuristic-2）算法类似了，分割的节点很多，占用的内存很大。

那，那问题在哪里呢？很庆幸的是，我们始终有一份正确的样板，每一次调试都有参照物，来确认我们算法是否正确。

问题根源，还是在处理端点值相等的情况下，对应的处理逻辑。在第二小节中，我们谈到权重补偿的逻辑；但是，这个补偿逻辑只是针对了端点值不等的情况时，才有逻辑。我们可以思考下，端点值相等的情况下，是否也需要类似的逻辑，以及，我应该进行怎样的权重补偿。

下面我们先给出，论文原算法的实现：

端点去重的逻辑实现：

for (pnt_num = 0, i = pnt_num + 1; i < num; i++) {

if (is_equal(&seg_pnts[pnt_num].pnt, &seg_pnts[i].pnt)) {

/* 更新pnt_num端点的起止flag标记 */

        seg_pnts[pnt_num].flag.begin |= seg_pnts[i].flag.begin;

        seg_pnts[pnt_num].flag.end |= seg_pnts[i].flag.end;

        if (i + 1 != num) {

            continue;

        }

        /* 处理最后一个端点的情况 */

if (seg_pnts[pnt_num].flag.begin & seg_pnts[pnt_num].flag.end) {

            seg_pnts[pnt_num + 1] = seg_pnts[pnt_num];

            seg_pnts[pnt_num++].flag.end = 0;

            seg_pnts[pnt_num].flag.begin = 0;

        }

        break;

}

/* 当曾经，出现过一个起点一个终点的情况时，这两个端点都需要存下来 */

    if (seg_pnts[pnt_num].flag.begin & seg_pnts[pnt_num].flag.end) {

        seg_pnts[pnt_num + 1] = seg_pnts[pnt_num];

        seg_pnts[pnt_num++].flag.end = 0;

        seg_pnts[pnt_num].flag.begin = 0;

    }

    seg_pnts[++pnt_num] = seg_pnts[i];

}

在小节2中，我们处理Pt[last].value == Pt[pidx].value的情况时，流程是：

• 1、 获取标记flag，是否是情况3

• 2、 再判断是否是情况2，若是，权重值-1，并更新

• 3、 再判断是否是情况1，若是，权重值+1，并更新

• 4、 如果flag为真，更新去重的端点集，并临时将权重值+1

是否还记得一件事，我们端点排序，只考虑端点的值；那么，在端点值相等的情况下，出现情况1（均为起点）和情况2（均为终点）之前，已经出现过情况3（一个起点一个终点的情况），但是呢，这次补偿和在Pt[last] != Pt[pid]不一样。

• 1、 针对情况1，我们选择再对权重正向补偿flag这么多差值；

也即是在曾经出现过该端点为起点，但是有经历终点，现在又来到起点，理应对上一次权重进行自增两次。

• 2、 针对情况2，我们同样对权重正向补偿flag这么多差值。

曾今出现过，先经历终点，再经历起点，然后是终点，理应对上次的权重，进行一次自增。

• 最后，再处理情况3，更新flag标记。

进行到这里，其实这个O(n)权重算法，已经修正的差不多了；但是，同原算法相比还是差了不少，比之前的肯定已经好很多了。

再次对比原算法，使用acl1_100测试用例集，发现，相关端点的权重差异很大：

原算法结果：

>> 0x00000000 begin 1, end 0, weight 1.

>> 0x405B6A00 begin 1, end 0, weight 11.

>> 0x405B6B00 begin 1, end 0, weight 13.

>> 0x405B6B00 begin 0, end 1, weight 11.

>> 0x405B6B02 begin 1, end 0, weight 13.

>> 0x405B6B02 begin 0, end 1, weight 11.

>> 0x405B6B04 begin 1, end 0, weight 14.

>> 0x405B6B04 begin 0, end 1, weight 12.

>> 0x405B6B07 begin 1, end 0, weight 13.

>> 0x405B6B07 begin 0, end 1, weight 11.

>> 0x405B6B09 begin 1, end 0, weight 19.

>> 0x405B6B09 begin 0, end 1, weight 11.

O(n)权重算法结果：

>> 0x00000000 begin 1, end 0, weight 1.

>> 0x405B6A00 begin 1, end 0, weight 11.

>> 0x405B6B00 begin 1, end 0, weight 12.

>> 0x405B6B00 begin 0, end 1, weight 14.

>> 0x405B6B02 begin 1, end 0, weight 13.

>> 0x405B6B02 begin 0, end 1, weight 14.

>> 0x405B6B04 begin 1, end 0, weight 16.

>> 0x405B6B04 begin 0, end 1, weight 15.

>> 0x405B6B07 begin 1, end 0, weight 16.

>> 0x405B6B07 begin 0, end 1, weight 19.

>> 0x405B6B09 begin 1, end 0, weight 18.

>> 0x405B6B09 begin 0, end 1, weight 19.

可以看出，两者算法从计算0x405B6B00这个端点开始的，正确权重一次是13，11；我们自己算法计算出来的权重是12，14。这个端点对应规则集中第一个域上的范围段是（0x405b6b00, 0x405b6b00），（0x405b6b00, 0x405b6b00）。

经过端点排序处理之后，结果如下：

···

>> seg_pnts[ 9] pnt 0x405B6A00, begin 1, end 0.

>> seg_pnts[10] pnt 0x405B6A00, begin 1, end 0.

>> seg_pnts[11] pnt 0x405B6B00, begin 1, end 0.

>> seg_pnts[12] pnt 0x405B6B00, begin 0, end 1.

>> seg_pnts[13] pnt 0x405B6B00, begin 1, end 0.

>> seg_pnts[14] pnt 0x405B6B00, begin 0, end 1.

>> seg_pnts[15] pnt 0x405B6B02, begin 1, end 0.

>> seg_pnts[16] pnt 0x405B6B02, begin 0, end 1.

···

从排序的结果来看，这个域上的这两个范围段，这两个点，被包含在以 0x405B6A00为起点的范围段，与后续0x405B6B02点无重合。

按照我们算法的基调，遇到起点加1，遇到终点减1，以weight = 11为基础值，我们是可以得到，正确权重值：13，11的。那为什么，我们最后算错了呢。我们在来看下端点排序后，红色字体部分。这个端点的起止标记顺序是：起(1)、止(0)、起(1)、止(0)。

我们单独将这个权重值计算方法摘取出来，运行这个特例。发现确实有问题，但是，我们将这个点的排序结果调整为（排序过程中，值升序排列；值相等时，按照end值升序排列）：

···

>> seg_pnts[11] pnt 0x405B6B00, begin 1, end 0.

>> seg_pnts[12] pnt 0x405B6B00, begin 1, end 0.

>> seg_pnts[13] pnt 0x405B6B00, begin 0, end 1.

>> seg_pnts[14] pnt 0x405B6B00, begin 0, end 1.

···

并将计算Pt[last] == Pt[pidx]情况时，当遇到，情况3时，我们同时更新last值为当前pidx值。然后我们处理值相等情况时，步骤如下：

• 1、 如果端点均为终点，权重减一后，在正向补偿flag这么多差值；

• 2、 如果端点均为起点，权重加一后，也正向补偿flag这么多差值；

• 3、 更新flag是否为一个起点和一个终点；

• 4、 当满足情况3时，将权重临时加一，并更新到当前端点的权重，再更新last值为当前pidx。

整理完代码后，再次运行结果：

运行是的acl1_100这测试用例和acl1_100_trace这个查询测试用例。

至此，我们当前至少保证了，我们修订了权重计算方式后，算法的正确性。上图的是测试是带有printf打印信息的。我们再以acl1_10K（实际有9603条规则）为测试用例集，且去掉打印，结果如下：

我们可以很明显看到，HyperSplit树建树时间从1888718(us)下降到488990(us)。

3.4. 小结：

在改善权重值计算时间复杂度的算法中，主要有以下几个要点：

• 1、 算法基本原则，权重值，遇到起点，累加1；遇到终点累减1；

• 2、 处理端点值相等时，进行权重值永久性补偿和临时补偿；

• 3、 我们算法中，端点排序，将端点是否为终点标记纳入排序条件。

最后，当前整个分裂过程，我们仍旧沿用的递归计算；其实，我们 可以将其改为非递归的方式；再者，计算过程中，我们进行多次malloc和free操作，这些我们都可以进行更进一步的优化（使用mempool来做）；排序方式，可以使用改进后的快速排序等等。这些都可以减少建树时间上的消耗。

对于在内存上的优化方式，论文作者，已经在原论文中给出了，我这里就不在赘述了。

4.参考链接

Ø http://security.riit.tsinghua.edu.cn/share/infocom09-hypersplit.pdf 

Ø https://github.com/fooozhe/HyperSplit 

如有兴趣与作者进一步沟通交流，可扫描下方二维码进群