数据包现状

    论文

1 数据包过滤规则匹配与并行化技术研究

主要介绍的哈希线性查找和分层树查找。没有介绍传统的软件和硬件，具体内容看论文。

数据包分类功能是由一个包含有一系列规则的数据包分类器完成，每一类数据包至少遵循其中的一个规则。这些规则是依据数据包头的内容把数据包分为不同的类流，以进行不同的处理，即丢弃、转发。决策代表数据包成功匹配规则之后该进行如何处理，如防火墙中包含的允许（Peimit）拒绝 (Deny)，路由器中包含的丢弃 (Drop)、转发（Forward）等。

  1. 线性查找
  2. 分层树查找

2 2020-基于 GPU 加速的包分类算法研究与实现

OpenFlow 作为数据层面转发数据包依据的主流协议，它打破了传统网络分层的概念，所有需要匹配的字段都包括在一张流表里面，实现了协议的扁平化。

从上面目前 OpenFlow 包分类算法面临的字段匹配需求来看，主要问题在于原有的基于纯 CPU 设计的包分类算法在包分类规模以及字段数量快速增加的情况下，该类算法的性能会大大降低，大部分原因是由于 CPU 的计算能力还不足导致的。从而我们可以考虑寻求计算能力更加强大的硬件来结合 CPU 构建异构包分类架构。其中可选的硬件主要有 TCAM、 FPGA、 GPU。

包分类是一种在预定义规则集中匹配数据包从而根据规则定义的动作处理数据包的方法， 其中输入包可以匹配一个或多个规则， 我们选择具有最高优先级的规则定义的动作处理输入数据包[5]。

  1. 软件
    1. Tries
      1. Hierarch Tries， Grid-of-tries [6-8]
    2. X-tree
      1. 布谷鸟过滤器
    3. 分割
      1. Hicuts，HyperCuts
    4. 哈希表
      1. TSS...
    5. 维度降解
      1. RFC
  2. 硬件
    1. TCAM
      1. 三态内容地址寄存器） 设计了一系列的包分类算法， 该系列算法具有的很高并行查找能力和极高包类吞吐量[4,15-17]
      2. TCAM 有高功耗高成本等问题
    2. FPGA
      1. 利用 FPGA 的流水线架构， 能够在大规模规则集上取得很高的吞吐量， 然而算法的处理延迟很高[18-23]
    3. GPU
      1. 利用 GPU 的并行计算能力， 基于 GPU 的计算特点来设计包分类算法， 该类算法能很好的加速数据包的匹配， 有效的缩短数据包处理时间[4,23-28]。
      2. 在国内， 也有很多学者基于 TCAM， FPGA，GPU 研究了很多优秀的包分类算法[29-31]，

2.1 指标

对于任何一个算法都有其性能评价标准，而包分类算法主要包括下面几个性能指标：

  1. 数据包的匹配速度（分类速度） ： 包分类算法就是为数据包的快速匹配所设计的，所以数据包的匹配速度作为包分类算法的核心评价指标， 关乎着包分类算法的设计意义。它是包分类算法最重要的性能指标，数据包处理系统应该满足线性处理能力，否则将成为整个系统的瓶颈，影响整个网络的服务质量。数据包的分类速度包括多种情况：

    1. 平均包分类速度，对一个包进行分类查找的平均速度；
    2. 最坏包分类速度，对一个包进行分类查找可能的最慢速度；
    3. 统计包分类速度，在符合某种预先指定的规则下，对一个包进行分类查找的速度。（来源：2015基于OpenFlow协议的高速包分类算法研究_万云凯）

  2. 算法内存占用 ： 一个好的算法设计， 不光要考虑到算法的运行速度，该算法的内存占用， 即空间复杂度也是需要考虑的， 优秀的算法都是在一定程度上优化空间复杂度， 以降低该算法的硬件成本， 所以算法的内存占用也是衡量包分类算法性能的重要指标之一。数据包分类算法的内存使用不仅包括

    1. 存放规则集本身所占用的存储空间
    2. 还包括算法建立的用于查找的数据结构的存储空间
    3. 一些算法在预处理阶段还需要一定的内存使用 （来源：2015基于OpenFlow协议的高速包分类算法研究_万云凯）

  3. 预处理时间： 对于包分类算法， 在设计过程中会涉及一些数据结构，而包分类算法的预处理时间基本上都耗费在数据结构的初始化过程中， 过长预处理时间会降低该包分类算法的整体效率， 由此可见尽量减少预处理时间是至关重要的。

  4. 算法更新时间（更新代价）： 在包分类算法中， 需要考虑到规则集的动态更新过程，需要保证规则集动态更新不能过长， 不然会拉低整个匹配速度， 降低了算法匹配的效率。在规则库中添加或删除规则所需要的代价，同样分为多种情况：

  5. 完全更新：修改整个规则集，甚至要重新建立包分类算法的数据结构；

  6. 增量更新：在规则集中增加或删除一条包分类规则。在一些规则集较为固定或者改动较小的场景下，更新代价显得不那么重要；而在一些规则库频繁更新的场景下，更新代价十分重要，某些算法分类速度很快，但更新代价很大，则不适用于这些场景。 （来源：2015基于OpenFlow协议的高速包分类算法研究_万云凯）

  7. 算法的可扩展性： 包分类算法涉及到网络中的数据包和规则集， 而随着互联网的发展， 网络中的数据包和规则集的架构会发生变化， 比如规则集的数量增多， 规则集中的字段增加， 这些都是在设计包分类算法的过程中需要考虑的，尤其是在 SDN 网络兴起后， 规则集的规模和字段数量急剧增加， 包分类算法的可扩展性变得越来越关键。

    主要是对规则的适应性，包括以下两个方面：一是对规则数量的扩展，当规则集中规则数量增多时，算法性能要求能够稳定；另一方面是分类规则维数和层次上的扩展，要求算法能够根据更多的字段分类，而这些字段可能来自于数据链路层、网络层、传输层等，网络发展日新月异，理想的包分类算法应该能够处理规则集在数量和维度上的扩展。 （来源：2015基于OpenFlow协议的高速包分类算法研究_万云凯）

然而以上五个包分类算法的性能评价指标之间难以同时满足， 达到最优化，从而 现实中设计包分类算法可以针对一些场景的特点， 适当提高某些性能指标的性能， 牺牲其它指标的性能来满足一些特定场景需求。

如果能够对规则集进行预处理归类， 在查找匹配的过程中只在某个类别的规则集中进行查找， 将会避免遍历整个规则集， 从而提高查找效率，（🟢 Tips 划重点） 例如上文提到的元组空间查找算法（TSS） 就依据字段之间组合的长度的不同把规则集进行元组划分， 在查找匹配的过程中只在某个元组中进行查找， 大大提高了查找匹配的速度。

🟢 Tips 划重点

所有方法都是这一思想，就是想办法怎么把更快的分类别查找

在本文中将利用网络中存在的局部流现象， 并结合规则集的优先级， 把规则集拆分为主规则集（Major-Table） 和次规则集（Rarely-Table） 两部分， 查找匹配的时候优先在主规则集中查找， 若查找不到再去次规则集中进行查找， 下文将用 Major-Table 和 Rarely-Table 来分别代替主规则集和次规则集。 为了更快的查找匹配， 对于主规则集和次规则集划分比例将依据局部流现象存在的比例进行划分。

有大量的研究表明，在现实网络中存在着这样一种现象： 在网络中某段时间内的流往往属于同一段流，而这部分分流占据了网络中的大部分流量，此部分分流被一些研究人员称之为大象流，而那部分占据网络中的少部分流量的分流则被称为老鼠流。并且有许多研究人员针对大象流和老鼠流的识别做了大量的研究工作, 同时应用于像数据中心这样的大数据流环境当中[44-45]。研究试验后，给出了具体的数据信息如下：

有大约 9% 的流量占据了网络中 86.7% 的数据包，而且该部分流量的字节数占据了总字节数的 90.5%[46] （什么意思不懂）。总结来说， 网络流的局部现象表现为： 网络中某一个连接的数据包往往会批量集中的到达，当一个数据包到达时，往往下一个数据包也同属于一个连接[47]。

一般规则集都是存储在交换设备中， 由一条条的规则项组成， 每条规则项都具有相同的结构

2.2 规则集字段的维度划分

如前文所述， 可以将规则集中的字段匹配方式分为精确匹配， 范围匹配， 前缀匹配三类， 精确匹配的代表字段有协议类型（TCP/UDP） ， 对于像端口号类型字段的匹配则采用范围匹配的方式， 而例如 IP 字段的匹配则采用的是前缀匹配。

由于不同匹配方式的特点不一样，目前还没有一种统一的匹配方式来满足三种字段匹配方式的需求，通常针对每种类型字段的特点，设计不同的匹配算法来各自进行匹配。 （🟢 Tips 划重点）

🟢 Tips 划重点

不同字段就得采用不同的查找方式

本文在研究三种类型字段的特点后，针对每种类型的字段各自提出了相应的匹配算法：

  1. 针对精确匹配字段，设计一种可以均衡哈希冲突和哈希查找时间的基于位运算的哈希算法；
  2. 对于范围匹配字段，利用了区间排序的思路对该类字段提出了聚类查找算法；
  3. 为前缀匹配字段建立了一颗前缀树，通过宽度优先搜索的方式去掉不相关的树分支，从而达到快速查找的目的，下面将进行具体的介绍。

在包分类问题中， 规则集中存在的字段大部分都是属于精确匹配字段， 所采用的查找算法几乎都是利用哈希来设计的。 本文设计了一种可以均衡哈希冲突和哈希查找时间的哈希算法， 通过加入位运算的一些特性来减少哈希冲突的概率。

根据上文所述， 在规则集中如源端口号， 目的端口号等字段的取值往往不是一个单一的数值， 基本上是以一个范围区间的形式来展现的， 针对此类字段我们需要设计相应的查找算法来进行范围匹配字段的查找， 目前针对范围匹配字段的查找算法往往都归类到了前缀匹配字段查找算法中， 主要思路是根据范围区间构建一棵类似前缀树的范围树来归类范围区间， 在查找的时候通过树结构查找特性快速的进行范围区间的定位， 从而查找到对应的规则集。 但此种根据范围树来设计的范围匹配字段查找算法的构建过程比较繁琐， 特别是范围区间之间交叠较多的时候， 构建的时间会显得比较长， 不利于快速的更新操作。（🟢 Tips 划重点）

🟢 Tips 划重点

缺点，有没有更好的解决方案

前缀匹配字段的查找算法目前比较主流的思路都是通过构建前缀查找树来设计的算法， 例如文献中所介绍的算法[50-51]。 此类基于前缀查找树的算法通常应用于 IP 查找中， 算法的主要思路在于像 IP 字段中会存在共同的前缀， 通过提取前缀构建查找树， 在查找匹配的过程中就可根据前缀范围快速的进行查找树减枝查找， 缩小查找范围， 加快查找速度。

本章介绍了一种基于维度分解的实时动态包分类算法，（🟢 Tips 划重点） 其中基于维度分解的实时动态包分类算法分为了规则集的动态更新算法和字段的维度分解两部分， 对于字段的维度分解主要包括了三类字段各自的查找算法：

  1. 基于位运算的哈希算法

  2. 基于二分查找的聚类查找算法（范围）

  3. 基于前缀树的查找算法

🟢 Tips 划重点

决策树和哈希表能够结合，那么决策树和维度降解，哈希表和维度降解能不能结合

2.3 异构平台编程模型-OpenCL

在目前的计算机架构体系下， 现行的处理器有 CPU， GPU 等， 而不同的处理器所涉及的应用场景不一样， 对于 CPU 来说， 需要处理多条指令和多条数据，属于典型的多指令多数据（Mutiple Instruction Mutiple Data， MIMD） 处理单元。而对于 GPU 来讲， 只需要处理单条指令和多条数据即可满足需求， 属于典型的单指令多数据（Single Instruction Mutiple Data， SIMD） 处理单元。

通常来讲，GPU 是执行特定的任务种类的， 只需要由控制器编译一条指令， 然后通过广播的方式发送到每个处理单元上执行即可[40]。 然而对于 CPU 的设计来说， 要并发处理多条指令和多条数据， 其结构设计十分复杂， 包括很复杂的流水线结构， 不再是单个控制路径， 具有多个控制路径的同时预编译也变得很复杂[41]。 基于以上 CPU 和 GPU 的设计理念来说， GPU 更加适合处理逻辑单一但数据量密集型的任务， 而 CPU 适合处理逻辑较复杂数据量较小的任务。

由于不同类型的处理器的执行逻辑不一样， 要想结合不同类型的处理器的优点设计一些异构计算的平台， 还需要一个能够统筹不同类型处理器的一个框架，而恰恰 OpenCL 就是这样一个异构平台的框架， 最开始有苹果公司提出， 经过多年发展， 已经成为了异构平台的一个标准， 应用非常广泛。

3 基于 FPGA 的包分类算法的设计与实现

综合比较 ， 区域分割算法相对适合 处理高速数据报文，典型的 区域分割算法有 Hicuts 算法和 HyperCuts 算法 ，是需要进行决策树的构造， 耗费大量时间。

表 2-2 各种算法性能比较 （33 页）

4 基于规则聚集特征的高速分类算法

里面有分类方法，分成了四类（没看完，再看吧，现在不想看 2022/11/06/15:34，原因实验室太压抑了，受不人这么多....

待看：

5 2016-GPU

  1. 有关于硬件 FPGA，TCAM，GPU 包分类的阐述。
  2. 软件有树方案，端口范围的元组表达：嵌套层和范围编号。

一个规则集含有任意多条规则，每条规则由三部分组成：

  1. 与域有关的条件表达式，表达式可能是前缀（数据包中的 IP 地址域需要进行前缀匹配），也可能是范围（端口号域需要进行范围匹配），或者是一个精确的值（协议类型需要进行精确匹配）
  2. 优先级，声明该条规则在规则集中的优先级，当一个数据包和多条规则匹配时，优先级最高的规则生效
  3. 执行动作，如果输入的数据包与规则匹配，则根据该动作对数据包处理。

5.1 基于软件的方案

字典树（Trie）广泛应用于 IP 地址查找以实现高效、稳定的最长前缀匹配[1-3]。由于多域规则匹配的难度和复杂性也主要来自于对于 IP 地址域的处理，层次化字典树同样也被采用来解决多域规则匹配[46]。文献[7]提出一种二维字典树结构来组织分类规则，并给出了相应的查找及更新算法。利用字典树结构的特性将各种长度的前缀组合进行分组，并依此将整个规则集分成多个子集。查找时将每一次查找过程分解成若干个可以独立运行的子任务，每个子任务处理一个子集。两级混合字典树结构保持了规则之间的独立性，因此可以快速地对单条规则进行增量删除或添加。实验结果表明，该算法在保持高速查找的基础上，将单条规则的增量更新操作速度提高到了和单次查找操作同样的量级，同时并行查找使得算法对规则类型和规模的敏感度大大降低，具有较好的可扩展

CBHT（Counting Bloom filter and Hash Table）算法[23]1 从数据包匹配规则的聚集特性出发，将计数布鲁姆过滤器和哈希表相结合。基于包匹配规则的聚集特性，对于五维包分类问题，CBHT 算法首先利用计数布鲁姆过滤器的过滤功能结合单域匹配获得与前两维匹配的小规模规则集，而后在此有限规则集中对后三维进行匹配。利用计数布鲁姆过滤器提高了包匹配速度并有效支持规则库的动态更新。实验结果表明 CBHT 算法比现有的 B2PC 算法节省 60% 的硬件资源，包匹配访问内存次数平均低于 B2PC 算法 22.8%。

文献[24]提出一种基于流的局部特性和多级查找的高效包分类算法，同时可以支持规则集动态更新，实现快速包分类。该算法分为三级结构，第一级缓存用于存放最近 10 秒内到达的流，第二级计数布鲁姆过滤器存放最近 10 秒至 60 秒内到达的流，第三级计数布鲁姆过滤器存放剩余的流。实验表明，该算法比传统的包分类算法，在空间消耗相近的情况下具有更好的时间性能。

元组空间（Tuple Space）的思想[25]于 1999 年被首次提出，作者设计了一系列基于元组空间的包分类算法。基于元组空间算法的基本思想是将整个规则库根据每个维度规则的特征，将规则集划分成多个子规则集，具有相同特征（划重点：什么叫相同特征，不同划分方式可以吗）的规则属于一个子规则集中。据此将一个复杂的问题分为多个简单的问题，那么一次复杂的包分类操作可以转化为多个互不相关的、较简单的匹配操作，不但匹配速度性能可以得到优化，分类器的设计也能得到简化。 表 2.2 中给出了一个简单规则集，作为说明元组空间算法思想的样例，其中源/目的 IP 地址域前缀长度为 4 比特，源/目的端口号为 4 比特，协议类型为 8 比特。对于不同的域，作者定义元组值的方式不同：

  1. 对于源/目的 IP 地址域，以前缀长度作为元组值；
  2. 对于协议类型域，如果协议类型是确定值，则定义元组值为 1，如果协议类型是通配符，则定义元组值为 0；
  3. 对于源/目的端口域，作者引入嵌套层（Nesting Level）和范围编号（Range ID）的概念，并将嵌套层的值作为端口域的元组值。如图 2.1 所示，嵌套层指明了层次，而范围编号是该层中范围的标识。这样可以把所有的端口范围转成一个由嵌套层和范围编号构成的二元组。 规则集 嵌套层

通过将原规则集按照规则特征分割成若干子规则集，在各个子规则集（元组空间）中的搜索可以采用高效的哈希技术，将数据包头中的值作为哈希函数的搜索关键字。例如，为元组空间 [4，0，2，0，0] 设计哈希函数，可以将源/目的 IP 地址、源/目的端口号范围编号以及协议类型作为搜索关键字。 对每个元组空间进行数据包分类的过程是独立的，因此元组空间算法可以并行实现，即并行地对所有的元组空间进行搜索，再合并搜索结果。然而，采用并行实现的难处在于，每个元组空间或其子集的大小是不可预料的，导致每个元组空间的时间耗费较为不稳定。但在大多数情况下，元组空间算法的性能表现较为理想。

5.2 基于硬件的方案

5.2.1 基于 FPGA 的解决方案

FPGA 包含可重编程逻辑块阵列，并且是可以重构互连，允许各块连接在一起的层次结构。以硬件描述语言（HDL 或者 ASIC）所完成的电路设计，可以经过简单的布局与设计，烧制到 FPGA 进行调试。因此 FPGA 是作为集成电路里面一种半定制的电路出现的，既解决了定制电路的不足，又克服了原有可编程器件门电路数有限的缺点。因此 FPGA 日益受到各方面研究者的欢迎，尤其是对于某些需要进行特定配置和能够进行重复配置的电路设计，如包分类算法电路的设计。

文献（26）在型号为 Xilinx Virtex 2 Pro 的 FPGA 上部署了 DCFL（Distributed Crosspro-ducting of Field Labels）算法[27]，完整实现了防火墙功能，并且支持规则集的更新功能。当规则集中有 128 条规则时，该实现方案可以达到 50 MPPS 的吞吐率。并且他们预测如果该方案在 Virtex-5 FPGA 上实现时，吞吐率可以达到 24 Gbps。 文献[28]提出一种基于维度分解的数据包分类算法，该算法在每个域使用了布鲁姆过滤器加速查询，最后合并查询结果。作者将该算法在 FPGA 上实现，称为 2sBFCE。该实现方案对内存空间的需求非常小，仅 178K 字节存储 4 千条规则。但是他们的实现方案平均 26 个时钟周期完成一次包分类，导致总体的系统吞吐率不高，平均只有 1.875 Gbps。并且该方案由于使用了布鲁姆过滤器，还存在假阳性的问题。

为了降低能耗，文献（29) 提出在型号为 Altera's Cyclone III 的 FPGA 上实现一种简化的 HyperCuts 算法。他们在叶子节点中存储上百条规则，并且在执行包分类时并行查询，因此芯片以很低的频率运行（32MHz）。但是由于决策树的结构不能实现流水线，该实现方案的性能不理想，在规则集为 2 万条防火墙类型规则的情况下，需要 23 个时钟周期去完成一次数据包分类，总体系统的吞吐率只有 0.47 Gbps。

5.2.2 基于 TCAM 的解决方案

TCAM（Ternary Content Address Memory）是一种基于内容查找的存储器。TCAM 不但能存储“0”、“1”状态，而且能够存储 “ * ”（Don’t Care）状态，因而被称为“三态”（Ternary Content）。 包分类规则在 TCAM 内部存储时一般以比特串和前缀掩码的形式表示。当包头关键字被送到 TCAM 输入端，TCAM 内部的所有存储表项都会被同时触发与输入进行匹配比较，并且能够保证在一个时钟内完成查找。当匹配发生时，匹配表项的地址将会被作为输出结果返回。

前缀扩展算法[30]是一种经典的使用 TCAM 实现包分类的算法。该算法将规则中源/目的端口域的范围匹配转换成若干个前缀匹配，并将每条前缀分别存储在 TCAM 中。例如，范围[0，10]可以转换成三条前缀匹配：0**，100 和 1010（怎么算的，不懂）。虽然该算法实现简单，性能较好，并且支持规则集的更新操作，但 TCAM 的利用率极低。在一般的五维包分类规则中，源端口域和目的端口域都属于范围匹配，在最差情况下，一条规则最多需要扩展为 900 条 TCAM 表项。而 Taylor[31]对多个实际规则集进行范围前缀扩展实验，结果显示每条规则的平均扩展系数为 6 倍多，TCAM 的存储空间利用率仅为 16.12%。

总体上，TCAM 的优点是逻辑简单，基于内容查找的特点和完全并发进行的能力，一个时钟就可以完成一次匹配过程，可以实现 O（1）的时间复杂度。但 TCAM 的缺点在于：（1）价格相对其他内存昂贵很多，且集成度低。这些是由于其内部实现的复杂，包含众多的比较器和逻辑连线，使得难以大规模的集成，并造成昂贵的价格。（2）能耗较大。由 TCAM 的工作原理可知，每次查找匹配时都进行完全并发的操作，所有表项均参与内容比较，从而导致了 TCAM 的运行功耗极高。（3）不支持数值范围类型的规则域值，需要将范围匹配转换成前缀匹配的形式，或者以编码的方式克服。

5.2.3 基于 GPU 的解决方案

基于 GPU 的包分类解决方案兼顾了灵活性与高性能，同时在可扩展性方面也有较大的优势，因此受到研究者们广泛的关注。基于 GPU 的解决方案通过编写并行程序，以软件形式实现高性能的包分类。其运行的程序可以及时、灵活地进行配置、更新。同时，整体系统平台通过升级、加装新的 GPU、CPU、网卡即可获得相应的性能的提升，容易实现横向扩展性能，因而系统的可扩展性较强。

文献[35]提出使用 GPU 加速线性搜索算法和 RFC 算法的方法，利用 GPU 的线程级并行处理能力加速包分类吞吐率，并对其性能及优化方法进行详细分析。实验结果表明，GPU 加速的线性搜索算法和 RFC 算法与纯 CPU 系统执行相比可达到 4.4 至 132.5 倍的加速比。 GPU 数据包

GPU 方法没看完，等做的时候在看吧。2022/22/07/11:58

5.3 ClassBench

由于涉及到网络的安全问题，实际网络中的用于数据包分类的规则集都是非公开的。这使得只有极少数的科研团体和组织中能够获得这些规则集，并用来对包分类算法进行测试、评估。华盛顿大学的 David E.Taylor 和 Jonathan S.Turner 开发了包分类规则集生成软件 ClassBench[46]，作为包分类算法的评估工具。

ClassBench 工具的设计者首先从实际应用场景中采集规则集，并分析这些规则集的特征，针对每个匹配域进行统计分析，得到一系列能够反映规则集特征的参数，并且据此生成与真实规则集类似的合成规则集。同时，它也能够根据生成的规则集，产生对应的模拟的数据包头文件，便于对数据包分类算法的验证和检测。ClassBench 由三个工具组成：

  1. 规则集分析器（database analyzer）
    1. 规则集分析器能够根据实际使用的真实规则集生成参数文件（parameter files）。该参数文件包含对真实规则集进行抽象之后的统计和概率分布，并作为规则集产生器的输入文件，以生成大量和原始规则集具有相关特性的合成规则集。此工具选择了 3 种类型（ACL、FW、IPC）共 12 个真实的规则集进行了筛选和研究。
  2. 规则集生成器（filter set generator）
    1. 在规则集生成器生成的规则集文件中，每一行含有一条规则。每条规则以 @ 开头，其各个域之间以制表符分隔。第一个域是点式十进制表示的源 IP 地址以及其前缀大小，例如 192.168.0.0/16 表示前 16 个比特满足 192.168 的前缀匹配。第二个域是目的 IP 地址及其前缀长度，与源 IP 地址域的表示形式相同。第三个域是源端口号，其下限值与上限值以冒号分隔，例如 0：1023 表示源端口号需在[0，1023]的范围内。第四个域是目的端口号，与源端口号域的表示形式相同。最后一个域是以十六进制形式表示的协议类型以及其掩码。
  3. 流生成器（trace generator）
    1. 流生成器的作用是分析规则集文件，并生成与之对应的数据包头文件，便于算，法的性能、正确性等各个方面的检测。其生成的数据包头中，每条规则都会有对应的确定数量的数据包。

5.3.1 比特划分树

比特划分树（Bit-Split Tree，简写为 BSTree）是一种基于比特划分的树形数据结构。 在 OpenFlow 协议的流表查询操作中，数据域有两种匹配条件，一种是前缀匹配，适用于 IP 地址，形如 192.168.0.0/16，即前 16 比特的前缀匹配，也可以转换为二进制的形式 1100000010101000 * * * * * * * * * * * * * ；另一种是可能含有通配符的精确匹配，适用于端口号、MAC 地址等域。因此，通过将前缀匹配转换成二进制，可以将规则视为含有通配符的比特串，形如 01010 *** 01010。

首先将流表中所有的规则转换为含有通配符的比特串形式。在构建 BSTree 的起始时，根节点中含有所有的规则。根据规则中某一比特位为 0 或 1，可以对规则集进行划分，形成两个子规则集，分别生成左、右子树。如果某条规则在选取的比特位是通配符，则该条规则同时进入两个子树。如何选取合适的比特位进行分割对 BSTree 的结构和性能影响重大。这里使用贪心的策略选取比特位，枚举所有的比特位，分别计算以该比特位划分后左右子树的大小。优先选择使得两棵子树大小的最大值最小化的比特位，如果有多个比特位满足这一条件，则进一步选择使得子树大小总和最小化的比特位。如果仍有多个比特位满足条件，则随机选取任一比特位。

通过不断地选取比特位、划分规则集、生成子树，子树中含有的规则数目将越来越小。如此递归地分割，直到叶子节点中规则数小于预设的阅值，则停止划分，该节点成为叶子节点。

一个简单的构造 BSTree 的例子如图 5.1 所示，这里假设有规则集中共有 5 条规则。 为了方便举例，假设每条规则有 2 个维度，每个维度中有 2 个比特位。

对于一些含有通配符较多的规则，例如 60%以上的比特位均为通配符的规则，若参与树的构建，将出现在绝大多数的叶子节点中，造成极大的空间开销，并且影响性能。所以这样的规则将不参与树的构建，而在查询时将单独处理。

5.3.2 流表查询操作

什么叫流表

对一个数据包的流表查询操作从 BSTree 的根节点开始，每进入一个非叶子节点，从数据包头中取出该节点选取的比特位，根据该比特位为 0 或 1，决定向左子树或右子树转移。该数据包不断地在 BSTree 中转移，直到进入叶子节点。当进入叶子节点，对叶子节点中的规则集进行线性搜索，找出与该数据包匹配的优先级最高的规则。

5.3.3 更新操作

  1. 插入
  2. 删除

看论文部分

6 2015-openflow 协议

  1. TCAM的介绍和分类方法的简介

网络安全和网络服务要求网络流量进行更加细粒度的分类[1-3]，以满足在防火墙 (Firewall)[4]、服务质量(Quality of Service)[5-6]、策略路由(Policy Routing)[7]、流量计费 (Traffic Billing)[8]等各个领域[9]的需求。数据包分类技术应运而生。

🟢 Tips 划重点

包分类算法的背景还需要了解一下，了解背景有助于发现问题的本质。比如包分类在哪些地方应用，Action都有哪些，

网络功能虚拟化（Network Function Virtualization）[10-11]以及软件定义网络（Software Defined Network，SDN）[12-13]等一系列前沿网络技术的发展，对数据 包分类技术提出了更高的标准和要求

了解一下SDN

表 2.1 是一个决策只包括允许和拒绝的 ACL 规则集，假设此时一个包头为（175.77.88.254, 195.156.61.102, 102, 1710，UDP）的数据包到来，那么它将匹配的规则是规则 1，也就是说它被允许通过。

7 2001-高性能 IP 路由查找和分组分类技术的研究_郑凯 里面有详细分类

  1. 详细的分类简介

2015 包分类算法研究综述张杰鑫，张铮

规则集特征概述和管理

文献［８］对大量实际的规则集进行了研究，结果表明，实际规则集的规则数目不会太多，规则的协议域通常只有很少的几个取值，端口号的取值范围很广等特征。实际统计结果是所有规则集的实际复杂度均远小于理论复杂度［９］。 [8] Gupta P, McKeown N. Packet Classification on Multiple Fields (C) // Proce edings of ACM SIGCOMM' 99. New York, USA: ACM Press, 1999:14 7-160. [9] 元亚炬，李军. 高性能网包分类理论与算法综述[J]. 计算机学报，2013，36（2）：408-421.

2018-决策树网包分类算法综述

实际应用中规则集的特点

虽然理论上的复杂性让我们很难设计一个单一的算法来很好的适应各种情况。但是，网包分类问题在现实应用中有一些内在的特点，可以用来降低网包分类的复杂度［7，8］ 。 Gupta 等人［9］通过对实际规则集的观察，总结出一系列规则集的特征:

  1. 规则集的协议域限定在一个很小的范围内。Taylor［10］等人通过对 12 个真实的规则集进行分析， 得到规则集中常出现的协议为 TCP、UDP、ICMP、IPE、GRE、ESP、AH、EIGRP、OSPF，其中 TCP 的使用频率 最高。

  2. 端口号的范围通常很大，经常出现大于1023 的端口号。

  3. 与同一网包完全匹配的规则一般情况下少于5 个。

  4. 常见的前缀长度为0、32、21、23、24、30。

  5. 同一规则集内，多个规则往往在某个域上有相同的值。

  6. 规则集中含有部分冗余的规则。

其中冗余是指: ①规则 T 出现在规则 R 之前，并且 R 是 T 的子集，因此网包会先匹配规则 T，而不会匹配规则 R。②规则 T 出现在规则 R 之后，并且 R 是 T 的子集，R 和 T 具 有相同的动作，在R 和 T 之间的规则，要么与R 不相交，要么与R 具有相同的动作。这种前向冗余可以只保 留具有相同动作并且范围更大的规则 T，对数据包进行匹配。

实际应用中的规则集重叠的情况也与理论上的有所不同，Qi［11］等人对 WUSTL( 华盛顿大学圣路易斯分校) 公开的数据集进行分析，统计包括 ACL、FW、IPC 等一系列的规则集在各个维度上的投影区间个数，说 明了网包分类问题的实际复杂性，如表2 所示，根据表2 结果可以看出:

  1. 同一类型规则集合在不同维度上的统计特性不同。

  2. 不同种类的规则集合的统计特性不同，虽然不同类型的规则有不同的特点。

  3. 所有规则集合的实际复杂度均远小于理论复杂度。

规则集复杂性比较

第二种，基于规则集的特点优化的软件算法，这类算法是对实际规则集 进行观察，了解规则集的一些特点，利用这些特点实现更有效的网包分类算法应用于实际网络中。算法通常在特定的规则集上才有明显的效果，由于不同环境下的规则集具有不同的特点，很少有算法可以 适应所有条件下的规则集。

最长前缀匹配，掩码匹配（什么是掩码匹配），精确匹配这些匹配方式的混合使用使得决策树中的每个节点都变得更加复杂。一种简单的解决方式是选择单一类型的匹配方式来覆盖匹配条件。例如将精确匹配，最长前缀匹配转 换成掩码匹配的形式，用1，0，* ( 通配) 来表示。表 4 规则集中的规则包含 2 个域: 3bit 的地址前缀，3bit 的 端口号范围。表5 为表4 的 bit 向量形式，将2 个域的向量串接起来即可构成一棵决策树，其中每个叶子都 唯一的代表规则集中的一条规则。图1 为根据表5 构建的决策树的部分示意图。

HyperCuts 并不是对所有域进行切割，而是选择部分域进行切割，其中的选择方式为计算每个域中唯一区间的数量，以及所有域唯一区间数量的均值，选择唯一区间数量大于均值的域进行切割。例如，对于五元 组的5 个域，每个域的唯一区间数量为45、15、35、10、3，均值是 22。那么选择第 1 个和第 3 个域进行切割。 切割次数 NC( number of cuts) 利用启发式算法来确定。通过以下3 个方面来确定切割次数 NC: ①所有叶子 中规则数量的均值; ②叶子中含有规则数量的最大值; ③空的叶子的数量。切割次数从 1 开始，每次调整将 切割的次数乘2，然后判断均值是否减小? 子节点中规则最大值是否减小? 空节点数量是否增加? 这样持 续下去，在可允许的空间内选择最优的切割次数。如果某次切割后，空节点数量明显增加，那么就回退到上 次的切割次数，作为最优的切割次数。

本文按照发展过程介绍了 7 个受到广泛关注的基于决策树的网包分类算法。决策树的结构提升了网包分类的速度，构建决策树的结构需要考虑以下几个方面:

  1. 是否划分规则集;

  2. 域空间的切割方式;

  3. 决策树节点的数据结构。

基于决策树的网包分类算法普遍存在以牺牲内存为代价提升了网包的分类速度的情况，为了快速的分类，树中不可避免的存在冗余的规则。通过划分规则集的方式可以减少规则冗余的数量，然而过多的规则子集数量将影响网包的分类速度。分类速度与内存空间构成矛盾，需按照实际情况平衡。但是基于决策树的算法规则更新的速度差强人意，规则的更新很可能导致决策树的重建。

总之，基于决策树的网包分类算法其优秀的分类性能满足了当前巨大网络流量的网络环境。但基于决策树的算法产生的规则冗余，占用大量内存空间，以及规则更新性能不佳的缺点导致其无法适用于对内存空间有严格限制，更新频繁的场景。减少决策树中的规则冗余，提高规则更新速度也是网包分类技术的研究重点。

page PV:  ・  site PV:  ・  site UV: